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 majord...@metzdowd.com
