Paper 2026/1542

Signing-Key Recovery from Unsalted Root Expansion and Salt-Binding Repair for MQOM v2

Abstract

We give the first passive classical EUF-CMA attack on MQOM v2 in which an optimal three-record parity-indexed XOR triangle detects every usable collision, recovers the complete signing key, and produces a fresh-message forgery. In MQOM v2, every correlated-GGM root is derived from a fresh $\lambda$-bit master seed using a fixed PRG call with zero salt, while a public opening reveals either the corresponding root or its XOR with a fixed prefix of the long-term MQ witness. The resulting root functions are shared by all signatures, keys, salts, and v2 releases, so repeated master seeds expose linear equations in the witness. In Category I at the permitted $Q=2^{64}$ signing-query boundary, the attack has birthday-regime success $0.393395296381$ with error $O(2^{-64})$. A rank-two extension recovers two unrelated keys, while reusable global tables attain membership-certified lower bounds of $0.632030733547$ for the complete triangle and $0.776706354579$ for the record-optimal one-root allocation at $P=Q=2^{64}$. The same fixed root functions support full-key recovery in every security category and reusable precomputation across targets and versions, while a streaming first-distinguished-point construction replaces storage of the signature corpus with certified chain coverage and an identifier-free endpoint index. Its membership-hit law is exact conditional on realized distinct coverage, with separate forecasts for chain construction, tags, fingerprints, and MPHF storage; a Category-I GF(2) design point uses 52 GiB, $2^{52}$ signatures, and target coverage $C=2^{77}$; conditional on that coverage, its success is $0.631940886333$ and its normalized serial forecast is below $2^{94}$. Pinned probes reproduce the fixed roots for every official tag from v2.0.0 through v2.1.1 and a pinned current revision in Categories I, III, and V, and salt-bound, domain-separated root expansion eliminates the collision and reusable-precomputation channels.

Note: Updated with MQOM team acknowledgment and artifact link.