Paper 2007/477

Algebraic Side-Channel Collision Attacks on AES

Andrey Bogdanov and Andrey Pyshkin


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
AEScollision attacksside-channel attacksgeneralized collisionsGroebner basesalgebraic attacksF4 algorithm
Contact author(s)
abogdanov @ crypto ruhr-uni-bochum de
2007-12-28: received
Short URL
Creative Commons Attribution


      author = {Andrey Bogdanov and Andrey Pyshkin},
      title = {Algebraic Side-Channel Collision Attacks on AES},
      howpublished = {Cryptology ePrint Archive, Paper 2007/477},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.