[144760] in cryptography@c2.net mail archive
Re: Certainty
daemon@ATHENA.MIT.EDU (james hughes)
Fri Aug 21 17:10:44 2009
From: james hughes <hughejp@mac.com>
To: Cryptography List <cryptography@metzdowd.com>
In-reply-to: <p06240807c6b22bf61439@[10.20.30.158]>
Date: Wed, 19 Aug 2009 19:10:22 -0700
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, =20
> but "certainly" is. When do we become "certain" that devastating =20
> attacks on one feature of hash functions (collision resistance) have =20=
> any effect at all on even weak attacks on a different feature =20
> (either first or second preimages)?
>
> This is a serious question. Has anyone seen any research that took =20
> some of the excellent research on collision resistance and used it =20
> 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 =20
> less "certain" I am that collision attacks are even related to =20
> preimage attacks.
There was an invited talk at Crypto about "Alice and Bob Go To =20
Washington: A Cryptographic Theory of Politics and Policy". This was =20
interesting in that it explained that facts are not what politicians =20
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, =20
but a political one. The block of people that have implemented MD-5 =20
believe that this algorithm is good enough and that the facts that the =20=
hash function contains no science of how it works, can not be proven =20
to be resistant to pre-image, nor even reduced to any known hard =20
problem, are not "certain". Maybe this particular block just wants it =20=
to be secure? If MD-5 is secure to pre-image attacks, the =20
cryptographic community does not know why. It seems that the only =20
proof that can be accepted as "certainty" is an existence proof that =20
the bad deed _has_ be done.
Maybe this is not really an MD-5 block, but an HMAC implementer's =20
block. This block does have some results to hang their hats on. The =20
paper "New Proofs for NMAC and HMAC: Security without Collision-=20
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 =20
is secure. This is mostly because the algorithm is keyed. This places =20=
HMAC into the class of ciphers as PRF and out of the class of hash =20
functions.
I find this "interesting". Cryptographers knew in 2004 that the wheels =20=
just came off MD-5, and it's future was going to be grim. The "common =20=
sense" was that a collision by itself was not relevant. Then there was =20=
the =E2=80=9CColliding X.509 Certi=EF=AC=81cates=E2=80=9D
http://eprint.iacr.org/2005/067
and still the "common sense" was that it could still be used. So then =20=
there was "Chosen-Pre=EF=AC=81x Collisions for MD5 and Colliding X.509 =20=
Certi=EF=AC=81cates for Di=EF=AC=80erent Identities"
http://www.win.tue.nl/hashclash/EC07v2.0.pdf
but that was still not enough. This Crypto, the paper "Short Chosen-=20
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 =20
"certainty" of pre-image attacks.
Some believe that the Best Paper award was given for the persistence =20
that the authors showed to continue to spend time and effort on what =20
the cryptographic community knows is an cart with no wheels on it to =20
counter the "common sense" implementing block that do not believe it =20
until they see it.
Effort placed on replacing MD-5 is more important now than taunting =20
the cryptographers to prove that MD-5 pre-images are feasible when =20
there is literally nothing proving that pre-images of MD-5 are =20
difficult. (Again, this is for bare MD-5, not HMAC.)
> Of course, I still believe in hash algorithm agility: regardless of =20=
> how preimage attacks will be found, we need to be able to deal with =20=
> them immediately.
I am curious if you mean Immediately as in now, or immediately when a =20=
pre-image attack is found?
> --Paul Hoffman, Director
> --VPN Consortium
Jim
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
