Paper 2023/551

Breaking DPA-protected Kyber via the pair-pointwise multiplication

Estuardo Alpirez Bock, Xiphera LTD
Gustavo Banegas, Qualcomm France SARL
Chris Brzuska, Aalto University
Łukasz Chmielewski, Masaryk University
Kirthivaasan Puniamurthy, Aalto University
Milan Šorf, Masaryk University
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 \emph{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 \emph{mkm4} repository. We initially perform simulations in the noisy Hamming-Weight model and achieve high success rates with just $13\,316$ templates while tolerating noise values up to $\sigma=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.

Note: This is a slightly extended version of the article published at Applied Cryptography and Network Security (ACNS 2024). No substantial new results are added, but due to a lack of page limit, more details are included.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published elsewhere. Minor revision. 22nd International Conference on Applied Cryptography and Network Security (ACNS 2024)
Keywords
Post-quantum CryptographyTemplate attackKyberSide-channel AttackSingle Trace
Contact author(s)
estuardo alpirezbock @ xiphera com
gustavo @ cryptme in
chris brzuska @ aalto fi
chmiel @ fi muni cz
kirthivaasan puniamurthy @ aalto fi
xsorf @ fi muni cz
History
2024-04-05: last of 3 revisions
2023-04-18: received
See all versions
Short URL
https://ia.cr/2023/551
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/551,
      author = {Estuardo Alpirez Bock and Gustavo Banegas and Chris Brzuska and Łukasz Chmielewski and Kirthivaasan Puniamurthy and Milan Šorf},
      title = {Breaking {DPA}-protected Kyber via the pair-pointwise multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/551},
      year = {2023},
      url = {https://eprint.iacr.org/2023/551}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.