Educated Guesswork: Hash function attack roundup

August 19, 2004

Hash function attack roundup

I promised earlier to write up my impressions of the implications of the recent hash function attacks. I meant to do a full writeup but I haven't had time, so in the interest of timeliness, here's my first cut.

Joux has found a single collision in SHA-0--an algorithm that nobody uses but that is very similar to SHA-1. However, SHA-0 was changed to fix a flaw (later found by Joux), thus becoming SHA-1 so we can hope that this attack can't be extended to SHA-1. The attack was fairly expensive, requiring about 2⁵¹ operations the brute force attack would take about 2⁸⁰).

Biham and Chen can find collisions in a reduced round version of SHA-1 (40 rounds). The full SHA-1 is 80 rounds. It's hard to know whether this can be extended to full SHA-1 or not. NSA (who designed SHA-1) seems to be generally pretty good at tuning their algorithms so that they're just complicated enough to be secure. My sources also tell me that Biham said at Crypto that he didn't expect to be able to extend the attack past 46 rounds or so.

Weng, Fang, Lai, and Yu have what appears to be a general method for finding collisions in MD4, MD5, HAVAL-128, and RIPEMD. They haven't published any details. They also say that they have a 2⁴⁰ attack on SHA-0.

What does this mean in practice for security protocols? I'll be writing up full details hopefully soon, but here's a short overview...

What's been shown?
An attacker can generate two messages M and M' such that Hash(M) = Hash(M'). Currently this is possible for MD5 but we have to consider the possibility that it will be eventually
possible for SHA-1. Note that he cannot (currently) generate a message M such that Hash(M) is a given hash value, nor can he generate a message M' such that it hashes the same as a fixed message M.

Uses of hash functions
Security protocols use hash algorithms in a bunch of different contexts. At minimum:

Digital signatures (you sign the hash of a message).
1. On messages (e.g. S/MIME).
2. On certificates.
3. In authentication primitives (e.g., SSH)
As MAC functions (e.g. HMAC)
As authentication functions (e.g. CRAM-MD5)
As key generation functions (e.g. SSL or IPsec PRF)

The potential attacks
The only situation in which the current attacks definitely apply is 1. The general problem is illustrated by the following scenario. Alice and Bob are negotiating a contract. Alice generates two messages:

M  = "Alice will pay Bob $500/hr"
M' = "Alice will pay Bob $50/hr"

In practice, the messages might not be this similar, but there turn out to be lots of opportunities to make subtle changes in any text message.

Where H(M) = H(M').

She gets Bob to sign M (and maybe signs it herself). Then when it comes time to pay Bob, she whips out M' and says "I only owe $50/hr", which Bob has also signed (remember that you sign the hash of the message).

So, this attack threatens non-repudiation or any kind of third party verifiability. Another, slightly more esoteric, case is certificates. Remember that a certificate is a signed message from the CA containing the identity of the user. So, Alice generates two certificate requests:

R  = "Alice.com, Key=X"
R' = "Bob.com, Key=Y"

Such that:

H(R) = H(R')

I'm simplifying here, but you get the idea...

When the CA signs R, it's also signing R', so Alice can present her new "Bob" certificate and pose as Bob. It's not clear that this attack can work in practice because Alice doesn't control the entire cert: the CA specifies the serial number. However, it's getting risky to sign certs with MD5.

What's safe?
First, anything that's already been signed is definitely safe. If you stop using MD5 today, nothing you signed already puts you at risk.

There is probably no risk to two party SSH/SSL-style authentication handshakes.

It's believed that HMAC is secure against this attack (according to Hugo Krawczyk, the designer) so the modern MAC functions should all be secure.

I'm not entirely sure about other non-HMAC challenge/response systems such asHTTP Digest. They're not as well designed as HMAC. I don't know any attacks but I haven't looked too hard either. It would be nice to see someone give them a thorough once over

The key generation PRFs should be safe.

The future?
There's a lot of concern in the crypto community that the attacks on MD5 can be turned into full pre-image attacks (being able to generate a message M such that H(M)=X for a given hash value X). If that were to happen, this would be really serious and potentially compromise a lot of the stuff mentioned above.

UPDATE: Paul Joseffson observes that CRAM-MD5 is actually HMAC, so it's probably OK. I'd misremembered it as an ad hoc function. Removed CRAM-MD5 from the list above.

UPDATE: Added the Chinese SHA-0 results, as reminded by Perry Metzger.

Posted by ekr at August 19, 2004 10:15 PM | TrackBack

Comments