Cryptology ePrint Archive: Report 2014/403

Generic Universal Forgery Attack on Iterative Hash-based MACs

Thomas Peyrin and Lei Wang

Abstract: In this article, we study the security of iterative hash-based MACs, such as HMAC or NMAC, with regards to universal forgery attacks. Leveraging recent advances in the analysis of functional graphs built from the iteration of HMAC or NMAC, we exhibit the very first generic universal forgery attack against hash-based MACs. In particular, our work implies that the universal forgery resistance of an n-bit output HMAC construction is not 2^n queries as long believed by the community. The techniques we introduce extend the previous functional graphs-based attacks that only took in account the cycle structure or the collision probability: we show that one can extract much more meaningful secret information by also analyzing the distance of a node from the cycle of its component in the functional graph.

Category / Keywords: secret-key cryptography / HMAC, NMAC, hash function, universal forgery

Original Publication (with minor differences): IACR-EUROCRYPT-2014

Date: received 31 May 2014, last revised 5 Jun 2014

Contact author: thomas peyrin at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140605:065015 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]