Post-Quanten-Krypto: BSI besorgt über McEliece

Classic McEliece ist eines der ältesten Schlüsselaustauschverfahren, das als quantensicher aufgefasst wurde. Es sollte auch dann noch Sicherheit bieten, wenn Quantencomputer die herkömmlichen Verfahren wie RSA und Diffie-Hellman knacken können. Jüngste Erkenntnisse säen jedoch Zweifel an der Widerstandsfähigkeit von Classic McEliece gegen Angriffe, die gar keine Quantencomputer benötigen. Deshalb rät das BSI jetzt vom Einsatz bei neuen Post-Quantum-Projekten ab. Aktuelle Implementierungen seien aber noch nicht praktisch angreifbar – vor allem, wenn sie gemäß den BSI-Empfehlungen hybrid mit einem der klassischen Key-Exchange-Verfahren kombiniert werden.

Der schnelle Fall des Klassikers

Classic McEliece ist ein Kryptoverfahren auf Basis fehlerkorrigierender Codes, das eigentlich als besonders sicher galt. Sein Nachteil war primär, dass es sehr große öffentliche Schlüssel benötigt, weshalb es auch von der NIST aus dem PQC-Standardisierungsverfahren ausgeschlossen wurde. Erst im Juni hat die ISO das Verfahren in den Rang eines internationalen Standards erhoben.

Doch nur kurze Zeit später erschien das Paper Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (PDF), das Zweifel an Grundannahmen von McEliece säte. Die Forscher zeigten, dass die Analyse der zugrundeliegenden algebraischen Struktur keinen exponentiellen, sondern nur quasipolynomiellen Zeitaufwand erfordert. Sie konnten die Komplexität eines – immer noch theoretischen – Angriffs von deutlich über 2²⁰⁰ Bit-Operationen auf etwa 2¹¹⁴ senken. Damit war McEliece zwar nicht gebrochen, aber doch deutlich angeknackst.

Das hat offenbar weitere Forschung inspiriert. Kürzlich veröffentlichte Stephen A. Weis von Anthropic ein Paper, das die Schätzungen noch weiter nach unten (PDF) korrigiert. Bei ihm sind es im schlimmsten Fall nur noch 2⁹⁴ bis 2¹⁰² Bit-Operationen. Damit landet man bei einer Sicherheit, die ganz grob nur noch jener von AES-128 entspricht, statt der ursprünglich versprochenen von AES-256 (das symmetrische Krypto-Verfahren AES wird gerne als Maßstab für Sicherheit verwendet).

Das BSI wird aktiv

Das BSI hat diese Entwicklung nicht nur verfolgt, sondern selbst analysiert. Die Krypto-Experten der Behörde halten offenbar nicht nur die Ergebnisse für valide, sondern weitere Verbesserungen der Angriffe für möglich und sogar für „zu erwarten“. Deshalb greift das Bundesamt zu der ungewöhnlichen Maßnahme, von der weiteren Nutzung eines bisher empfohlenen Krypto-Verfahrens abzuraten. Denn in der Technischen Richtlinie TR-02102-1 Kryptographische Verfahren: Empfehlungen und Schlüssellängen ist Classic McEliece seit 2020 als Empfehlung aufgeführt; die Ausgabe vom Januar 2026 stuft es noch als sicher ein – allerdings in Kombination mit einem klassischen Kryptoverfahren.

Das soll sich in der nächsten TR-Iteration, die Anfang 2027 ansteht, ändern, erklärt das BSI jetzt bereits vorab. Doch offenbar mag es nicht einmal mehr so lange warten und warnt schon jetzt, dass zumindest neue Projekte Classic McEliece nicht mehr nutzen sollten: „Es wird dazu geraten, für die Schlüsseleinigung FrodoKEM, ML-KEM oder HQC (sobald der entsprechende Standard veröffentlicht ist) gemäß den Empfehlungen der TR-02102-1 zu verwenden“, heißt es in den Hinweisen zu aktuellen Entwicklungen um Classic McEliece (PDF).

Bereits existierende Projekte müssten nicht zwingend handeln. Die Angriffe stellen noch keine konkrete Gefahr dar – insbesondere dann nicht, wenn man McEliece wie empfohlen Hybrid einsetze. Gemeint ist die Kombination mit einem klassischen Verfahren wie ECDH, beispielsweise mit Curve25519/X25519. Dabei bleibe zumindest die Sicherheit des klassischen Verfahrens erhalten. Das klingt nicht gerade beruhigend für die Zukunft der PQC-Komponente.

Mehr Krypto-Agilität

Insgesamt zeigt dieses Beispiel einmal mehr, wie schnell PQC-Verfahren in Ungnade fallen können, und dass man sich bei der anstehenden Umstellung auf quantensichere Kryptografie nicht auf ein einzelnes Verfahren verlassen darf. Wichtig ist nicht nur der kombinierte Einsatz mit klassischen Verfahren, sondern auch die Fähigkeit, einzelne Verfahren mit möglichst wenig Aufwand gegen andere auszutauschen.

Diese Forderung nach Krypto-Agilität ist in den vergangenen Jahren angesichts voranschreitender Standardisierung von PQC-Verfahren zu Unrecht etwas in den Hintergrund getreten. Warum sollte man sich die Mühe machen, eine agile Infrastruktur zu bauen, wenn es doch verlässliche Standards gibt? Weil auch scheinbar verlässliche Standards vielleicht schon nächstes Jahr ausgemustert werden müssen – das zeigt der Fall McEliece.