Certainty

[james hughes]

Caution, the following contains a rant.

On Aug 19, 2009, at 3:28 PM, Paul Hoffman wrote:
> I understand that "creaking" is not a technical cryptography term,  
> but "certainly" is. When do we become "certain" that devastating  
> attacks on one feature of hash functions (collision resistance) have  
> any effect at all on even weak attacks on a different feature  
> (either first or second preimages)?
>
> This is a serious question. Has anyone seen any research that took  
> some of the excellent research on collision resistance and used it  
> directly for preimage attacks, even with greatly reduced rounds?

This is being done. What Perry said.

> The longer that MD5 goes without any hint of preimage attacks, the  
> less "certain" I am that collision attacks are even related to  
> preimage attacks.

There was an invited talk at Crypto about "Alice and Bob Go To  
Washington: A Cryptographic Theory of Politics and Policy". This was  
interesting in that it explained that facts are not what politicians  
want
	http://www.iacr.org/conferences/crypto2009/acceptedpapers.html#crypto06
and that politicians form blocks to create shared power.

It seems that your comment about "certainty" is not a technical one,  
but a political one. The block of people that have implemented MD-5  
believe that this algorithm is good enough and that the facts that the  
hash function contains no science of how it works, can not be proven  
to be resistant to pre-image, nor even reduced to any known hard  
problem, are not "certain". Maybe this particular block just wants it  
to be secure? If MD-5 is secure to pre-image attacks, the  
cryptographic community does not know why. It seems that the only  
proof that can be accepted as "certainty" is an existence proof that  
the bad deed _has_ be done.

Maybe this is not really an MD-5 block, but an HMAC implementer's  
block. This block does have some results to hang their hats on. The  
paper "New Proofs for NMAC and HMAC: Security without Collision- 
Resistance" was publushed in 2006
	http://eprint.iacr.org/2006/043.pdf
that states that as long as the "compression function is a PRF" HMAC  
is secure. This is mostly because the algorithm is keyed. This places  
HMAC into the class of ciphers as PRF and out of the class of hash  
functions.

I find this "interesting". Cryptographers knew in 2004 that the wheels  
just came off MD-5, and it's future was going to be grim. The "common  
sense" was that a collision by itself was not relevant. Then there was  
the “Colliding X.509 Certificates”
	http://eprint.iacr.org/2005/067
and still the "common sense" was that it could still be used. So then  
there was "Chosen-Prefix Collisions for MD5 and Colliding X.509  
Certificates for Different Identities"
	http://www.win.tue.nl/hashclash/EC07v2.0.pdf
but that was still not enough. This Crypto, the paper "Short Chosen- 
Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate"
	http://www.iacr.org/conferences/crypto2009/acceptedpapers.html#crypto04
	https://documents.epfl.ch/users/l/le/lenstra/public/papers/Crypto09nonanom.pdf
seems to have put a nail in this issue, but not the issue of the  
"certainty" of pre-image attacks.

Some believe that the Best Paper award was given for the persistence  
that the authors showed to continue to spend time and effort on what  
the cryptographic community knows is an cart with no wheels on it to  
counter the "common sense" implementing block that do not believe it  
until they see it.

Effort placed on replacing MD-5 is more important now than taunting  
the cryptographers to prove that MD-5 pre-images are feasible when  
there is literally nothing proving that pre-images of MD-5 are  
difficult. (Again, this is for bare MD-5, not HMAC.)

> Of course, I still believe in hash algorithm agility: regardless of  
> how preimage attacks will be found, we need to be able to deal with  
> them immediately.

I am curious if you mean Immediately as in now, or immediately when a  
pre-image attack is found?

> --Paul Hoffman, Director
> --VPN Consortium

Jim

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