International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Multiple-Valued Plaintext-Checking Side-Channel Attacks on Post-Quantum KEMs

Authors:
Yutaro Tanaka , Tohoku University, 2–1–1 Katahira, Aoba-ku, Sendai-shi, 980-8577, Japan; CREST, JST, 4–1–8 Honcho, Kawaguchi, Saitama, 332-0012, Japan
Rei Ueno , Tohoku University, 2–1–1 Katahira, Aoba-ku, Sendai-shi, 980-8577, Japan; CREST, JST, 4–1–8 Honcho, Kawaguchi, Saitama, 332-0012, Japan
Keita Xagawa , Social Informatics Laboratories, NTT Corporation, 3–9–11 Midori-cho, Musashino-shi, Tokyo, 180-8535, Japan
Akira Ito , Social Informatics Laboratories, NTT Corporation, 3–9–11 Midori-cho, Musashino-shi, Tokyo, 180-8535, Japan
Junko Takahashi , Social Informatics Laboratories, NTT Corporation, 3–9–11 Midori-cho, Musashino-shi, Tokyo, 180-8535, Japan
Naofumi Homma , Tohoku University, 2–1–1 Katahira, Aoba-ku, Sendai-shi, 980-8577, Japan
Download:
DOI: 10.46586/tches.v2023.i3.473-503
URL: https://tches.iacr.org/index.php/TCHES/article/view/10971
Search ePrint
Search Google
Abstract: In this paper, we present a side-channel analysis (SCA) on key encapsulation mechanisms (KEMs) based on the Fujisaki–Okamoto (FO) transformation and its variants. Many post-quantum KEMs usually perform re-encryption during key decapsulation to achieve chosen-ciphertext attack (CCA) security. The side-channel leakage of re-encryption can be exploited to mount a key-recovery plaintext-checking attack (KR-PCA), even if the chosen-plaintext attack (CCA) secure decryption constructing the KEM is securely implemented. Herein, we propose an efficient side-channel-assisted KR-PCA on post-quantum KEMs, and achieve a key recovery with significantly fewer attack traces than existing ones in TCHES 2022 and 2023. The basic concept of the proposed attack is to introduce a new KR-PCA based on a multiple-valued (MV-)PC oracle and then implement a dedicated MV-PC oracle based on a multi-classification neural network (NN). The proposed attack is applicable to the NIST PQC selected algorithm Kyber and the similar lattice-based Saber, FrodoKEM and NTRU Prime, as well as SIKE. We also present how to realize a sufficiently reliable MV-PC oracle from NN model outputs that are not 100% accurate, and analyze the tradeoff between the key recovery success rate and the number of attack traces. We assess the feasibility of the proposed attack through attack experiments on three typical symmetric primitives to instantiate a random oracle (SHAKE, SHA3, and AES software). The proposed attack reduces the number of attack traces required for a reliable key recovery by up to 87% compared to the existing attacks against Kyber and other lattice-based KEMs, under the condition of 99.9999% success rate for key recovery. The proposed attack can also reduce the number of attack traces by 85% for SIKE.
BibTeX
@article{tches-2023-33297,
  title={Multiple-Valued Plaintext-Checking Side-Channel Attacks on Post-Quantum KEMs},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 3},
  pages={473-503},
  url={https://tches.iacr.org/index.php/TCHES/article/view/10971},
  doi={10.46586/tches.v2023.i3.473-503},
  author={Yutaro Tanaka and Rei Ueno and Keita Xagawa and Akira Ito and Junko Takahashi and Naofumi Homma},
  year=2023
}