[saag] Propping up SHA-1 (or MD5)

[Ben Laurie]

Nicolas Williams wrote:
> On Mon, Mar 21, 2005 at 11:56:44AM +0000, Ben Laurie wrote:
> 
>>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)
> 
> 
> Eric proposed sending Random, Signature(H(Random || M)) and I then
> proposed sending Random || Signature(H(Random || M)) to avoid having to
> add a slot in existing protocols for Random.
> 
> Another alternative: send Random-Key || Signature(HMAC(H(), Random-Key, M).
> 
> 
>>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).
> 
> 
> This proposal is specific to the use of hashes in signatures.
> 
> 
>>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.
> 
> 
> Yes.
> 
> 
>>A third is that the length of the hash is changed, which could break 
>>existing protocols.
> 
> 
> Tie this to new algorithm OIDs and this problem goes away.  You still
> have to figure out how to deploy new software.
> 
> 
>>Musing on these points, I wondered about the construction:
>>
>>H'(x)=H(H(x) || H(H(x) || x))
> 
> 
> Note that this is not on-line.
> 
> 
>>which doesn't allow an attacker any choice, doesn't change APIs and 
>>doesn't change the length of the hash. Does this have any merit? Note 
>>that this is essentially an HMAC where the key is H(x). I omitted the 
>>padding because it seems to me that this actually makes HMAC weaker 
>>against the current attacks.
> 
> 
> Yes.
> 
> Now that we know that the attack is a differential cryptanalysis where
> the attacker has to control the first pair of blocks of the original
> message anything that makes it hard for the attacker to do this helps.
> 
> H'(x) = H(H(x))) might do that trick, and on-line, but surely there's
> problems with that too (IANAC).

This construction cannot solve the problem since H(x)=H(x') => 
H(H(x))=H(H(x')).

> Note that the attack implies that there exist weak messages, and Wang
> et. al. explicitly mention this in the paper on breaking MD4, and they
> mention the use of weak messages in second pre-image computation -- if a
> given message begins with a weak block pair then you can construct
> second pre-images.  It'd be nice to know what the weak message
> distribution is for MD5 and SHA-1...

Wouldn't it?


-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com