Single-Trace Side-Channel Attacks on Scalar Multiplications with Precomputations

Single-trace side-channel attacks are a serious threat to elliptic curve cryptography in practice because they can break also cryptosystems where scalars are nonces (e.g., ECDSA). Previously it was believed that single-trace attacks can be avoided by using scalar multiplication algorithms with regular patterns of operations but recently we have learned that they can be broken with correlation tests to decide whether different operations share common operands. In this work, we extend these attacks to scalar multiplication algorithms with precomputations. We show that many algorithms are vulnerable to our attack which correlates measurements with precomputed values. We also show that successful attacks are possible even without knowledge of precomputed values by using clustering instead of correlations. We provide extensive evidence for the feasibility of the attacks with simulations and experiments with an 8-bit AVR. Finally, we discuss the effectiveness of certain countermeasures against our attacks.