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.