Improved Generic Attacks Against Hash-Based MACs and HAIFA

Abstract : The security of HMAC (and more general hash-based MACs) against state-recovery and universal forgery attacks was shown to be suboptimal, following a series of results by Leurent et al. and Peyrin et al. These results have shown that such powerful attacks require significantly less than 2 computations, contradicting the common belief (where denotes the internal state size). In this work, we revisit and extend these results, with a focus on concrete hash functions that limit the message length, and apply 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^4l/5. Then, we describe improved tradeoffs between the message length and the complexity of a state-recovery attack on HMAC with a Merkle-Damgård hash function. Consequently, we obtain improved attacks on several HMAC constructions used in practice, in which the hash functions limits 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. Despite their theoretical interest, our attacks do not seem to threaten the practical security of the analyzed concrete HMAC constructions.
Document type :
Journal articles
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01407953
Contributor : Gaëtan Leurent <>
Submitted on : Friday, December 2, 2016 - 5:49:11 PM
Last modification on : Tuesday, July 23, 2019 - 1:16:03 AM
Long-term archiving on: Tuesday, March 21, 2017 - 12:03:44 PM

File

HMAC-haifa.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Itai Dinur, Gaëtan Leurent. Improved Generic Attacks Against Hash-Based MACs and HAIFA. Algorithmica, Springer Verlag, 2017, Special Issue: Algorithmic Tools in Cryptography, 79 (4), pp.1161--1195. ⟨10.1007/s00453-016-0236-6⟩. ⟨hal-01407953⟩

Share

Metrics

Record views

261

Files downloads

440