To Hash or Not to Hash
Again? (In)differentiability Results for H^2 and HMAC
Yevgeniy Dodis (NYU)
Thomas Ristenpart (University of Wisconsin-Madison)
John
Steinberger (
Stefano
Tessaro (MIT)
Abstract:
We show that the second iterate $H^2(M) = H(H(M))$
of a random oracle $H$ cannot achieve strong security in the sense of indifferentiability from a random oracle. We do so by
proving that indifferentiability for $H^2$ holds
only with poor concrete security by providing a lower bound (via an attack)
and a matching upper bound (via a proof requiring new techniques) on the
complexity of any successful simulator. We then investigate HMAC when it is
used as a general-purpose hash function with arbitrary keys (and not as a MAC
or PRF with uniform, secret keys). We uncover that HMAC's
handling of keys gives rise to two types of weak key pairs. The first allows
trivial attacks against its indifferentiability;
the second gives rise to structural issues similar to that which ruled out
strong indifferentiability bounds in the case
of~$H^2$. However, such weak key pairs do not arise, as far as we know, in any
deployed applications of HMAC. For example, using keys of any fixed length
shorter than $d-1$, where $d$ is the block length in bits of the underlying
hash function, completely avoids weak key pairs. We therefore conclude with a
positive result: a proof that HMAC is indifferentiable
from a RO (with standard, good bounds) when applications use keys of a fixed
length less than $d-1$.