D 2024

pyecsca: Reverse engineering black-box elliptic curve cryptography via side-channel analysis

JANČÁR, Ján, Vojtěch SUCHÁNEK, Petr ŠVENDA, Vladimír SEDLÁČEK, Lukasz Michal CHMIELEWSKI et. al.

Basic information

Original name

pyecsca: Reverse engineering black-box elliptic curve cryptography via side-channel analysis

Authors

JANČÁR, Ján (703 Slovakia, guarantor, belonging to the institution), Vojtěch SUCHÁNEK (203 Czech Republic, belonging to the institution), Petr ŠVENDA (203 Czech Republic, belonging to the institution), Vladimír SEDLÁČEK (203 Czech Republic) and Lukasz Michal CHMIELEWSKI (616 Poland, belonging to the institution)

Edition

Německo, IACR Transactions on Cryptographic Hardware and Embedded Systems, p. 355-381, 27 pp. 2024

Publisher

Ruhr-University of Bochum

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Germany

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

Organization unit

Faculty of Informatics

ISSN

DOI

Keywords in English

elliptic curve cryptography; black-box implementations; reverse engineering; ECDH; ECDSA

Tags

International impact, Reviewed
Změněno: 8/10/2024 18:16, RNDr. Ján Jančár

Abstract

V originále

Side-channel attacks on elliptic curve cryptography (ECC) often assume a white-box attacker who has detailed knowledge of the implementation choices taken by the target implementation. Due to the complex and layered nature of ECC, there are many choices that a developer makes to obtain a functional and interoperable implementation. These include the curve model, coordinate system, addition formulas and the scalar multiplier, or lower-level details such as the finite-field multiplication algorithm. This creates a gap between the attack requirements and a real-world attacker that often only has black-box access to the target -- i.e., has no access to the source code nor knowledge of specific implementation choices made. Yet, when the gap is closed, even real-world implementations of ECC succumb to side-channel attacks, as evidenced by attacks such as TPM-Fail, Minerva, the Side Journey to Titan or TPMScan. We study this gap by first analyzing open-source ECC libraries for insight into real-world implementation choices. We then examine the space of all ECC implementations combinatorially. Finally, we present a set of novel methods for automated reverse-engineering of black-box ECC implementations and release a documented and usable open-source toolkit for side-channel analysis of ECC called pyecsca. Our methods turn attacks around, instead of attempting to recover the private key, they attempt to recover the implementation configuration given control over the private and public inputs. We evaluate them on two simulation levels and study the effect of noise on their performance. Our methods are able to 1) reverse-engineer the scalar multiplication algorithm completely and 2) infer significant information about the coordinate system and addition formulas used in a target implementation. Furthermore, they can bypass coordinate and curve randomization countermeasures.

Links

MUNI/A/1586/2023, interní kód MU
Name: Aplikovaný výzkum na FI: Forenzní aspekty kritických infrastruktur, aplikovaná kryptografie, kyberbezpečnostní cvičení, algoritmy plánování v logistice a pro zpracování dat z fyzikálních sensorů
Investor: Masaryk University, Applied research at FI: Forensic aspects of critical infrastructures, applied cryptography, cybersecurity trainings, scheduling algorithms logistics and algorithms for physical sensors
VJ02010010, research and development project
Name: Nástroje pro verifikaci bezpečnosti kryptografických zařízení s využitím AI (Acronym: AI-SecTools)
Investor: Ministry of the Interior of the CR