FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks
Authors:
- 5 December 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 691-696
Abstract
This paper proposes the first side-channel attack on FALCON—a NIST Round-3 finalist for the post-quantum digital signature standard. We demonstrate a known-plaintext attack that uses the electromagnetic measurements of the device to extract the secret signing keys, which then can be used to forge signatures on arbitrary messages. The proposed attack targets the unique floating-point multiplications within FALCON’s Fast Fourier Transform through a novel extend-and-prune strategy that extracts the sign, mantissa, and exponent variables without false positives. The extracted floating-point values are then mapped back to the secret key’s coefficients. Our attack, notably, does not require pre-characterizing the power profile of the target device or crafting special inputs. Instead, the statistical differences on obtained traces are sufficient to successfully execute our proposed differential electromagnetic analysis. The results on an ARM-Cortex-M4 running the FALCON NIST’s reference software show that approximately 10k measurements are sufficient to extract the entire key.Keywords
Funding Information
- National Science Foundation
This publication has 17 references indexed in Scilit:
- Side-Channel Attacks on BLISS Lattice-Based Signatures2017
- Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption2017
- Chosen ciphertext Simple Power Analysis on software 8-bit implementation of ring-LWE encryption2016
- Power Analysis Attacks and Countermeasures on NTRU-Based Wireless Body Area NetworksKSII Transactions on Internet and Information Systems, 2013
- Countermeasures against Power Analysis Attacks for the NTRU Public Key CryptosystemIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2010
- Correlation Power Analysis with a Leakage Model2004
- Template Attacks2003
- Electromagnetic Analysis: Concrete Results2001
- Differential Power Analysis1999
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Review, 1999