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.
Keywords Side-channel attacks - collision attacks - algebraic cryptanalysis - multiple-differential collision attacks - ternary voting - AES - DPA