Germany’s BSI Advises Against New Classic McEliece Deployments After Researchers Estimate Key Recovery Below Its Claimed Security Levels

October 2, 2026 – Germany’s Federal Office for Information Security (BSI) advised organizations on October 1 not to use Classic McEliece in new developments or when planning new cryptographic applications. In a note published in English and a German press release, the agency cited significant progress in the cryptanalysis of the code-based post-quantum key-encapsulation mechanism and said its security level is substantially lower than previously assumed.

BSI said no practical attack is currently possible against the parameter sets recommended in its Technical Guideline TR-02102-1, which has listed Classic McEliece since 2020 and has recommended it only in combination with a classical key-agreement scheme. Such hybrid deployments still provide at least the security of the classical scheme, the agency said. BSI is still evaluating the findings and expects to revise the guideline’s Classic McEliece entries in its next edition, in early 2027.

No one has publicly recovered a key or decrypted a ciphertext for any real Classic McEliece parameter set, and the researchers behind the new attacks say none of the attacks can be run on existing hardware. Three research groups have nonetheless published key-recovery cost estimates that are below the security level claimed for every Classic McEliece parameter set. Germany’s federal cybersecurity agency, which had recommended the scheme since 2020, now wants no new projects built on it.

Tobias Hemmert announced the statement on NIST’s pqc-forum mailing list on behalf of BSI’s cryptography division. Hemmert has published structural attacks on McEliece himself: a key-recovery method this summer and, with Andreas Wiemers, the higher-order-vanishing distinguisher presented at CRYPTO 2026, both estimated well above the claimed security levels.

Classic McEliece is a key-encapsulation mechanism built on Robert McEliece’s 1978 public-key cryptosystem, which disguises a binary Goppa code as the public key. Across its five main parameter sets, public keys range from about 261 KB to 1.36 MB and ciphertexts from 96 to 208 bytes.

NIST advanced Classic McEliece to the fourth round of its post-quantum standardization process but chose HQC (Hamming Quasi-Cyclic) in March 2025 as its code-based backup to ML-KEM (formerly CRYSTALS-Kyber), explaining the decision in NIST IR 8545. ISO added Classic McEliece, ML-KEM and FrodoKEM to its asymmetric-cipher standard in ISO/IEC 18033-2:2006/Amd 2:2026, published in June 2026.

The advisory follows less than two months of preprints on the IACR Cryptology ePrint Archive. In a paper the archive received on August 7, Ashrujit Ghoshal of IIT Madras, Yuval Ishai of Technion and AWS, and Aayush Jain and Nuozhou Sun of Carnegie Mellon University gave a provable method for telling Classic McEliece public keys apart from random matrices at an estimated $$2^{114}$$ to $$2^{124}$$ bit operations. That is less than the cost of generic decoding, the attack the Classic McEliece parameters were chosen to resist.

A revision on August 27 added details of a heuristic key-recovery algorithm that the first version had outlined, and postquantum.com/ analyzed the original version on August 10.

The method looks for low-degree polynomials that vanish to high order at every column of the public key except one held-out column. On a genuine Classic McEliece key the polynomials also vanish at the held-out column, while on a random matrix they vanish there only by chance.

Researchers then turned this holdout test into key recovery. Kirill Vedenev of CryptoPro and Southern Federal University posted an extension on August 22, Markku-Juhani O. Saarinen of Tampere University began a public cost tally on August 24, and Stephen A. Weis of Anthropic submitted an improved key-recovery analysis on September 11.

The groups counted cost in bit operations and compared it with the reference points NIST uses for its security categories. NIST estimates key search on AES-128, AES-192 and AES-256 at $$2^{143}$$, $$2^{207}$$ and $$2^{272}$$ classical gates, the levels claimed for Classic McEliece’s Category 1 set (mceliece348864), for its Category 3 set (mceliece460896) and for its three Category 5 sets (mceliece6688128, mceliece6960119 and mceliece8192128).

