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.