Paper 2024/060

The Insecurity of Masked Comparisons: SCAs on ML-KEM’s FO-Transform

Abstract

NIST released the draft standard for ML-KEM, and we can expect its widespread use in the embedded world in the near future. Several side-channel attacks have been proposed, and one line of research has focused on attacks against the comparison step of the FO-transform. A work published at TCHES 2022 stressed the need for secure higher-order masked comparisons beyond the $t$-probing model and proposed a higher-order masked comparison method. Subsequently, D'Anvers, Van Beirendonck, and Verbauwhede improved upon the performance of several previous proposals; their higher-order masked algorithm currently achieves the highest performance for masked comparisons. In this work, we show that while this proposal is secure in the $t$-probing model, its security in practice is questionable. We first propose an approximate template attack that requires only a small number of traces for profiling and has an exceptionally high noise tolerance. We demonstrate that, without knowledge of the targeted values, a vertical analysis of the distribution of certain points of interest can replace the profiling phase. Finally, we explain how a decryption failure oracle may be constructed from a single trace. We prove that these attacks are not affected by higher masking orders for noise levels that by far prevent previous profiled attacks on ML-KEM. Further, we provide simulations showing that even under extreme noise levels, the attacks are not prevented by realistic masking orders. Additionally, we carry out the attacks on multiple physical devices to stress the practicality of our attack. We discuss the underlying causes for our attack, demonstrate the difficulty of securing the FO-transform in ML-KEM, draw conclusions about the (in-)sufficiency of $t$-probing security in this context, and highlight an open gap in securing ML-KEM on embedded devices.