Ghoshal and his co-authors put their own key-recovery algorithm at $$2^{130}$$ to $$2^{149}$$ bit operations across the five sets. Saarinen, in his September 15 revision, costs a version of the same attack at about $$2^{127}$$ to $$2^{145}$$ in what he calls conditional arithmetic estimates, and Weis reports $$2^{94}$$ to $$2^{102}$$.

The figures from all three groups include no charge for memory or for moving data. Weis wrote that his attack is far beyond anything that can be run. Against the smallest parameter set, he wrote, its main computation would move about $$2^{93}$$ bits through a 28 TiB array, and the larger sets need up to 540 TiB. Weis then multiplied his figures by the cube root or the square root of the memory used, the two cost models he takes from the Classic McEliece team’s security guide, and got about $$2^{110}$$ to $$2^{128}$$, still below every claimed level.

End-to-end attacks have worked only on toy-sized codes. Weis recovered the secret key of instance 253 in the Technology Innovation Institute’s 2023 McEliece key-recovery challenges, a code of length 214 over a field of 256 elements, using about 700 core-hours for each of two kernel computations. Saarinen solved instance 254 with a variant of the method, and both researchers stated that these challenge codes are far smaller than any Classic McEliece parameter set and say nothing direct about the security of the real sets.

The Classic McEliece team, in a statement posted on August 21 by Daniel J. Bernstein, a member of the design team, said the original distinguisher only recognizes public keys and does not attack the scheme’s security goals. The team estimated the paper’s plaintext-recovery attack at about $$2^{266}$$ bit operations against mceliece6960119.

In later posts that he labeled as his own views, Bernstein argued that the key-recovery estimates leave out the cost of moving data and of parallel hardware, and that the new attacks gain nothing from multiple targets or from quantum computers. He also wrote that no nation-state has the resources to run any of them against a Classic McEliece parameter set. On September 30 he wrote that the papers had not changed his assessment that ML-KEM carries higher risk than McEliece.

Saarinen wrote on September 16 that multiple independent tallies agree the key-recovery cost is below the claimed level for every parameter set, and that he and other researchers were ready to recommend against using Classic McEliece at its stated security levels. John Preuß Mattsson of Ericsson said that would also be his recommendation. Filippo Valsorda asked the team twice whether it still recommends the standardized parameter sets as alternatives to ML-KEM; by October 2, no answer labeled as a team statement had appeared on the forum.

BSI said ML-KEM, FrodoKEM and HQC are not affected, that ML-KEM and FrodoKEM should be preferred to Classic McEliece, and that it will recommend HQC once a standard is available. Saarinen and Sophie Schmieg of Google wrote on the forum that the attacks have no bearing on lattice-based schemes. Saarinen added that HQC uses neither Goppa codes nor the hidden structure the attacks exploit.

The ISO amendment covers four base parameter sets, mceliece460896, mceliece6688128, mceliece6960119 and mceliece8192128, each with f, pc and pcf variants, according to the Classic McEliece team’s ISO page. The amendment does not include mceliece348864. Excerpts that a forum participant posted after buying the standard show informative annexes that recommend, without requiring, that any upgrade from classical encryption keep that classical layer and add the post-quantum scheme to it.

Mullvad VPN uses Classic McEliece together with ML-KEM to exchange a pre-shared key for its WireGuard tunnels, a feature on by default on all its desktop apps since a January 2025 release. Rosenpass, a post-quantum key exchange for WireGuard, uses Classic McEliece 460896 for static keys and Kyber-512 for ephemeral keys. PQConnect, which Bernstein works on, pairs X25519 with mceliece6960119 for long-term keys and with the lattice-based sntrup761 for short-term keys.

European agencies had already diverged on the scheme. The Dutch PQC Migration Handbook from AIVD, CWI and TNO rated Classic McEliece acceptable in its 2024 second edition, as a more conservative option than ML-KEM. Mattsson and Demi Marie Obenour, who started the forum discussion, wrote that France’s ANSSI rated it lower in confidence than ML-KEM, FrodoKEM and HQC.

Sweden’s NCSC recommends only algorithms standardized through open processes and already in large-scale use, a test it says only NIST’s five standards meet.

