On the recent "Guessing Game" Attack (2026/1318) on Hawk
168 views
Skip to first unread message
Markku-Juhani O. Saarinen
Jul 5, 2026, 8:34:55 AM (2 days ago) Jul 5
to pqc-forum
Hi All,
A recent preprint "Cryptanalysis of HAWK: a Guessing Game" ( https://eprint.iacr.org/2026/1318 ) claimed a classical polynomial-time attack on HAWK. The authors had not implemented their attack; the polynomial-time claim rested on four explicitly stated number-theoretic hypotheses.
Through implementation and experimentation, we found "Heuristic 4" of Guessing Game to be faulty, and as a consequence, the attack appears to run in exponential time in practice. The authors have acknowledged our findings. I have written a brief note (a "cryptanalysis-analysis") explaining why the attack, in its present form, does not pose a risk to Hawk's security.
A recent preprint "Cryptanalysis of HAWK: a Guessing Game" ( https://eprint.iacr.org/2026/1318 ) claimed a classical polynomial-time attack on HAWK. The authors had not implemented their attack; the polynomial-time claim rested on four explicitly stated number-theoretic hypotheses.
Through implementation and experimentation, we found "Heuristic 4" of Guessing Game to be faulty, and as a consequence, the attack appears to run in exponential time in practice. The authors have acknowledged our findings. I have written a brief note (a "cryptanalysis-analysis") explaining why the attack, in its present form, does not pose a risk to Hawk's security.
The preprint, and all relevant source & data can be found at: https://github.com/mjosaarinen/gg-artifact
Repo contents:
gg-note.pdf
Attack refutation write-up PDF (HAWK ``Guessing Game'' is not Polynomial-Time).
gg-sage/
Sage/Python scripts and JSON data for the experimental class-number and Heuristic-4 measurements.
gg-sage/gg-poc/
Reduced-parameter, public-data key-recovery proof-of-concept. This is a correctness witness for the algebraic recovery chain, not a scalable attack PoC.
gg-lean/
Lean 4 / mathlib formalizations of the super-polynomial and exponential conditional reductions.
This write-up should also appear within a week as an IACR ePrint:
Markku-Juhani O. Saarinen.
HAWK ``Guessing Game'' is not Polynomial-Time.
IACR Cryptology ePrint Archive, Report 2026/???, 2026.
Abstract.
We show that the runtime complexity of the attack described in "Cryptanalysis of HAWK: a Guessing Game" is much higher than originally claimed by its authors, and the attack is unlikely to pose a threat to HAWK's security in its present form.
The attack algorithm had not been implemented before this work; the polynomial-time running-time claim was based on four ``plausible heuristics''. Our experiments and implementation data point to a super-polynomial class-number obstruction, consistent with exponential-scale growth. The experiments also helped to identify faulty ``Heuristic 4'' as the source of the observed computational wall when scaling dimension $n$. The authors of Guessing Game have acknowledged our findings. To make the argument more universal, we also offer a machine-checked conditional reduction from explicit assumptions that shows the complexity to be at least super-polynomial.
In terms of methodology, our work demonstrates the role of powerful AI tools in contemporary cryptanalysis -- the sudden feasibility of rapid exploration and trial implementation of advanced attack techniques. A public research artifact contains all source code and datasets to reproduce our results.
--
Repo contents:
gg-note.pdf
Attack refutation write-up PDF (HAWK ``Guessing Game'' is not Polynomial-Time).
gg-sage/
Sage/Python scripts and JSON data for the experimental class-number and Heuristic-4 measurements.
gg-sage/gg-poc/
Reduced-parameter, public-data key-recovery proof-of-concept. This is a correctness witness for the algebraic recovery chain, not a scalable attack PoC.
gg-lean/
Lean 4 / mathlib formalizations of the super-polynomial and exponential conditional reductions.
This write-up should also appear within a week as an IACR ePrint:
Markku-Juhani O. Saarinen.
HAWK ``Guessing Game'' is not Polynomial-Time.
IACR Cryptology ePrint Archive, Report 2026/???, 2026.
Abstract.
We show that the runtime complexity of the attack described in "Cryptanalysis of HAWK: a Guessing Game" is much higher than originally claimed by its authors, and the attack is unlikely to pose a threat to HAWK's security in its present form.
The attack algorithm had not been implemented before this work; the polynomial-time running-time claim was based on four ``plausible heuristics''. Our experiments and implementation data point to a super-polynomial class-number obstruction, consistent with exponential-scale growth. The experiments also helped to identify faulty ``Heuristic 4'' as the source of the observed computational wall when scaling dimension $n$. The authors of Guessing Game have acknowledged our findings. To make the argument more universal, we also offer a machine-checked conditional reduction from explicit assumptions that shows the complexity to be at least super-polynomial.
In terms of methodology, our work demonstrates the role of powerful AI tools in contemporary cryptanalysis -- the sudden feasibility of rapid exploration and trial implementation of advanced attack techniques. A public research artifact contains all source code and datasets to reproduce our results.
--
Feedback (cryptanalysis-analysis-analysis?) is welcome :)
Cheers,
-markku
Cheers,
-markku
Reply all
Reply to author
Forward
0 new messages