|No such thing as a small change|
On showing the weakness in the MD5 digest function and getting bitten by scalar contextby grinder (Bishop)
|on Aug 26, 2004 at 22:18 UTC||Need Help??|
For those of you who have been living in a cave for the past few weeks (or without net access, voluntarily, or not, as in my case), you may not be aware that researchers have found a method that seriously weakens the usefulness of MD5, and, to a certain extent, SHA-1 digests.
MD5 produces a fixed 128 bit string from any given string. SHA-1 does the same except that the length of the bit string is 160 bits. The strength of the digests comes from the fact that if the digest of a given string (say, the text of this node) produces a certain digest. To find another string that maps to the same digest (i.e. a collision in the MD5-space) should theoretically take 2^128 steps. The research shows how to find a collision reliably in 2^40 steps. As someone points out:
The difference between those two numbers is several days, versus several million years.
Anyway, the point of this all is that while trying to find out more about the issue, I came across a weblog cum forum where someone posted a Perl program to show the flaw. Someone then produced an improved version that was more cross-platform (not relying on an external program).
The really funny part was when another participant posted the following reply:
Not being able to see the difference in the bytestreams, I decided to run the bytes through SHA1. When I saw that the SHA1s were the same hash... AND realized that the bytestreams were different... Well I almost poo'ed my pants.
Yes folks, the person who wrote the original snippet created an array of 128 values, and assigned it to scalar. Thereby storing the length of the array, rather than its contents.
To find out more, take a look at Freedom to Tinker - Report from Crypto 2004 for more details.
Oh, and, it's time to stop using MD5. Seriously. If you ar using it for security (rather than just checking to see that your file was copied correctly), use a longer hash. Use SHA-512 if you can.
- another intruder with the mooring of the heat of the Perl