Avengers assemble! Supervised learning meets lattice reduction

Overview & Synopsis

In this paper, we attack Kyber's key-generation algorithm using power analysis and lattice reduction. More specifically, we target the Centered Binomial Distribution (CBD) sampler which generates the secret data of the underlying Learning With Error (LWE) instance. From a side-channel perspective, our attack uses a single trace, leveraging classifiers developed through supervised learning. We enhance the classification with the AdaBoost strategy, which provides more reliable results and exploitable statistics, enabling the identification of error-free classified samples. In optimal scenarios, our classifiers, combined with the outputted statistics, allow us to recover up to 68% of the secret key's coefficients from the trace, ensuring that these recovered coefficients are error-free. In such cases, we show that the secret keys can be recovered by Gaussian elimination over a finite field in a few seconds. For less advantageous cases, we assess the block-size in lattice reduction that would complete the key recovery, providing a fine-grained trade-offs between the correctly guessed proportion and the block-size, based on standard estimates. Finally, we conducted large-scale experiments, from power traces to secret key recovery (for most of the instances) under a threshold of 18 hours, targeting all three Kyber's security levels. Our average rate of success across all security level is more than 96%.