FlagThis

Abstract

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 __ = FirstBits __ ( _x_ ) denotes the prefix of the long-term witness _x_ , the sibling path determines a public value _A_ such that tree parity gives _s_ = _ A_ . Substitution into the published hidden-leaf commitment then yields the public equation Enc _K_ ( _ A_ ) = _T _ LinOrtho( __ ) _,_ where _K_ and _T_ are public transcript values. The correction contained in the same signature expands a solution into a complete witness, and the public MQ relation identifies the solutions that yield valid signing keys; serializing such a witness produces the complete secret key, which the reference signer uses to produce a fresh-message signature accepted by the reference verifier. We evaluate this equation over the specified AES/Rijndael circuits by retaining the circuit state along a Gray traversal. Complete-domain scans for Categories I and V cost 2[142] _[.]_[335112] and 2[271] _[.]_[794162] Boolean gates, while the 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, respectively. All four totals lie below the corresponding NIST security benchmarks. Reduced-domain executions against the reference implementation recover the byte-exact witness and key in all three categories and produce a freshmessage forgery accepted by the reference verifier; independently generated sourcesyntax circuits evaluate the fixed ciphers directly over the stated complete domains and translated L3 prefixes, and an exact ideal-cipher factorial-moment bound controls the number of additional equation preimages passed to public-key validation. Every value in the equation is determined by the accepted transcript, so salt-bound globalroot expansion changes its public constants without removing the one-signature recovery channel.