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

[John Kelsey]

>From: Jerrold Leichter <jerrold.leichter at smarts.com>
>Sent: Aug 24, 2004 7:18 AM
>To: Joseph Ashwood <ashwood at msn.com>
>Cc: cryptography at metzdowd.com
>Subject: Re: On hash breaks, was Re: First quantum crypto bank transfer


[[Note: I've tried to sort out who wrote what, but something odd was
going on in the quoting of the messages, so I may have it all
wrong....]]

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

How about this: When someone finds any collision at all in your hash
compression function, even a pseudocollision or a free-start
collision, it's time to change hash functions.  This is true, even
when the alternatives are slower, and the existing attacks don't yet
turn into a full attack.  Also, when your collision resistance is
known to be vulnerable to brute-force collision attacks, you really
need to stop using it.  Even when the alternatives are slower, and you
think you can maybe get away with using MD5 here if the stars all line
up properly.

Now, for fielded hardware and (to some extent) software, you can try
to phase out the use of the broken primitive, if the attack isn't yet
leading to a practical fast collision-finding algorithm.  If MD5 had
started being phased out when the pseudocollision attack was found, or
even when the Dobbertin attack was found, it seems like we'd be in
better shape now.  

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

True.  But was anyone surprised at another attack on MD5, which had
already had two high-profile attacks on its compression function?  Was
anyone surprised at an attack on HAVAL?  

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

You would have lost the bet.  Where's the fundamental flaw in SHA1,
SHA256, SHA512, or RIPE-MD160?  Where's the fundamental flaw in
Whirlpool?  There may *be* such flaws in any or all of these hashes,
but they haven't been shown yet.  (Phil Hawkes' results on SHA256 look
interesting; it will be interesting to see if they lead anywhere, but
it sure doesn't look trivial to control those corrective patterns with
choices of message block differences.)  

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

Remember that we had the algebraic attacks, which claimed the ability
to break the whole AES, though the attacks apparently don't work as
claimed because of a miscounting of variables.  (It's certainly
possible that someone will find an algebraic attack on AES.)  

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

I don't know.  If you had to build something today to be secure, it
wouldn't be crazy to use SHA1, IMO.  But you just can't ever rule out
cryptanalytic advances of this kind.  I think the difference between
block ciphers and hash functions is that there's a much better
developed theory of block cipher design and analysis in the public
world than for hash function design and analysis.  This may be
changing, though.  And new attacks (algebraic attacks, the integral
attack that is so effective against reduced-round Rijndael versions)
are always coming up, even so.  

I think seriously trying to beat up on our algorithms, publishing
intermedaite results, etc., is the best we can do at our current state
of knowledge.  

>-- Jerry

--John Kelsey

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