Propping up SHA-1 (or MD5)

David Wagner daw at
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.

>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 

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

More information about the cryptography mailing list