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

Abstract

This paper presents 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 CCA security. It has been shown that the side-channel leakage of re-encryption can be exploited for mounting a key-recovery plaintext-checking attack (KR-PCA), even if the CPA secure decryption constructing the KEM is securely implemented. In this paper, we propose an efficient side-channel-assisted KR-PCA on post-quantum KEMs, which achieves a key recovery with significantly fewer attack traces than the existing one. The basic ideas of the proposed attack are to present a new KR-PCA based on a multiple-valued (MV-)PC oracle and to utilize a dedicated multi-classification neural network (NN) to implement an MV-PC oracle. This paper also presents how to realize a sufficiently reliable MV-PC oracle from not completely accurate NN model outputs, and analyzes the tradeoff between the key recovery success rate and the number of attack traces, with its application to NIST PQC selected algorithm Kyber and similar lattice-based Saber, FrodoKEM and NTRU Prime, as well as SIKE, a candidate for the fourth round. Furthermore, the feasibility of the proposed attack is assessed through attack experiments on three typical PRF implementations (i.e., SHAKE, SHA3, and AES software). In consequence, we confirm that 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. We also confirm that the proposed attack can reduce the number of attack traces by 85% for SIKE.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Side-channel analysism Fujisaki–Okamoto transformation Post-quantum cryptography Deep learning
Contact author(s)
yutaro tanaka t6 @ dc tohoku ac jp
rei ueno a8 @ tohoku ac jp
keita xagawa zv @ hco ntt co jp
akira ito as @ hco ntt co jp
junko takahashi fc @ hco ntt co jp
naofumi homma c8 @ tohoku ac jp
History
2022-07-20: approved
See all versions
Short URL
https://ia.cr/2022/940

CC BY

BibTeX

@misc{cryptoeprint:2022/940,
author = {Yutaro Tanaka and Rei Ueno and Keita Xagawa and Akira Ito and Junko Takahashi and Naofumi Homma},
title = {Multiple-Valued Plaintext-Checking Side-Channel Attacks on Post-Quantum KEMs},
howpublished = {Cryptology ePrint Archive, Paper 2022/940},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/940}},
url = {https://eprint.iacr.org/2022/940}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.