FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks

FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks

연구 분야: Cryptography

학회: DAC '21: Proceedings of the 58th Annual ACM/IEEE Design Automation Conference

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.