Cryptology ePrint Archive: Report 2012/684

Generic Related-key Attacks for HMAC

Thomas Peyrin and Yu Sasaki and Lei Wang

Abstract: In this article we describe new generic distinguishing and forgery attacks in the related-key scenario (using only a single related-key) for the HMAC construction. When HMAC uses a k-bit key, outputs an n-bit MAC, and is instantiated with an l-bit inner iterative hash function processing m-bit message blocks where m=k, our distinguishing-R attack requires about 2^{n/2} queries which improves over the currently best known generic attack complexity 2^{l/2} as soon as l>n. This means that contrary to the general belief, using wide-pipe hash functions as internal primitive will not increase the overall security of HMAC in the related-key model when the key size is equal to the message block size. We also present generic related-key distinguishing-H, internal state recovery and forgery attacks. Our method is new and elegant, and uses a simple cycle-size detection criterion. The issue in the HMAC construction (not present in the NMAC construction) comes from the non-independence of the two inner hash layers and we provide a simple patch in order to avoid this generic attack. Our work finally shows that the choice of the opad and ipad constants value in HMAC is important.

Category / Keywords: secret-key cryptography / HMAC, hash function, distinguisher, forgery, related-key.

Publication Info: Extended version of the Asiacrypt 2012 article

Date: received 4 Dec 2012, last revised 17 Jul 2013

Contact author: thomas peyrin at gmail com

Available format(s): PDF | BibTeX Citation

Note: We noticed an independent work by Dodis et al., and interestingly these two papers complement each other.

Version: 20130718:043031 (All versions of this report)

Short URL: ia.cr/2012/684

Discussion forum: Show discussion | Start new discussion