Cryptology ePrint Archive: Report 2021/1595

A formula for disaster: a unified approach to elliptic curve special-point-based attacks

Vladimir Sedlacek and Jesús-Javier Chi-Domínguez and Jan Jancar and Billy Bob Brumley

Abstract: The Refined Power Analysis, Zero-Value Point, and Exceptional Procedure attacks introduced side-channel techniques against specific cases of elliptic curve cryptography. The three attacks recover bits of a static ECDH key adaptively, collecting information on whether a certain multiple of the input point was computed. We unify and generalize these attacks in a common framework, and solve the corresponding problem for a broader class of inputs. We also introduce a version of the attack against windowed scalar multiplication methods, recovering the full scalar instead of just a part of it. Finally, we systematically analyze elliptic curve point addition formulas from the Explicit-Formulas Database, classify all non-trivial exceptional points, and find them in new formulas. These results indicate the usefulness of our tooling, which we released publicly, for unrolling formulas and finding special points, and potentially for independent future work.

Category / Keywords: public-key cryptography / elliptic curve cryptography, ECC, elliptic curve Diffie-Hellman, ECDH, side-channel analysis, Refined Power Analysis, RPA, Zero-Value Point attack, ZVP, Exceptional Procedure Attack, EPA, exceptional points

Original Publication (in the same form): IACR-ASIACRYPT-2021

Date: received 5 Dec 2021, last revised 5 Dec 2021

Contact author: 445358 at mail muni cz, vlada sedlacek at mail muni cz, jesus dominguez at tii ae, billy brumley at tuni fi

Available format(s): PDF | BibTeX Citation

Version: 20211206:035532 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]