Keng-Yu Chen, Ming Qing Ching, Jiun-Peng Chen, Bo-Yin Yang

When Masking Multiplication Isn’t Enough: Exploiting Floating-Point Leakage in Falcon’s Pre-Image Computation

Introduction

When masking multiplication isn’t enough: exploiting floating-point leakage in falcon’s pre-image computation. Exploit new floating-point leakage in Falcon's pre-image computation with an improved correlation power analysis (CPA) attack. Recover secret keys efficiently, demonstrating multiplication masking is insufficient.

Abstract

In this paper, we present an improved correlation power analysis (CPA) attack on the pre-image computation of the digital signature scheme Falcon. Our attack exploits new side-channel leakage that multiplication masking schemes fail to protect. To enhance both the efficiency and accuracy of the attack, we develop new theoretical insights for recovering the secret floating-point numbers, which can also be leveraged to improve prior attacks. For mantissa recovery, we identify and correct a flaw in an earlier work and provide a more complete and practical analysis. For exponent recovery, we analyze the distribution of Falcon’s secret key after the fast Fourier transform, reduce the number of required traces, and mitigate false positives. To validate our attack, we conducted two experiments targeting existing countermeasures on floating-point multiplication. In our environment, we successfully recovered the secret key using only around one thousand power traces. Our results demonstrate that protecting floating-point multiplication alone is insufficient to defend Falcon against side-channel attacks. A comprehensive masking including at least floating-point addition is necessary.

Review

This paper presents a significant advancement in correlation power analysis (CPA) attacks targeting the pre-image computation of the Falcon digital signature scheme. The core contribution lies in identifying and exploiting novel side-channel leakage specifically related to floating-point operations that existing countermeasures, particularly those focused on masking multiplication, fail to protect. This work critically evaluates the robustness of current side-channel defenses for Falcon, highlighting a crucial vulnerability that has previously been overlooked or inadequately addressed by protection schemes concentrating solely on arithmetic operations. To enhance the attack's efficacy, the authors develop refined theoretical insights for the recovery of secret floating-point numbers, offering improvements that can benefit prior attacks as well. For mantissa recovery, the paper identifies and rectifies a flaw in earlier research, providing a more rigorous and practical analytical framework. Concurrently, for exponent recovery, the authors leverage an analysis of Falcon’s secret key distribution post-Fast Fourier Transform, which effectively reduces the number of power traces required for a successful attack and mitigates false positives, thereby increasing both the efficiency and accuracy of the key recovery process. The practical impact of this research is demonstrated through experiments targeting existing floating-point multiplication countermeasures. The authors successfully recovered the secret key in their environment using approximately one thousand power traces, a considerably low number for such an attack. This compelling result unequivocally shows that protecting only floating-point multiplication is insufficient to secure Falcon against sophisticated side-channel attacks. The paper concludes with a vital recommendation: a comprehensive masking strategy, extending to include at least floating-point addition, is imperative for adequately defending Falcon implementations against the vulnerabilities exposed by this work.

Full Text

Comments

You need to be logged in to post a comment.