Post-quantum cryptography addresses the threat posed by large-scale quantum computers to current public-key cryptosystems. After an eight-year evaluation process, NIST has standardized ML-KEM, a quantum-resistant scheme for publickey encryption and key encapsulation, whose global deployment is anticipated by 2035. Beyond algorithmic security, the resistance of physical implementations of ML-KEM to sidechannel attacks is important for a secure transition. This paper evaluates the resistance of a software implementation of MLKEM protected against side-channel analysis using masking and shuffling. Despite these countermeasures, we can recover the secret key using only one third of the traces compared to the state-of-the-art attack. Our main contribution is a novel chosenciphertext construction method that 1) circumvents the shuffling countermeasure, and 2) overcomes the inter-device variation problem. This method is applicable not only to ML-KEM, but also to other lattice-based PKE or KEM algorithms. We provide an in-depth analysis of the attack methodology, validate the attack on an ARM Cortex-M4 platform recommended by NIST for benchmarking, and suggest potential countermeasures for hardening ML-KEM implementations against side-channel attacks.

Shuffling is a well-known countermeasure against side-channel attacks. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel attacks more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the long-term secret key was reported. In this paper, we present an attack that can recover the long-term secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decryption algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k∗ l chosen ciphertexts constructed using a new method based on error-correcting codes of length l, where k is the module rank, we recover the long-term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.