Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Structural cryptanalysis of classic McEliece".

Elias: Here's the gist of the paper. Structural cryptanalysis of classic McEliece reveals that recent advances in classical structural attacks have progressed significantly, leading to conditional key-recovery estimates that are lower than previously thought, though no practical full-size break has been demonstrated Structural Attacks and Progress Classical structural attacks on binary Goppa codes have advanced over the last two years with higher-ordervanishing distinguishers and key recovery The wave of 2024–2026 structural attacks included a sequence of results such as Randriambololona’s syzygy distinguisher, higher-order-vanishing (HOV) distinguishers, and quasi-polynomial Holdout/Hermite distinguishers These attacks have led to public key-recovery challenges with brute-force labels up to 254 being solved along the way The lowest published estimates for Classic McEliece parameter sets are now conditional figures of about 2 89 to 2 128 per run of a large sparse linear-algebra computation Key Recovery Estimates and Cost Models The paper separates proved distinguishers, conditional key-recovery estimates, and actual recoveries The cost model is identified as the main quantitative uncertainty, with about thirty bits between the cheapest and the most expensive model for the same computation For the four larger parameter sets, every model considered leaves the conditional estimates far below the targeted levels The structural estimates are lower than Grover-accelerated information-set decoding for the four larger sets in essentially every model and comparable for mceliece348864 Analysis of Specific Attacks The paper details analyses of specific key-recovery routes, including Saarinen’s HOVER algorithm, his conditional cost analysis of Holdout key recovery, and his recovery of the TII-254 challenge Weis’s cost study on Holdout/Hermite key recovery is also analyzed with figures per parameter set and cost model Saarinen’s HOVER replaces the MinRank search by linear algebra The demonstrated TII-254 recovery uses a two-anchor Holdout/Hermite attack which is a different result from both HOVER and the preceding cost table Assessment and Conclusions Weis’s paper establishes that if its heuristic assumptions hold at full size, the hidden Goppa structure, not generic decoding, is the weakest point of every Classic McEliece parameter set The cost model is now the main quantitative uncertainty The BSI’s response, no use in new developments, hybrid use only, and a re-evaluation expected in early 2027 matches this evidence The open questions center on whether the low conditional estimates and small-instance recoveries extrapolate to the standard sets Standardization and Deployment Guidance The ISO/IEC standardized selected parameter sets in June 2026, which exclude mceliece348864 The BSI note of 29 September 2026 records this standardisation and the BSI’s recommendation of Classic McEliece since 2020 Its assessment is that the published results do not yet enable a practical attack on the parameter sets recommended in TR-02102-1, that the estimates and cost models of the most recent, unreviewed works must be checked carefully Consequences The episode illustrates again that weaknesses tend to appear where algebraic structure is hidden, in ideal lattices In conclusion, the lowest published estimates are no longer those of generic decoding with a Grover speed-up but those of classical structural attacks whose concrete cost is under revision The lower conditional estimates warrant scrutiny of the structural assumptions and of realistic memory costs The open questions will decide whether the remaining gap between conditional estimates and a demonstrated attack closes Open Questions The open questions include whether the Holdout/Hermite key-recovery methods succeed on the Classic McEliece parameter distributions with what structural success probabilities and end-to-end costs Can the reported small-instance recoveries be extended without assuming the full-size rank and locator-uniqueness properties What does a run cost under realistic models of memory access and communication Does a quantum computer accelerate the sparse linear algebra over F2 that dominates these attacks Is there a hidden-structure attack on quasi-cyclic syndrome decoding analogous to the structural attacks on hidden Goppa codes Within a few months of 2026, structural cryptanalysis moved the lowest published estimates for key recovery on Classic McEliece from more than 2 3000 to conditional per-run figures near 2 100 The figures are conditional: they rest on heuristic assumptions tested on instances tens of thousands to hundreds of thousands of times smaller than the target, and they vary by about thirty bits with the cost model No full-size key recovery has been demonstrated, and Weis notes that no machine of the kind a run would require exists The BSI’s response, no use in new developments, hybrid use only, and a re-evaluation expected in early 2027 matches this evidence The open questions above, and the next revisions of the preprints discussed here, will decide whether the remaining gap between conditional estimates and a demonstrated attack closes References

