Post-quantum signatures take a dual cryptanalytic hit

Two independent lines of cryptanalysis landed on the post-quantum community in quick succession, and neither is easy to dismiss as an academic curiosity. HAWK, a lattice signature still in the NIST signatures process, has been withdrawn after a key-recovery attack that halves the effective dimension of the underlying lattice problem and was found with substantial help from a large language model. At nearly the same moment, new holdout-style results against Classic McEliece claim that every parameter set the team put forward falls short of its advertised security level. The combined effect is immediate pressure on remaining candidates, on implementers who already shipped or planned to ship those schemes, and on the agencies that treated “conservative code-based crypto” as a safe hedge.

The HAWK story broke first on the pqc-forum. Steve Weis announced an improved key-recovery attack “against HAWK-n that reduces to SVP in dimension n/2 + 1.” In the gate-count model of AGPS’20 the cost for HAWK-512 drops from 2^150 to 2^108; for HAWK-1024 it falls from 2^288 to 2^182. A practical demonstration recovers a HAWK-256 secret key “end-to-end in a few hours on a single server.” Weis was careful to bound the blast radius: “This result does not impact Falcon, ML-DSA, or other latticed-based schemes.” He also stated plainly that the weakness “was found by Claude, with minimal technical guidance from people.” Daniel Apon independently checked the claim and replied simply, “Nice. It checks out independently for me.”

That was not the only attack. Damien Robert later relayed work by Guilhem Mureau and Alice Pellet-Mary describing a third key-recovery attack on Hawk whose concrete effect is “very similar” to an earlier result by Hengyi Luo, reached by yet another mathematical route. Multiple independent breaks of the same design, arriving within weeks of one another, left little room for parameter tweaks or optimistic reinterpretation of the security reduction. The HAWK team’s cooperation in verifying the first result was noted; the scheme’s official withdrawal from the NIST signatures round followed.

The McEliece thread is messier because the attacks are still partly heuristic and because the scheme already sits in ISO standards and in several national recommendations. Demi Marie Obenour summarized the opening shot: a paper by Ashrujit Ghoshal, Yuval Ishai, Aayush Jain, and Nuozhou Sun claiming a provable quasipolynomial-time distinguisher for Classic McEliece public keys from random bytes, plus a heuristic quasipolynomial decryption algorithm. “The claimed complexity of the distinguisher is below security level 1 for all parameter sets proposed by the Classic McEliece team.” Obenour’s assessment was blunt: “The attack is currently impractical, but if it works, it seems quite devastating for Classic McEliece and for Goppa McEliece in general.” Mitigations that restore the claimed margins would push ciphertext sizes to quadratic in the security parameter, at which point she asked whether the scheme would retain “any advantages over HQC or BIKE.”

Subsequent refinements tightened the numbers. A follow-on holdout paper claims attack costs in the 2^94 to 2^102 bit-operation range across the Classic McEliece parameter sets. Christopher Peikert pressed the obvious consequence for the higher categories: even the Category 3 and 5 sets, previously advertised near 2^207 and 2^272, are claimed to fall to roughly 2^102. Quoting Obenour, he asked whether it is now “fair to claim that Classic McEliece is broken” for those parameters and how the risk analysis should be rewritten.

Not everyone accepts the cost model at face value. D. J. Bernstein argued that the stated 2^94 figure for mceliece348864 understates the real bottleneck: “generating and routing roughly 2^93 bits across many terabytes of RAM.” Unlike a pure search that benefits from massive parallelism or Grover speedups, “2026/1984 doesn’t merge work across keys: each key has a separate gigantic linear-algebra problem.” Bernstein has long opposed 128-bit search targets on practical grounds; here he is using similar hardware-cost reasoning to push back on the idea that the new numbers already equal a practical break. The disagreement is therefore not only about asymptotic complexity but about what “bit operations” mean once memory movement dominates.

Even so, several voices on the forum have moved from caution to explicit non-recommendation. Markku-Juhani O. Saarinen wrote that “multiple researchers familiar with the matter, myself included, are now ready to recommend against using Classic McEliece at its stated security levels.” John Mattsson agreed and added an institutional critique: it is “a bit embarrassing for ISO that it standardized Classic McEliece only a few months ago, despite clear warnings from ANSSI and some other cybersecurity agencies.” He contrasted that with NIST’s process, which he still regards as having done “almost everything right,” and pointed to guidance that privileges open standardization and large-scale deployment experience.

A natural fear is contagion to the lattice schemes already standardized or nearing final approval. Oscar Smith asked whether anything “in principal” stops the same techniques from taking down the rest of lattice-based crypto. Saarinen and Jacob Alperin-Sheriff both answered in the negative. The McEliece attacks exploit the specific hidden Goppa structure; “the hidden structure in all the other schemes public keys is very different.” Saarinen further noted that HQC, the code-based KEM advancing toward FIPS 207, does not rely on Goppa codes or the same trapdoor. NIST IR 8545 had left a door open for future McEliece consideration; that door is now under active re-evaluation.

What remains unresolved is the practical gap between “below the claimed level” and “deployed systems are unsafe today,” and how quickly standards bodies and national agencies will revise language that still calls Classic McEliece conservative. HAWK is gone from the signatures round; Falcon and ML-DSA are explicitly untouched by the dimension-halving result. Classic McEliece still has defenders on cost-model grounds and still appears in recent ISO text, yet a growing set of cryptographers no longer endorse its stated margins. Implementers who chose it for long-term conservatism now face a narrower set of alternatives and a tighter calendar. The dual hit does not collapse the entire post-quantum portfolio, but it compresses the margin for error on everything that is left.