On the security of iterated message authentication codes

The security of iterated message authentication code (MAC) algorithms is co nsidered, and in particular, these constructed from unkeyed hash functions. A new MAC forgery attack applicable to all deterministic iterated MAC algo rithms is presented, which requires on the order of 2(n/2) known text-MAC p airs for algorithms with n bits of internal memory, as compared to the best previous general attack which required exhaustive key search. A related ke y-recovery attack is also given which applies to a large class of MAC algor ithms including a strengthened version of CBC-MAC found in ANSI X9.19 and I SO/IEC 9797, and envelope MAC techniques such as "keyed MD5." The security of several related existing MAC's based directly on unkeyed hash functions, including the secret prefix and secret suffix methods, is also examined.