Paper 2022/563

Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber

Muyan Shen
Chi Cheng
Xiaohan Zhang
Qian Guo
Tao Jiang

Side-channel resilience is a crucial feature when assessing whether a post-quantum cryptographic proposal is sufficiently mature to be deployed. In this paper, we propose a generic and efficient adaptive approach to improve the sample complexity (i.e., the required number of traces) of plaintext-checking (PC) oracle-based side-channel attacks (SCAs), a major class of key recovery chosen-ciphertext SCAs on lattice-based key encapsulation mechanisms. This new approach is preferable when the constructed PC oracle is imperfect, which is common in practice, and its basic idea is to design new detection codes that can determine erroneous positions in the initially recovered secret key. These secret entries are further corrected with a small number of additional traces. This work benefits from the generality of PC oracle and thus is applicable to various schemes and implementations. We instantiated the proposed generic attack framework on Kyber512 and fully implemented this attack instance. Through extensive computer simulations and also a real-world experiment with electromagnetic (EM) leakages from an ARM-Cortext-M4 platform, we demonstrated that the newly proposed attack could greatly improve the state-of-the-art in terms of the required number of traces. For instance, the new attack requires only 41% of the EM traces needed in a majority-voting attack in our experiments, where the raw oracle accuracy is fixed.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCHES 2023
Lattice-based cryptography Side-channel attacks Plaintext-checking oracle Kyber Key mismatch attacks
Contact author(s)
chengchizz @ qq com
2022-11-30: revised
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Muyan Shen and Chi Cheng and Xiaohan Zhang and Qian Guo and Tao Jiang},
      title = {Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber},
      howpublished = {Cryptology ePrint Archive, Paper 2022/563},
      year = {2022},
      doi = {10.46586/tches.v2023.i1.89-112},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.