Hash Algorithms Broken On August 16th in Crypto2004 By Chinese Scholars

Here are some broken news in cryptography as summarized by Eric Rescorla:


As you may or may not have heard, this year's CRYPTO conference
has been very interesting:

* 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^51 operations the brute force attack
would take about 2^80).

* 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.

* 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.

What does this mean for us? 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'). 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. Currently this is possible for MD5 but we have to consider the possibility that it will be eventually possible for SHA-1.

USES OF HASH FUNCTIONS

We use hash algorithms in a bunch of different contexts. At minimum:

1. Digital signatures (you sign the hash of a message).
(a) On messages (e.g. S/MIME).
(b) On certificates.
(c) In authentication primitives (e.g., SSH)
2. As MAC functions (e.g. HMAC)
3. As authentication functions (e.g. CRAM-MD5)
4. 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" [0]

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).

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 worry a bit about CRAM-MD5 and HTTP Digest. They're not as well
designed as HMAC and you might potentially be able to compromise them to mount some kind of active cut-and-paste attack, though I don't have one in my pocket.

The key generation PRFs should be safe.



Here is a link of the preprint of Wang et al. Those breakthroughs lead NIST to deliver the following comments:



The current Federal Information Processing Standard SHA-1 algorithm, which has been in effect since it replaced SHA-0 in 1994, was also analyzed, and a weakened variant was broken, but the full SHA-1 function was not broken and no collisions were found in SHA-1. The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010. SHA-1 and the larger hash functions are specified in FIPS 180-2. For planning purposes by Federal agencies and others, note also that the use of other cryptographic algorithms of similar strength to SHA-1 will also be phased out in 2010.”