On hash breaks, was Re: First quantum crypto bank transfer

Jerrold Leichter jerrold.leichter at smarts.com
Tue Aug 24 07:18:14 EDT 2004

| > Alternatively, how anyone can have absolute confidence in conventional
| > crypto
| > in a week when a surprise attack appears against a widely-fielded
| > primitive
| > like MD5 is beyond me.  Is our certainty about AES's security really any
| > better today than was our certainty about RIPEM - or even SHA-0 - was
| > three
| > weeks ago?
| > -- Jerry
| Actually for years the cryptography community has been saying "retire MD5,"
...because it's been seen as giving too short a hash, and because of a minor
weakness - widely described as "certificational" - in the compression function
that no one ever showed lead to an attack.  (While the details of the current
attack aren't yet completely clear, the fact that it worked on so many
functions strongly indicates that the particular weakness in the MD5
compression function has nothing to do with it.)

The advice may have been prudent, but it doesn't rise to the level of a theory
for distinguishing good from bad hash functions.

| SHA-0 has been required to be replaced by SHA-1 for some time,
because the NSA said so.  It turns out they were ahead of public crypto by a
couple of years.  I will grant you that this is indirect evidence that NSA
has no attacks on AES, since this is now the second time that they've
strengthened a proposed primitive against which no publically-known attacks
existed.  It tells us little about how strong AES actually is - and absolutely
nothing about any other system out there, since NSA has no reason to comment
on those and every reason not to.

|                                                               the RIPEM
| series is functionally-speaking unused
...but not because anyone thought there was a weakness.  MD5 happened to be
widely used, SHA-1 had standards pushing it; little room was left for another

|                                        and represented the only real
| surprise. Except for RIPEM there were known to be reasons for this, MD5 was
| known to be flawed, SHA-0 was replaced because it was flawed (although
| knowledge of the nature of the flaw was hidden). Even with RIPEM (and SHA-1
| for the same reason) I have plans in place (and have had for some time) the
| move away from 160-bit hashes to larger ones, so the attack on RIPEM had
| little effect on me and my clients, even a full attack on SHA-1 would have
| little effect on the clients that actually listen (they all have backup
| plans that involve the rest of the SHA series and at the very least
| Whirlpool).
Moving to a larger hash function with no underlying theory isn't very far from
the "million-bit key" algorithms you see all over the place.  Bigger probably
can't be worse, but is it really better?

| So basically I encourage my clients to maintain good business practices
| which means that they don't need to have belief in the long term security of
| AES, or SHA-1, or RSA, or ......... This is just good business, and it is a
| process that evolved to deal with similar circumstances.
Real good business practice has to make judgements about possible risks and
trade them off against potential costs.  I quite agree that your advice is
sound.  But that doesn't change the facts:  Our theoretical bases for security
are much weaker than we sometimes let on.  We can still be surprised.

Suppose a year ago I offered the following bet:  At the next Crypto, all but
one of the widely-discussed hash functions will be shown to be fundamentally
flawed.  What odds would you have given me?  What odds would you have given me
on the following bet:  At the next Crypto, an attack against AES that is
substantially better than brute force will be published?  If the odds were
significantly different, how would you have justified the difference?

Let's update the question to today:  Replace "widely-discussed hash functions"
with "SHA-1 and the related family".  Keep the AES bet intact.  But let's got
out 5 years.  Now what odds do you give me?  Why?

							-- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list