New Results on NMAC/HMAC when Instantiated with Popular Hash Functions

Message Authentication Code (MAC) algorithms can provide cryptograph- ically secure authentication services. One of the most popular algorithms in commercial applications is HMAC based on the hash functions MD5 or SHA-1. In the light of new collision search methods for members of the MD4 family including SHA-1, the security of HMAC based on these hash functions is reconsidered. We present a new method to recover both the inner-and the outer key used in HMAC when instantiated with a concrete hash function by observing text/MAC pairs. In ad- dition to collisions, also other non-random properties of the hash function are used in this new attack. Among the examples of the proposed method, the first theoretical full key recovery attack on NMAC-MD5 is presented. Other examples are distinguishing, forgery and partial or full key recovery attacks on NMAC/HMAC-SHA-1 with a re- duced number of steps (up to 62 out of 80). This information about the new, reduced security margin serves as an input to the selection of algorithms for authentication purposes.