An Improved Two-Step Attack on Kyber

After three rounds of post-quantum cryptography (PQC) strict evaluations conducted by the national institute of standards and technology (NIST), CRYSTALS-Kyber was successfully selected in July 2022 and standardized in August 2024. It becomes urgent to further evaluate Kyber's physical security for the upcoming deployment phase. In this brief, we present an improved two-step attack on Kyber to quickly recover the full secret key, s, by using much fewer energy traces and less time. In the first step, we use the correlation power analysis (CPA) to obtain a portion of guess values of s with a small number of energy traces. The CPA is enhanced by utilizing both the Pearson and Kendall's rank correlation coefficients and modifying the leakage model to improve the accuracy. In the second step, we adopt the lattice attack to recover s based on the results of CPA. The success rate is largely built up by constructing a trial-and-error method. We implement the proposed attack for the reference implementation of Kyber512 (4 128-value groups of s) on ARM Cortex-M4 and successfully recover a 128-value group of s in about 9 minutes using a 16-core machine. Additionally, in that case, we only cost at most 60 CPA guess values for a group and 15 power traces for a guess.