$10M breaks MD5 in 24 days
I am not attending the Crypto conference, but I sat in on the evening "rump session" the other day. One of the more interesting papers had a claim (with little detail, unfortunately) that for ten million dollars you could build a machine that would "break" MD5, in the sense of finding another message which would hash to the same as a chosen one, in 24 days. This result did not depend on any internal structure in MD5, but was purely a result of the hash size (128 bits) and the time it takes to calculate a hash. The main new result which allowed this was a more efficient way of handling a parallel search for collisions (two messages which hash to the same thing). In some earlier methods, n machines provide only a sqrt(n) speedup. The new method improves this, although my notes don't show exactly how close they come to an n-fold speedup. The Secure Hash Standard (SHS, aka SHA) is, they said, 64K times slower, hence this technique would take 64K times longer (or cost ~64K times more?) to break that hash. I don't think this is probably anything to really worry about, but maybe it points out a need for a longer hash in the next few years. Hal P.S. The paper was by Paul C. van Oorschot & Michael J. Wiener.
Hal says:
The Secure Hash Standard (SHS, aka SHA) is, they said, 64K times slower, hence this technique would take 64K times longer (or cost ~64K times more?) to break that hash.
Well, I suppose this demonstrates that the NSA knew what they were doing when they set the SHA's length to 160 bits. Let it never be said that they aren't right on top of everything... Perry
Well, I suppose this demonstrates that the NSA knew what they were doing when they set the SHA's length to 160 bits. Let it never be said that they aren't right on top of everything...
On the other hand, I can't imagine that NSA is unaware that strong cryptographic hash functions designed for authentication are also useful building blocks for a confidentiality cipher. Which might make them less than wholly enthusiastic about doing their best on a public standard like SHA. Caveat emptor NSA. (John Cleese, if you're out there, feel free to correct my Latin). Phil
Phil Karn says:
Well, I suppose this demonstrates that the NSA knew what they were doing when they set the SHA's length to 160 bits. Let it never be said that they aren't right on top of everything...
On the other hand, I can't imagine that NSA is unaware that strong cryptographic hash functions designed for authentication are also useful building blocks for a confidentiality cipher. Which might make them less than wholly enthusiastic about doing their best on a public standard like SHA.
True enough. However, we don't have a lot of alternatives right now. MD6, anyone? .pm
One of the more interesting papers had a claim (with little detail, unfortunately) that for ten million dollars you could build a machine that would "break" MD5, in the sense of finding another message which would hash to the same as a chosen one, in 24 days.
This in itself wouldn't give an attacker much of anything would it? I mean, once they discovered a message which hashed to a given value, the new message wouldn't be in the proper format, would it? Wouldn't it just be noise, instead of text in english, crypto keys, etc.?
alex says:
One of the more interesting papers had a claim (with little detail, unfortunately) that for ten million dollars you could build a machine that would "break" MD5, in the sense of finding another message which would hash to the same as a chosen one, in 24 days.
This in itself wouldn't give an attacker much of anything would it? I mean, once they discovered a message which hashed to a given value, the new message wouldn't be in the proper format, would it? Wouldn't it just be noise, instead of text in english, crypto keys, etc.?
Schneier has a good discussion of this. Suffice it to say, if I have a magic collision search box, I might very well be able to produce an interesting result very easily. Imagine the existance or nonexistance of a space at some number of locations in a document as being a bit. Then, imagine that I have a hash signed by you. If I can search very fast, I could compose a contract that you never signed, and search through the trivial variations of that contract with spaces present or absent at some number of points. I can thus trivially generate the number of variations on the contract needed to find a collision -- if I can only search those variations fast enough you lose. Given that ten million dollars isn't real money, if this is true MD5 isn't worth that much any longer -- it certainly isn't safe for use in signing digital drafts, for example. Perry
On Aug 25, 7:01pm, alex wrote:
Subject: Re: $10M breaks MD5 in 24 days
One of the more interesting papers had a claim (with little detail, unfortunately) that for ten million dollars you could build a machine that would "break" MD5, in the sense of finding another message which would hash to the same as a chosen one, in 24 days.
This in itself wouldn't give an attacker much of anything would it? I mean, once they discovered a message which hashed to a given value, the new message wouldn't be in the proper format, would it? Wouldn't it just be noise, instead of text in english, crypto keys, etc.?
Not necessarily. If you're forging some packet, certificate or file, it is often adequate to have just a couple of fields (potentially a few bits) which contain data you want, and the rest can be garbage. If your search engine could fix these and play with the rest of the packet, the chances are good (but decreasing with the more bits you use for a fixed size packet) that you will find a packet which will have the correct signature _and_ contain the forged data you need. If you can play with the packet size, then your chances of finding a match increase. Ian.
participants (5)
-
alex -
Hal -
Ian Farquhar -
Perry E. Metzger -
Phil Karn