Germany's federal cybersecurity agency has advised organisations not to build new systems on Classic McEliece, one of the oldest post-quantum key-agreement schemes, after three research groups independently estimated that its secret keys can be recovered far more cheaply than the security levels the scheme claims.

In a note dated 1 October, the Bundesamt für Sicherheit in der Informationstechnik (BSI) said 2026 had brought significant progress in the cryptanalysis of the code-based key-encapsulation mechanism, and that it now recommends against using it "for new developments as well as when planning new cryptographic applications". The agency stressed that the results so far do not enable a practical attack on the parameter sets recommended in its Technical Guideline TR-02102-1, but added that further improvements are "conceivable and to be expected".

The rapid fall of a classic

Classic McEliece descends from Robert McEliece's 1978 public-key cryptosystem, which hides a binary Goppa code inside a large public key. Its long-standing drawback was key size: the five main parameter sets carry public keys of roughly 261 KB to 1.36 MB, with ciphertexts of 96 to 208 bytes. That is why NIST did not select the scheme in its main post-quantum standardisation process and instead chose HQC in March 2025 as its code-based backup to ML-KEM. The scheme nonetheless kept a reputation as the conservative choice, and ISO added it — alongside ML-KEM and FrodoKEM — to its asymmetric-cipher standard, ISO/IEC 18033-2 Amendment 2, published in June 2026. BSI had listed it, only in combination with a classical algorithm, since 2020.

What changed in ten weeks

The trouble began on 7 August, when Ashrujit Ghoshal (IIT Madras), Yuval Ishai (Technion and AWS) and Aayush Jain and Nuozhou Sun (Carnegie Mellon University) posted a provable method for distinguishing a Classic McEliece public key from a random matrix, at an estimated 2^114 to 2^124 bit operations — below the cost of the generic decoding the parameters were designed to resist. As first posted, the paper did not break the scheme. A revision on 27 August added details of a heuristic key-recovery algorithm, which is a different matter: an attacker who recovers the private key can decrypt every ciphertext sent to it.

By mid-September three groups had published key-recovery estimates that undercut the claimed security of every parameter set. Ghoshal and his co-authors put their own algorithm at 2^130 to 2^149 bit operations; Markku-Juhani O. Saarinen of Tampere University costed a version of the same attack at about 2^127 to 2^145; and Stephen A. Weis of Anthropic reported 2^94 to 2^102. Those figures sit below the AES key-search gates NIST uses as reference points: 2^143 for AES-128, 2^207 for AES-192 and 2^272 for AES-256, the levels the parameter sets claim. Charging Weis's attack for memory, using cost models from the Classic McEliece team's own security guide, still leaves roughly 2^110 to 2^128.

No practical break — yet

Nobody has publicly recovered a key or decrypted a ciphertext for a real Classic McEliece parameter set, and the attacks cannot be run on existing hardware. Weis's run against the smallest set would push about 2^93 bits through a 28 tebibyte array; the larger sets need up to 540 TiB. The only end-to-end successes are on toy codes from a 2023 challenge, far smaller than anything deployed.

The design team has pushed back. Daniel J. Bernstein, writing for the team and later in posts he labelled as his own views, argued that the original distinguisher attacks no security goal the scheme ever claimed, that bit-operation counts ignore the cost of moving data and of parallel hardware, and that no nation-state could run the attacks. On 30 September he wrote that the papers had not changed his assessment that ML-KEM carries higher risk than Classic McEliece. The team put the paper's plaintext-recovery route at about 2^266 operations against mceliece6960119.

What operators should do

BSI says nothing needs to be ripped out in a hurry. A hybrid deployment that pairs Classic McEliece with a classical exchange such as X25519 still delivers at least the security of the classical half. The catch is harvest-now, decrypt-later exposure: the classical half is precisely what a future quantum computer would break, so if the post-quantum component is weaker than advertised, recorded traffic loses the long-term protection it was meant to gain.

For key agreement the agency recommends FrodoKEM or ML-KEM, and HQC once a standard for it is published, saying all three are unaffected by the new attacks. It plans to revise the Classic McEliece entries in TR-02102-1 in early 2027. Deployments already in the wild include Mullvad VPN, which combines Classic McEliece with ML-KEM for its WireGuard tunnels, and Rosenpass, which uses mceliece460896 for static authentication keys.

The wider lesson is crypto-agility — the ability to swap one algorithm for another at low cost. Post-quantum schemes can fall out of favour in weeks, as this case shows, and the organisations least exposed are those that recorded which parameter sets they run, know which long-lived secrets depend on them, and can change the algorithm on a planned schedule rather than in a panic.

Sources