Breaking DPA-protected Kyber via the pair-pointwise
multiplication

D 2024

Breaking DPA-protected Kyber via the pair-pointwise multiplication

BOCK, Estuardo Alpirez; Gustavo BANEGAS; Chris BRZUSKA; Lukasz Michal CHMIELEWSKI; Kirthivaasan PUNIAMURTHY et. al.

Základní údaje

Originální název

Breaking DPA-protected Kyber via the pair-pointwise multiplication

Autoři

BOCK, Estuardo Alpirez; Gustavo BANEGAS; Chris BRZUSKA; Lukasz Michal CHMIELEWSKI; Kirthivaasan PUNIAMURTHY a Milan ŠORF

Vydání

Abu Dhabi, 22nd International Conference on Applied Cryptography and Network Security, ACNS 2024, od s. 101-130, 30 s. 2024

Nakladatel

Springer

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í

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/24:00135460

Organizační jednotka

Fakulta informatiky

ISBN

978-3-031-54772-0

ISSN

DOI

https://doi.org/10.1007/978-3-031-54773-7_5

UT WoS

001206023700005

EID Scopus

2-s2.0-85187807598

Klíčová slova anglicky

Kyber; Post-quantum Cryptography; Side-channel Attack; Single Trace; Template attack

Štítky

core_B, firank_B

Změněno: 2. 4. 2025 14:53, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We introduce a novel template attack for secret key recovery in Kyber, leveraging side-channel information from polynomial multiplication during decapsulation. Conceptually, our attack exploits that Kyber’s incomplete number-theoretic transform (NTT) causes each secret coefficient to be used multiple times, unlike when performing a complete NTT. Our attack is a single trace known ciphertext attack that avoids machine-learning techniques and instead relies on correlation-matching only. Additionally, our template generation method is very simple and easy to replicate, and we describe different attack strategies, varying on the number of templates required. Moreover, our attack applies to both masked implementations as well as designs with multiplication shuffling. We demonstrate its effectiveness by targeting a masked implementation from the mkm4 repository. We initially perform simulations in the noisy Hamming-Weight model and achieve high success rates with just 13316 templates while tolerating noise values up to σ=0.3. In a practical setup, we measure power consumption and notice that our attack falls short of expectations. However, we introduce an extension inspired by known online template attacks, enabling us to recover 128 coefficient pairs from a single polynomial multiplication. Our results provide evidence that the incomplete NTT, which is used in Kyber-768 and similar schemes, introduces an additional side-channel weakness worth further exploration.

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ů

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

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 24

Citovat

BOCK, Estuardo Alpirez; Gustavo BANEGAS; Chris BRZUSKA; Lukasz Michal CHMIELEWSKI; Kirthivaasan PUNIAMURTHY a Milan ŠORF. Breaking DPA-protected Kyber via the pair-pointwise multiplication. In 22nd International Conference on Applied Cryptography and Network Security, ACNS 2024. Abu Dhabi: Springer, 2024, s. 101-130. ISBN 978-3-031-54772-0. Dostupné z: https://doi.org/10.1007/978-3-031-54773-7_5.

@inproceedings{2369500,
   author = {Bock, Estuardo Alpirez and Banegas, Gustavo and Brzuska, Chris and Chmielewski, Lukasz Michal and Puniamurthy, Kirthivaasan and Šorf, Milan},
   address = {Abu Dhabi},
   booktitle = {22nd International Conference on Applied Cryptography and Network Security, ACNS 2024},
   doi = {https://doi.org/10.1007/978-3-031-54773-7_5},
   keywords = {Kyber; Post-quantum Cryptography; Side-channel Attack; Single Trace; Template attack},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Abu Dhabi},
   isbn = {978-3-031-54772-0},
   pages = {101-130},
   publisher = {Springer},
   title = {Breaking DPA-protected Kyber via the pair-pointwise multiplication},
   year = {2024}
}

TY  - CONF
ID  - 2369500
AU  - Bock, Estuardo Alpirez - Banegas, Gustavo - Brzuska, Chris - Chmielewski, Lukasz Michal - Puniamurthy, Kirthivaasan - Šorf, Milan
PY  - 2024
TI  - Breaking DPA-protected Kyber via the pair-pointwise multiplication
PB  - Springer
CY  - Abu Dhabi
SN  - 9783031547720
KW  - Kyber
KW  - Post-quantum Cryptography
KW  - Side-channel Attack
KW  - Single Trace
KW  - Template attack
N2  - We introduce a novel template attack for secret key recovery in Kyber, leveraging side-channel information from polynomial multiplication during decapsulation. Conceptually, our attack exploits that Kyber’s incomplete number-theoretic transform (NTT) causes each secret coefficient to be used multiple times, unlike when performing a complete NTT. Our attack is a single trace known ciphertext attack that avoids machine-learning techniques and instead relies on correlation-matching only. Additionally, our template generation method is very simple and easy to replicate, and we describe different attack strategies, varying on the number of templates required. Moreover, our attack applies to both masked implementations as well as designs with multiplication shuffling. We demonstrate its effectiveness by targeting a masked implementation from the mkm4 repository. We initially perform simulations in the noisy Hamming-Weight model and achieve high success rates with just 13316 templates while tolerating noise values up to σ=0.3. In a practical setup, we measure power consumption and notice that our attack falls short of expectations. However, we introduce an extension inspired by known online template attacks, enabling us to recover 128 coefficient pairs from a single polynomial multiplication. Our results provide evidence that the incomplete NTT, which is used in Kyber-768 and similar schemes, introduces an additional side-channel weakness worth further exploration.
ER  -

BOCK, Estuardo Alpirez; Gustavo BANEGAS; Chris BRZUSKA; Lukasz Michal CHMIELEWSKI; Kirthivaasan PUNIAMURTHY a Milan ŠORF. Breaking DPA-protected Kyber via the pair-pointwise multiplication. In \textit{22nd International Conference on Applied Cryptography and Network Security, ACNS 2024}. Abu Dhabi: Springer, 2024, s.~101-130. ISBN~978-3-031-54772-0. Dostupné z: https://doi.org/10.1007/978-3-031-54773-7\_{}5.

Přehled o publikaci