Cryptology ePrint Archive: Report 2021/874

Chosen-ciphertext Clustering Attack on CRYSTALS-KYBER using the Side-channel Leakage of Barrett Reduction

Bo-Yeon Sim and Aesun Park and Dong-Guk Han

Abstract: This study proposes a chosen-ciphertext side-channel attack against a lattice-based key encapsulation mechanism (KEM), the third-round candidate of the national institute of standards and technology (NIST) standardization project. Unlike existing attacks that target operations such as inverse NTT and message encoding/decoding, we target Barrett Reduction in the decapsulation phase of CRYSTALS-KYBER to obtain a secret key. We show that a sensitive variable-dependent leakage of Barrett Reduction exposes an entire secret key. The results of experiments conducted on the ARM Cortex-M4 microcontroller accomplish a success rate of 100%. We only need six chosen ciphertexts for KYBER512 and KYBER768 and eight chosen ciphertexts for KYBER1024. We also show that the m4 scheme of the pqm4 library, an implementation with the ARM Cortex-M4 specific optimization (typically in assembly), is vulnerable to the proposed attack. In this scheme, six, nine, and twelve chosen ciphertexts are required for KYBER512, KYBER768, and KYBER1024, respectively.

Category / Keywords: public-key cryptography / Lattice-based cryptography, key decapsulation mechanism, Barrett reduction, side-channel attack, chosen-ciphertext attack

Date: received 25 Jun 2021, last revised 29 Jun 2021

Contact author: sboyeon37 at etri re kr, aesons at dssc mil kr, christa at kookmin ac kr

Available format(s): PDF | BibTeX Citation

Version: 20210629:122724 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]