Improved Side-Channel Collision Attacks on AES

Andrey Bogdanov

The 14th Annual Workshop on Selected Areas in Cryptography (SAC 2007), Ottawa, Ontario, Canada, August 16-17, 2007.


Side-channel collision attacks were proposed in [1] and applied to AES in [2]. These are based on detecting collisions in certain positions of the internal state after the ?rst AES round for di?erent executions of the algorithm. The attack needs about 40 measurements and 512 MB precomputed values as well as requires the chosen-plaintext possibility.

In this paper we show how to mount a collision attack on AES using only 6 measurements and about 2 37.15 o?ine computational steps working with a probability of about 0.85. Another attack uses only 7 measurements and ?nds the full encryption key with an o?ine complexity of about 2 34.74 with a probability of 0.99. All our attacks require a negligible amount of memory only and work in the known-plaintext model. This becomes possible by considering collisions in the S-box layers both for di?erent AES executions and within the same AES run. All the attacks work under the assumption that one-byte collisions are detectable.

[pdf] [Bibtex] [Talk Slides]

tags: AES, collision attacks, connected components, generalized collisions, random graphs, side-channel attacks