Cryptology ePrint Archive: Report 2013/438

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

Johann Heyszl and Andreas Ibing and Stefan Mangard and 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 because of cryptographic protocols or side-channel countermeasures such as blinding. We propose a new class of algorithms, i.e. unsupervised cluster classification algorithms, to attack cryptographic exponentiations and recover secret exponents without any prior profiling or heuristic leakage models. Not requiring profiling is a significant advantage to attackers. In fact, 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 improve the signal-to-noise ratio of available leakage. We present empirical results from attacking an elliptic curve scalar multiplication and exploit location-based leakage from high-resolution electromagnetic field measurements without prior profiling. Individual measurements lead to a sufficiently low remaining brute-force complexity of the secret exponent. An errorless recovery of the exponent is achieved after a combination of few measurements.

Category / Keywords: public-key cryptography / Exponentiation, side-channel attack, non-profiled, single-execution, unsupervised clustering, simultaneous measurements, EM

Date: received 12 Jul 2013

Contact author: johann heyszl at aisec fraunhofer de

Available format(s): PDF | BibTeX Citation

Version: 20130718:185112 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]