On the physical security of falcon

Abstract

Falcon ist von NIST zur Standardisierung als Post-Quanten digitales Signaturverfahren ausgewählt worden. Zwar sind bereits mehrere Angriffe auf Falcon publiziert worden, die auf Schwachstellen der Implementierung abzielen, jedoch ist die physische Sicherheit des Verfahrens noch nicht allgemein untersucht worden. Wir stellen eine Analyse der physischen Sicherheit des Falcon Signaturverfahrens vor, die sowohl Angriffe aus früheren Publikationen, als auch neue Schwachstellen enthält und in die die mathematischen Grundlagen des Verfahrens (zum Beispiel die Fast Fourier Transformation, diskrete Normalverteilungen und ein Turm von Körpern) miteinfließen. Weiters betrachten wir einen der neuen Angriffsvektoren, NarrowSampling, genauer. Wir simulieren einen Angriff, der auf einer Parallelepiped-Lernmethode aufbaut, die auf eine Signaturverteilung mit veringerter Standardabweichung angewendet wird. Jede einzelne Phase des Angriffs wird analysiert und der Einfluss der wichtigsten Angriffsparameter wird gemessen und evaluiert. Für Falcon Parametersets mit reduzierter Sicherheit gelingt es uns, damit den vollständigen privaten Schlüssel zu bestimmen.

Falcon has been selected for standardization by NIST as a post-quantum digital signature scheme. Although there have been several published attacks against Falcon that target vulnerabilities on the implementation side, the physical security of the scheme has not been thoroughly studied yet. We present a broad analysis of the physical security of the Falcon signature scheme that includes attacks from prior publications as well as novel vulnerabilities and takes into account the mathematical foundations of the scheme, such as the Fast Fourier Transform, discrete Gaussian distributions and a tower of fields. Additionally, we closely investigate one of the new attack vectors, NarrowSampling. We simulate a fault injection attack based on a parallelepiped learning technique applied to a signature distribution with lowered standard deviation. Each individual phase of the attack is analyzed and the influence of the most important attack parameters is measured and evaluated. For Falcon parameter sets with reduced security we are able to fully recover the secret key.