My Analysis

What Changed Since My August 10 Analysis of the Distinguisher

On August 10 I wrote that the Ghoshal, Ishai, Jain and Sun distinguisher was not a break, because recognizing a Classic McEliece public key violates no security property the team ever claimed. The team designs the underlying encryption for one-way security and builds its IND-CCA2 KEM on that foundation. A distinguisher attacks neither, and that reading still holds for the paper as it was posted in August.

Key recovery defeats one-way security directly: an attacker who recovers the private key can decrypt every ciphertext sent to it. Ghoshal and his co-authors added the details of their key-recovery algorithm on August 27, and by mid-September three groups had estimated key recovery below the claimed level of every parameter set. My line that no security claim had fallen no longer fits the published estimates, and I am adding a note to the August article that points here.

The exabyte figure in that article also needs context. It was the distinguisher’s storage as its authors costed it, about $$2^{66}$$ to $$2^{71}$$ bits, a number they said they had not tried to reduce. Weis organizes a key-recovery run around a working memory of $$2^{47.8}$$ to $$2^{52.1}$$ bits, 28 to 540 TiB. Large systems have that much memory; the obstacle is the number of operations and the volume of data that has to move between memory and the units doing the arithmetic.

The migration advice in the August piece, to keep Classic McEliece inside hybrids and to look for any standalone use, matches what BSI now says.

Key-Recovery Estimates for Each Parameter Set

All figures below are modeled bit-operation costs with no charge for memory. The three key-recovery columns are conditional estimates that depend on heuristic assumptions, and none has been run at these sizes.

The AES gate reference is NIST’s classical-gate estimate for key search on the AES variant that defines each claimed category. Generic decoding figures are from Bernstein and Chou’s CryptAttackTester as quoted by Weis. The Ghoshal et al. figures are from Table 3 of their August 27 revision, Saarinen’s from his September 15 revision, and Weis’s from the optimized single-run variant in his Table 1. mceliece348864 is not part of the ISO standard.

Until this year the best attack on every set was generic decoding, in the form of information-set decoding (ISD). For mceliece460896, mceliece6688128 and mceliece6960119 its bit-operation cost was already below the claimed level. NIST flagged the Category 3 case in IR 8545 in March 2025. Independent estimates had long put mceliece460896 short of its target, NIST wrote, though it remained confident the set met at least Category 2, and it said of the scheme as a whole that recent cryptanalysis “somewhat undermines the case for treating it as an especially conservative choice.” Weis charged his attack for memory using the cube-root and square-root models he takes from the team’s security guide. With the square-root charge his figures come to about $$2^{118}$$ to $$2^{128}$$: 25 bits under the Category 1 level for mceliece348864; 82 to 145 bits under the claimed levels for the other four sets.

The three analyses are related rather than independent. Weis builds on the key-recovery algorithm of Ghoshal and his co-authors, Saarinen costs a version of the same attack, and Weis reproduced their cost formulas to two decimal places before improving on them. Their agreement checks the accounting within one framework; the assumptions the three papers share still need testing at full size.

Daniel Bernstein’s Objection on Memory and Parallel Hardware

Bernstein argues that bit-operation counts misprice this attack. Holdout key recovery is one large sparse linear-algebra computation, and most of its counted operations fetch a bit from an array of tens to hundreds of terabytes. He calculated that routing the roughly $$2^{93}$$ bits of the mceliece348864 attack through the bisection bandwidth reported for LineShine, which he described as the new top supercomputer, would take about 90,000 years, a figure he gave for that one component of the cost rather than for the whole computation. He cited the Brent–Kung area-time bounds to argue that no circuit layout removes the overhead, and he challenged Weis’s claim, given without a derivation, that generating the matrix entries on demand adds no operations.

Weis accepts much of the mechanism. His paper says a run is a chain of $$2^{32}$$ to $$2^{36}$$ mutually dependent passes over its memory and that he knows of no data layout that makes the access pattern local. He also writes that an AES key search needs almost no memory, amortizes across many targets and gains from Grover’s algorithm, so comparing the two favors the attack.

