FrodoKEM: Der konservative Fels in der Brandung der Post-Quanten-Kryptografie

Einleitung

Die Post-Quanten-Kryptografie steht unter einem enormen Effizienzgebot. Schlüssel sollen klein sein, Berechnungen schnell, Protokolle schlank. Wer diese Anforderungen nicht erfüllt, hat im Standardisierungswettbewerb des NIST kaum eine Chance – und so hat sich ML-KEM (Kyber) als primärer Standard für quantensichere Schlüsselkapselung durchgesetzt: kompakt, schnell, elegant.

Doch es gibt einen Algorithmus, der sich diesem Effizienzgebot bewusst entzieht. Nicht aus Gleichgültigkeit, sondern aus Überzeugung. FrodoKEM ist die Antwort auf eine Frage, die in der Euphorie um strukturierte Gitterverfahren leicht untergeht: Was, wenn wir uns irren?

Was, wenn die algebraische Struktur, die ML-KEM so effizient macht, eines Tages auch zu seiner Schwachstelle wird? Was, wenn ein kryptoanalytischer Durchbruch die Sicherheitsannahmen von Ring-LWE oder Module-LWE erschüttert – so wie Shor seinerzeit RSA und ECC erschüttert hat?

FrodoKEM gibt auf diese Frage eine klare Antwort: Es verzichtet vollständig auf algebraische Struktur, akzeptiert dafür größere Schlüssel und langsamere Berechnungen – und kauft sich damit ein Sicherheitsvertrauen, das auf einem der am besten untersuchten Probleme der Gitterkryptografie beruht. Es ist kein Kompromiss. Es ist eine Philosophie.

Das Fundament: Plain LWE statt Ring-LWE

Um zu verstehen, warum FrodoKEM so konservativ ist, muss man verstehen, worauf ML-KEM seine Effizienz aufbaut – und was FrodoKEM bewusst anders macht.

ML-KEM basiert auf Module-LWE, einer strukturierten Variante des Learning-with-Errors-Problems. Dabei werden Polynome in einem Restklassenring $\mathbb{Z}_q[x]/(x^n + 1)$ verwendet. Diese Ringstruktur erlaubt es, Matrixmultiplikationen durch schnelle Polynommultiplikation zu ersetzen – beschleunigt durch die Number-Theoretic Transform (NTT). Das Ergebnis sind sehr kleine Schlüssel und sehr schnelle Operationen.

FrodoKEM basiert dagegen auf plain LWE – dem ursprünglichen, unstrukturierten Learning-with-Errors-Problem, das Oded Regev 2005 eingeführt hat. Hier gibt es keinen Ring, keine Polynome, keine algebraischen Abkürzungen. Stattdessen arbeitet FrodoKEM mit echten, zufälligen Matrizen über $\mathbb{Z}_q$.

Das LWE-Problem lässt sich so beschreiben: Gegeben eine zufällige Matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$, einen geheimen Vektor $\mathbf{s} \in \mathbb{Z}_q^n$ und einen kleinen Fehlervektor $\mathbf{e}$, ist es rechnerisch schwer, $\mathbf{s}$ aus $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$ zu rekonstruieren. Das Rauschen – also $\mathbf{e}$ – ist dabei nicht Störfaktor, sondern mathematische Notwendigkeit: Ohne es wäre das System trivial lösbar.

Der entscheidende Unterschied zu Ring-LWE liegt in der Matrix $\mathbf{A}$. Bei strukturierten Verfahren ist $\mathbf{A}$ nicht wirklich zufällig – sie hat eine zyklische oder negativ-zyklische Struktur, die aus einem einzigen Polynom generiert wird. Das ist effizient, aber es bedeutet: Die Sicherheit hängt davon ab, dass diese Struktur keine Angriffsfläche bietet. Bei FrodoKEM ist $\mathbf{A}$ eine echte Zufallsmatrix ohne jede algebraische Eigenschaft. Die Sicherheitsreduktion auf das allgemeine LWE-Problem ist damit direkter und ohne zusätzliche Strukturannahmen.

Die Schlüsselerzeugung: Wie FrodoKEM einen Schlüssel aufbaut

Die Schlüsselerzeugung in FrodoKEM folgt einer eleganten, aber rechentechnisch aufwendigen Logik.

Schritt 1: Matrixgenerierung. Eine große Matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times n}$ wird pseudozufällig aus einem öffentlichen Seed generiert. FrodoKEM erlaubt hier zwei Primitive: AES-128 (im ECB-Modus, ideal für Hardware mit AES-NI-Beschleunigung) oder SHAKE-128 (eine Keccak-basierte XOF, schneller auf Software ohne AES-NI). Der Seed selbst ist öffentlich – die Sicherheit des Systems hängt nicht von der Geheimhaltung von $\mathbf{A}$ ab.

