Does Floating-Point Sink Falcon? | FORTRESS Expert Review #2
Introduction
Welcome back to the Expert Review series, where, together with FORTRESS’s consortium, we delve into the dynamic world of cybersecurity to bring you unbiased and detailed analyses from seasoned professionals. If you missed our previous edition, check it out here.
Among the standards pushed by the NIST for post-quantum digital signatures, Falcon, a.k.a. FN-DSA, is still in a public review stage before the effective standardization process by the NIST to produce the FIPS 206 (FIPS 206). Falcon offers several advantages compared to other post-quantum digital signatures: a short signature size, a fast signing process, and is based on the “hash-and-sign” paradigm. But like any cryptographic algorithm, a Falcon signature implementation does not escape the side-channel threat if no effort is taken to investigate implementation choices regarding hardware attacks. In this review, we take a look at a side-channel attack targeting a Falcon signature implementation specially designed for embedded devices.
About the paper (TL;DR)
In “One Fell Swoop: A Single-Trace Key-Recovery Attack on the Falcon Signing Algorithm”, K. Li et al. introduced a key-recovery attack from a few signing traces, or a single trace under some assumptions about the compilation. From leakages related to floating-point conversions and Fast Fourier Transform (FFT) operations, the attacker derives some of the secret key coefficients. Helped by the lattice structure, the whole key is recovered as the solution of a set of linear equations built using the recovered coefficients.
Let’s dive in…
Our Expert Review
What was studied?
Side-channel analysis of Falcon has already received significant attention. Most existing attacks require several thousand signature traces to recover the signing key. While a pre-existing single-trace attack existed, it focused solely on key generation (KeyGen). However, due to memory constraints on embedded devices, storing a pre-expanded key is often unfeasible, making the on-the-fly key expansion (sign_dyn) the standard choice.
The “One Fell Swoop” attack targets this very expansion—which performs floating-point conversions and FFT multiplications—to extract leakages from the secret coefficients. In a profiled setting, once the leakage model is established via template or machine learning attacks, the attacker exploits floating-point operations to determine the partition to which each coefficient belongs to. Once these partitions are sufficiently refined and more than half of the coefficients are recovered, the mathematical properties of the NTRU lattice structure are leveraged to reconstruct the entire secret key.
The major contributions of the paper are: presenting the first single-trace attack on Falcon’s signing process, demonstrating how to leverage leakages in floating-point arithmetic, and highlighting how a key memory-saving optimization introduces a critical vulnerability. The single-trace attack, alongside a multi-trace variant designed to handle noise, was validated on a real STM32F405 microcontroller.
Why is it important?
As the standardization process of FN-DSA is currently underway, feedback regarding implementation vulnerabilities during this active review phase is highly valuable. This work, by demonstrating an effective attack on floating-point arithmetic, advocates for specification adjustments to address the root causes of side-channel leakage, while urging designers to adopt rigorous mitigation strategies such as masking. Recently, another devastating single-trace attack has emerged, targeting a specific constant-time implementation of the Number Theoretic Transform (NTT). By employing a forward-and-backward pruning strategy, this attack significantly reduces the complexity of subsequent lattice basis reduction algorithms to recover Falcon’s private signing key.
Expanding our understanding of these diverse physical vulnerabilities is crucial to preventing insecure implementation choices that could otherwise compromise the practical cryptographic resistance of resource-constrained devices.
Which new insights have been contributed, and how significant are they?
While the earliest attacks on Falcon focused on the Gaussian sampler, this article pinpoints floating-point arithmetic and the FFT as major sources of leakage that are difficult to mitigate. It also demonstrates, once again, that ensuring arithmetic operations run in constant-time is not sufficient on its own, and should not be the sole hardware security metric when selecting new cryptographic standards.
The dynamic expansion of the secret key on constrained devices significantly increases the attack surface. This not only degrades side-channel resistance but also threatens overall performance, in light of the heavy countermeasures now required. Indeed, because this attack can succeed with a single trace—once an appropriate characterization of the leakage model is obtained—the range of viable countermeasures is highly constrained.
Furthermore, by incorporating Maximum Likelihood Estimation (MLE) and Information Set Decoding (ISD), the multi-trace variant introduces excellent error tolerance while keeping the number of required attack traces to a bare minimum. In this context, recent efforts to develop a fixed-point version of Falcon (c.f., Braga et al., Toward a Secure Fixed-Point Implementation of the Falcon Signature Scheme) will be essential to bypass the massive performance overhead associated with masking floating-point operations.
How practical are the results?
Demonstrating the attack on the specific sign_dyn implementation—which is designed for constrained devices and serves as a reference for several cryptographic libraries—makes the results of this work highly valuable for developers deploying Falcon. Additionally, the side-channel evaluation platform used by the authors is standard and widely deployed, making their physical validation highly realistic.
Reducing the required number of traces to a bare minimum (and even to a single trace in ideal conditions) significantly increases the practical threat of this attack compared to prior works that required thousands of traces. Furthermore, even in the presence of noise, which increases the required number of traces and introduces errors in the recovered key fragments, the authors proposed a post-processing phase so that the attack remains extremely efficient on currently available standard computers. This way, despite the noise, the post-processing achieves excellent key recovery rates for both Falcon-512 and Falcon-1024.
When is the impact expected?
Since Falcon is still in its public review and finalization phase, there is currently a low probability that vulnerable implementations have already been widely deployed in the field. Setting aside developers who are less familiar with side-channel analysis, the real-world impact on applications is a matter of mitigating this single-trace attack with an effective, masked implementation.
In the context of RoT, when the services are provided by an embedded device, this attack is a real threat to take into account.
While the use of fixed-point arithmetic is not a defense in itself, it should significantly lower the performance overhead of implementing masking countermeasures, and its adoption in the standard would certainly be a good thing. Fortunately, the timeline for the final publication of the standard leaves ample room for the cryptographic community to develop side-channel-resistant implementations prior to widespread adoption. Keeping the community aware of this single-trace attack is therefore essential to minimize the risk of deploying vulnerable implementations on constrained devices.
What’s next?
Stay tuned for more write-ups on other modern embedded cryptography articles in the upcoming episodes of the FORTRESS Expert Review.
