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