For mceliece348864 the memory-charged estimate is 25 bits under the Category 1 level, a gap that a harsher cost model could plausibly close, and ISO left that set out of its standard. For the Category 3 and 5 sets the memory-charged gap is 82 to 145 bits, and nobody in the forum discussion has offered a cost model that adds that much.

In 2020, Bernstein argued that NIST’s rules held Kyber-512 to this same gate-count metric, even though he considered the metric unrealistic. His official comment on Kyber said every known attack on a Category 1 parameter set had to cost at least about $$2^{143}$$ classical gates, whatever happened in other metrics. NIST replied in the same discussion that it was inclined to give a parameter set the benefit of the doubt when known attacks came very close to the AES gate count and needed heavy random access to large memory, and less inclined otherwise. The Kyber team’s lower estimates then, $$2^{136}$$ and $$2^{141}$$ gates, fell two to seven bits short.

The Category 3 and 5 gaps here are 82 bits or more under either accounting. Mike Hamburg pointed out on the forum that the attack paper Bernstein now cites against ML-KEM-1024, which puts it 12.3 bits under its category, itself cautions that its estimates ignore the cost of memory access.

Measured against the categories the team claimed for its parameter sets, every published estimate falls short, by far more than the gaps argued over for Kyber-512 or ML-KEM-1024. Measured against ISO’s requirement of at least 128 bits of security in its quantum model, as the team’s ISO page describes it, Weis’s memory-charged figures of $$2^{110}$$ to $$2^{128}$$ are near the line, and Bernstein’s case that real costs are much higher than any of these models is unresolved. My reading is that, if the heuristic assumptions are correct at full size, Classic McEliece no longer meets the security levels its team claimed for it. Whether it still clears a 128-bit floor is an open question.

Field Degree m and the Cost of Key Recovery

A Classic McEliece parameter set is described mainly by three numbers: the code length $$n$$, the number of errors $$t$$, and the field degree $$m$$, which fixes the size of the finite field the Goppa code is built over. The team scaled its sets against generic decoding, whose cost grows with $$n$$ and $$t$$, and kept $$m$$ at 12 for mceliece348864 and at 13 for all four sets in the ISO standard.

Weis finds that the cost of a holdout run depends on $$m$$ and $$t$$ but not on $$n$$, and grows by about eight bits for each unit of $$m$$. With $$m$$ fixed at 13, the Category 5 sets gain almost nothing against these attacks. Ghoshal and his co-authors and Saarinen put key recovery against them below the Category 3 set (about $$2^{141}$$ and $$2^{137}$$, against $$2^{149}$$ and $$2^{145}$$ for mceliece460896), and Weis puts them about three bits above it.

Bernstein objected on the forum to the word “quasipolynomial” in the original paper’s title on the same grounds. Ghoshal and his co-authors state their result for code families in which $$m$$ grows like $$\log n$$, and Weis notes that the cost is not quasipolynomial in $$n$$ for families in which $$m$$ grows faster.

Bernstein and Weis point to the same direction for new parameters: raise $$m$$ while keeping $$n$$ well below $$2^m$$. Weis shows that $$m$$ of 18, 26 and 34 push the cost of this holdout run above the three reference values, with public keys of about 0.6, 2.1 and 7.1 MB, 2.3 to 6.8 times today’s sizes. He labels them illustrations rather than proposals and did not examine how other attacks behave at those sizes. Bernstein’s example, $$m = 18$$ with $$n = 6176$$ and $$t = 112$$, keeps the 1 MB key of mceliece6688128 with a 252-byte ciphertext, and Weis estimates a run against it at about $$2^{142}$$. The first version of Weis’s paper had assumed $$n = 2^m$$ and concluded that the higher levels would need gigabyte keys; Bernstein identified the error and Weis corrected it the next day.

