PDA

View Full Version : MD4/MD5/SHA-0 Dead


halvar
August 19th, 2004, 01:50
Hey all,


at the crypto rump session, a few chinese published collision-breaks
for MD4/MD5/HAVAL. This might be interesting for some of us.
They didn't explain their methodology, so we'll have to figure it out
ourselves. I'll read through it and try to understand what's going on.
(don't expect another post until september
Anyone else tackling it ?

CHeers,
Halvar
www.sabre-security.com

JMI
August 19th, 2004, 02:05
Here is another discussion about this subject:

http://www.exetools.com/forum/showthread.php?t=5032

Regards,

dELTA
August 19th, 2004, 08:41
Hi Halvar, thanks for the info (and nice to see you around here btw, I hope you stick around ).

Here are some more links regarding this matter:

SHA-1 Break Rumored
http://www.freedom-to-tinker.com/archives/000661.html

The effect of a break in SHA-1
Almost a collision in MD5
http://www.rtfm.com/movabletype/archives/2004_08.html

Technical report by the Chinese guys themselves:
http://eprint.iacr.org/2004/199.pdf

(the latter two links were also mentioned in the thread JMI referred to)


And some more info from Eric Rescorla:

Quote:

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.

-Ekr


[0] 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.

mike
August 20th, 2004, 03:02
When the details come out I'll have a look and explain how it works.

halvar
August 20th, 2004, 06:53
Historically speaking, the details might not come out (see Dobbertin's mid-
90's MD5 attack :-)

I looked a bit at the MD4 collision (mainly coz I know MD4 better than MD5)
and a certain similarity to Dobbertin's attack is visible. I only had about one
hour, so here is what I have so far (apologies if it is sparse, figuring out what
the attack does just from the two hashes is hard)
The attack consists of changing block X1, X2 and X12 of the hashed
data.

The choice of block X12 is not surprising:
It is used in step 12, step 19, and step 35.
This means that the distance over which a change in X12 can propagate
is 35-12 = 23 steps, which is minimal amongst all the blocks. Further-
more the distance between step 12 and step 19 is minimal amongst all
blocks used in the first two rounds.
Dobbertin's attack focused on changing only X12 for these reasons.

What is immediately evident is that two out of three changed blocks
are always used in adjancent steps:
Block X1 Block X2 Block X12

Round 1: 1 2 12
Round 2: 20 24 19
Round 3: 40 36 35

This means we have the following pattern:
X1, X2 get used
(...)
X12 gets used
(...)
X12, X1 gets used
(...)
X2 gets used
(...)
X12, X2 gets used
(...)
X1 gets used

After the last use of X1, all introduced delta's have cancelled out.
The occurence of "pairs" and then a single modified block in each
round looks interesting.

Cheers,
Halvar