Paper 2013/438

Clustering Algorithms for Non-Profiled Single-Execution Attacks on Exponentiations

Johann Heyszl, Andreas Ibing, Stefan Mangard, Fabrizio De Santis, and Georg Sigl

Abstract

Most implementations of public key cryptography employ exponentiation algorithms. Side-channel attacks on secret exponents are typically bound to the leakage of single executions due to cryptographic protocols or side-channel countermeasures such as blinding. We propose for the first time, to use a well-established class of algorithms, i.e. unsupervised cluster classification algorithms such as the k-means algorithm to attack cryptographic exponentiations and recover secret exponents without any prior profiling, manual tuning or leakage models. Not requiring profiling is of significant advantage to attackers, as are well-established algorithms. The proposed non-profiled single-execution attack is able to exploit any available single-execution leakage and provides a straight-forward option to combine simultaneous measurements to increase the available leakage. We present empirical results from attacking an FPGA-based elliptic curve scalar multiplication using the k-means clustering algorithm and successfully exploit location-based leakage from high-resolution electromagnetic field measurements to achieve a low remaining brute-force complexity of the secret exponent. A simulated multi-channel measurement even enables an error-free recovery of the exponent.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. CARDIS 2013, Springer. The final publication is available at link.springer.com
Keywords
Exponentiationside-channel attacknon-profiledsingle- executionunsupervised clusteringsimultaneous measurementsEM
Contact author(s)
johann heyszl @ aisec fraunhofer de
History
2014-01-17: last of 2 revisions
2013-07-18: received
See all versions
Short URL
https://ia.cr/2013/438
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/438,
      author = {Johann Heyszl and Andreas Ibing and Stefan Mangard and Fabrizio De Santis and Georg Sigl},
      title = {Clustering Algorithms for Non-Profiled Single-Execution Attacks on Exponentiations},
      howpublished = {Cryptology ePrint Archive, Paper 2013/438},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/438}},
      url = {https://eprint.iacr.org/2013/438}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.