Cryptology ePrint Archive: Report 2012/485

Exploiting Collisions in Addition Chain-based Exponentiation Algorithms

Neil Hanley and HeeSeok Kim and Michael Tunstall

Abstract: Public key cryptographic algorithms are typically based on group exponentiation algorithms, and many algorithms have been proposed in the literature based on addition chains. We describe attacks based on collisions of variables manipulated in group operations extending attacks described in the literature. These collisions are visible where one is able to acquire information through some suitable side channel that provides a trace during the computation of a group exponentiation algorithm. For example, through measuring the instantaneous power consumption or the electromagnetic emanations of a microprocessor. The advantage of our attacks over previous work is that the attacks can be applied to a single trace and do not require any knowledge of the input to the exponentiation algorithm. Moreover, we prove that our attacks are applicable to all addition chain-based exponentiation algorithms. This means that a side channel resistant implementation of a group exponentiation will require countermeasures that introduce enough noise that an attack is not practical.

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

Date: received 22 Aug 2012, last revised 1 Oct 2012

Contact author: tunstall at cs bris ac uk

Available formats: PDF | BibTeX Citation

Note: Some clarification of the target of our attacks

Version: 20121001:105044 (All versions of this report)

Discussion forum: Show discussion | Start new discussion