Cryptology ePrint Archive: Report 2011/095

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

Orr Dunkelman and 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.

Category / Keywords: secret-key cryptography / ALRED, Alpha-MAC, Pelican

Date: received 24 Feb 2011, last revised 26 May 2011

Contact author: orr dunkelman at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20110526:130054 (All versions of this report)

Short URL: ia.cr/2011/095

Discussion forum: Show discussion | Start new discussion