Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems with Chosen Ciphertexts: The Case Study of Kyber

Zhuang Xu; Owen Pemberton; Sujoy Sinha Roy; David Oswald; Wang Yao; Zhiming Zheng

Paper 2020/912

Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems with Chosen Ciphertexts: The Case Study of Kyber

Zhuang Xu, Owen Pemberton, Sujoy Sinha Roy, David Oswald, Wang Yao, and Zhiming Zheng

Abstract

Lattice-based cryptography, as an active branch of post-quantum cryptography (PQC), has drawn great attention from side-channel analysis researchers in recent years. Despite the various side-channel targets examined in previous studies, detail on revealing the secret-dependent information efficiently is less studied. In this paper, we propose adaptive EM side-channel attacks with carefully constructed ciphertexts on Kyber, which is a finalist of NIST PQC standardization project. We demonstrate that specially chosen ciphertexts allow an adversary to modulate the leakage of a target device and enable full key extraction with a small number of traces through simple power analysis. Compared to prior research, our techniques require fewer traces and avoid building complex templates. We practically evaluate our methods using both a reference implementation and the ARM-specific implementation in pqm4 library. For the reference implementation, we target the leakage of the output of the inverse NTT computation and recover the full key with only four traces. For the pqm4 implementation, we develop a message-recovery attack that leads to extraction of the full secret key with between eight and 960 traces, depending on the compiler optimization level. We discuss the relevance of our findings to other lattice-based schemes and explore potential countermeasures.

Note: The strategy of ciphertext selection is described in more detail. Comparisons with previous work and more appendices are added.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. IEEE Transactions on Computers
DOI: 10.1109/TC.2021.3122997
Keywords: Lattice-based cryptography Kyber Side-channel analysis Chosen-ciphertext attack
Contact author(s): xu_zhuang @ buaa edu cn
zhuang xu @ hotmail com
History: 2021-11-21: last of 3 revisions; 2020-07-23: received; See all versions
Short URL: https://ia.cr/2020/912
License: CC BY

BibTeX

@misc{cryptoeprint:2020/912,
      author = {Zhuang Xu and Owen Pemberton and Sujoy Sinha Roy and David Oswald and Wang Yao and Zhiming Zheng},
      title = {Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems with Chosen Ciphertexts: The Case Study of Kyber},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/912},
      year = {2020},
      doi = {10.1109/TC.2021.3122997},
      url = {https://eprint.iacr.org/2020/912}
}