[Openswan dev] [saag] Another bad day at the hash function factory

Thu Feb 17 10:59:07 CET 2005

-----BEGIN PGP SIGNED MESSAGE-----

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

ESP and AH with MD5 and SHA1 authentication are *SAFE*.
IKE itself is safe.

  The only people to be *slightly* concerned are those using X.509 CA
  authenticated policy with predicable serial numbers, and those using
  DNSSEC. 

  2^69 is a LOT of work.

  If you are using PSK, or any pre-exchanged rsa/dsa key, including:
     raw-rsa, pgp, X.509
  where the keys are already in a "local" database (disk, LDAP, etc.)
  then you have little worries.

  (Well, if you are using PSK, realize that few PSK have anywhere near
  2^69 of work.
  And if you are using Group-PSK with xauth, then there are already
  crack tools out there. SHA1/MD5 is the least of your worries)

To: saag at mit.edu
X-Mailer: MH-E 7.4.3; nmh 1.0.4; XEmacs 21.4 (patch 15)
Date: Thu, 17 Feb 2005 07:25:20 -0800
From: Eric Rescorla <ekr at rtfm.com>
Subject: [saag] Another bad day at the hash function factory

According to Bruce Schneier, Wang, Yin, and Yu have made some
very substantial progress in attacking SHA-1.

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

The headline claim is the ability to find a collision in
SHA-1 in 2^69 operations. Here's a somewhat revised version
of my post after the MD5 attacks last year.

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. 

This attack is especially difficult to mount at the current
security level of SHA-1 because you have to know the contents
of the certificate at the time you start generating the colliding
pair. Because that process takes 2^69 operations, you're
probably talking days to weeks and predicting the exact
next serial number over that time span is not going to be easy.
If VeriSign and other CAs add just a very small bit of randomness
to their certs, they should be able to defend against it.

Remember, also, that there are other ways to get false certs
if you're willing to expend the amount of money represented
by 2^69 operations.

WHAT'S SAFE?
First, anything that's already been signed should be 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.

When this happened to MD5, I worried a bit about CRAM-MD5 and HTTP Digest.
They're not as well designed as HMAC. I've done a little thinking about how
to attack them and not come up with anything, but there's no guarantee.
But again, you'd need to expend a truly enormous amount of CPU power.

The key generation PRFs should be safe.

NEXT STEPS
This isn't a catastrophe, but we need to start planning for the future.
(warning, slightly heavy sledding ahead).

The bad news is that there is no standard function that is guaranteed
to be more secure. In particular, we can't really be confident that
SHA-256 is going to be stronger. 

Here are a few alternatives:
Randomized hashing: The whole reason why this attack works is that
the attacker knows the exact message you're going to hash. If you
prefix the message with a random value, this effectively defeats
the attack. So, when you sign a message you would sign 
H(random || message) instead of H(message). In particular, 
CAs should immediately start using unpredictable serial numbers. [1]
Note, however, that this simple variant only works against the
attack where the relying party generates the colliding pairs.
If the attesting party does then they can shoose whatever
randomness they want. However, a variant in which the parties
jointly choose the random seed does work.

A non-MDx-based hash function: All of the major standard hash functions
ultimately derive from MD4. It's possible to design hash functions
based on block ciphers (see http://dimacs.rutgers.edu/Workshops/Practice/slides/shrimpton.ppt) for an overview. Unfortunately, as I understand it
you can't prove security for these constructions in a realistic
model of the underlying algorithm. However, there's some hope
that you would have to make a pretty serious dent in that block
cipher in order to break the hash.

Strangely enough, it's actually easier to specify a new hash function
than it is to move to randomized hashing. At the end of the day,
we'll probably want to do both because randomized hashing provides
protection against this kind of attack in general, regardless of
the status of the hash function.

Here's one non-alternative:
Concatenation: The obvious thing to do is to take a SHA-1 and an
MD5 and concatenate them on the theory that this makes things
harder. Unfortunately, Joux's CRYPTO 2004 paper on multicollisions
suggests that this doesn't make things anywhere near as much harder
as you would expect.

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

[1] It's easy to make these monotonically increasing. Just use
Counter || random

_______________________________________________
saag mailing list
saag at mit.edu
https://jis.mit.edu/mailman/listinfo/saag

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
Comment: Finger me for keys

iQCVAwUBQhS/SYqHRg3pndX9AQF0gwP8CSgQvubxXYOYFO4KIrnn33OFph4ySahn
cWYIH0WfQZ2u0++6h+hz319LlynSl+hZi3BEZoY3O5eqlNft07BEWw6AN/MdMVm2
U1+HTip5+JWIE3AOygL8tJzuZdxh1/zfaxj5Im6HyanK99jrF6e6IwaZ5FZw+bDm
wykWpKbu9Jk=
=2B4/
-----END PGP SIGNATURE-----