Propping up SHA-1 (or MD5)

[Dan Kaminsky]

Ben,

    x can equal either test vector released by Wang, and H(x) will be
identical.  With H(x) identical, the rest of the HMAC stays identical too. 

    As a couple people pointed out, it's OK that HMAC is "vulnerable" to
the Wang attack, since in order to execute the attack the key is
required (and like AES, if the key is compromised, all bets are off). 
But you're not using HMAC as a MAC; you're using it to prop up a broken
hash. 

    Regarding the "Random" appendage, people don't seem to realize how
important syncronized initial states are to many hashing algorithms. 
One of the major uses of a hashing algorithm is to act as an
*exchangable* handle to data, in other words, you and I can both hash
our respective datasets and see if they're identical.  If we're each
using different initial states, that process fails utterly.

--Dan

P.S.  Your construction *will* work if you replace H(x) with H(x xor
ipad) and H(x xor opad), with ipad and opad as defined in the HMAC
spec.  (We can collide against either permutation of our block data, but
not both simultaneously.)  This does end up rather significantly
reducing throughput though.

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)
>
> 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).
>
> 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.
>
> A third is that the length of the hash is changed, which could break
> existing protocols.
>
> Musing on these points, I wondered about the construction:
>
> H'(x)=H(H(x) || H(H(x) || x))
>
> 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.
>
> Cheers,
>
> Ben.
>


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