Breaking DPA-Protected Kyber via the Pair-Pointwise Multiplication

Estuardo Alpirez Bock, Gustavo Banegas, Chris Brzuska, Łukasz Chmielewski*, Kirthivaasan Puniamurthy, Milan Šorf

*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationApplied Cryptography and Network Security - 22nd International Conference, ACNS 2024, Proceedings
EditorsChristina Pöpper, Lejla Batina
PublisherSpringer
Pages101-130
Number of pages30
ISBN (Electronic)978-3-031-54773-7
ISBN (Print)978-3-031-54772-0
DOIs
Publication statusPublished - 1 Mar 2024
MoE publication typeA4 Conference publication
EventInternational Conference on Applied Cryptography and Network Security - Abu Dhabi, United Arab Emirates
Duration: 5 Mar 20248 Mar 2024
Conference number: 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume14584 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Applied Cryptography and Network Security
Abbreviated titleACNS
Country/TerritoryUnited Arab Emirates
CityAbu Dhabi
Period05/03/202408/03/2024

Keywords

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

Fingerprint

Dive into the research topics of 'Breaking DPA-Protected Kyber via the Pair-Pointwise Multiplication'. Together they form a unique fingerprint.

Cite this