Secret Key Recovery of FALCON using Simple Power Analysis in Conditional Calculator

초록

Among the NIST-standardized algorithms, FALCON is a lattice-based digital signature scheme that offers strong security and compactness. However, FALCON’s reliance on floating-point arithmetic makes it vulnerable to side-channel attacks. In particular, certain operations in FALCON, such as floating-point conversion and floating-point addition within the FFT transform, may result in data-dependent power consumption patterns. These patterns can be exploited by Simple Power Analysis to extract secret key information, even from a single trace. We present a Simple Power Analysis against the FALCON digital signature scheme, focusing on the Conditional calculator involved in floating-point conversion and floating-point addition. We also analyze the effectiveness of two countermeasures for the Conditional calculator. We propose a post-processing procedure that computes all possible candidates and applies a pruning strategy to eliminate impossible ones. The secret key can be recovered within 0.12 seconds for secret keys generated from a discrete Gaussian distribution and 21.02 seconds for those generated from a uniform distribution. We further propose an advanced post-processing procedure that ranks candidate keys based on their consistency with observed side-channel information, enabling full secret key recovery even when partial information is incorrect. The proposed attack is evaluated with up to 5,000 intentionally corrupted side-channel information entries (≈ 9.3% of the leakage bits); within this range, the correct key was consistently recovered with a 100% success rate. Additionally, we successfully recovered the correct secret key across 1,000 distinct FALCON secret keys. © 2026, Ruhr-University of Bochum. All rights reserved.

키워드