NIST Hash Workshop Liveblogging (2)

In the morning we had a series of interesting papers: “Strengthening Digital Signatures via Randomized Hashing,” by Halevi and Krawczyk; “Herding Hash Functions and the Nostradamus Attack,” by Kelsey and Kohno; and “Collision-Resistant usage of MD5 and SHA-1 via Message Preprocessing,” by Szydlo and Yin. The first and third papers are suggestions for modifying SHA-1 to make it more secure. The second paper discusses some fascinating and cool, but still theoretical, attacks on hash functions.

The last session before lunch was a panel discussion: “SHA-1: Practical Security Implications of Continued Use.” The panel stressed that these are collision attacks and not pre-image attacks, and that many protocols simply don’t care. Collision attacks are important for digital signatures, but less so for other uses of hash functions. On the other hand, this difference is only understood by cryptographers; there are issues if the public believes that SHA-1 is “broken.”

Niels Ferguson pointed out that the big problem is MD5, which is still used everywhere. (Hell, DES is still everywhere.) It takes much longer to upgrade algorithms on the Internet than most people believe; Steve Bellovin says it takes about one year to get the change through the IETF, and another five to seven years to get it depoloyed. And that’s after we all figure out which algorithm they should use.

Georg Illies gave a perspective from Germany, where there is a digital-signature law in effect. In addition to the technology, there are legal considerations that make it harder to switch.

The panel seemed to agree that it’s still safe to use SHA-1 today, but that we need to start migrating to something better. It’s way easier to change algorithms when you’re not in the middle of a panic.

There was more talk about algorithm agility. This problem is larger than SHA. Our Internet protocols simply don’t have a secure methodology for migrating from one cryptographic algorithm to another.

Bottom line: Don’t use SHA-1 for anything new, and start moving away from it as soon as possible. To SHA-256, probably.

And now it’s lunchtime.

Tags: academic papers, cryptography, DES, hashes, IETF, Internet, laws, MD5, NIST, security conferences, SHA-1, SHA-2, signatures

Posted on October 31, 2005 at 11:50 AM • 11 Comments

Comments

Larry • October 31, 2005 1:16 PM

Thanks for the post. I couldn’t be there so it is especially nice to get a running account. Thanks Bruce!!

Brent Dax • October 31, 2005 2:26 PM

I was reading a book on SSL recently, and I was really surprised at how deeply MD5 and SHA-1 were hardwired into the protocol, with no thought given to the possibility that someday they might not be adequate. I know you’re supposed to keep cryptographic systems simple, but allowing algorithms to change in an environment where someone could totally break your security next week seems like common sense to me.

Hal • October 31, 2005 2:46 PM

Why is there no published source code for an implementation of Wang’s MD5-collision attacks? There have been several papers presented by different groups, all of which show examples of MD5 collisions. So they must have the software. But no one has created something they are willing to publish and distribute.

It would be useful to have such a tool so that people could more easily show practical weaknesses in MD5 and encourage migration away from that hash.

(I might add, I tried to write such a program, and I failed. The techniques in Wang’s paper didn’t work for me. I guess I was doing it wrong. I was able to break MD4 using her methods but MD5 never worked.)

Bruce Schneier • October 31, 2005 3:07 PM

“Why is there no published source code for an implementation of Wang’s MD5-collision attacks?”

I, too, would like to see real code and a distributed implementation of the attack. For MD5 and for SHA-1.

Patrick Stach • October 31, 2005 3:36 PM

I’ll post working code in the next week or two for many of the algorithms, although tuning the loops for SHA-0 and SHA-1 may require more CPU time than I have (currently I’ve only generated a small handful)

Anyhow, here’s an MD5 collision where I got really lucky on time. Usually takes about 2 hours for a fully unique collision such as this one (will be explained in README bundled with code).

/* data in LSB */
u_int32_t m0[32] = {
0x6c15bc12, 0x051adccb, 0x35459b85, 0xb0b7cc57,
0x147eb332, 0xedc64193, 0x11518a68, 0x7082bea0,
0x06332cb1, 0x82346bf7, 0x7f8eef23, 0xd31a4113,
0x3bee52df, 0xb3a8abe4, 0x974b118e, 0x072878f6,
0x6ea7a8fb, 0x26159be4, 0x089ceec0, 0x974c4697,
0xc5f79485, 0x0dd0ddbe, 0x17a09cf6, 0x9fa59e52,
0x3f3aaf65, 0x298e4381, 0x23430c8a, 0x68368865,
0x464d9ca0, 0xaecbed56, 0x12b3c7e5, 0x77485296,
};
u_int32_t m1[32] = {
0x6c15bc12, 0x051adccb, 0x35459b85, 0xb0b7cc57,
0x947eb332, 0xedc64193, 0x11518a68, 0x7082bea0,
0x06332cb1, 0x82346bf7, 0x7f8eef23, 0xd31ac113,
0x3bee52df, 0xb3a8abe4, 0x174b118e, 0x072878f6,
0x6ea7a8fb, 0x26159be4, 0x089ceec0, 0x974c4697,
0x45f79485, 0x0dd0ddbe, 0x17a09cf6, 0x9fa59e52,
0x3f3aaf65, 0x298e4381, 0x23430c8a, 0x68360865,
0x464d9ca0, 0xaecbed56, 0x92b3c7e5, 0x77485296,
};

real 8m25.236s
user 7m39.305s
sys 0m1.044s

Hal • October 31, 2005 3:46 PM

That sounds great, Patrick, I will look forward to seeing it. I assume that you have not actually generated any collisions for SHA-1; as far as I know, no one has ever found such a collision. It will be quite a newsworthy event when it happens.

Patrick Stach • October 31, 2005 3:52 PM

Further, I would like to comment on the paper by Szydlo and Yin.

It is very easy to follow the state variables in md4/md5/sha0/sha1/etc and accumulate the number of dependency bits in the currently processed block.
If said counter is above a certain threshhold, attempt computing the complementary collision pair and check to see if the final state is a match.

This method is common sense, however has its flaws. It only detects the collision differential presented by Wang, et al. If other collision differentials are found the compress function becomes more and more performance lossy in order to compensate for the known differentials (Anti-virus software anyone? 🙂

Hal • October 31, 2005 4:37 PM

Patrick, if I understand your point, you are describing a technique by which a person hashing some data supplied by someone else could determine if it was likely an attempt to create a Wang-style collision, right? You would count the number of bits meeting a certain condition, and if they exceed the threshold, that would not be something that would be likely to happen by chance. So you could determine that the hash value was a Wang collision and warn the signer or verifier that something fishy was afoot.

As you say, this technique might be “brittle”, such that any given detection code could be worked around so that there would be a class of collisions (perhaps somewhat more costly to find but still feasible) which it did not detect.

znoren • November 10, 2005 9:17 AM

I spent most of the summer working on the MD5 attack, so I better make sure it wasn’t wasted. Clicking my name will take you to a page that has my (primitive) implementation.
Further information on the page.

Patrick Stach • November 13, 2005 12:03 PM

My name in this post links to my MD4 generator

Patrick Stach • November 13, 2005 12:04 PM

My name in this post links to my MD5 generator.

Schneier on Security

NIST Hash Workshop Liveblogging (2)

Comments

Leave a comment Cancel reply