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

Abstract

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
PublisherSpringer
Publication date2008
Pages251-265
ISBN (Print)978-3-540-89753-8
ISBN (Electronic)978-3-540-89754-5
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event9th International Conference on Cryptology in India - Kharagpur, India
Duration: 14 Dec 200817 Dec 2008
Conference number: 9
http://www.informatik.uni-trier.de/~ley/db/conf/indocrypt/indocrypt2008.html

Conference

Conference9th International Conference on Cryptology in India
Number9
CountryIndia
CityKharagpur
Period14/12/200817/12/2008
Internet address
SeriesLecture Notes in Computer Science
Volume5365
ISSN0302-9743

Cite this

Bogdanov, A., Kizhvatov, I., & Pyshkin, A. (2008). Algebraic methods in side-channel collision attacks and practical collision detection. In Progress in Cryptology - INDOCRYPT 2008. Proceedings (pp. 251-265). Springer. Lecture Notes in Computer Science, Vol.. 5365 https://doi.org/10.1007/978-3-540-89754-5_20