A Formula for Disaster: A Unified Approach to Elliptic Curve Special-Point-Based Attacks

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1
EditorsMehdi Tibouchi, Huaxiong Wang
PublisherSpringer
Pages130-159
Number of pages30
ISBN (Electronic)9783030920623
ISBN (Print)9783030920616
DOIs
Publication statusPublished - 2021
Publication typeA4 Article in a conference publication
EventInternational Conference on Theory and Application of Cryptology and Information Security - Virtual, Online
Duration: 6 Dec 202110 Dec 2021

Publication series

NameLecture Notes in Computer Science
Volume13090
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Theory and Application of Cryptology and Information Security
CityVirtual, Online
Period6/12/2110/12/21

Keywords

  • ECC
  • ECDH
  • Elliptic curve cryptography
  • Elliptic curve Diffie-Hellman
  • EPA
  • Exceptional points
  • Exceptional procedure attack
  • Refined Power Analysis
  • RPA
  • Side-channel analysis
  • Zero-value point attack
  • ZVP

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'A Formula for Disaster: A Unified Approach to Elliptic Curve Special-Point-Based Attacks'. Together they form a unique fingerprint.

Cite this