Generic Related-Key Attacks for HMAC

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.