Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber
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-che...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-11-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/9948 |
| _version_ | 1811190377573515264 |
|---|---|
| author | Muyan Shen Chi Cheng Xiaohan Zhang Qian Guo Tao Jiang |
| author_facet | Muyan Shen Chi Cheng Xiaohan Zhang Qian Guo Tao Jiang |
| author_sort | Muyan Shen |
| collection | DOAJ |
| description |
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.
|
| first_indexed | 2024-04-11T14:50:25Z |
| format | Article |
| id | doaj.art-2bb37f2db03746edaadafe706a0ebfdd |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-11T14:50:25Z |
| publishDate | 2022-11-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-2bb37f2db03746edaadafe706a0ebfdd2022-12-22T04:17:30ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252022-11-012023110.46586/tches.v2023.i1.89-112Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of KyberMuyan Shen0Chi Cheng1Xiaohan Zhang2Qian Guo3Tao Jiang4Hubei 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, ChinaHubei 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, ChinaHubei 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, ChinaLund University, Lund, SwedenResearch Center of 6G Mobile Communications, School of Cyber Science and Engineering, Huazhong University of Science and Technology, Wuhan, China 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. https://tches.iacr.org/index.php/TCHES/article/view/9948Lattice-based cryptographySide-channel attacksPlaintext-checking oracleNIST Post-Quantum cryptography standardizationKyberKey mismatch attacks |
| spellingShingle | Muyan Shen Chi Cheng Xiaohan Zhang Qian Guo Tao Jiang Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber Transactions on Cryptographic Hardware and Embedded Systems Lattice-based cryptography Side-channel attacks Plaintext-checking oracle NIST Post-Quantum cryptography standardization Kyber Key mismatch attacks |
| title | Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber |
| title_full | Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber |
| title_fullStr | Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber |
| title_full_unstemmed | Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber |
| title_short | Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber |
| title_sort | find the bad apples an efficient method for perfect key recovery under imperfect sca oracles a case study of kyber |
| topic | Lattice-based cryptography Side-channel attacks Plaintext-checking oracle NIST Post-Quantum cryptography standardization Kyber Key mismatch attacks |
| url | https://tches.iacr.org/index.php/TCHES/article/view/9948 |
| work_keys_str_mv | AT muyanshen findthebadapplesanefficientmethodforperfectkeyrecoveryunderimperfectscaoraclesacasestudyofkyber AT chicheng findthebadapplesanefficientmethodforperfectkeyrecoveryunderimperfectscaoraclesacasestudyofkyber AT xiaohanzhang findthebadapplesanefficientmethodforperfectkeyrecoveryunderimperfectscaoraclesacasestudyofkyber AT qianguo findthebadapplesanefficientmethodforperfectkeyrecoveryunderimperfectscaoraclesacasestudyofkyber AT taojiang findthebadapplesanefficientmethodforperfectkeyrecoveryunderimperfectscaoraclesacasestudyofkyber |