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
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
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”
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"
but that was still not enough. This Crypto, the paper "Short Chosen- Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate"
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


The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to

Reply via email to