A Simple Power Attack on a Randomized Addition-Subtraction Chains Method for Elliptic Curve Cryptosystems

We show that a randomized addition-subtraction chains countermeasure against side channel attacks is vulnerable to an SPA attack, which is a kind of side channel attack, under distinguishability between addition and doubling. The side channel attack takes advantage of information leaked during execution of a cryptographic procedure. The randomized addition-subtraction chains countermeasure was proposed by Oswald-Aigner, and is based on a random decision inserted into computations. However, the question of its immunity to side channel attacks is still controversial. The randomized addition-subtraction chains countermeasure has security flaw in timing attacks, another kind of side channel attack. We have implemented the proposed attack algorithm, whose input is a set of AD sequences, which consist of the characters "A" and "D" to indicate addition and doubling, respectively. Our program has clarified the effectiveness of the attack. The attack algorithm could actually detect secret scalars for given AD sequences. The average time to detect a 160-bit scalar was about 6 milliseconds, and only 30 AD sequences were enough to detect such a scalar. Compared with other countermeasures against side channel attacks, the randomized addition-subtraction chains countermeasure is much slower.