A re-parameterized Classic McEliece is possible on paper. In the same cost model, Weis’s September estimates are 36 to 50 bits lower than the key-recovery figures Ghoshal and his co-authors posted on August 27. About 16 of those bits depend on two of Weis’s heuristic assumptions. His single-run method requires further assumptions, tested only on small codes. Any new parameter set would need substantial fresh cryptanalysis and standardization review against attacks that have moved that fast. Nobody has proposed one for standardization. Obenour argued on the forum that a scheme in this position is too risky to deploy even with new parameters, and I agree for anything being designed now.

What Has Been Demonstrated, and What Depends on Assumptions

The distinguisher of Ghoshal and his co-authors is proved, and so are four statements in Weis’s paper about binary Goppa codes. Key recovery at real size depends on dimension counts and genericity assumptions of the kind that is usual in algebraic cryptanalysis. Weis states five such assumptions and tested them on small keys and on the TII instance, where the shortened code had dimension 46 against at least 154 for the real parameter sets.

Weis also ran the final algebraic step at full mceliece348864 and mceliece8192128 size, starting from data he computed with the secret key, and recovered keys that rebuilt the public codes. No one has publicly run the expensive kernel computation against any real parameter set. Saarinen wrote on September 16 that no exponential obstruction had turned up in the remaining attack paths despite an active search, and that he believed some of Weis’s assumptions had since been proved.

Daniel Apon of Anduril Industries published a lower bound showing that Vedenev’s original reconstruction step needs far more held-out columns than Vedenev assumed, which puts that route above $$2^{1500}$$ bit operations for mceliece8192128. Vedenev has since added a second, minor-code route that he estimates, conditional on his assumptions, at a few runs of the distinguisher. The routes used by Ghoshal and his co-authors and by Weis do not depend on the reconstruction step either. Bernstein’s first objection concerns the experiments: he wrote that the algorithm fails on every small input, which makes useful tests hard, and that claims of success at real sizes are extrapolations.

Both papers disclose AI assistance: Weis’s states that it was prepared with Claude, and Ghoshal and his co-authors disclose that AI tools verified their results and worked on the concrete cost analysis. Errors have been found and corrected in public. Bernstein caught the $$n = 2^m$$ slip in Weis’s first version, and Weis credits Sanketh Menda with finding errors in the cost figures of earlier versions. Greg Maxwell suggested on the forum that a model will agree an attack is impossible as soon as someone tells it so.

I give the most weight to figures that a second group has reproduced, and none to unpublished ones. Apon wrote on October 1 that an unpublished analysis of his puts Category 1 key recovery at $$2^{89}$$ to $$2^{92}$$ including memory costs. On October 2 he wrote that he would not release it, because further cryptanalysis would only harm current users. Until it is published, nobody else can assess that figure.

Do Hybrids With Classic McEliece Still Protect Recorded Traffic?

BSI’s statement that hybrids with Classic McEliece still provide at least classical security is correct for today’s attackers: the new attacks are classical, and nobody has published a comparable attack on X25519 or ECDH. Mattsson replied on the forum that this gives nothing to people who deployed a hybrid for quantum resistance, and that he is now more convinced that high-security key exchange should combine two post-quantum families, such as ML-KEM and HQC. He pointed to these attacks and to the earlier scare over Daniel Simon’s claimed polynomial-time quantum algorithm for the dihedral coset problem, which threatened lattice schemes and which he now calls debunked.

Oscar Smith objected that RSA-2048 resists any quantum computer with fewer than about 3,000 logical qubits, so a classical-plus-PQC hybrid still protects against every machine that exists. Bas Westerbaan put the threshold at about 1,400 logical qubits, citing Gidney’s 2025 estimate, and Uri Blumenthal of MIT Lincoln Laboratory replied that by the same logic plain P-384 ECDH is quantum-resistant today.

For harvest-now, decrypt-later exposure, the classical half of a hybrid protects nothing on the day a CRQC decrypts the recording, as I argued in August. A hybrid whose post-quantum half failed would therefore leave recorded traffic without long-term protection. Mullvad’s tunnels stay quantum-resistant as long as ML-KEM is unbroken, and Rosenpass pairs Classic McEliece static keys with ephemeral Kyber-512 keys while WireGuard supplies the classical layer. Mattsson noted that Rosenpass uses Classic McEliece for authentication, where an attacker’s goal would be impersonation rather than reading recorded traffic.

