MAMBA-NIKE

A few hundred chosen one-pass messages and the responder's reactions recover its long-term secret

Practical · Tested at small scale · Cause: construction

Property: key recovery

Cost against claim: static key recovery with a few hundred chosen messages, against 128 to 512

Scope: Every deployment in which the responder's long-term key serves more than one session and its acceptance of the derived key can be observed.

The responder keeps one long-term secret s and derives a key from every message it receives: it rebuilds the response label û and the helper h from the message as sent, computes û·s and reconciles, with no validity check on the message and no transform that would expose a dishonest one. An attacker who sends chosen (û, h) pairs and learns whether the responder's key agrees with a guess (a key confirmation, a first protected record) reads the secret off block by block: the reused-key signal-leakage attack on reconciliation-based key exchange, which the design does nothing to prevent, on a key that is static by definition of the scheme.

What causes it

Algorithm 3 (Derive) takes µ, u and h straight from M1, computes w = û·s and ν = Rec(w, h), and derives the key; nothing is re-encrypted or compared, and section 8.11 asks an implementation to check lengths only, so any u and h of the right length are processed with the long-term key (nike_shareda and kex_derive_ss_b in the code do the same). Section 6 and Appendix B prove passive real-or-random security only, and Appendix B.4 states that no IND-CCA or active security is claimed. The call, however, requires a key exchange to withstand active adversaries, and a party with a long-term key that answers arbitrary messages is exactly the setting of the reused-key attacks; a non-interactive key exchange cannot escape it by refreshing its key.

Evidence

PQC-X first recovered 8 of 8 blocks of a secret with 312 chosen pairs (39 scalar multiples of the secret, 8 helper values) against a byte-for-byte port of the submitted decoder. A second member of PQC-X rewrote the run in C around the submitted error_correction.c itself, checked it against the specification's reconciliation formula on 102,400 random blocks (no mismatch), and applied the same 312 pairs to all 256 blocks of full n = 1024 secrets: 205 and 234 blocks of 256 are pinned uniquely for η = 7 (the distribution of the 256 set), 196 and 207 for η = 5 (that of the 512 set), and every remaining block is left with a few candidates that always include the true one; 632 pairs give identical counts. The scalar family therefore recovers about four fifths of the secret outright, and the rest needs probes of a richer shape rather than more of the same, still far below 2⁸⁰.

Cause in the specification: the attack also works on a model built from the specification alone.

Limits

The run idealises the oracle in two ways: the probes are exact scalar multiples of the secret, which the label and dither grid of a real message only approximates, and about a fifth of the blocks stay ambiguous with scalar probes alone; the general reused-key attack removes both, at a cost that stays far below 2⁸⁰ but was not measured. The attack needs to observe the responder's reaction to the derived key, which the specification's passive experiment does not expose but which any use of the key provides. A responder that draws a fresh key for every session is not affected, but the exchange is then no longer non-interactive.

Credit

Found by PQC-X.

Fluhrer (ePrint 2016/085); Ding, Alsayigh, Saraswathy, Fluhrer and Lin (IEEE ICC 2017).

A 32-byte secret seed at every level caps MAMBA-NIKE-384 and -512 at 2²⁵⁶

Minor break · Argued · Cause: parameter size

Property: key recovery

Cost against claim: key recovery 2²⁵⁶ classical, about 2¹²⁸ quantum, against 384 and 512

The long-term secret s and the ephemeral secret r are both expanded by ChaCha20 from a 32-byte seed, at every level. Guessing the seed, regenerating the secret and recomputing the public label (b from the public key, u from the one-pass message) identifies the right guess with a deterministic check, so no key and no session of MAMBA-NIKE-384 or -512 costs more than 2²⁵⁶ classically, or about 2¹²⁸ Grover iterations, whatever the ring dimension. The lattice problem itself is far harder (PQC-X's own estimates stay above 2⁴⁸⁰ at both levels in every cost model tried): the seed is the binding limit.

What causes it

Section 8.6 (Secret Sampling) fixes a fresh 32-byte seed for s and another for r, each expanded by ChaCha20 into centered-binomial coefficients; section 8 sets SEEDBYTES = 32 for every profile. Section 8.11 then requires a conforming implementation to reproduce the reference's seed expansion and sampling exactly. The submitted code follows it in all five profiles and both tracks: nike.c draws a 32-byte noise seed and poly_getnoise feeds it to a ChaCha20 stream keyed on 256 bits. The secrets themselves carry well over 2000 bits of entropy at every level, so only the seed limits the search.

Evidence

Argued from the specification and checked in the code: the 32-byte seed and the 256-bit ChaCha20 key were found in the reference and optimised sources of all five profiles. A second member of PQC-X reread section 8.6, re-derived the entropy of the secrets (about 3000 to 5500 bits for the 256, 384 and 512 sets, so the seed is the limit), recomputed the cost against each level's classical and quantum requirement, and confirmed that the ephemeral seed gives the same ceiling to a purely passive attacker. Nothing was run: the search is out of reach.

Cause in the specification, traced to the specification text.

Limits

At MAMBA-NIKE-256 the seed equals the claim, 2²⁵⁶ classical and 2¹²⁸ quantum, with no margin; at 128 and 192 the seed exceeds the level. A seed of the level's length is the fix.

Credit

First public report: M.-J. Saarinen (ngcc.dev kex-06-1, 2026-09-21). Found independently by PQC-X.