Paper 2021/874 Original: eprint.iacr.org/2021/874 ↗

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

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.