GyuSang Kim, JeongHwan Lee, Myeonghoon Lee, Seokhie Hong, HeeSeok Kim

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

Introduction

Secret key recovery of falcon using simple power analysis in conditional calculator. Simple Power Analysis (SPA) attack on FALCON digital signatures. Recovers secret keys by exploiting floating-point operations in conditional calculators. Countermeasures analyzed.

Abstract

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.

Review

This paper presents a critical analysis of the FALCON digital signature scheme, a NIST-standardized lattice-based algorithm recognized for its strong security and efficiency. The authors effectively highlight a significant vulnerability in FALCON: its reliance on floating-point arithmetic, which can introduce data-dependent power consumption patterns. Specifically, the work focuses on how Simple Power Analysis (SPA) can exploit these patterns during operations like floating-point conversion and addition within the Fast Fourier Transform (FFT) on a component referred to as the "Conditional calculator." This premise establishes a clear and important security concern for a widely adopted cryptographic standard. The methodology involves a detailed Simple Power Analysis targeting the identified vulnerable operations within the Conditional calculator. A key contribution is the proposal of two distinct post-processing procedures designed to enhance key recovery. The first procedure computes all possible key candidates and applies a pruning strategy to eliminate invalid ones. Building upon this, an advanced post-processing technique is introduced that ranks candidate keys based on their consistency with observed side-channel information, enabling successful secret key recovery even when partial information might be erroneous. The paper also includes an analysis of countermeasures, demonstrating a comprehensive approach to both attack and defense. The results presented are compelling and underscore the severity of the attack. The proposed SPA can recover secret keys remarkably quickly, within 0.12 seconds for keys generated from a discrete Gaussian distribution and 21.02 seconds for those from a uniform distribution. Crucially, the advanced post-processing procedure exhibits high robustness, achieving a 100% success rate in recovering the correct key even when up to 9.3% of the side-channel information entries were intentionally corrupted. Furthermore, the attack was successfully demonstrated across 1,000 distinct FALCON secret keys, validating its broad applicability. This research provides a crucial wake-up call for implementers of FALCON, emphasizing the urgent need for robust side-channel countermeasures, particularly concerning floating-point operations, to ensure the integrity of this post-quantum cryptographic standard.

Full Text

Comments

You need to be logged in to post a comment.