3: Albrecht, M.R., Bernstein, D.J., Chou, T., Cid, C., Gilcher, J., Lange, T., Maram, V., von Maurich, I., Misoczki, R., Niederhagen, R., Paterson, K.G., Persichetti, E., Peters, C., Schwabe P.: Classic McEliece: Conservative code-based cryptography.

Nadia: Submission to the NIST Post-Quantum Cryptography Standardization Process Round 4 (2022), https://classic.mceliece.org/mceliece-security-20221023.pdf (2026), web page, version June 15, 2026; consulted October 11, 2026]

4: Albrecht, M.R., et al.: Classic McEliece: Conservative code-based cryptography: Guide for security reviewers.

Elias: https://classic.mceliece.org/mceliece-security-20221023.pdf (2026), web page, version June 15, 2026; consulted October 11, 2026]

5: Apon, D.: An algebraic-geometry lower bound against the ePrint:2026/1747 McEliece key-recovery attack.

Nadia: Cryptology ePrint Archive, Paper 2026/1810 (2026), posted August 26, 2026; revised August 28, 2026.

Paper summary: Nadia: So we're looking at this paper right now, "Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence." It seems the main point is that the classical structural attacks on binary Goppa codes have really advanced in the last couple of years, showing things like higher-order vanishing distinguishers and these quasi-polynomial Holdout/Hermite distinguishers.

Elias: Exactly. The authors are giving a critical look at this progress, separating what they've actually proven from the conditional estimates and the actual key recoveries that have been demonstrated so far. They’re also breaking down specific analyses like Saarinen’s HOVER algorithm and Weis’s cost study of Holdout/Hermite recovery.

Priya: I wonder what this means for us on the ground, because they're looking at how these attacks progress in terms of the parameters of Classic McEliece, which is a pretty large scheme. They mention that some public key-recovery challenges with brute-force labels up to two hundred fifty-four have been solved along the way <ref:2610.31196#pg1,challenges with brute-force labels up to 254>.

Nadia: That’s what I’m thinking, Priya. It sounds like they’re pointing out that we used to think these structural attacks were much slower, but now they've shown conditional key-recovery estimates of about two to eight nine to two one two eight per run of a large sparse linear-algebra computation, depending on the parameter set and memory access costs.

Elias: That conditional estimate is what caught my attention; it’s about two eighty-nine to two one hundred twenty-eight per run of that specific type of computation, which is pretty low compared to what we expected before <ref:2610.31196#pg1,about $2^{89}$ to $2^{128}$ per run of>. They’re also pointing out that the cost model itself is now the main quantitative uncertainty, with about thirty bits between the cheapest and most expensive model for the same computation.

Priya: So if it’s about memory access costs versus not charging for them, that makes sense because those are real-world constraints when we talk about how much work something actually takes to do.

Nadia: Right. And they compare the structural estimates, which are lower than Grover-accelerated information-set decoding for the four larger parameter sets in essentially every model, and comparable for mceliece348864.

Paper summary: Elias: That comparison is interesting because it suggests that for those larger parameter sets, even with these structural attacks, the conditional estimates they've found are still well below what we might consider a practical attack level.

Priya: So if we take this into account, the paper’s conclusion seems to be that none of this is a demonstrated attack because the underlying heuristics have only been tested on instances that are tens of thousands to hundreds of thousands of times smaller than the target size.

Nadia: That's a key caveat they mention; they’re showing us some promising paths, but they’re stressing that we haven't actually done a full-size break yet. They also mention that the German BSI advised against new deployments of this scheme back in September two thousand twenty-six because of these results <ref:2610.31196#pg1,the German BSI advised against new deployments of>.

Elias: That BSI advice, combined with the analysis in this paper, suggests that hybrid use might be what's left for now, and a re-evaluation is expected around early two thousand twenty-seven <ref:2610.31196#pg1>. The paper itself gives a version-aware critical assessment of all these results.

Priya: So what’s the main thing we need to take away from this specific paper, "Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence"? It seems to be about moving from just saying an attack is possible to understanding exactly what it would cost in reality.

Nadia: Right. The paper separates proved distinguishers, conditional key-recovery estimates, and actual recoveries so we can see where the confidence level is actually sitting with these new structural attacks on binary Goppa codes.

