Paper 2011/095

ALRED Blues: New Attacks on AES-Based MAC's

Orr Dunkelman, Nathan Keller, and Adi Shamir


The ALRED family of Message Authentication Codes (MAC's) is based on three principles: Using a keyless block cipher in CBC mode to process the message, choosing AES-128 as this cipher, and reducing the effective number of rounds to 4 in order to speed up the processing. In this paper we show that each one of these principles creates significant weaknesses. More specifically, we show that any ALRED-type MAC which uses a keyless block cipher is vulnerable to new time/memory tradeoff attacks which are faster than generic tradeoff attacks on one-way functions. We then use the special properties of keyless AES to attack any number of rounds (4, 10, or a million) by forging the MAC of essentially any desired message in negligible time and space after a one-time preprocessing stage requiring 2^{96} time and negligible space. For the recommended 4-round version we show how to do the same using an improved preprocessing stage with a semi-practical time complexity of 2^{65}, which is the best one can hope for in such MAC constructions. Finally, we show that even if we replace the 4-round keyless AES by a 5-round or a 6-round version with additional secret round keys we can still compute such MAC's much faster than via exhaustive search.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
orr dunkelman @ weizmann ac il
2011-05-26: last of 2 revisions
2011-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Orr Dunkelman and Nathan Keller and Adi Shamir},
      title = {ALRED Blues: New Attacks on AES-Based MAC's},
      howpublished = {Cryptology ePrint Archive, Paper 2011/095},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.