Schritt 2: Fehlersampling. Der private Schlüssel besteht aus zwei Matrizen mit kleinen Einträgen: $\mathbf{S}$ und $\mathbf{E}$, beide aus einer diskreten Gaußverteilung gesampelt. Diese Fehlermatrizen sind das Herzstück der Sicherheit – ihre Einträge sind klein (typischerweise im einstelligen Bereich), aber ihre Existenz macht das System rechnerisch schwer angreifbar.

Schritt 3: Öffentlicher Schlüssel. Der öffentliche Schlüssel ist $\mathbf{B} = \mathbf{A}\mathbf{S} + \mathbf{E} \pmod{q}$. Wer $\mathbf{B}$ und $\mathbf{A}$ kennt, aber nicht $\mathbf{S}$ und $\mathbf{E}$, kann $\mathbf{S}$ nicht rekonstruieren – das ist exakt das LWE-Problem.

Der entscheidende Kostenpunkt liegt in der Matrixmultiplikation $\mathbf{A}\mathbf{S}$. Bei ML-KEM wird diese durch NTT auf $\mathcal{O}(n \log n)$ reduziert. Bei FrodoKEM mit einer echten $n \times n$-Matrix ist es naiv $\mathcal{O}(n^3)$ – in der Praxis optimiert, aber dennoch deutlich teurer. Das ist der direkte Preis der fehlenden algebraischen Struktur.

Kapselung und Dekapselung

Die eigentliche Schlüsselkapselung – also das Aushandeln eines gemeinsamen Geheimnisses – funktioniert in FrodoKEM nach dem Prinzip des Regev-Kryptosystems, angepasst für KEMs.

