### 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.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2014
Keywords
Hash functionsMACHMACMerkle-DamgårdHAIFAstate-recovery attackuniversal forgery attackGostStreebogSHA family.
Contact author(s)
gaetan leurent @ normalesup org
History
2014-06-14: revised
See all versions
Short URL
https://ia.cr/2014/441

CC BY

BibTeX

@misc{cryptoeprint:2014/441,
author = {Itai Dinur and Gaëtan Leurent},
title = {Improved Generic Attacks Against Hash-based MACs and HAIFA},
howpublished = {Cryptology ePrint Archive, Paper 2014/441},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/441}},
url = {https://eprint.iacr.org/2014/441}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.