Generic State-Recovery and Forgery Attacks on ChopMD-MAC and on NMAC/HMAC

This paper presents new attacks on message authentication codes (MACs). Our attacks are generic and applicable to (secret-prefix) ChopMD-MAC and to NMAC/HMAC, all of which are based on a Merkle-Damgård hash function. We show that an internal state value of these MACs can be recovered with time/queries less than

O

(2

n

)—roughly, with an

O

(2

n

/

n

) complexity, where ChopMD has 2

n

-bit state and NMAC/HMAC

n

-bit. We also show that state-recovery can be extended to MAC-security compromise, such as almost universal forgeries and distinguishing-H attacks. While our results remain to be of theoretical interest due to the high attack complexity, they lead to profound consequences. Namely, our analyses provide us with

proper

understanding of these MAC constructions, for in the literature the complexity has been implicitly and explicitly assumed to be

O

(2

n

). Since the complexity is very close to 2

n

, we make a precise calculation of attack complexities and of success probabilities in order to show that the total complexity is indeed less than 2

n

. Moreover, we perform an experiment by computer simulation to demonstrate that our calculation is correct.