A Generic Power/EM Analysis On Post-Quantum KEMs

Cryptology ePrint Archive

• Papers
  Updates from the last:
  • 7 days
  • 31 days
  • 6 months
  • 365 days
  • Listing by year
  • All papers
  • Compact view
  • Subscribe
  • How to cite
  • Harvesting metadata
• Submissions
  • Submit a paper
  • Revise or withdraw a paper
  • Acceptance and publishing conditions
• About
  • Goals and history
  • News
  • Statistics
  • Contact

Search Advanced search

Paper 2021/849

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

Rei Ueno, Keita Xagawa, Yutaro Tanaka, Akira Ito, Junko Takahashi, and Naofumi Homma

Abstract

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 psuedorandom function (PRF) 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 allows 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 demonstrated 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). The success of the proposed attack against all of these implementations, which include masked hardware based on threshold implementation, confirms its practicality.

Metadata

Available format(s) PDF Category Public-key cryptography Publication info Published elsewhere. IACR-TCHES-2022 Keywords Side-channel analysisFujisaki–Okamoto transformationKey encapsulation mechanismPublic key encryptionPost-quantum cryptographyand Deep learning Contact author(s) rei ueno a8 @ tohoku ac jpkeita xagawa zv @ hco ntt co jpy-tanaka @ riec tohoku ac jpito @ riec tohoku ac jpjunko takahashi fc @ hco ntt co jphomma @ riec tohoku ac jp History 2021-10-15: last of 3 revisions 2021-06-22: received See all versions Short URL https://ia.cr/2021/849 License CC BY

BibTeX Copy to clipboard

@misc{cryptoeprint:2021/849, author = {Rei Ueno and Keita Xagawa and Yutaro Tanaka and Akira Ito and Junko Takahashi and Naofumi Homma}, title = {Curse of Re-encryption: A Generic Power/{EM} Analysis on Post-Quantum {KEMs}}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/849}, year = {2021}, url = {https://eprint.iacr.org/2021/849} } Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.