Paper 2025/2159

One Fell Swoop: A Single-Trace Key-Recovery Attack on the Falcon Signing Algorithm

Abstract

Falcon, a lattice-based signature scheme selected for NIST post-quantum standardization, is notable for its compact signature size alongside a complex signing procedure involving extensive floating-point arithmetic. Prior side-channel attacks on Falcon, while demonstrating vulnerabilities, have consistently required a large number of power traces for successful key recovery; this critical efficiency gap means previously reported attacks are often impractical in real-world scenarios where trace collection is limited. This paper presents a new single-trace attack on the Falcon. We identify and exploit novel leakage points within the floating-point conversion and Fast Fourier Transform (FFT) routines during the secret key expansion, which allow us to progressively partition the possible values of the secret key coefficients. By identifying a sufficient number of these coefficients, we establish a system of linear equations that can be solved to recover the entire secret key. Our attack is particularly critical for the \texttt{sign\_dyn} design---the memory-efficient implementation adopted in important cryptographic libraries and reference implementations---as it executes key expansion during every signature operation. We emphasize that this is the \textbf{first single-trace attack on the Falcon signing procedure itself}, providing a more compelling threat scenario than previous work. We validate our attack on an ARM Cortex-M4 microcontroller, demonstrating a 100\% key recovery success rate with just a single power trace for both Falcon-512 and Falcon-1024 in both signing designs—\texttt{sign\_tree} and \texttt{sign\_dyn}, compiled at the \texttt{-O0} level. While the \texttt{-O3} optimization level mitigates some leakages, our multi-trace attack remains effective in the practically used \texttt{sign\_dyn} design, recovering 80 out of 100 Falcon-512 keys with only 5 traces. Our findings expose a critical implementation vulnerability in Falcon, highlighting the urgent necessity of integrating countermeasures to protect Falcon in real-world applications.