Algebraic methods in side-channel collision attacks and practical collision detection

Andrey Bogdanov, Ilya Kizhvatov, Andrey Pyshkin

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


This paper presents algebraic collision attacks, a new powerful cryptanalytic method based on side-channel leakage which allows for low measurement counts needed for a successful key recovery in case of AES. As opposed to many other side-channel attacks, these techniques are essentially based on the internal structure of the attacked cryptographic algorithm, namely, on the algebraic properties of AES. Moreover, we derived the probability distributions of Euclidean distance for collisions and non-collisions. On this basis, a statistical framework for finding the instances of side-channel traces leaking most key information in collision attacks is proposed. Additionally to these theoretical findings, the paper also contains a practical evaluation of these side-channel collision attacks for a real-world microcontroller platform similar to many smart card ICs. To our best knowledge, this is the first real-world study of collision attacks based on generalized internal collisions. We also combined our methods with ternary voting [1] which is a recent multiple-differential collision detection technique using profiling, where neither plaintexts, ciphertexts nor keys have to be known in the profiling stage. © 2008 Springer Berlin Heidelberg.
Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2008. Proceedings
Publication date2008
ISBN (Print)978-3-540-89753-8
ISBN (Electronic)978-3-540-89754-5
Publication statusPublished - 2008
Externally publishedYes
Event9th International Conference on Cryptology in India - Kharagpur, India
Duration: 14 Dec 200817 Dec 2008
Conference number: 9


Conference9th International Conference on Cryptology in India
Internet address
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Algebraic methods in side-channel collision attacks and practical collision detection'. Together they form a unique fingerprint.

Cite this