Classic McEliece pod ostrzałem

Earlier this year I wrote about BSI recommendations regarding post-quantum transition. Roughly, a half year later these recommendations must change due to rapid progress in weakening the Classic McEliece cryptosystem, standardized under ISO/IEC 18033-2:2006/Amd 2:2026.

The Classic McEliece withdrawal

The current BSI statement is as follows:

Classic McEliece should currently no longer be used in new developments or when planning new cryptographic applications. For key agreement, it is advised to use FrodoKEM, ML-KEM or HQC (once the corresponding standard has been published) in accordance with the recommendations of TR-02102-1

However, BSI also adds:

It is important to note that the most recent publications in particular have not yet completed a full peer-review process and require thorough analysis. In particular, it must be examined carefully to what extent the claimed complexity estimates are accurate and the cost model is realistic, for example with regard to memory access costs. The BSI is also monitoring and analyzing the cryptanalysis results mentioned.

2026: A year of a rapid progress

This year brought major progress, including several new distinguishers, in Classic McEliece cryptanalysis and, although still theoretical, a noticeable reduction in the estimated cost of attacks.

The distinguisher

Before going further, it’s worth to introduce the distinguisher term first.

As an example, think of the Fast Fourier Transform (uhh, not an easy one!), which can reveal certain frequencies hidden in noise.

In Classic McEliece, however, this means distinguishing a public Goppa code from a random linear code (a Goppa code is a special, highly structured type of linear code).

Research progression

Key recovery for the McEliece cryptosystem using higher-order vanishing

It started with “Key recovery for the McEliece cryptosystem using higher-order vanishing”, interestingly, by Hemmert, who works at BSI.

Classic McEliece is a code-based cryptosystem built on Goppa codes. Its security relies on the hardness of decoding random linear codes and historically has been estimated against generic decoding attacks (assuming that the hidden Goppa structure does not lead to a cheaper attack).

Previous work had shown that this structure is not completely hidden, and higher-order vanishing relations can distinguish a binary Goppa code from a random linear code. In other words, there is a mathematical fingerprint left in the public key.

What the above paper brought to the table was showing that this fingerprint can be used for more than just recognizing a Goppa code. Hemmert exploited the structure behind the distinguisher to build a key recovery algorithm, even though its estimated cost was still way above the targeted security level.

Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)

The next paper Quasipolynomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece) brought another distinguisher and was somewhat of a breakthrough. It essentially showed that a Classic McEliece public key can be distinguished from one based on a random linear code.

The estimated cost of the distinguisher was around $2^{ 114 }$ to $2^{124}$ bit operations.

Improving GIJS Key Recovery for Classic McEliece

Finally, the Weis paper Improving GIJS Key Recovery for Classic McEliece specifically benefits from the previous paper and further lowers the attack cost to $2^{ 89 }$ to $2^{ 98 }$, however with an (unrealistic) assumption that the memory access is basically free.

Weis then adds memory access cost, estimating $2^{ 107 }$ to $2^{ 117 }$, but under the “square root” heuristic. It means that if an operation addresses (uses) $M$ bits of memory (when conducting the attack), the cost is proportional to $\sqrt M$ (see the appendix E The cost model: omitted terms and comparisons for detailed analysis).

The practical lesson

One might argue that RSA 2048 is ~112 bits of security and still widely in use, however, this year brought a major progess. Specifically, the best known algorithm for recovering the hidden Goppa structure/key was previously estimated basically above $2^{3000}$ and now it reduced to $2^{107}$ to $2^{117}$.

This is a real concern, and this year didn’t end yet. Neither may the progress.

Managing the risk is to act seeing the threat and its impact, thus BSI has already advised against using Classic McEliece for new developments.

The final, pragmatic observation from BSI:

The current situation shows that the recommendation to use post-quantum cryptography in hybrid mode has proven its worth. We are witnessing a dynamic development that must continue to be monitored.