Most of the policy argument over hybrid cryptography has compared classical-plus-PQC with pure post-quantum deployment, which is why regulators disagree on hybrid deployment. Mattsson argues for a third pattern, two post-quantum families together, and the Classic McEliece attacks are a real test of it. The attacks do not show that recorded hybrid traffic can be decrypted. After a CRQC breaks the classical half, an attacker would still have to break Classic McEliece, and every published estimate for that is far beyond anything that can be run. The change is in confidence: Classic McEliece is now a weaker basis for keeping that traffic protected for decades, and a second post-quantum algorithm in the same key exchange, combined correctly, removes the dependence on it.

What Organizations Using Classic McEliece Should Do

BSI’s advice covers new developments. Existing deployments need decisions of their own:

• Start nothing new on Classic McEliece. Use ML-KEM, or FrodoKEM where national guidance calls for it, and evaluate HQC once NIST publishes its standard.
• Find every instance. Record the parameter set, the hybrid partner, whether the scheme protects confidentiality or authenticates long-term keys, and how long the data must stay secret. A cryptographic bill of materials that captures parameter sets answers the first two questions; the last two need input from the system and data owners.
• Avoid emergency removals from existing hybrids. BSI says they still provide at least classical security. In my view, pulling Classic McEliece out in a hurry adds change risk without adding protection, so replace it on a planned schedule after checking each protocol’s design and the vendor’s guidance.
• Move standalone uses to the front of the queue. A system that relies on Classic McEliece alone, particularly for data that must stay confidential for decades or for authenticating long-term keys, depends on a security level that three research groups now estimate below its claim.
• Ask your vendors. The Classic McEliece team’s 2024 presentation to NIST listed deployments in hardware security modules and optical network encryption as well as in VPNs. Ask suppliers whether their products use it and what will replace it.
• Log the event. Record it against every system that depends on binary Goppa codes, with a review date tied to BSI’s TR-02102-1 revision in early 2027, and reopen it sooner if new analysis appears.

Organizations that built for crypto-agility can handle this as a scheduled algorithm change. None of it is a reason to doubt ML-KEM; BSI, Saarinen and Schmieg all say the attacks depend on hidden Goppa-code structure that lattice schemes do not have. It does not move the CRQC timeline either, since every attack in this story is classical.

Organizations that followed BSI’s or AIVD’s guidance toward Classic McEliece, or chose it for its reputation as the conservative option, are the ones exposed. Deployments limited to NIST-standardized KEMs do not contain it, though organizations that follow NIST can still find it inside VPNs and vendor products. In Quantum Sovereignty I argued that each jurisdiction takes on the cryptanalytic exposure of the algorithms it chooses, and this is a concrete case of it.

What Comes Next for Classic McEliece

The team has answered earlier attack papers with dated rebuttals on its website, including one dated June 23, 2026, and its introduction page, last versioned June 19, 2026, still describes the security level of the McEliece system as remarkably stable. Valsorda’s question asks for what implementers need: a team recommendation for or against its own standardized parameter sets.

NIST’s IR 8545 left the door open to standardizing Classic McEliece later, and Saarinen expects NIST to revisit that position. ISO’s June amendment lists four base parameter sets, and all four now have key-recovery estimates below their claimed levels. BSI expects to publish its revised TR-02102-1 in early 2027, and AIVD, which Mattsson asked to update its description of Classic McEliece as a conservative choice, had not commented on the forum by October 2.

A kernel computation on a code closer to the real parameter sets would test the assumptions at a larger size than any run so far. BSI expects further improvements in the attacks. So do I, because three groups improved on one another within weeks, and nobody in the forum discussion has identified an obstruction for the routes they used.

BSI recommended Classic McEliece from 2020, after decades in which no structural attack came near the cost of generic decoding for its parameters. It changed that recommendation for new systems less than two months after the first holdout paper appeared, while four base Classic McEliece parameter sets remain in an ISO standard published in June.