SHIFT SNARE: Uncovering Secret Keys in FALCON via Single-Trace Analysis

Jinyi Qiu; Aydin Aysu

Paper 2025/146

SHIFT SNARE: Uncovering Secret Keys in FALCON via Single-Trace Analysis

Jinyi Qiu

, North Carolina State University

Aydin Aysu, North Carolina State University

Abstract

This paper presents a novel single-trace side-channel attack on FALCON, a lattice-based post-quantum digital signature protocol recently approved for standardization by NIST. We target the discrete Gaussian sampling operation within FALCON’s key generation scheme and demonstrate that a single power trace is sufficient to mount a successful attack. Notably, negating the results of a 63-bit right-shift operation on 64-bit secret values leaks critical information about the assignment of ‘-1’ versus ‘0’ to intermediate coefficients during sampling. These leaks enable full recovery of the secret key. We demonstrate a ground-up approach to the attack on an ARM Cortex-M4 microcontroller executing both the reference and optimized implementations from FALCON’s NIST round 3 software package. We successfully recovered all of the secret polynomials in FALCON. We further quantify the attacker’s success rate using a univariate Gaussian template model, providing generalizable guarantees. Statistical analysis with over 500,000 tests reveals a per-coefficient success rate of 99.9999999478% and a full-key recovery rate of 99.99994654% for FALCON-512. We verify that this vulnerability is present in all implementations included in FALCON’s NIST submission package. This highlights the vulnerability of current software implementations to single-trace attacks and underscores the urgent need for single-trace- resilient software in embedded systems.

Note: Update: now submitted for peer review in ICCAD 2025. Added Author information

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Post quantum cryptography FALCON Side-channel attack
Contact author(s): jqiu2 @ ncsu edu
aaysu @ ncsu edu
History: 2025-04-28: last of 3 revisions; 2025-01-30: received; See all versions
Short URL: https://ia.cr/2025/146
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2025/146,
      author = {Jinyi Qiu and Aydin Aysu},
      title = {{SHIFT} {SNARE}: Uncovering Secret Keys in {FALCON} via Single-Trace Analysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/146},
      year = {2025},
      url = {https://eprint.iacr.org/2025/146}
}