Paper 2012/485

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

Neil Hanley, HeeSeok Kim, and Michael Tunstall


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 high probability. Moreover, our attacks do not require any knowledge of the input to the exponentiation algorithm. These attacks would therefore be applicable to algorithms such as EC-DSA, where an exponent is ephemeral, or to implementations where an exponent is blinded. Moreover, we define attacks against exponentiation algorithms that are considered to be resistant to collision attacks and prove that collision attacks are applicable to all addition chain-based exponentiation algorithms. Hence, we demonstrate 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.

Note: Updated results.

Available format(s)
Publication info
Preprint. MINOR revision.
Side channel analysisexponentiationsmart card security
Contact author(s)
mike tunstall @ yahoo co uk
2013-12-19: last of 5 revisions
2012-08-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Neil Hanley and HeeSeok Kim and Michael Tunstall},
      title = {Exploiting Collisions in Addition Chain-based Exponentiation Algorithms Using a Single Trace},
      howpublished = {Cryptology ePrint Archive, Paper 2012/485},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.