Propping up SHA-1 (or MD5)
David Wagner
daw at cs.berkeley.edu
Mon Mar 21 14:26:59 EST 2005
Ben Laurie writes:
>It was suggested at the SAAG meeting at the Minneapolis IETF that a way
>to deal with weakness in hash functions was to create a new hash
>function from the old like so:
>
>H'(x)=Random || H(Random || x)
Yes. Suppose we use this for signing. The crucial part is to have
the *signer* choose the Random value when computing the signature.
This may be secure even if H fails to be collision-resistant, because
even if an attacker finds a collision for H, he doesn't know which
Random value the signer is going to use.
More generally, we could try to use any universal one-way hash function
(UOWHF). This concept is also known as target collision resistant (TCR).
It is natural to conjecture that H' is a UOWHF, i.e., is TCR, and this
may be true even if H is not collision-resistant. Of course, there is
no proof of this, and this conjecture is speculative, but it does weaken
the assumptions we are making about our hash.
I have been advocating this kind of construction ever since hearing about
the hash cryptanalysis results last August. Not everyone agrees with me,
and there is a lengthy discussion going on about this on the IRTF CFRG
working group.
http://www1.ietf.org/mail-archive/web/cfrg/current/threads.html
http://www1.ietf.org/mail-archive/web/cfrg/current/thrd2.html
http://www1.ietf.org/mail-archive/web/cfrg/current/thrd3.html
>However, this allows an attacker to play with Random (the advice I've
>seen is that if one is going to use an IV with a hash function, then one
>should transfer the IV with integrity checks to deny attackers this
>freedom).
No, not if you use it right. The way to use this is to have the signer
choose the value of Random, not anyone else. A signer can play with Random
and maybe find collisions M,M', but in this case the signer will be viewed
as having signed both M and M', so this doesn't help the signer at all.
>Another objection is that this construction changes the API at the
>sender end, which could lead to a great deal of complexity when the use
>of the hash API is deeply embedded.
Shouldn't be a big deal for signing. A much bigger deal is that this
changes the on-the-wire format.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list