Paper 2026/1313

So Long, and Thanks for All the Seeds: Attacking GGM-trees in Post-quantum signatures

Abstract

Post-quantum signatures built from Fiat--Shamir transforms of zero-knowledge identification protocols---including LESS, CROSS, and MEDS---use GGM-tree seed compression to shrink signatures, revealing only the seeds of public rounds while hiding the challenge-dependent ones. This mechanism introduces a fault-attack surface: faulting the seed-publication can expose hidden seeds alongside their zero-knowledge responses, enabling recovery of secret information. We introduce the Generic ZK Seed Tree (GZKST), a unified abstraction of GGM-tree generation, challenge partitioning, and seed publication across these schemes, and formalize its correctness and seed-hiding invariants. We show that prior attacks on LESS-v1 and LESS-v2 violate the same invariant despite targeting different implementation layers and tree constructions, derive generic key-recovery algorithms from this view, and bound the number of effective faulted signatures needed for full recovery---only a few successful queries suffice for every MEDS parameter set. We further demonstrate the attacks in practice through clock-glitch fault injection against the MEDS reference implementation on an ARM Cortex-M4 (ChipWhisperer-Lite), identifying multiple exploitable surfaces in tree traversal and path construction that enable complete tree disclosure, partial subtree recovery, or leakage of hidden leaves.