[17125] in cryptography@c2.net mail archive
Propping up SHA-1 (or MD5)
daemon@ATHENA.MIT.EDU (David Wagner)
Fri Mar 25 09:46:30 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: David Wagner <daw@cs.berkeley.edu>
To: cryptography@metzdowd.com
Date: Mon, 21 Mar 2005 11:26:59 -0800 (PST)
Reply-To: daw-usenet@taverner.CS.Berkeley.EDU (David Wagner)
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@metzdowd.com
