The SHA-1 crack (below) by the now legendary team from Shandong University has me thinking. It's great work. It opens the door to some really serious thinking (this remark was made by Ron Rivest at Crypto 2004, I recall).
But the crack doesn't quite get there. 69 bits is still too many. It's even more than MD5 had at full 64 bit strength. This all sounds like a replay of the fabled Skipjack case, where the algorithm had so many interesting artifacts that cryptographers expected it to break ... but try as they might, they couldn't quite get there.
Skipjack was a case of excellent engineering. Almost no margin for error, and a clear sign that the NSA knew precisely where the limits were.
Now we know that SHA-1 moves from 80 bit strength to 69 bit strength. Maybe it is destined to lose a few more bits. That still makes it good and practical, albeit a little dated. Maybe, just maybe when the NSA fixed up the flaws in SHA-0 that took it from its now 39 bit strength to 69 bits, they consulted a table just like Lenstra and Verhal's and decided on what they needed?
Just idle speculation, mind!
Posted by iang at February 17, 2005 09:49 AM | TrackBack(Greg writes on cryptography in answer to another question:)
If you look at Phil Hawkes' paper , you will see that the SHA-2s are very different algorithms, and my own opinion is that the data-expansion part of the algorithm is *seriously* beefed up. My guess is that the NSA were already worried about this kind of attack (whether they'd found it or not). We don't have a good analysis of the data-expansion part, but I'm pretty sure that it'll defeat the Wang attacks.
Greg.
Posted by: Greg R at February 17, 2005 05:11 PMI wanted to second Greg's point about SHA256, but with a caveat: Since we haven't seen Wang's techniques, it's hard to have a huge amount of confidence that she won't be able to find something despite rather different structure of SHA256. But the message expansion is much more complex, and introduces some carry bits into the mix. Similarly, the internal mixing of bits among different bit positions within the "encryption" function in MDx, RIPE-MDx, and SHA0/1 is mostly done by carry bits and the small number of rotations. SHA256 introduces a much stronger internal (linear) mixing operation that's going on by rotating a word three times by different amounts and XORing the result together.
The point is that it seems much more straightforward to apply the same techniques to MD5 and SHA1, than to apply the same techniques to SHA1 and SHA256. But then, a week ago, I thought SHA1 would probably be okay for the time being--what do I know?
--John
Posted by: John Kelsey at February 18, 2005 10:00 AM