International Association
for Cryptologic Research

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.