Das Bundesamt für Sicherheit in der Informationstechnik (BSI) rät davon ab, neue Systeme auf Classic McEliece aufzubauen – einem der ältesten Post-Quanten-Schlüsselvereinbarungsverfahren. Grund sind drei Forschungsgruppen, die unabhängig voneinander geschätzt haben, dass sich die geheimen Schlüssel weit günstiger zurückgewinnen lassen als die vom Verfahren beanspruchten Sicherheitsniveaus.

In einem auf den 1. Oktober datierten Hinweis erklärte das BSI, das Jahr 2026 habe „deutliche Fortschritte" in der Kryptoanalyse des codebasierten Key-Encapsulation-Mechanismus gebracht. Das Amt empfiehlt derzeit, Classic McEliece „für Neuentwicklungen sowie bei der Planung neuer kryptographischer Anwendungen nicht zu verwenden". Zugleich betonte es, die bisherigen Ergebnisse ermöglichten keinen praktischen Angriff auf die in der Technischen Richtlinie TR-02102-1 empfohlenen Parametersätze – Weiterentwicklungen seien aber „denkbar und zu erwarten".

Der schnelle Fall eines Klassikers

Classic McEliece geht auf Robert McEliece' Public-Key-Kryptosystem von 1978 zurück, das einen binären Goppa-Code in einem großen öffentlichen Schlüssel verbirgt. Sein langjähriger Nachteil war die Schlüsselgröße: Die fünf wichtigsten Parametersätze tragen öffentliche Schlüssel von etwa 261 KB bis 1,36 MB, die Chiffrate liegen zwischen 96 und 208 Byte. Deshalb nahm die NIST das Verfahren nicht in ihr zentrales Post-Quanten-Standardisierungsverfahren auf und wählte im März 2025 stattdessen HQC als codebasiertes Backup zu ML-KEM. Dennoch galt das Verfahren als konservative Wahl, und die ISO nahm es im Juni 2026 – gemeinsam mit ML-KEM und FrodoKEM – in ihre Norm für asymmetrische Chiffren auf (ISO/IEC 18033-2 Amendment 2). Das BSI führte es seit 2020 als Empfehlung, allerdings nur in Kombination mit einem klassischen Verfahren.

Was sich in zehn Wochen änderte

Der Ärger begann am 7. August: Ashrujit Ghoshal (IIT Madras), Yuval Ishai (Technion und AWS) sowie Aayush Jain und Nuozhou Sun (Carnegie Mellon University) veröffentlichten eine beweisbare Methode, um einen Classic-McEliece-Public-Key von einer Zufallsmatrix zu unterscheiden – geschätzt auf 2^114 bis 2^124 Bitoperationen und damit unter den Kosten der generischen Dekodierung, gegen die die Parameter ausgelegt wurden. In der ersten Fassung brach das Paper das Verfahren nicht. Eine Revision vom 27. August ergänzte jedoch Details eines heuristischen Schlüsselrückgewinnungsalgorithmus – und das ist etwas anderes: Wer den privaten Schlüssel erlangt, kann jede an ihn gerichtete Chiffre entschlüsseln.

Bis Mitte September veröffentlichten drei Gruppen Schätzungen zur Schlüsselrückgewinnung, die das beanspruchte Sicherheitsniveau jedes Parametersatzes unterbieten. Ghoshal und seine Koautoren veranschlagen ihren eigenen Algorithmus mit 2^130 bis 2^149 Bitoperationen; Markku-Juhani O. Saarinen von der Universität Tampere bezifferte eine Variante desselben Angriffs mit etwa 2^127 bis 2^145; Stephen A. Weis von Anthropic nennt 2^94 bis 2^102. Diese Werte liegen unter den AES-Schlüsselsuchschwellen, die die NIST als Referenz verwendet: 2^143 für AES-128, 2^207 für AES-192 und 2^272 für AES-256. Rechnet man Weis' Angriff mit Kostenmodellen aus dem Sicherheitsleitfaden des Classic-McEliece-Teams den Speicher hinzu, bleiben es noch etwa 2^110 bis 2^128.

Noch kein praktischer Bruch

Niemand hat öffentlich einen Schlüssel für einen echten Classic-McEliece-Parametersatz zurückgewonnen oder eine Chiffre entschlüsselt, und die Angriffe lassen sich auf vorhandener Hardware nicht ausführen. Weis' Lauf gegen den kleinsten Satz würde rund 2^93 Bit durch ein 28-Tebibyte-Array bewegen; die größeren Sätze benötigen bis zu 540 TiB. Die einzigen durchgängigen Erfolge gelten Spielzeugcodes aus einer Challenge von 2023 – weit kleiner als jeder eingesetzte Parametersatz.

Das Designteam widerspricht. Daniel J. Bernstein argumentierte zunächst für das Team, später in als persönliche Ansicht gekennzeichneten Beiträgen, der ursprüngliche Distinguisher greife kein Sicherheitsziel an, das das Verfahren je beansprucht habe; Bitoperationszählungen ignorierten Kosten für Datenbewegung und parallele Hardware, und kein Nationalstaat könne die Angriffe ausführen. Am 30. September schrieb er, die Papiere hätten seine Einschätzung nicht geändert, dass ML-KEM ein höheres Risiko trage als Classic McEliece. Den Klartextrückgewinnungsweg des Papers veranschlagt das Team mit etwa 2^266 Operationen gegen mceliece6960119.

Was Betreiber tun sollten

Nach Einschätzung des BSI muss nichts überstürzt aus laufenden Systemen entfernt werden. Eine hybride Konfiguration, die Classic McEliece mit einem klassischen Verfahren wie X25519 kombiniert, bietet weiterhin mindestens die Sicherheit der klassischen Komponente. Der Haken ist die „Harvest-now, decrypt-later"-Exposition: Genau die klassische Hälfte wäre es, die ein künftiger Quantencomputer bricht. Ist die Post-Quanten-Komponente schwächer als angepriesen, verlieren aufgezeichnete Daten den angestrebten Langfristschutz.

Für die Schlüsselvereinbarung empfiehlt das BSI FrodoKEM oder ML-KEM sowie HQC, sobald ein Standard vorliegt; keines der drei sei von den neuen Angriffen betroffen. Die Einträge zu Classic McEliece in der TR-02102-1 sollen Anfang 2027 überarbeitet werden. Bereits im Einsatz ist das Verfahren unter anderem bei Mullvad VPN, das Classic McEliece mit ML-KEM für WireGuard-Tunnel kombiniert, sowie bei Rosenpass, das mceliece460896 für statische Authentifizierungsschlüssel nutzt.

Die übergeordnete Lehre heißt Krypto-Agilität – die Fähigkeit, einen Algorithmus mit geringem Aufwand gegen einen anderen zu tauschen. Post-Quanten-Verfahren können binnen Wochen in Ungnade fallen, wie dieser Fall zeigt. Am wenigsten exponiert sind Organisationen, die festgehalten haben, welche Parametersätze sie betreiben, die wissen, welche langlebigen Geheimnisse davon abhängen, und die den Algorithmus nach Plan statt in Panik wechseln können.

Quellen