CryptoDB

Paper: Chosen Ciphertext k-Trace Attacks on Masked CCA2 Secure Kyber

Authors: Mike Hamburg , Rambus Labs, San Jose, USA Julius Hermelink , Universität der Bundeswehr München, Munich, Germany Robert Primas , Graz University of Technology, Graz, Austria Simona Samardjiska , Radboud University, Nijmegen, The Netherlands Thomas Schamberger , Technical University of Munich (TUM), Munich, Germany Silvan Streit , Fraunhofer Institute AISEC, Garching near Munich, Germany Emanuele Strieder , Fraunhofer Institute AISEC, Garching near Munich, Germany Christine van Vredendaal , NXP Semiconductors, Eindhoven, The Netherlands DOI: 10.46586/tches.v2021.i4.88-113 URL: https://tches.iacr.org/index.php/TCHES/article/view/9061 Search ePrint Search Google Single-trace attacks are a considerable threat to implementations of classic public-key schemes, and their implications on newer lattice-based schemes are still not well understood. Two recent works have presented successful single-trace attacks targeting the Number Theoretic Transform (NTT), which is at the heart of many lattice-based schemes. However, these attacks either require a quite powerful side-channel adversary or are restricted to specific scenarios such as the encryption of ephemeral secrets. It is still an open question if such attacks can be performed by simpler adversaries while targeting more common public-key scenarios. In this paper, we answer this question positively. First, we present a method for crafting ring/module-LWE ciphertexts that result in sparse polynomials at the input of inverse NTT computations, independent of the used private key. We then demonstrate how this sparseness can be incorporated into a side-channel attack, thereby significantly improving noise resistance of the attack compared to previous works. The effectiveness of our attack is shown on the use-case of CCA2 secure Kyber k-module-LWE, where k ∈ {2, 3, 4}. Our k-trace attack on the long-term secret can handle noise up to a σ ≤ 1.2 in the noisy Hamming weight leakage model, also for masked implementations. A 2k-trace variant for Kyber1024 even allows noise σ ≤ 2.2 also in the masked case, with more traces allowing us to recover keys up to σ ≤ 2.7. Single-trace attack variants have a noise tolerance depending on the Kyber parameter set, ranging from σ ≤ 0.5 to σ ≤ 0.7. As a comparison, similar previous attacks in the masked setting were only successful with σ ≤ 0.5.
BibTeX
@article{tches-2021-31312,
title={Chosen Ciphertext k-Trace Attacks on Masked CCA2 Secure Kyber},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2021, Issue 4},
pages={88-113},
url={https://tches.iacr.org/index.php/TCHES/article/view/9061},
doi={10.46586/tches.v2021.i4.88-113},
author={Mike Hamburg and Julius Hermelink and Robert Primas and Simona Samardjiska and Thomas Schamberger and Silvan Streit and Emanuele Strieder and Christine van Vredendaal},
year=2021
}