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

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.

Základní údaje

Originální název

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

Autoři

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

Vydání

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

Nakladatel

Ruhr-University of Bochum

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

URL

Kód RIV

RIV/00216224:14330/24:00136268

Organizační jednotka

Fakulta informatiky

ISSN

DOI

https://doi.org/10.46586/tches.v2024.i4.355-381

EID Scopus

2-s2.0-85204339379

Klíčová slova anglicky

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

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 18. 3. 2025 15:15, RNDr. Ján Jančár

Anotace

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.

Návaznosti

MUNI/A/1586/2023, interní kód MU

Název: 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: Masarykova univerzita, 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ů

VJ02010010, projekt VaV

Název: Nástroje pro verifikaci bezpečnosti kryptografických zařízení s využitím AI (Akronym: AI-SecTools)

Investor: Ministerstvo vnitra ČR, Tools for AI-enhanced Security Verification of Cryptographic Devices

Citovat

JANČÁR, Ján; Vojtěch SUCHÁNEK; Petr ŠVENDA; Vladimír SEDLÁČEK a Lukasz Michal CHMIELEWSKI. pyecsca: Reverse engineering black-box elliptic curve cryptography via side-channel analysis. Online. In IACR Transactions on Cryptographic Hardware and Embedded Systems. Německo: Ruhr-University of Bochum, 2024, s. 355-381. ISSN 2569-2925. Dostupné z: https://doi.org/10.46586/tches.v2024.i4.355-381.

@inproceedings{2411818,
   author = {Jančár, Ján and Suchánek, Vojtěch and Švenda, Petr and Sedláček, Vladimír and Chmielewski, Lukasz Michal},
   address = {Německo},
   booktitle = {IACR Transactions on Cryptographic Hardware and Embedded Systems},
   doi = {https://doi.org/10.46586/tches.v2024.i4.355-381},
   keywords = {elliptic curve cryptography; black-box implementations; reverse engineering; ECDH; ECDSA},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Německo},
   pages = {355-381},
   publisher = {Ruhr-University of Bochum},
   title = {pyecsca: Reverse engineering black-box elliptic curve cryptography via side-channel analysis},
   url = {https://tches.iacr.org/index.php/TCHES/article/view/11796},
   year = {2024}
}

TY  - CONF
ID  - 2411818
AU  - Jančár, Ján - Suchánek, Vojtěch - Švenda, Petr - Sedláček, Vladimír - Chmielewski, Lukasz Michal
PY  - 2024
TI  - pyecsca: Reverse engineering black-box elliptic curve cryptography via side-channel analysis
PB  - Ruhr-University of Bochum
CY  - Německo
KW  - elliptic curve cryptography
KW  - black-box implementations
KW  - reverse engineering
KW  - ECDH
KW  - ECDSA
UR  - https://tches.iacr.org/index.php/TCHES/article/view/11796
N2  - 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.
ER  -

JANČÁR, Ján; Vojtěch SUCHÁNEK; Petr ŠVENDA; Vladimír SEDLÁČEK a Lukasz Michal CHMIELEWSKI. pyecsca: Reverse engineering black-box elliptic curve cryptography via side-channel analysis. Online. In \textit{IACR Transactions on Cryptographic Hardware and Embedded Systems}. Německo: Ruhr-University of Bochum, 2024, s.~355-381. ISSN~2569-2925. Dostupné z: https://doi.org/10.46586/tches.v2024.i4.355-381.

Přehled o publikaci