Cryptology ePrint Archive: Report 2007/477

Algebraic Side-Channel Collision Attacks on AES

Andrey Bogdanov and Andrey Pyshkin

Abstract: This paper presents a new powerful side-channel cryptanalytic method - algebraic collision attacks - representing an efficient class of power analysis being based on both the power consumption information leakage and specific structure of the attacked cryptographic algorithm. This can result in an extremely low measurement count needed for a key recovery.

The algebraic collision attacks are well applicable to AES, if one-byte collisions are detectable. For the recovery of the complete AES key, one needs 3 measurements with a probability of 0.42 and 4.24 PC hours post-processing, 4 measurements with a probability of 0.82 and several seconds of offline computations or 5 measurements with success probability close to 1 and several seconds of post-processing.

Category / Keywords: secret-key cryptography / AES, collision attacks, side-channel attacks, generalized collisions, Groebner bases, algebraic attacks, F4 algorithm

Date: received 20 Dec 2007

Contact author: abogdanov at crypto ruhr-uni-bochum de

Available formats: PDF | BibTeX Citation

Version: 20071228:012512 (All versions of this report)

Discussion forum: Show discussion | Start new discussion