Elias: They really detail Saarinen’s HOVER algorithm and his conditional cost analysis of Holdout key recovery, as well as Weis’s cost study on Holdout/Hermite key recovery, comparing them to other routes like the two-anchor Holdout/Hermite attack.

Priya: I’m curious about what this means for the future of McEliece security in practice; are these conditional estimates enough to worry about?

Nadia: It sounds like the paper suggests that if you're looking at those four larger parameter sets, every model they considered leaves the conditional estimates far below the targeted levels, which is a pretty strong statement against immediate practical exploitation.

Paper summary: Elias: And they also state that if their heuristic assumptions hold at full size, then for every Classic McEliece parameter set, the hidden Goppa structure itself is the weakest point of those sets, not just generic decoding.

Priya: So the structural analysis points to a specific weakness in the code's algebraic structure when you look at it this way. But what about whether these small-instance recoveries can actually be extended to real, full-size instances?

Nadia: That’s one of the open questions they raise; whether those small-instance recoveries extrapolate without assuming the full rank and locator-uniqueness properties of the code.

Elias: Another thing they ask is what a run cost would look like under realistic models of memory access and communication, because that’s where their cost uncertainty really lies.

Priya: I also want to know if a quantum computer accelerates the sparse linear algebra over F2 that dominates these attacks; is there a quantum speedup for those specific computations?

Nadia: They also ask if there's any hidden-structure attack on quasi-cyclic syndrome decoding that’s analogous to the structural attacks they’ve done on hidden Goppa codes.

Elias: So, to wrap up this assessment of "Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence," the main point is that while structural attacks have progressed significantly over the last two years, we don't have a demonstrated full-size break yet.

Priya: And what does that mean for deployment right now?

Nadia: It means we need to be very careful about which parameter sets we use, because the estimates and cost models of the most recent unreviewed works still need to be checked carefully. The open questions center on whether these low conditional estimates and small-instance recoveries really hold up when scaled up.

Elias: So we're left wondering if the gap between those conditional estimates and a demonstrated attack closes soon, or if we still have a significant hurdle to cross before we can trust these structural findings in practice.

Priya: That sounds like the core tension here: there’s technical progress showing potential weaknesses, but practical confidence is still missing because of those scaling issues and cost uncertainties.

Conclusion: Nadia: So, we're wrapping up this deep dive into "Structural cryptanalysis of classic McEliece: Assessment of claims, costs and evidence."

Elias: Yeah, the core idea here is that these recent structural attacks on binary Goppa codes have gotten much more aggressive over the last couple of years.

Nadia: They’ve moved past just finding simple distinguishers; we're talking about higher-order vanishing stuff and these quasi-polynomial Holdout/Hermite attacks.

Elias: And what this paper does is separate the actual proven attacks from the conditional cost estimates and the real key recoveries that have been demonstrated so far.

Priya: I’m looking at how they handle the numbers, because those conditional estimates—the two eighty-nine to two one hundred twenty-eight per run of linear algebra—they feel like a big step up from what we used to see.

Nadia: Exactly, Priya. But the authors are really stressing that these figures are conditional; they rely on heuristics tested on instances that are way smaller than the actual target size.

Elias: And they point out that for the four larger parameter sets, every single model they considered leaves those conditional estimates far below what we'd actually need for a full break.

Priya: So, even with these structural weaknesses, if you run it at full size on those standard sets, the cost still seems too high based on their current math.

Nadia: That’s the tension: the structural analysis suggests a weakness is there, but the cost models and scaling issues mean it’s not a practical threat right now.

Elias: The authors are essentially saying that if these heuristic assumptions hold true at full size, then the hidden Goppa structure itself is actually what makes those Classic McEliece parameters weak.

Priya: That shifts the focus from just generic decoding to something more fundamental about how the code is built algebraically.

Nadia: Right. They are forcing us to question if those small-instance recoveries can even be extended reliably without assuming things like rank and locator uniqueness hold up for the full key size.

Elias: It really makes you wonder what kind of attack would actually need to exist if these conditional estimates were suddenly much closer to a demonstrated full-size break.

Priya: We're left with some big questions about whether those low conditional estimates actually translate into something useful for real security evaluations.