Chosen-Ciphertext Clustering Attack on CRYSTALS-KYBER Using the Side-Channel Leakage of Barrett Reduction

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 targetBarrett~reductionin the decapsulation phase ofCRYSTALS-KYBERto obtain a secret key. We show that a sensitive variable-dependent leakage ofBarrett~reductionexposes 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 forKYBER512andKYBER768and eight chosen ciphertexts forKYBER1024. We also show that them4scheme of thepqm4library, 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 forKYBER512,KYBER768, andKYBER1024, respectively.