Find the Bad Apples: An efficient method for perfectkey recovery under imperfect SCA oracles– A case study of Kyber
(2023) In IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES) 2023(1). p.89-112- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/52c11aee-9137-489d-af1c-7ddd7bd8502d
- author
- Shen, Muyan ; Cheng, Chi ; Zhang, Xiaohan ; Guo, Qian LU and Jiang, Tao
- organization
- publishing date
- 2023
- type
- Contribution to journal
- publication status
- published
- subject
- in
- IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)
- volume
- 2023
- issue
- 1
- pages
- 89 - 112
- publisher
- Ruhr-University of Bochum
- external identifiers
-
- scopus:85142910479
- ISSN
- 2569-2925
- DOI
- 10.46586/tches.v2023.i1.89-112
- project
- Lightweight Cryptography for Autonomous Vehicles
- Side-Channel Vulnerability and Threat Analysis with Machine Learning Awareness
- Securing Quantum-Safe Signatures
- language
- English
- LU publication?
- yes
- id
- 52c11aee-9137-489d-af1c-7ddd7bd8502d
- date added to LUP
- 2022-12-17 12:39:35
- date last changed
- 2023-11-19 13:25:28
@article{52c11aee-9137-489d-af1c-7ddd7bd8502d,
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.<br/>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.}},
author = {{Shen, Muyan and Cheng, Chi and Zhang, Xiaohan and Guo, Qian and Jiang, Tao}},
issn = {{2569-2925}},
language = {{eng}},
number = {{1}},
pages = {{89--112}},
publisher = {{Ruhr-University of Bochum}},
series = {{IACR Transactions on Cryptographic Hardware and Embedded Systems (TCHES)}},
title = {{Find the Bad Apples: An efficient method for perfectkey recovery under imperfect SCA oracles– A case study of Kyber}},
url = {{http://dx.doi.org/10.46586/tches.v2023.i1.89-112}},
doi = {{10.46586/tches.v2023.i1.89-112}},
volume = {{2023}},
year = {{2023}},
}