Cryptology ePrint Archive: Report 2014/441

Improved Generic Attacks Against Hash-based MACs and HAIFA

Itai Dinur and Gaëtan Leurent

Abstract: The security of HMAC (and more general hash-based MACs) against state-recovery and universal forgery attacks was very recently shown to be suboptimal, following a series of surprising results by Leurent \emph{et al.} and Peyrin \emph{et al.}. These results have shown that such powerful attacks require much less than $2^{\ell}$ computations, contradicting the common belief (where $\ell$ denotes the internal state size). In this work, we revisit and extend these results, with a focus on properties of concrete hash functions such as a limited message length, and special iteration modes.

We begin by devising the first state-recovery attack on HMAC with a HAIFA hash function (using a block counter in every compression function call), with complexity $2^{4\ell/5}$. Then, we describe improved trade-offs between the message length and the complexity of a state-recovery attack on HMAC. Consequently, we obtain improved attacks on several HMAC constructions used in practice, in which the hash functions limit the maximal message length (e.g., SHA-1 and SHA-2). Finally, we present the first universal forgery attacks, which can be applied with short message queries to the MAC oracle. In particular, we devise the first universal forgery attacks applicable to SHA-1 and SHA-2.

Category / Keywords: secret-key cryptography / Hash functions, MAC, HMAC, Merkle-Damgård, HAIFA, state-recovery attack, universal forgery attack, Gost, Streebog, SHA family.

Original Publication (with major differences): IACR-CRYPTO-2014

Date: received 10 Jun 2014, last revised 14 Jun 2014

Contact author: gaetan leurent at normalesup org

Available format(s): PDF | BibTeX Citation

Version: 20140614:180204 (All versions of this report)

Short URL: ia.cr/2014/441

Discussion forum: Show discussion | Start new discussion