International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Muyan Shen , Hubei Key Laboratory of Intelligent Geo-Information Processing, School of Computer Science, China University of Geosciences, Wuhan, China; State Key Laboratory of Integrated Services Networks, Xidian University, Xian, China
Chi Cheng , Hubei Key Laboratory of Intelligent Geo-Information Processing, School of Computer Science, China University of Geosciences, Wuhan, China; State Key Laboratory of Integrated Services Networks, Xidian University, Xian, China
Xiaohan Zhang , Hubei Key Laboratory of Intelligent Geo-Information Processing, School of Computer Science, China University of Geosciences, Wuhan, China; State Key Laboratory of Integrated Services Networks, Xidian University, Xian, China
Qian Guo , Lund University, Lund, Sweden
Tao Jiang , Research Center of 6G Mobile Communications, School of Cyber Science and Engineering, Huazhong University of Science and Technology, Wuhan, China
Download:
DOI: 10.46586/tches.v2023.i1.89-112
URL: https://tches.iacr.org/index.php/TCHES/article/view/9948
Search ePrint
Search Google
Abstract: Side-channel resilience is a crucial feature when assessing whether a postquantum 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 sidechannel attacks (SCAs), a major class of key recovery chosen-ciphertext SCAs on lattice-based key encapsulation mechanisms (KEMs). 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.Our main target is Kyber since it has been selected by NIST as the KEM algorithm for standardization. We instantiated the proposed generic attack on Kyber512 and then conducted extensive computer simulations against Kyber512 and FireSaber. We further mounted an electromagnetic (EM) attack against an optimized implementation of Kyber512 in the pqm4 library running on an STM32F407G board with an ARM Cortex-M4 microcontroller. These simulations and real-world experiments demonstrate 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.
BibTeX
@article{tches-2022-32682,
  title={Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 1},
  pages={89-112},
  url={https://tches.iacr.org/index.php/TCHES/article/view/9948},
  doi={10.46586/tches.v2023.i1.89-112},
  author={Muyan Shen and Chi Cheng and Xiaohan Zhang and Qian Guo and Tao Jiang},
  year=2022
}