MAMBA-Frost

Every Frost profile clears its level in the MATZOV model only; in core-SVP all five are below it

Holds · Argued · Cause: parameter size

Property: key recovery

Cost against claim: key recovery 2^107.8, 2^175.3, 2^236.4, 2^376.8 and 2^498.7 in core-SVP against 2¹²⁸, 2¹⁹², 2²⁵⁶, 2³⁸⁴ and 2⁵¹²; above every level in the MATZOV model, the designers' main estimate

No attack below the requirement was found, but the margin depends on the cost model, which the call leaves open. The designers rate their profiles with the MATZOV estimate, in which every profile clears its level: by 3.8 bits at Frost-128, 5.7 at Frost-192, 1.1 at Frost-256, 9.8 at Frost-384 and about 1 at Frost-512. In the core-SVP model, the conservative baseline they report beside it, the generic key-recovery attacks on the same instance cost 2^107.8, 2^175.3, 2^236.4, 2^376.8 and 2^498.7 (the dual-hybrid attack), 7 to 20 bits under the level, and the primal attack is also below it at Frost-128, Frost-192 and Frost-256 (2^110.4, 2^185.4 and 2^251.1). The one-bit MATZOV margins at Frost-256 and Frost-512 belong to the dual-hybrid attack alone, whose heuristics are debated; the primal attack leaves 12 bits at Frost-256 and more than 20 at Frost-512.

What causes it

Table 3 (section 3.1) fixes n = m, q, the binomial parameter η and the quantization steps of each profile, and gives three estimates for each: MATZOV, core-SVP classical and core-SVP quantum. Claim 6.3 (section 6.1) and section 6.4 take MATZOV as the main estimate and present the core-SVP columns as a conservative baseline: the claim is that the MATZOV estimates exceed the targets, and the core-SVP column, reported beside it, is below the target at every profile. The dither is public and drawn from the whole range 0 to Δ−1 (section 9.7), so the LWQ key instance is an ordinary LWE instance whose error is uniform on an interval of width Δ = q/2^t (its second moment is the one used in section 6.2), and the generic lattice attacks apply to it unchanged.

Evidence

The key-recovery instance was read from the specification: LWE with n = m = 512, 880, 1288, 1928 and 2600, q = 2¹⁵ at Frost-128 and 2¹⁶ above, a centred binomial secret with η = 2 at Frost-128 and η = 1 above, and a bounded uniform error of width 32, 32, 8, 8 and 4 (at Frost-256 the ciphertext instance, of width 16, is the harder one, so the public-key instance is the one rated). Costs were computed with the public lattice estimator in both models, after checking the setup on Kyber-512 (block size 406, 2^118.6 core-SVP), with its block-size and dimension ceilings lifted, since the primal block size at Frost-512 (1828) exceeds the default ceiling. The MATZOV figures so obtained agree with the designers' Table 3 to 0.1 bit from Frost-128 to Frost-384; at Frost-512 the run without ceilings gives 2^513.2 against their 2^512.97. A second member of PQC-X re-read the parameters from the specification, re-ran the core-SVP figures at every profile with the ceilings lifted (all agree to 0.1 bit with the figures above), reproduced the primal block sizes with an independent calculator that uses no estimator code (379, 635, 860, 1380 and 1828), checked at Frost-256 that a Gaussian error of the same variance gives the same figures, and checked that no ceiling binds at Frost-384.

Cause in the specification, traced to the specification text.

Limits

An estimate, not an attack: no key was recovered and nothing runs below 2⁸⁰. The shortfall exists in one cost model and not in the other, and the call names none, so it is not counted as a break; the site's own precision is 8 bits. The dual-hybrid figures rest on independence heuristics that the literature questions. The MATZOV figure at Frost-512 (2^512.97 in the designers' table, 2^513.2 in our run without the estimator's ceilings) was not re-derived by a second member of PQC-X; the core-SVP figures were. Frost-CC-384 and Frost-CC-512 exchange the two message dimensions and leave the key-recovery instance unchanged. Frost-192 targets a level the call does not define.

