Full-Key Recovery and Forgery from One MQOM v2.1 Signature

This paper presents a full-key-recovery attack on MQOM v2.1, a Round-3 candidate in the NIST additional-signature process. The attack recovers the complete signing key from one accepted signature and uses it to produce a fresh-message forgery accepted by the reference verifier.

The attack derives a public equation from a single signature. The paper states: "The signature opens all but one leaf of a correlated binary seed tree; because each parent is the XOR of its children, the published sibling path expresses the hidden leaf as s = δ ⊕ A, where A is public and δ = FirstBitsλ(x) is a fixed prefix of the long-term witness x."

Substituting this identity into the commitment to s gives the public equation:

EncK(δ ⊕ A) = T ⊕ LinOrtho(δ) (Equation 1)

where K and T are public transcript values. The paper explains: The correction suffix expands a solution δ̂ into a complete candidate witness x̂; the public MQ equation identifies the candidates that can be serialized as signing keys and used for fresh-message signing.

The attack evaluates this equation over the specified AES/Rijndael circuits using a Gray traversal that retains circuit state between adjacent candidates. The reported costs are:

• Category I (L1): Complete domain scan costs 2 142.335112 Boolean gates (gap of 0.664888 below the 2 143 benchmark)

• Category III (L3): Two scans covering 1/2 + 2-20 and 0.580004770183 of the domain at costs of 2 206.774558 and 2 206.988685 gates respectively (gaps of 0.225442 and 0.011315 below the 2 207 benchmark)

• Category V (L5): Complete domain scan costs 2 271.794162 Boolean gates (gap of 0.205838 below the 2 272 benchmark)

Theorem 1 (Hidden-leaf path identity): The paper proves that δ = se ⊕ Ae, where se is the hidden leaf and Ae is the XOR of published sibling roots. The proof states: The XOR of a parent's two children equals the parent, and induction on the subtree height therefore identifies every node with the XOR of the leaves below it.

Theorem 2 (Commitment-to-δ compilation): For every published commitment half Ce,c, defining Te,c = Ce,c ⊕ LinOrtho(Ae) yields the public equation EncKe,c(δ ⊕ Ae) = Te,c ⊕ LinOrtho(δ).

Proposition 1 (Signing-key recovery from a validated prefix): If x̂ satisfies the public MQ instance Q(x̂) = y, then the public-key seed and serialized x̂ form a valid secret key for the reference implementation.

Theorem 3 (Exact factorial moments): For the ideal-cipher model, the paper proves E[(X)t] = (P-1)t/(N-1)t and Pr[X ≥ t] ≤ (P-1)t/((N-1)t·t!). For P = N and t = 64, the bound is exactly 1/64! < 2-295.995143941724.

Theorem 4 (One-signature full-key recovery): The attack succeeds with probability at least 1 - 1/64! in Categories I and V, at least 1/2 + 2-20 - 2-346.29 for the L3 half-coverage row, and greater than 0.580004770182 for the L3 high-coverage row.

The paper reports: "For the F256 representative of each category, the reference harness performs the following computation: reference key generation, signing, and verification; extraction of the hidden commitment and sibling path from the accepted signature; enumeration of a 16-bit affine section using the public Equation (3); reconstruction of δ, every required seed, the complete MQ witness, and the serialized secret key; signing of a fresh message with the recovered key and verification by the reference verifier."

These executions recover the byte-exact witness and key in all three categories and produce a fresh-message forgery accepted by the reference verifier.

For transcript L1 e11h0, the paper describes an internal-cut optimization: "The optimal cut among the twenty evaluated positions for transcript L1 e11h0 has log2 G = 141.99331513385556, M = 934816 bytes, and stores complete 128-bit cut states, making every match equivalent to a solution of Equation (3)."

The paper identifies three critical components that enable the attack: (i) the path-to-prefix map, (ii) the hidden-leaf predicate, and (iii) the correction-to-witness map. It states: Removing the one-signature channel requires a change to the path, commitment, or correction map.

Regarding salt-bound root expansion, Theorem 6 proves: Salt binding changes the path nodes and the resulting public value Ae, but tree parity still gives se = δ ⊕ Ae, whose substitution into the commitment gives Equation (3). Thus, salt-bound global-root expansion changes its public constants without removing the one-signature recovery channel.

The paper notes: "Feneuil and Rivain describe an attack in which a correct guess of the λ-bit witness prefix reconstructs the hidden path, leaf, missing share, and complete witness. In their partial-guessing one-wayness game, a correctness oracle identifies the prefix; exhaustive testing has estimated cost 2 λ·tG. The current attack obtains that correctness predicate from an accepted v2.1 signature" without needing an oracle.

