Edwards Curve and BIG MAC Attack

Abstract In 2001, Walter introduced the BIG MAC attack on RSA systems. This hori- zontal collision attack exploits the detection of common operands between two multiplications. It is highly effective, as a single power consumption trace is suffi- cient to recover all the bits of the secret exponent. Initially, the BIG MAC attack was not applicable to cryptosystems based on elliptic curves. It was only in 2013 that Bauer et al. enhanced the attack and proposed a version adapted to ellip- tic curves. This new approach specifically targets the atomicity countermeasure and relies on identifying common operands between two multiplications within the addition and doubling algorithms for elliptic curve points. In 2016, Danger et al. further refined the attack by significantly improving its efficiency: instead of comparing only two multiplications, their method compares sixteen, thereby achieving much better results. In this work, we first analyze the atomicity coun- termeasure applied to Edwards curves, Twisted Edwards curves, and Edwards curves defined over binary fields. Then, we study the BIG MAC attack on these curves, focusing on its effectiveness against atomicity-based countermeasures.