Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Security

Implications Of The Recent Hash Function Attacks 262

Posted by timothy from the some-but-not-all dept.
An anonymous reader writes "Cryptography Research has issued a Q&A that explains the security implications of the hash function collision attacks recently announced at CRYPTO 2004. Apparently the consequences can be catastrophic for certain kinds of code signing and digital signatures, but MD5 sums for checking binaries are (mostly) OK. While the speculation that SHA-1 is about to fail seems to be overblown, updating the many legacy systems and protocols that rely on MD5 is going to be a massive undertaking."
This discussion has been archived. No new comments can be posted.

Implications Of The Recent Hash Function Attacks More

Implications Of The Recent Hash Function Attacks

Comments Filter:

  • This is what I've been saying! (Score:5, Insightful)

    by Dthoma ( 593797 ) on Wednesday September 01, 2004 @12:45PM (#10130499) Journal
    "While the speculation that SHA-1 is about to fail seems to be overblown, updating the many legacy systems and protocols that rely on MD5 is going to be a massive undertaking."

    Any time I've tried to point this out, I've been shouted down by hysterical people (such as relex) squawking that because it may be possible to generate two messages with the same MD5 hash, SHA-1 is automatically broken. Um, no. They're two totally different algorithms. Use some common sense, people. I'm as cautious as the next person but screaming about how "all hash algos are insecure" is hyperbole at its worst.
    • Frankly I think people who are crying that we should all ditch the MD5 hash are similarly hysterical.

      It's like if the same person won the lottery two weeks in a row.. would that mean the method they used for choosing the numbers was null and void? No. Likewise, finding a collission (or even several collissions) in MD5 does not invalidate its use.

      What would invalidate its use is having some programatic way of changing the hash of some data by merely throwing in some junk to make it match a hash of choice..

      • Re:This is what I've been saying! (Score:5, Insightful)

        by swillden ( 191260 ) * <shawn-ds@willden.org> on Wednesday September 01, 2004 @12:59PM (#10130653) Journal

        finding a collission (or even several collissions) in MD5 does not invalidate its use.

        No, but having an algorithm to generate collisions in a practical period of time *does* make it suspect.

        What would invalidate its use is having some programatic way of changing the hash of some data by merely throwing in some junk to make it match a hash of choice

        That would make it completely useless for all security-related applications, yes, but a weaker break (such as being able to generate collisions) can break its usage for some security applications. Read the Cryptography Research Q&A for some examples.

      • yes, it does invalidate its use (Score:5, Interesting)

        by bani ( 467531 ) on Wednesday September 01, 2004 @01:01PM (#10130675)
        you don't have to generate specific malicious code in order to exploit md5.

        merely creating pure trash would be sufficient, think of the case of BIOS or other firmware. create random garbage with the same md5 hash and voila, you've turned your victim's PC/laptop/celphone/pda/etc into a doorstop.

        there are many other ways that md5 can be exploited, this is only one.
        • Comment removed based on user account deletion

        • Re:yes, it does invalidate its use (Score:5, Informative)

          by quasi_steller ( 539538 ) <Benjamin,Cutler&gmail,com> on Wednesday September 01, 2004 @01:18PM (#10130832)
          Yes, but remember that this is a collision attack, not a preimage attack. You can find two pieces of plaintext that have the same hash, but you don't get to choose what the hash is. Thus it is still computationally difficult to find a document (even garbage) that has the same hash as some preexisting document.

        • Re:yes, it does invalidate its use (Score:5, Informative)

          by argent ( 18001 ) <(peter) (at) (slashdot.2006.taronga.com)> on Wednesday September 01, 2004 @01:21PM (#10130858) Homepage Journal
          create random garbage with the same md5 hash

          A collision attack doesn't let you create random garbage that generates a given md5 hash. It lets you generate two pieces of random garbage (or nongarbage) that generate the same hash. It can't be used to attack a third party's existing hash.

        • Re:yes, it does invalidate its use (Score:5, Insightful)

          by JSBiff ( 87824 ) on Wednesday September 01, 2004 @02:04PM (#10131287) Journal
          But, it still is worth pointing out to people that the uses of this collision finding technique is still *very* limited. Someone can't take a digitally signed contract, make arbitrary changes to it, and still have the signature valid. In most cases, the change would be non beneficial (to the attacker that is), like maybe changing 3 characters in the document (this statement is made based upon the fact that, in the collision examples given by the author of the paper, the two messages differed only by like 4 bits or something like that), and the odds are slim that the 3 characters would end up being in the right place in the text, and have an appropriate value, to make it useful. For example, what *would* be useful, but unlikely, would be to change the string '$1995' to '$2995', but as likely as not, to get it to hash right, you'd end up with like '$#g95' or some other rubbish, even if you managed to get the changed bits to line up with the critical bit of data (in this case a dollar amount). It's more likely that you'd end up changing some word like 'benefactor' to '2knefactor'.

          However, for the example you gave, of firmware code, where you want it to be exactly right, or else it will cause problems (even 4 bits of difference in bios code can make a computer inoperable), you are right that the hash collision can be a much bigger, much harder to detect, problem.
          • For example, what *would* be useful, but unlikely, would be to change the string '$1995' to '$2995', but as likely as not, to get it to hash right, you'd end up with like '$#g95' or some other rubbish, even if you managed to get the changed bits to line up with the critical bit of data (in this case a dollar amount). It's more likely that you'd end up changing some word like 'benefactor' to '2knefactor'.

            Or, you could get it to hash right by making other, less noticable changes. Extra spaces between words

      • Very good, particular for the common use in password authentication. No attacker is going to bother with breaking MD5 when it's just easier to guess poorly chosen passwords. So I'd say that using MD5 to hash passwords is going to be with us for a long time.

      • I didn't read the attack too well, but from the Q&A, it appears that the attacks are collision attacks (like the Birthday attack, but, I imagine, more efficient). The Q&A states "In contrast [to a preimage attack], a collision attack finds two messages with the same hash, but the attacker can't pick what the hash will be."

        So, shouldn't it be possible to edit something in the document that doesn't change the meaning (such as a misspelling, or punctuation) before you sign it, thereby changing the ha

      • [...] finding a collission (or even several collissions) in MD5 does not invalidate its use.

        Indeed, mathematically speaking, there MUST be collisions when you map a set of larger cardinality to one with a smaller cardinality. The probability of a collision between two arbitrary elements of the larger set is still very, very remote.

        The issue to worry about is if you can somehow derive or predict the input from the output, as in most cryptographic uses of the hash.

        However, if you're only using MD5 for UU

      • Re:This is what I've been saying! (Score:5, Insightful)

        by tyler_larson ( 558763 ) on Wednesday September 01, 2004 @04:31PM (#10132747) Homepage

        Have we forgotten what a hash function is?

        Finding a few collisions, or even an algorithm to generate collisions doesn't change a damn thing. We've always known that there are collisions. A hash function maps in infinite input set to a finite output set. Of course there are collisions. There are an infinite number of collisions for ANY hash function. We already knew that--it's a mathematical certainty. Yet somehow we're shocked and horrified when we actually find some.

        Tell me something I didn't already know. Then I'll be impressed.

    • All hash algorithms have collisions. That's just the nature of the beast. The issue is that a way has been found to create and exploit MD5 collisions. SHA-1 will eventually be a target of something similar, just not today.

      • Re:This is what I've been saying! (Score:2, Interesting)

        by Anonymous Coward
        Wrong.
        They cannot "create" collisions. They can only try and find them.
        In fact the chances of finding a colision that could be used in a malicious manor are slim. Did you even look at the colision they found? It was two huge strings of random characters. Now if they find lots and lots more, and patters emerge, we're in trouble.

    • Comment removed (Score:4, Insightful)

      by account_deleted ( 4530225 ) on Wednesday September 01, 2004 @12:50PM (#10130549)
      Comment removed based on user account deletion
      • "The problem as I see it is if a method is found to predict collisions in a hash. Is this possible with md5 and sha-1?"

        If by this you mean "Is it possibly to construct a message to have a pre-determined hash value?" the answer is no. It's in the article, search for "preimage" if you're lazy.
      • Finding 2 things that give the same hash is not such a big deal. Having a search algo that lets you find that second thing (given the first) in substantially less computational time / complexity than previously thought possible is a huge deal. Given that MD5 can hash more than 2^32 objects, the first is inherent. It's that second trait, and recently discovered algo, that's the real kicker.
      • Why it's a big deal is explained in the article:

        Let's say someone uses this attack to generate two ssl certificates with the same hash, one benign, one malignant (ie * for host, 2200 AD for expiry). This person then sends the benign one in to Verisign and gets it signed as a trusted certificate. He then applies the malignant certificate, with a valid Verisign signature, to his little scam website - people log on, check the certificate, see that it's signed, trust the website...

        Jw

      • Re:This is what I've been saying! (Score:4, Informative)

        by xxxJonBoyxxx ( 565205 ) on Wednesday September 01, 2004 @02:32PM (#10131527)
        What is means is "MD5 is not a secure hash".

        In the United States, the National Institute of Standards and Technology determines what is and what is not to be considered secure enough for federal data processing using the definition below. I highlighted the part where MD5 would run into trouble because a method has been discovered to predict collisions in MD5. (NIST never classified MD5 as a "secure" hash.)

        From the NIST site, FIPS 180-2 (http://www.nist.gov):

        Federal Information Processing Standards Publication 180-2

        3. Explanation: This Standard specifies four secure hash algorithms - SHA-1, SHA-256, SHA-384, and SHA-512 - for computing a condensed representation of electronic data (message). When a message of any length < 264 bits (for SHA-1 and SHA-256) or < 2128 bits (for SHA-384 and SHA-512) is input to an algorithm, the result is an output called a message digest. The message digests range in length from 160 to 512 bits, depending on the algorithm. Secure hash algorithms are typically used with other cryptographic algorithms, such as digital signature algorithms and keyed-hash message authentication codes, or in the generation of random numbers (bits).

        The four hash algorithms specified in this standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest. Any change to a message will, with a very high probability, result in a different message digest. This will result in a verification failure when the secure hash algorithm is used with a digital signature algorithm or a keyed-hash message authentication algorithm.

        • for a given algorithm, it is computationally infeasible to find two different messages that produce the same message digest.

          This is the trick to figure out if MD5 is secure in how you use it. If I'm using md5 to sign a 4 character string, then md5 is secure for that reason because there are no collisions in the 4 billion input strings (its insecure because I can reverse it because I easily do 2^32 md5s)

          There are a number of applications where md5 is still secure. One of them is hmac since the sending
    • Why not generate hashes that use both SHA-1 and MD5. The combined result would be that more unique. Finding two files that generate the same hash value in BOTH algorithms would be that much more improbable. Take the hash generated by SHA-1 and concatentate it [with a sensible delimiter if required] with the hash generated by MD5. Ta dah.

      • Re:This is what I've been saying! (Score:4, Informative)

        by Zeinfeld ( 263942 ) on Wednesday September 01, 2004 @01:32PM (#10130955) Homepage
        Why not generate hashes that use both SHA-1 and MD5. The combined result would be that more unique.

        SSL does this. It is not a very good idea.

        The problem is that MD5 and SHA-1 are both variations of MD4. Each one has an extra cycle. SHA-1 has in addition a mysterious expansion function that blocks many attacks and has five chaining variables rather than four. But at root there is no real difference. Both use the exact same functions for the transformation.

        There would be slightly more point to using SHA-1 with a hash algorithm with an entirely different construction mechanism. But even then the keying mechanism is not very satisfactory.

    • I think the SHA-1 speculation originated because of the SHA-0 collision, not the MD5 collision.

      SHA-0 obviously is related to SHA-1. So although no one has yet extended the SHA-0 collision to SHA-1, it is conceivable it might be possible.
    • Finally another voice of sense. I'm with you brother!

      All the "security community" got all rattled up ebcause of SHA. My clients came over to me all shaken saying how does this affect us. Sheesh. Had to explain that almost nobody uses SHA anymore, so this is mostly legacy code and implementations.

      I hate it how all the paranoids jump up and down when they see something they can't even attest to...

      get a free ipod! [freeipods.com] This really works [iamit.org]. (Free gmail invite to the ones using this referal and completing the offer
    • Even if you could quickly be given a message and generate a separate message which has the same hash but is the same size of the original message, it still won't really matter simply because you have no control over what the second message is. For example, in the article they use "I, Bob, agree to pay Charlie $ 5000.00 on 4/12/2005.", well a 2nd message that has the same hash and is the same length as the first message would probably look like this "bhedjfgd70gdgr6rhg2rkjhgvrek342rgkhverghvgkhkfgr r e2wd".

  • Idiot Question (Score:5, Insightful)

    by OverlordQ ( 264228 ) * on Wednesday September 01, 2004 @12:45PM (#10130503) Journal
    Say I have program A that I distributed and I supply the md5/sha1 sum to insure it's 'validity'. From what I read you can get two bitstreams to produce the same sum, ok that was expected. But what I dont get is this still doesn't allow somebody to arbitrarily pick whatever sum they want for their code right? I mean still the chances of somebody writing some trojan'd program and magically somehow getting the sum's to match is extreemly small and/or really computationally expensive. If they were that smart, wouldn't they be working for one of the TLA's (Three letter Acronyms) already?

    • Re:Idiot Question (Score:4, Informative)

      by cpeikert ( 9457 ) <.ude.tim.mula. .ta. .trekiepc.> on Wednesday September 01, 2004 @12:48PM (#10130534) Homepage
      But what I dont get is this still doesn't allow somebody to arbitrarily pick whatever sum they want for their code right? I mean still the chances of somebody writing some trojan'd program and magically somehow getting the sum's to match is extreemly small and/or really computationally expensive.

      Right. The breaks that were announced of the variety: "Here are two totally contrived documents that hash to the same value (which I can't control)." The attack does not allow someone to "hit" a desired hash value. So for the use you described, MD5 is still OK (so far).
      • But even if someone finds a technique to pad junk-bytes on a malicious code package so that the malicious package's MD5 hash is equivalent to the actual code that this doppelganger is claiming to be, a quick workaround would be to publish BOTH an md5sum hash and another hash-function identifier for the package. Now even if supervillian Alice could mask Trojan-ribbed to appear to be Trojan-regular to Bob under the MD5sum, the other hash function would show it to be not the case.

        In fact, that's also the re

    • Re:Idiot Question (Score:5, Interesting)

      by ponds ( 728911 ) on Wednesday September 01, 2004 @12:51PM (#10130565)
      In many situations any data inconsistancy can cause catastrophe. When distributing binaries it isn't that big of a deal, however there are other applications of hashing algorithms.

      Think about forensics: Someone gets arrested, computer confiscated. The first thing that happens is a hash checksum is ran of the disk, then a disk image is made, then the image checksum is verified to make sure that it is the same as the original disk. If the checksum of the original disk ever changes, the evidence is useless. When there are collisions in the algorithm, the checksum cannot prove, beyond a reasonable doubt, that the data has not been tampered with. Especially when the hashing algorithm is ran on 20 or more gigabytes of data, which is the typical case in forensics.
      • Maybe the disk example isn't the best - simply mounting the disk
        might change data on it. File access times, mount count..

        • Re:Idiot Question (Score:3, Interesting)

          by ponds ( 728911 )
          Yes, if you mount a disk, it is completely useless as evidence. Any forensics practitioner who has been on the job for more than a day would never mount a disk. Thats why an image is made.

      • Re:Idiot Question (Score:3, Insightful)

        by gordyf ( 23004 )
        These hashes ALWAYS have collisions. A checksum could never definitively prove that the data has not been tampered with, as there are far more bits in a harddrive than there are bits in a hash.

        The new discovery is that it's not hard to generate two messages with the same hash. The discovery is not "hashes have collisions" - this has always been the case.

        • Re:Idiot Question (Score:4, Insightful)

          by Brandybuck ( 704397 ) on Wednesday September 01, 2004 @02:07PM (#10131318) Homepage Journal
          Correct me if I'm wrong, but isn't it still just as difficult to create a collision with a *known* message, as it was before this "attack" was discovered? In other words, there's no feasible way for a crooked forensics technician to alter the data. And even if it were practical to create a collision with a known message, the result of this on a harddrive is not going to be data that looks like it came from a harddrive. Rather, it's going to look like data that came from a random number generator.

          Hmmm, I guess that's one thing a crooked cop could do. He could make it look like the entire disk is encrypted. In France that's enough to convict your Grandmother with...
      • But there are always and necessarily possible collisions any time the checksum space is smaller than the data space (in this case, any time the data is more than 32 characters, never mind 20GB).

        I'd say "reasonable doubt", rather than mathematical certainty, is the key term here. Any checksum raises the odds that the data hasn't changed, but it can't prove that it hasn't unless there are at most the same number of possible checksums as there possible versions of the data.

        The question is one of likelihood

      • Think about forensics: Someone gets arrested, computer confiscated. The first thing that happens is a hash checksum is ran of the disk, then a disk image is made, then the image checksum is verified to make sure that it is the same as the original disk. If the checksum of the original disk ever changes, the evidence is useless. When there are collisions in the algorithm, the checksum cannot prove, beyond a reasonable doubt, that the data has not been tampered with.

        Well, the operative word there would be

      • Re:Idiot Question (Score:4, Informative)

        by ajna ( 151852 ) on Wednesday September 01, 2004 @01:12PM (#10130780) Homepage Journal
        Hash functions map a bigger space (unbounded strings, for example) to a smaller space (64 bits, perhaps), so collisions are inevitable. The linked article is not significant because it points out that MD-5 has collisions, since this is trivially true as I've attempted to make clear. It's significant because researchers have found a way to find multiple inputs which both hash to the same value. Since they have not found out how to create an input string that hashes to a value of their choice (preimage problem) MD-5 is not fundamentally broken.

        "When there are collisions in the algorithm, the checksum cannot prove, beyond a reasonable doubt, that the data has not been tampered with." This preceding sentence demonstrates a remarkable lack of understanding about hash functions. Collisions are inevitable, see above. How hash functions work is by making the hash values unpredictable and spread out evenly over the space of the hash values, given random input. Read up: http://www.cs.sunysb.edu/~skiena/214/lectures/lect 21/lect21.html or by googling for "hash functions collisions probablility".
      • If the checksum of the original disk ever changes, the evidence is useless. When there are collisions in the algorithm, the checksum cannot prove, beyond a reasonable doubt, that the data has not been tampered with.

        Neither of those statements are true. Hashing algorithms are useful for forensic verification but changing a single bit on a disk image will not cause it to be tossed from a case, as long as any changes can be explained as a result of something legitimate the forensic analyst did. Booting th

      • The particular attack mentioned in the article and your parent post does not apply in your forensics example - you are thinking of a preimage attack (where you can find a collision to an existing key) and not a collision attack (where you can find two messages that match a new arbitrary key).

      • Re:Idiot Question (Score:3, Insightful)

        by rsmith-mac ( 639075 )
        In many situations any data inconsistency can cause catastrophe

        Bingo. Take BitTorrent for example; it uses SHA-1 hashing to make sure every piece downloaded isn't corrupt, and otherwise helps ensure that no one is tampering with the torrent(and if they are, most clients kick them). However, if you can generate an arbitrary SHA-1 hash, anyone could seed the swarm with bad data, and the clients would never know. This could not only be used by the **AA to disrupt illegitimate torrents, but script kiddies coul

    • Re:Idiot Question (Score:5, Informative)

      by Westley ( 99238 ) on Wednesday September 01, 2004 @12:51PM (#10130575) Homepage
      I *think* this is the difference the article talked about between a preimage attack and a collision attack. An attacker still can't find a message (program, whatever) that produces the same hashcode as your one - but they *can* produce two messages which produce the same hashcode as each other. One of those may be perfectly acceptable, the other not - but once a user/system/whatever has accepted (or signed) the first one, they've effectively signed the second one.

      That's only my impression based on the article, and I wouldn't like to swear to it - but it does make a certain amount of sense.
      • If you sign for one hash, you've signed for anything that can generate that hash... which is a great deal more than 2 different sets of data. It's an infinite set of data (in theory)!
    • You are right in describing what happens in a "collision" scenario whereby you can get two streams to match each other without knowing what the hash would be. But there is still the problem of "preimage attack", whereby you *CAN* choose an alternative input that has the same hash as another output. Both would be similarly problematic and could potentially be catastrophic should an attacker attempt to compromise, say, a CA system.
    • I believe this collision algorithm takes a seed value and munges it (using neutral bits theory?) until you have two values that hash the same.

      If you use your code as the seed, and design the algorithm so that the way it munges one part of it to only introduce NOPs and the other

      oh yeah I see.

      Yeah a collision algorithm can't really be used in this case. Or any case now that I'm thinking about it. Unless you can find a way to design the algorithm to give you specific outputs. But then its not a collision

    • Re:Idiot Question (Score:5, Informative)

      by WolfWithoutAClause ( 162946 ) on Wednesday September 01, 2004 @01:13PM (#10130790) Homepage
      But what I dont get is this still doesn't allow somebody to arbitrarily pick whatever sum they want for their code right?

      It's based on the birthday party paradox.

      For two randomly chosen hashes, the chances of them being the same is 1/p where p is the maximum size of the hash.

      However, if you pick n hashes at random, then the chance that any two of them match is approximately n^2/2p, since any one of the 'n' could match with any other of the 'n'.

      So if p is 1/(2^160) and you generate 2^80 hashes of random (or partly random) data, then theres about a probability of 1 that two of them match each other. 2^80 is still a big number, but they've managed to reduce it further with some clever tricks, and modern processors can do billions of operations per second.

      So, if you write two programs one evil, one good, and then add 2^80 different random fillers on the end of each, chances are, two of the good/bads will have the same hash.

      But the chances of any of the bads matching a given hash that somebody hands you is only 2^80/2^160 which is 1/2^80- much too small.

    • The specific result is that it's much easier than random chance to generate two strings with the same MD5 value. This implies that MD5 is much less secure than previously assumed.

      No, it's not an algorithm that will efficiently find a string with the same MD5 value as your program A, but it's a significant step in that direction. MD5 is now known to have enough of a flaw that it is reasonable to assume that it's only a matter of time and ingenuity to exploit it.

    • The implications are largely academic for now. What seems to have been discovered is that there are some shortcuts in MD5 and SHA0 that make these algorithms less robust than previously expected. The existance of one "hole" in an encryption or hash algorithm suggests that there might be more waiting to be discovered. This might take 1 year or it might never happen.

      So, right now the primary risk is that someday we wake up to find that enough holes have been discovered to compromise preimage resistance.

  • New methods needed? (Score:3, Insightful)

    by scumbucket ( 680352 ) on Wednesday September 01, 2004 @12:46PM (#10130511)
    In the wake of stories like this is this a message that we need more secure forms of encryption than we already have? RSA is great so far, but how long until 1024 is broken? Or any other schemes, like the MD5 hashing that's used for digital signatures?

    Keeping ahead of the crackers is a big concern not only for security of transactions, but for personal privacy as well.

    • Re:New methods needed? (Score:5, Insightful)

      by merlin_jim ( 302773 ) <James@McCracken.stratapult@com> on Wednesday September 01, 2004 @12:59PM (#10130649)
      The question isn't how long until its broken... the question is how long until its broken for cheap.

      RSA-512 was already broken. It took a major portion of the world's computing resources for several years. You're not really in danger that your wife is going to find out about your girlfriend. Or that your state is gonna find out about your cocaine habit.

      If you're using RSA-512 you just might be on the cusp of being in danger of the government, having caught you and trying you for terrorism, is able to decode your e-mail enough in the six months before your trial to convict you.

      See its all about level of effort. How long till RSA-512 can be broken by anyone in a few minutes?

      Well 40-bit SSL was supposedly bulletproof when it was introduced. My P4 1.8 can decode SSL messages in about 10 seconds. So RSA-512 should be good for another 3-5 years.

      Honestly; always use the maximum number of bits. If your data is important enough to encrypt, its important enough to encrypt right.

      • Re:New methods needed? (Score:3, Informative)

        by gordyf ( 23004 )
        I think you're confusing symmetric and asymmetric cryptography. Current browsers use "128-bit SSL", which refers to 128-bit symmetric keys, which are still very secure (as long as the algorithm isn't weak and the implementation isn't flawed). 1024 or 2048-bit keys for asymmetric crypto are considered secure, I believe.

        But yes, 40-bit SSL is too weak to use. I don't think 512-bit RSA is considered very secure either.

      • Re:New methods needed? (Score:5, Informative)

        by Meostro ( 788797 ) * on Wednesday September 01, 2004 @01:35PM (#10130989) Homepage Journal
        Slight correction: AFAIK RSA-512 was not broken, it was brute-forced. There is a huge difference between the two.

        Breaking a combination lock is figuring out that you can hear the tumblers go *click* when you hit the right number. It will take you twenty seconds and five tries to get the right combination.

        Brute-Forcing a combination lock is trying every combination from 00-00-00 through 99-99-99 until you get the right one. You will get the right combination, it will just take you long enough that someone will notice you.

        Just to give you back a little bit of a warm-fuzzy feeling about RSA strength, realize that every bit added doubles the brute-force keyspace. So if you can brute-force 40-bit SSL in 10 seconds, you can do 41-bit SSL in 20 seconds, but it'll take 98 billion-billion years for the same computer to do 128-bit SSL.

        For the combo lock analogy, it would be adding on another number to guess, a 4 number lock instead of 3, which would give you 100x as much work (original amount of work to get numbers A-B-C with D=00, then lather, rinse, repeat until D=99). If the combo lock were truly broken instead, it would take you about a minute and seven tries, instead of 100x as long.
        • ust to give you back a little bit of a warm-fuzzy feeling about RSA strength, realize that every bit added doubles the brute-force keyspace. So if you can brute-force 40-bit SSL in 10 seconds, you can do 41-bit SSL in 20 seconds, but it'll take 98 billion-billion years for the same computer to do 128-bit SSL.

          Of course, that presumes that your computer gets no faster in the next hundred pentillion years. If Moore's Law holds--really, more Moore's Observation--then you get an extra bit off the key 'for fre

    • As a side note, RSA relies on hashing for it to work in signing messages, if you can break hashing algorithms, you can break most public key crypto. (It has been a while since I kept up on crypto, but IIRC all public key signing required using hashing to sign the message and then use the private/public key crypto to encrypt the key, they article actually alludes to this problem.)

  • browsers check for wildcard in domain names??????? (Score:4, Interesting)

    by stonebeat.org ( 562495 ) on Wednesday September 01, 2004 @12:49PM (#10130545) Homepage
    For example, a devastating attack would be one that enabled adversaries to obtain a legitimate server certificate with a collision to one containing a wildcard for the domain name and an expiration date far in the future.

    quick questions:
    1) Don't the browser check for wildcard domain names in the certificates???
    2) If not, why not???

  • Ok... (Score:3, Insightful)

    by doublebackslash ( 702979 ) <doublebackslash@gmail.com> on Wednesday September 01, 2004 @12:51PM (#10130560)
    Use both!
    You say its easier than ever to find the soloution to each one of these hashes, so just use em both. I really think that the number of collisions that occur similtaniously are a bit fewer and farther between. I think that will be secure until we find a better and decently fast hash.

  • How about this... (Score:4, Interesting)

    by Millennium ( 2451 ) on Wednesday September 01, 2004 @12:58PM (#10130642)
    Has a collision been found yet concerning data which has both the same MD5 sum and the same SHA-1 sum?

    It would seem as though even if SHA-1 were to fail, the two algorithms used together could bolster each other security-wise. This slows things down, of course, but would it not suffice for the time being?

    • Re:How about this... (Score:5, Informative)

      by merlin_jim ( 302773 ) <James@McCracken.stratapult@com> on Wednesday September 01, 2004 @01:01PM (#10130673)
      FTA...

      SSL3.0/TLS does use both, and is therefore immune to this attack.

      Also FTA, SHA-1 is still believed to be secure, and Cryptography Researchers does not believe it is in danger to this same attack.

    • Re:How about this... (Score:5, Informative)

      by Anonymous Coward on Wednesday September 01, 2004 @01:38PM (#10131008)
      It would seem as though even if SHA-1 were to fail, the two algorithms used together could bolster each other security-wise. This slows things down, of course, but would it not suffice for the time being?

      Using two hashes in conjunction does not work as well as you would expect it to work. There are at least half a dozen posters here proposing this idea, so I will try to explain in some detail why it does not work.

      In general an n-bit hash can be collided in 2^(n/2) time using the birthday paradox attack. When you concactenate two hashes of lengths n and m bits, you get a hash of length n+m bits. However, this (n+m)-bit hash can in fact be collided in m*2^(n/2) + 2^(m/2) time (assuming n is greater than or equal to m). This is only slightly more effort than it takes to collide both hashes separately. In the case of SHA-1 and MD5, n is 160 and m is 128, so colliding both hashes would take 128*2^80 + 2^64 = 2^87.00000017 effort versus 2^80 effort for SHA-1 alone.

      It must be especially stressed that m*2^(n/2) + 2^(m/2) is considerably smaller than the attack time of 2^((n+m)/2) which you would normally expect from a well designed hash having n+m output bits.

      So how does the attack on two hashes work, you ask? It exploits a curious property of the birthday attack which says that generating a multicollision (three or more messages all with the same hash) by brute force takes only marginally more effort than generating a single collision. Specifically, generating a 2^(m/2) way multicollision takes only m/2 times as much effort as generating a single collision. So what you do to collide two hash functions is: you generate a huge multicollision in the first hash function, and then from that set you look randomly for a pair that collides the second function. It seems very counterintuitive, but the point is you can break the hash functions one by one instead of having to break both of them at once. Strength in numbers doesn't apply here.

      If one of the hash functions (say MD5) has a better than brute force attack, then that can be used to speed up the attack against both hash functions by the same factor. The only uncertainty is if both of the hash functions have better than brute force attacks; in this case it would depend on the particulars of the attacks as to whether one can make them interact in such a way as to break both. However, no matter what, the idea of concactenating two hash functions has such low security compared to designing a good hash function of the same length from scratch that it is unlikely that this concept will ever be useful from a pure cryptography standpoint.

      For more information on multicollisions and attacking concactenated hash functions, see A. Joux "Multicollisions in Iterated Hash Functions", Proceedings of Crypto 2004, LNCS 3152.

  • to protect binaries (Score:2, Interesting)

    by Anonymous Coward
    it would be better to post both the MD5 hash _and_ the SHA-1 sum. What's the chance of 2 different binaries having the same MD5 and the same SHA-1 at the same time??

    Artaxerxes

  • Another writeup on this (Score:2, Informative)

    by Anonymous Coward
    Is here [pantsfactory.org].

  • Summary for those too lazy to read it (Score:5, Insightful)

    by rewt66 ( 738525 ) on Wednesday September 01, 2004 @01:16PM (#10130811)
    The world is going to end! Giant asteroids will destroy all life on earth!

    Oops, wrong article. Um... The world is going to end! Global warming... um, well... the Patriot Act... umm...

    Well, it's not that bad. Somebody might be able to flip four very carefully selected bits in a file, and still produce the same MD5 hash. This could let me, for example, create an executable that had a normal, benign behaviour, and an evil trojan behaviour, and have one of the bits that I flip change a conditional so that the trojan behaviour was activated. (Note that open source tends to be immune to this kind of nonsense, since in the source code, the actual trojan part - not the conditional that activates it, but the actual evil payload - tends to stick out like a sore thumb.)

    Note well that this does not let me create an evil version of somebody else's file. It only lets me create two closely related files, one of which differs by four bits from the other. I have to be able to construct the benign file in such a way that I can turn it into an evil file by changing four bits. And it can't be just any four bits, either; it's a very specific four bits.

    So this isn't the end of the world. What it means is that you can't quite trust MD5 to guarantee that you got exactly, bit-for-bit, what you think you got.

    But really, this new situation isn't much worse than what we had before. I mean, I could simply have the evil behaviour activated by the date, or by the IP address of the installed machine, or whatever, and get somebody else (who never saw the evil part run) to state that the program did what it was supposed to. Having an MD5 hash doesn't guarantee that the program isn't evil. Bottom line: don't run code written by bad people, whether it has a valid MD5 or not. (I know, I know. How do you tell who the bad people are? That's a hard question, but my point is that a valid MD5 has never told you whether the authors were bad people or not.)

    • Re:Summary for those too lazy to read it (Score:4, Interesting)

      by Isao ( 153092 ) on Wednesday September 01, 2004 @01:35PM (#10130983)
      What it means is that you can't quite trust MD5 to guarantee that you got exactly, bit-for-bit, what you think you got.

      You never could. It merely said that it was unlikely for you to be getting something else. The difficulty of arranging such a situation just got easier. Not easy. Not trivial. Just easier. Probably by the same factor it got easier over the past four years due to Moore's law increases. Eventually this will become a real issue, and we should be prepared for that, much the same way we don't use plain DES any more.

  • Oh no! my nick is compromised! (Score:4, Funny)

    by d41d8cd98f00b204e980 ( 808839 ) on Wednesday September 01, 2004 @01:16PM (#10130813)
    A bad day for me.

  • How to Expoit (Score:3, Informative)

    by notthepainter ( 759494 ) <oblique@alu3.14m.mit.edu minus pi> on Wednesday September 01, 2004 @01:20PM (#10130846) Homepage
    So as I understand it, from read many of the above comments, the exploint is as thus.

    I write 2 programs, lets call one "Cool Whizzy Must Have Util" and the other "Soul Sucking Destruction" and I tweak and tweak one of the binaries so that they have the same checksum.

    Then I release the first one, everybody is eventually using it.

    So then on my servers, I replace the first one with the 2nd one.

    Gotcha!

    Is that the danger here?

  • Access (Score:2, Funny)

    by lateralus_1024 ( 583730 )
    Yes but what does this mean to me, "Mr.MSAccess Guru/Administrator"?

    Microsoft certification available upon request.

  • Frequently questioned answers (Score:5, Informative)

    by Anonymous Coward on Wednesday September 01, 2004 @01:30PM (#10130939)
    "SHA1 is a totally different algorithm, so it's still perfectly safe."

    Yes and no. MD5 collisions are not SHA1 collisions, and the attack that generated the MD5 collisions doesn't seem to be applicable to SHA1, or its authors would have published collisions on SHA1. The published collisions on several other algorithms: HAVAL-128, MD4, and RIPEMD. They also say that their method will work against SHA0. All these hash functions share similar design principles. It seems highly probable that the MD5 attack will have at least some applicability to SHA1 even though it isn't directly an attack against SHA1. Also, other researchers have published results against SHA1. In particular, Biham and Chen con produce collisions on reduced versions of SHA1 with up to about 40 rounds (the full hash function has 80). That isn't a break of the full hash function, and there's no guaranteed it can be extended to more rounds, but it looks worrisome.

    "This attack produces two messages with the same hash, no guarantee what that hash would be, instead of one message with a chosen desired hash, so it isn't a threat to real systems."

    That's just stupid. "No practically-findable collisions" is one of the design requirements for a secure hash function. Protocols using secure hash functions are based on the assumption that the functions used are secure hash functions. If your hash function doesn't guarantee collision resistence, then your protocols must be assumed to be broken unless you can go back and prove, for every protocol, "This one is still secure even if we use something that is not a real secure hash function."

    One way a hash collision could be useful, for instance, would be against some signature schemes where the secret key is revealed if you ever sign an identical message more than once. People who use those schemes are careful to avoid signing the same message twice... but if you had two different messages and they had the same hash, it's quite possible to imagine that you could be tricked into signing the same hash more than once (because people sign hashes, not actual messages) and making trouble for yourself. Similarly, if you use hash output for initialization vectors in cipher modes that use those, the result could be encrypting two messages with the same keystream, which means an attacker can probably recover both messages (and then use them as stepping-stones to breaking the rest of your system).

    Also, a fast way of finding collisions may well be extensible to a somewhat-slower, but still faster-than-brute-force, way of finding the preimages that you think an attacker really wants.

    "This attack depends on the messages having a special form; they don't look like real plaintext, so it isn't a threat to real systems."

    One of the conditions for a secure cryptographic system is that you don't depend on the plaintext having (or NOT having) a specific form. If your system doesn't work regardless of the content of the data I put through it, then I will punt on your system, and recommend to my clients some other system that will actually work. It's also not clear that the attack on MD5 really does require a specific form... those strings look randomly-generated to me, even though the XOR difference of them clearly is not. Maybe with just a little more work they can produce collisions of two meaningful and interesting strings with opposite meanings.

    "All hash functions have collisions, so it was bound to happen and isn't a threat."

    The important question is whether people can actually find collisions. With a good hash function, collisions should be rare enough that nobody has any reasonable chance of finding them on purpose any time soon. Wang, Feng, Lai, and Yu can find collisions on MD5 deliberately, with practical amounts of computer power. They have done this more than once, and have at least outlined a plausible theoretical explanation of how they can do it. That means MD5 does not provide the guarantees that a secure hash function must

    • Re:Frequently questioned answers (Score:4, Informative)

      by Idarubicin ( 579475 ) on Wednesday September 01, 2004 @02:53PM (#10131767) Journal
      Wang, Feng, Lai, and Yu can find collisions on MD5 deliberately, with practical amounts of computer power. They have done this more than once, and have at least outlined a plausible theoretical explanation of how they can do it. That means MD5 does not provide the guarantees that a secure hash function must provide; MD5 is not a secure hash function.

      It depends on how you define 'secure' and for what purposes you intend to use MD5. For a lot of cases, MD5 is still 'secure'.

      Wang et al. have demonstrated that they can generate collisions in a reasonable period of time. They have not demonstrated that they can generate a collision for a given hash--a so-called preimage attack.

      In other words, it is possible to produce two files full of junk that have the same MD5 hash. It's not possible (yet) to produce a file that has the same MD5 hash as a Linux kernel. It's not possible to create Trojan malware that shares an MD5 hash with a useful application. For most of us, that still counts as 'secure'.

  • The next hash (Score:3, Interesting)

    by augustz ( 18082 ) on Wednesday September 01, 2004 @01:34PM (#10130977)
    The work that went into putting together AES was really fantastic.

    I'm just looking forward to a similar effort around an advanced hashing standard.

    Where would an effort like this form?

    • Re:The next hash (Score:3, Informative)

      by xxxJonBoyxxx ( 565205 )
      NIST (http://csrc.nist.gov/cryptval/) ran the AES contest (http://csrc.nist.gov/CryptoToolkit/aes/index.html ). They would be the body to run future contests of the same sort.

      BTW, NIST never approved MD5 for government use (as per FIPS), but they have been validating implementations of SHA-1 for several years. NIST also now validates SHA-224, SHA-256, SHA-384, and SHA-512, each essentially a longer version of SHA-1 ("160").
  • Upon hearing these news, Tom Ridge raised the level of alert to "Amber".

    At least this time he had something a tad more substantial to instill fear in the hearts of all patriotic Americans such as myself.

    Thank you Department of Homeland Defense! I sleep so much better at night!

  • Real scoop (Score:4, Interesting)

    by Anonymous Coward on Wednesday September 01, 2004 @01:38PM (#10131010)
    I wasn't there this year. A friend told me that the embarrassing thing was that the Chinese paper was REJECTED from the conference. They presented their results at the rump session. Other non-Asian researchers with hash collisions got papers in the conference. This doesn't help one's faith in academia, does it, when one of the most important developments at a conference is rejected by the program committee. There is a growing rift between Asian research and Western research. The Asian side has much lower standards, but also has some good results. Sometimes good Asian papers end up being rejected by association with so many mediocre Asian papers.

    Posted anonymously to avoid offending any of my colleagues.

    • Re:Real scoop (Score:4, Informative)

      by randombit ( 87792 ) on Wednesday September 01, 2004 @03:22PM (#10132044) Homepage
      I wasn't there this year. A friend told me that the embarrassing thing was that the Chinese paper was REJECTED from the conference. They presented their results at the rump session.

      Of course, it would have helped the paper's chances of being accepted if:

      a) They had actually presented the methods they used

      and/or

      b) The results had been correct. Initially, they were not finding collisions for MD5, but what they *thought* was MD5 (due to a translation error).

      So what the reviewers read was a claimed attack on MD5, with no details, and their examples did not work. If I were reviewing that paper, I would have rejected it too. They didn't correct the paper until (IIRC) the day before the rump session.

  • Hash function attack roundup at Educated Guesswork (Score:2, Informative)

    by Anonymous Coward
    More info on the implications at Educated Guesswork [rtfm.com]. (It isn't my work, so anonymously it is.)

  • a better solution already exists (Score:5, Funny)

    by poot_rootbeer ( 188613 ) on Wednesday September 01, 2004 @01:57PM (#10131221)

    ROT-13 is completely invulnerable to hash collisions; no two non-identical inputs will ever result in identical outputs!

    I recommend that everybody replace their existing encryption systems with ROT-13 immediately.

    -Cbbg
  • http://eprint.iacr.org/2004/199.pdf

  • The attack does matter. (Score:4, Informative)

    by Chandon Seldon ( 43083 ) on Wednesday September 01, 2004 @03:11PM (#10131922) Homepage
    With a collision attack, you can perform an attack that matters - here's an example:

    Imagine that Microsoft won't sign any audio drivers for Windows XP that allow raw audio data to be output to disk. Also imagine that you are the driver release engineer at Creative (Sound Blaster division) and you want to release a driver that can do that.

    What you do is build both drivers (one that Microsoft will sign, and one that you want to release with the "unacceptable" feature) with a large static data buffer that isn't used in the binary. You then try to modify both buffers in such a way as the two files will have the same hash (doesn't matter what hash, just that it's the same). This will take about 2^40 worth of work for MD5 instead of the 2^64 that it should take because of this security issue.

    Once you've created your two binaries with the same hash, you send the acceptable binary to Microsoft and they sign it. Then, in the release section of your website you post the other binary with the signature you got from Microsoft... and the signature verifys just like they signed it.

    There is also a break in the digital check situation, *if* the digital check protocal has random padding (many do) *and* the payee generates the check (also possible).

Slashdot Top Deals

A committee takes root and grows, it flowers, wilts and dies, scattering the seed from which other committees will bloom. -- Parkinson

Close