International Association
for Cryptologic Research

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. 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.