Credit

Found by PQC-X.

Core-SVP: Alkim, Ducas, Pöppelmann and Schwabe (USENIX Security 2016). The MATZOV cost model and dual-hybrid attack: MATZOV, Report on the Security of LWE (2022); its independence heuristic is questioned by Ducas and Pulles (CRYPTO 2023). Figures from the lattice estimator of Albrecht, Player and Scott (Journal of Mathematical Cryptology 2015, maintained since).

Decapsulation restores the sign of each secret coefficient with a branch, in every submitted build

Holds · Demonstrated · Cause: code

Property: constant-time execution of decapsulation, which the specification requires; no claimed security property falls

Cost against claim: none without local access; with every sign of S known, key recovery still costs about 2⁹⁷ to 2¹⁰¹ at Frost-128 and 2¹⁵⁷ to 2¹⁶⁹ at Frost-256 (core-SVP)

Decapsulation unpacks the long-term secret matrix S from its packed form and restores the sign of each coefficient with a conditional on its top bit. gcc compiles it to a conditional jump and a conditional store in every submitted build, so the control flow of one decapsulation reveals which coefficients are negative: about 0.9 of the 2.03 bits of each coefficient at Frost-128 and 0.8 of 1.5 bits above, where every coefficient equal to −1 is exposed outright. The pattern is the same at every call, so an observer of the control flow on the device (power or electromagnetic traces on the Cortex-M4 platform the designers benchmark, branch-predictor probing) can average it; remote timing sees only about 10 bits per key. No claimed property falls: even with every sign known, recovering the rest of S costs about 2⁹⁷ to 2¹⁰¹ at Frost-128 in core-SVP.

What causes it

Section 8.3 requires implementations to avoid secret-dependent branches and memory accesses, and section 9.3 packs S with 3 bits per coefficient at Frost-128 and 2 bits above. The specification is sound on this point; the defect is in the code. In crypto_kem_dec (kem.c, line 493 of the reference and optimised trees; line 492 of the native tree and line 381 of its kem_u32.c), the loop that follows the unpacking of S tests the top bit of each coefficient and writes the sign-extended value only when it is set. A branch-free sign extension (an arithmetic shift, or a mask derived from the top bit) removes it; the comparison, the selection of the shared secret and the E8 decoder are already constant-time.

Evidence

Fresh, unmodified builds of the reference Frost-128 (gcc 13.3, -O2) and of the optimised Frost-128 (-O3 -mavx2 -maes -flto), both reproducing the official test vectors byte for byte, contain for this loop a test of the sign bit, a conditional jump and a conditional store, executed over the 4096 coefficients of S; the reference Frost-512 shows the same sequence over its 20800 coefficients. Under valgrind, with only the packed S and the rejection string z marked undefined, one decapsulation reports exactly one context, this loop: 4096 conditional jumps at Frost-128 (reference and optimised), 20800 at Frost-512, and nothing elsewhere in decapsulation. The same loop is in all ten reference and all ten optimised instances, in their API_PKC copies and in the native trees. A second member of PQC-X rebuilt the three instances from the submission, re-read the disassembly, ran an own valgrind harness with the same counts, computed what the branch reveals per coefficient, and re-ran the key-recovery estimates with the sign pattern taken as known: the primal core-SVP cost falls from 2^110.4 to about 2¹⁰¹ at Frost-128, from 2^251.1 to 2^168.8 at Frost-256 and from 2^533.8 to 2^365.6 at Frost-512; the dual-hybrid, to about 2⁹⁶ to 2⁹⁷ at Frost-128 and 2^156.5 at Frost-256.

Cause in the submitted code; the specification is not affected.

Limits

A finding on the submitted code, not on the design, which asks for the opposite. The leak needs an observer of the control flow on the device (power, electromagnetic or micro-architectural), not a network peer. The sign-conditioned costs are estimates with the whole pattern assumed known, and they stay far above 2⁸⁰; no key was recovered.

Credit

Found by PQC-X.