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 [EMAIL PROTECTED]
