Paper 2011/095

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

Orr Dunkelman, Nathan Keller, and Adi Shamir

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
ALREDAlpha-MACPelican
Contact author(s)
orr dunkelman @ weizmann ac il
History
2011-05-26: last of 2 revisions
2011-02-28: received
See all versions
Short URL
https://ia.cr/2011/095
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/095,
      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{https://eprint.iacr.org/2011/095}},
      url = {https://eprint.iacr.org/2011/095}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.