Summary: 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 G. Leurent et al. [Asiacrypt 2013, Lect. Notes Comput. Sci. 8270, 1–20 (2013; Zbl 1314.94083)] and T. Peyrin and L. Wang [Eurocrypt 2014, Lect. Notes Comput. Sci. 8441, 147–164 (2014; Zbl 1332.94077)]. 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.
For the entire collection see [Zbl 1292.94002].