Collision Attacks on AES-based MAC: Alpha-MAC

A. Biryukov, Andrey Bogdanov, D. Khovratovich, Timo Kasper

Cryptographic Hardware and Embedded Systems - CHES 2007, 9. International Workshop, Vienna, Austria, Proceedings. LNCS, Springer-Verlag, September 10 - 13, 2007.


Message Authentication Code construction Alred and its AES-based instance Alpha-MAC were introduced by Daemen and Rijmen in 2005. We show that under certain assumptions about its implementation (namely that keyed parts are perfectly protected against side-channel attacks but bulk hashing rounds are not) one can e?ciently attack this function. We propose a side-channel collision attack on this MAC recovering its internal state just after 29 measurements in the known-message scenario which is to be compared to 40 measurements required by collision attacks on AES in the chosen-plaintext scenario. Having recovered the internal state, we mount a selective forgery attack using new 4 to 1 round collisions working with negligible memory and time complexity

[pdf] [Bibtex]