Kapselung (Sender): Der Sender generiert ebenfalls Fehlermatrizen $\mathbf{S}'$, $\mathbf{E}'$ und $\mathbf{E}''$, berechnet $\mathbf{B}' = \mathbf{S}'\mathbf{A} + \mathbf{E}'$ sowie $\mathbf{C} = \mathbf{S}'\mathbf{B} + \mathbf{E}'' + \text{encode}(\mu)$, wobei $\mu$ die zu kapselnde Nachricht (der Schlüsselmaterial-Seed) ist. Der Ciphertext ist das Tupel $(\mathbf{B}', \mathbf{C})$.

Dekapselung (Empfänger): Der Empfänger berechnet $\mathbf{M} = \mathbf{C} - \mathbf{S}^T\mathbf{B}'$. Durch die LWE-Struktur heben sich die zufälligen Terme fast auf – es bleibt $\text{encode}(\mu)$ plus ein kleiner Fehlterm übrig. Da der Fehler klein ist, kann $\mu$ durch Runden dekodiert werden. Aus $\mu$ wird dann über eine Hash-Funktion der gemeinsame Schlüssel abgeleitet.

Das Runden ist dabei der kritische Schritt: Es funktioniert genau dann, wenn der akkumulierte Fehler klein genug bleibt – was durch die sorgfältige Wahl der Fehlerverteilung und der Parameter garantiert wird.

Die zwei Gesichter: FrodoKEM und eFrodoKEM

FrodoKEM existiert in zwei Varianten, die unterschiedliche Einsatzszenarien adressieren.

eFrodoKEM (Ephemeral) ist für Szenarien optimiert, in denen für jede Sitzung ein frisches Schlüsselpaar erzeugt wird. Der öffentliche Schlüssel wird einmal verwendet und dann verworfen. Das ist das klassische Szenario im TLS-Handshake: Forward Secrecy ist eingebaut, weil es keinen langlebigen privaten Schlüssel gibt, der kompromittiert werden könnte.

FrodoKEM (Salted) adressiert ein subtileres Problem: Multi-Ciphertext-Angriffe. Wenn ein langlebiger öffentlicher Schlüssel für viele Kapselungen wiederverwendet wird, kann ein Angreifer, der viele Ciphertexte sammelt, unter Umständen Informationen akkumulieren. FrodoKEM-Salted begegnet dem, indem ein öffentlicher Salt-Wert in die Schlüsselerzeugung einbezogen wird, der jeden Kapselungsvorgang einzigartig macht – ohne die Sicherheitsstruktur zu verändern.

Die Wahl zwischen beiden Varianten ist damit keine Geschmacksfrage, sondern eine Frage des Einsatzszenarios: Kurzlebige Schlüssel in ephemeren Protokollen nehmen eFrodoKEM. Langlebige Public Keys in Infrastrukturen, die viele Kapselungen pro Schlüsselpaar erleben, nehmen FrodoKEM-Salted.

Parameter: Drei Sicherheitsstufen, zwei Primitive

FrodoKEM kommt in drei Parametersätzen, die den NIST Security Categories 1, 3 und 5 entsprechen:

Variante	NIST Level	Äquivalent
FrodoKEM-640	1	AES-128
FrodoKEM-976	3	AES-192
FrodoKEM-1344	5	AES-256

Jeder Parametersatz ist außerdem in zwei Primitive-Varianten verfügbar: AES und SHAKE. AES-NI-fähige Hardware – also praktisch jeder moderne Server-Prozessor und die meisten Smartphones – beschleunigt die AES-Variante erheblich. Ohne Hardware-Beschleunigung ist SHAKE typischerweise die schnellere Wahl. Beide Varianten sind sicherheitsäquivalent; die Wahl ist eine reine Implementierungsentscheidung.

Warum das BSI anders denkt als NIST

Dass NIST ML-KEM als primären Standard gewählt hat und FrodoKEM nicht, ist keine Ablehnung von FrodoKEM. Es ist eine Priorisierungsentscheidung zugunsten von Effizienz und breiter Einsetzbarkeit.

Das BSI hat diese Abwägung anders getroffen. In seinen Technischen Richtlinien empfiehlt das BSI FrodoKEM auf Level 3 und 5 explizit für Anwendungen mit langfristigen Vertraulichkeitsanforderungen – also genau die Szenarien, die für „Store Now, Decrypt Later"-Angriffe besonders anfällig sind. Wer Daten schützt, die in zehn oder zwanzig Jahren noch geheim sein müssen, fährt mit FrodoKEM auf Nummer sicher.

Das ist auch der Kontext, in dem Classic McEliece und FrodoKEM oft gemeinsam genannt werden: Beide sind BSI-Favoriten für konservative, langfristige Sicherheit. Classic McEliece basiert auf code-basierter Kryptografie und ist noch konservativer als FrodoKEM – mit noch größeren Schlüsseln, dafür aber einer fast fünfzigjährigen Sicherheitshistorie der zugrundeliegenden Goppa-Codes. FrodoKEM und Classic McEliece sind damit keine Konkurrenten zu ML-KEM, sondern Ergänzungen – für Kontexte, in denen Effizienz gegenüber maximalem Sicherheitsvertrauen zurücktritt.

Dass neben dem BSI auch die französische ANSSI und die niederländischen Behörden NLNCSA und AIVD FrodoKEM empfehlen, ist kein Zufall. Es ist ein koordiniertes Signal europäischer Sicherheitsbehörden: Wir vertrauen strukturierten Gittern – aber wir wollen eine Rückfalloption, die keine algebraischen Annahmen macht.

Implementierung: Einfachheit als Sicherheitsmerkmal

Ein oft übersehener Vorteil von FrodoKEM ist seine Implementierungsfreundlichkeit. Strukturierte Gitterverfahren wie ML-KEM erfordern eine korrekte Implementierung der NTT, sorgfältiges Handling von Polynomringen und komplexe Modularitätseigenschaften. Fehler in diesen Bereichen können zu Seitenkanalangriffen führen – Timing-Angriffe, Power-Analysen, Cache-Timing.

FrodoKEM arbeitet ausschließlich mit Matrixmultiplikationen und einfachem Fehlersampling über ganzzahligen Vektoren. Die Operationen sind geradlinig, gut parallelisierbar und von Natur aus leichter in konstanter Zeit zu implementieren. Das ist bei sicherheitskritischen Implementierungen kein Luxus, sondern eine grundlegende Anforderung: Algorithmen, die in variabler Zeit laufen, lecken Informationen über geheime Werte.

Dass FrodoKEM sich natürlich in konstanter Zeit implementieren lässt, ist damit nicht nur ein akademisches Detail. Es ist ein praktischer Vorteil in der realen Welt der Embedded-Systeme, HSMs und Smartcards, wo Seitenkanalresistenz nicht nachträglich eingebaut, sondern von Anfang an in den Algorithmus hineindesigned sein muss.

Fazit: Die Versicherungspolice der Post-Quanten-Welt

FrodoKEM ist nicht der schnellste Algorithmus. Es ist nicht der kompakteste. Und es ist nicht der, den die meisten Entwickler als ersten in ihre Anwendungen integrieren werden.

Aber es ist der Algorithmus, dem europäische Sicherheitsbehörden vertrauen, wenn es darauf ankommt. Der, der keine algebraischen Abkürzungen nimmt. Der, der im Falle eines kryptoanalytischen Durchbruchs gegen strukturierte Gitter noch stehen wird.

In einer Welt, in der Krypto-Agilität zur Pflicht wird und Migrationsentscheidungen für die nächsten zwanzig Jahre getroffen werden, ist FrodoKEM die Antwort auf eine einfache Frage: Was, wenn wir uns irren?

Die Antwort lautet: Dann haben wir FrodoKEM.