Cryptology ePrint Archive: Report 2012/485

Exploiting Collisions in Addition Chain-based Exponentiation Algorithms Using a Single Trace

Neil Hanley and HeeSeok Kim and Michael Tunstall

Abstract: Public key cryptographic algorithms are typically based on group exponentiation algorithms where the exponent is private. A collision attack is typically where an adversary seeks to determine whether two operations in an exponentiation have the same input. In this paper we extend this to an adversary who seeks to determine whether the output of one operation is used as the input to another. We describe implementations of these attacks to a 192-bit scalar multiplication over an elliptic curve that only require a single power consumption trace to succeed with a certain probability. All the implementations of similar attacks described in the literature require an adversary to generate a mean trace from numerous traces to succeed. Moreover, our attacks do not require any knowledge of the input to the exponentiation algorithm. These attacks would therefore be applicable to EC-DSA, where an exponent is ephemeral, or to implementations where an exponent is blinded. Moreover, we prove that collision attacks are applicable to all addition chain-based exponentiation algorithms. This means that a side-channel resistant implementation of a group exponentiation algorithm will require countermeasures that introduce enough noise such that an attack is not practical.

Category / Keywords: Side channel analysis, exponentiation, smart card security

Date: received 22 Aug 2012, last revised 14 Aug 2013

Contact author: tunstall at cs bris ac uk

Available format(s): PDF | BibTeX Citation

Note: Updated results.

Version: 20130814:163359 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]