The paper also presents multi-signature master-seed extensions that reverse the data–work balance: choose a searchable set of 128-bit master-seed candidates, collect many signatures, and succeed when the signing seed of any retained signature lies in that set. These achieve Category-I gate work of approximately 2 122.67-2 123.00 at costs of 774,144 to 2,097,152 signatures and 9.97-50.62 GiB memory.

The paper concludes: "We show that one accepted MQOM v2.1 signature determines a fixed-cipher equation in the long-term witness prefix: the sibling path fixes its affine input, and the hidden-leaf commitment fixes its target. We use the published correction to expand a validated solution into the complete MQ witness, serialize that witness as the signing key, and sign a fresh message. The attack derives every value in its equation from public fields of an accepted transcript, and the same equation persists under salt-bound global-root expansion."

Improvement 1: Cryptographic Protocol Auditing via Automated Equation Derivation

The improved AI system can automatically parse a signature scheme’s specification (e.g., tree structures, commitment schemes, linear maps) and derive public equations linking secret prefixes to transcript values. It would detect hidden-leaf path identities (like Theorem 1) and compile commitment-to-prefix equations (like Theorem 2) without manual cryptanalysis. This enables proactive identification of one-signature key-recovery channels in any candidate scheme before standardization.

Improvement 2: Cost-Aware Attack Planning with Circuit-State Reuse

The AI can optimize exhaustive-search attacks over structured domains (e.g., Gray traversal) by modeling Boolean-gate costs and retaining intermediate circuit states between adjacent candidates. It would automatically select optimal internal cuts (as in the L1 e11h0 transcript) to minimize total gate work, predict exact cost gaps below security benchmarks, and generate implementation-level attack plans with memory/time trade-offs.

Improvement 3: Probabilistic Success Bounds for Multi-Signature Attacks

The AI can compute exact factorial moments (as in Theorem 3) for any candidate attack distribution, then derive tight upper bounds on failure probability (e.g., 1/64!) and success thresholds for partial domain coverage. It would recommend optimal signature counts and memory allocations (e.g., 774K–2M signatures, 10–50 GiB) to achieve target success probabilities under resource constraints.

Improvement 4: Formal Verification of Key-Recovery Conditions

The AI can formally prove or disprove that a recovered prefix (δ̂) serializes into a valid signing key by checking public MQ instances (Proposition 1). It would integrate with reference implementations to validate byte-exact key reconstruction, ensuring that any proposed attack yields a fresh-message forgery accepted by the verifier—not just a theoretical match.

Improvement 5: Design-Space Exploration for Protocol Hardening

Given a vulnerable scheme, the AI can systematically mutate the path, commitment, or correction maps (as suggested in the paper) and re-run automated equation derivation to test whether the one-signature channel persists. It would identify minimal changes (e.g., salt-bound root expansion) that fail to remove the vulnerability, and propose alternative structures that break the public-equation link.

Improved AI System Capability Summary

The enhanced system can: (1) automatically discover hidden algebraic relations in signature schemes, (2) quantify attack costs in exact gate counts with optimized circuit traversal, (3) compute rigorous success probabilities for adaptive attack strategies, (4) verify end-to-end forgeries against reference implementations, and (5) guide designers toward provably secure modifications—all without human cryptanalytic effort.

We give a full-key-recovery attack on MQOM v2.1, a Round-3 candidate in the NIST additional-signature process, that recovers the complete signing key from one accepted signature and uses it to sign a fresh message. If delta= FirstBits lambda(x) is the prefix of the witness x, the sibling path determines a public value A such that tree parity gives s= delta A. Substitution into the hidden-leaf commitment yields K(delta A)=T (delta) with public values K and T. The correction in the same signature expands a solution into a complete witness, while the public MQ relation identifies those yielding valid signing keys; serializing such a witness gives the secret key, enabling a fresh-message signature accepted by the reference verifier. We evaluate this equation over the specified AES/Rijndael circuits using retained circuit state along a Gray traversal. Complete-domain scans for Categories I and V cost 2 142.335112 and 2 271.794162 Boolean gates. Category-III scans cover 1/2+2-20 and 0.580004770183 of the domain at costs of 2 206.774558 and 2 206.988685 gates. All four totals are below the NIST security benchmarks. Reduced-domain runs against the reference implementation recover the byte-exact witness and key in all three categories and produce a fresh-message forgery accepted by the reference verifier. Independently generated source-syntax circuits evaluate the fixed ciphers over the stated domains and translated L3 prefixes, while an exact ideal-cipher factorial-moment bound controls additional equation preimages passed to public-key validation. Every value in the equation is fixed by the accepted transcript, so salt-bound global-root expansion changes its public constants without removing the one-signature recovery channel.