Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs

This paper presents a side-channel analysis (SCA) on key encapsulation mechanism (KEM) based on the Fujisaki–Okamoto (FO) transformation and its variants. The FO transformation has been widely used in actively securing KEMs from passively secure public key encryption (PKE), as it is employed in mos...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, Naofumi Homma
Formato:	article
Lenguaje:	EN
Publicado:	Ruhr-Universität Bochum 2021
Materias:	Side-channel analysis Fujisaki–Okamoto transformation Key encapsulation mechanism Public key encryption Post-quantum cryptography Deep learning Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
Acceso en línea:	https://doaj.org/article/93e0523fe0ca4698810313a80831a37f
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:93e0523fe0ca4698810313a80831a37f
record_format	dspace
spelling	oai:doaj.org-article:93e0523fe0ca4698810313a80831a37f2021-11-19T14:36:11ZCurse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs10.46586/tches.v2022.i1.296-3222569-2925https://doaj.org/article/93e0523fe0ca4698810313a80831a37f2021-11-01T00:00:00Zhttps://tches.iacr.org/index.php/TCHES/article/view/9298https://doaj.org/toc/2569-2925 This paper presents a side-channel analysis (SCA) on key encapsulation mechanism (KEM) based on the Fujisaki–Okamoto (FO) transformation and its variants. The FO transformation has been widely used in actively securing KEMs from passively secure public key encryption (PKE), as it is employed in most of NIST post-quantum cryptography (PQC) candidates for KEM. The proposed attack exploits side-channel leakage during execution of a pseudorandom function (PRF) or pseudorandom number generator (PRG) in the re-encryption of KEM decapsulation as a plaintext-checking oracle that tells whether the PKE decryption result is equivalent to the reference plaintext. The generality and practicality of the plaintext-checking oracle allow the proposed attack to attain a full-key recovery of various KEMs when an active attack on the underlying PKE is known. This paper demonstrates that the proposed attack can be applied to most NIST PQC third-round KEM candidates, namely, Kyber, Saber, FrodoKEM, NTRU, NTRU Prime, HQC, BIKE, and SIKE (for BIKE, the proposed attack achieves a partial key recovery). The applicability to Classic McEliece is unclear because there is no known active attack on this cryptosystem. This paper also presents a side-channel distinguisher design based on deep learning (DL) for mounting the proposed attack on practical implementation without the use of a profiling device. The feasibility of the proposed attack is evaluated through experimental attacks on various PRF implementations (a SHAKE software, an AES software, an AES hardware, a bit-sliced masked AES software, and a masked AES hardware based on threshold implementation). Although it is difficult to implement the oracle using the leakage from the TI-based masked hardware, the success of the proposed attack against these implementations (even except for the masked hardware), which include masked software, confirms its practicality. Rei UenoKeita XagawaYutaro TanakaAkira ItoJunko TakahashiNaofumi HommaRuhr-Universität BochumarticleSide-channel analysisFujisaki–Okamoto transformationKey encapsulation mechanismPublic key encryptionPost-quantum cryptographyDeep learningComputer engineering. Computer hardwareTK7885-7895Information technologyT58.5-58.64ENTransactions on Cryptographic Hardware and Embedded Systems, Vol 2022, Iss 1 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Side-channel analysis Fujisaki–Okamoto transformation Key encapsulation mechanism Public key encryption Post-quantum cryptography Deep learning Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64
spellingShingle	Side-channel analysis Fujisaki–Okamoto transformation Key encapsulation mechanism Public key encryption Post-quantum cryptography Deep learning Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Rei Ueno Keita Xagawa Yutaro Tanaka Akira Ito Junko Takahashi Naofumi Homma Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs
description	This paper presents a side-channel analysis (SCA) on key encapsulation mechanism (KEM) based on the Fujisaki–Okamoto (FO) transformation and its variants. The FO transformation has been widely used in actively securing KEMs from passively secure public key encryption (PKE), as it is employed in most of NIST post-quantum cryptography (PQC) candidates for KEM. The proposed attack exploits side-channel leakage during execution of a pseudorandom function (PRF) or pseudorandom number generator (PRG) in the re-encryption of KEM decapsulation as a plaintext-checking oracle that tells whether the PKE decryption result is equivalent to the reference plaintext. The generality and practicality of the plaintext-checking oracle allow the proposed attack to attain a full-key recovery of various KEMs when an active attack on the underlying PKE is known. This paper demonstrates that the proposed attack can be applied to most NIST PQC third-round KEM candidates, namely, Kyber, Saber, FrodoKEM, NTRU, NTRU Prime, HQC, BIKE, and SIKE (for BIKE, the proposed attack achieves a partial key recovery). The applicability to Classic McEliece is unclear because there is no known active attack on this cryptosystem. This paper also presents a side-channel distinguisher design based on deep learning (DL) for mounting the proposed attack on practical implementation without the use of a profiling device. The feasibility of the proposed attack is evaluated through experimental attacks on various PRF implementations (a SHAKE software, an AES software, an AES hardware, a bit-sliced masked AES software, and a masked AES hardware based on threshold implementation). Although it is difficult to implement the oracle using the leakage from the TI-based masked hardware, the success of the proposed attack against these implementations (even except for the masked hardware), which include masked software, confirms its practicality.
format	article
author	Rei Ueno Keita Xagawa Yutaro Tanaka Akira Ito Junko Takahashi Naofumi Homma
author_facet	Rei Ueno Keita Xagawa Yutaro Tanaka Akira Ito Junko Takahashi Naofumi Homma
author_sort	Rei Ueno
title	Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs
title_short	Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs
title_full	Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs
title_fullStr	Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs
title_full_unstemmed	Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs
title_sort	curse of re-encryption: a generic power/em analysis on post-quantum kems
publisher	Ruhr-Universität Bochum
publishDate	2021
url	https://doaj.org/article/93e0523fe0ca4698810313a80831a37f
work_keys_str_mv	AT reiueno curseofreencryptionagenericpoweremanalysisonpostquantumkems AT keitaxagawa curseofreencryptionagenericpoweremanalysisonpostquantumkems AT yutarotanaka curseofreencryptionagenericpoweremanalysisonpostquantumkems AT akiraito curseofreencryptionagenericpoweremanalysisonpostquantumkems AT junkotakahashi curseofreencryptionagenericpoweremanalysisonpostquantumkems AT naofumihomma curseofreencryptionagenericpoweremanalysisonpostquantumkems
_version_	1718420084634943488

Curse of Re-encryption: A Generic Power/EM Analysis on Post-Quantum KEMs

Ejemplares similares