Reports › sign-11

FlexTree (sign-11)

sign-11-1: PORS counter grinding reduces every claimed security level

FlexTree first derives the PORS instance from HMSG(R, PK.seed, PK.root, msg), then searches a 32-bit counter in HPORS(R, ctr, md) until the selected subset passes forced pruning. Verification accepts any successful counter. An attacker can therefore keep the instance fixed while trying up to 2^32-1 different subsets, whereas the submitted bound models every trial as selecting a fresh random instance.

At the unstated q_sig = 2^64 budget that reproduces the specification's security table, an independent evaluation of the paper's raw attack gives 133.1, 128.9, 225.2, 224.2, 352.2, 352.0, 480.0, and 480.0 bits for the 160s through 512f sets. Accounting for repeated leaves and the forced-pruning condition raises these estimates but still leaves the claims overstated by approximately 20 to 32 bits.

The repair is to bind the counter into the hash that selects the PORS instance, or require and verify the unique minimal acceptable counter.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py

sign-11-2: The specified deterministic mode is length-extendable

The specification permits deterministic signing with optRand = PK.seed and defines PRFMSG as a raw secret-prefix SM3 construction rather than a PRF such as HMAC. For 160 and 256, R is a truncation of SM3(SK.prf || PK.seed || M); for 384 and 512, its first block is SM3(SK.prf || PK.seed || M || 1). Because SM3 is Merkle-Damgård, a signature reveals enough chaining state to predict the randomizer for suitable message extensions. The 160-bit sets require recovery of the 96 truncated state bits; the other sets disclose a full state.

The predictable randomizer lets a chosen-message attacker determine the PORS/XMSS instance of an extension before requesting its signature, then combine chosen-instance accumulation with counter grinding. Kudinov estimates total costs between 2^74.5 and 2^79.4 for the 256-, 384-, and 512-bit sets and 2^96 for both 160-bit sets, all below their claims.

The submitted code always draws fresh optRand, so this is a break of the normative deterministic option rather than the shipped hedged mode. PRFMSG should use HMAC-SM3 or another prefix-free PRF construction.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py

This confirms the raw secret-prefix construction, the counter-mode XOF, and the shipped implementation's hedged-only path. It does not reproduce the optimized attack cost or the end-to-end witness, which is not part of this repository.

sign-11-3: The specified OTS verifier omits its encoding checks

Algorithm 9 accepts an OTS digest only when its leading zb bits are zero and its digit vector has the required constant sum. Algorithm 10 and the abstract verifier in Construction 1 recompute the digits but enforce neither condition. Without those checks, the claimed incomparable encoding becomes an ordinary checksum-free Winternitz encoding.

Given one OTS signature with digits x, an attacker searches for a target digest whose digits x' satisfy x' >= x componentwise, then advances every disclosed chain by x'-x. Independent generating-function calculations reproduce Kudinov's per-trial costs of 2^33.35 through 2^128 for all eight specified parameter sets. Reusing the top XMSS signature and freely choosing the lower signature material adds the seven-bit top-layer leaf match for FlexTree-160s, giving about 2^(33.35+7) = 2^40.4 work. The analogous estimate for 160f is about 2^(47.25+3) = 2^50.3.

The submitted wots_pk_from_sig does perform both checks, so existing binaries are not affected. The normative verifier must explicitly enforce the zero-bit and constant-sum conditions.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py

sign-11-4: A 256-bit SM3 state caps the 384- and 512-bit sets

The 384- and 512-bit parameter sets expand SM3's 256-bit state with a counter-mode XOF. Longer output does not increase the internal state: a state collision extends to every output block, and generic preimage security remains capped at 256 classical bits and 128 quantum bits. These sets therefore cannot provide the 384/192 and 512/256 classical/quantum strengths printed in Table 1.3.

The specification acknowledges on page 45 that the SM3 instantiations may not reach their named levels, but still presents those levels as the parameter sets' security strengths. Meeting them requires a primitive with a sufficiently large internal state, not merely a longer XOF output.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py

The script checks the submitted counter-mode SM3 construction and the affected parameter widths. This is a source/parameter check, not a brute-force attack.

sign-11-5: Unchecked PORS padding makes signatures malleable

PORS signatures reserve space for mMAX authentication nodes and zero-pad the unused suffix. The verifier recomputes the actual node count and reads only those nodes; neither the specification nor the implementation requires the remaining bytes to be zero. Whenever padding is present, it can be changed freely without invalidating the signature.

The existing 160f harness result is a direct witness: flipping bit 28911 at byte 3613 yields a byte-distinct signature that verifies for the same message and key. Source inspection places that byte in the unused PORS authentication-node suffix. This does not forge a new message and no explicit SUF-CMA claim was found, but it defeats canonical signatures and can break protocols that use a signature or its hash as an identifier.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

make -C sign-11 lib/libFlextree-160f.so
security/ngcc_security sign-11/lib/libFlextree-160f.so sig-signature-flip

sign-11-6: The specified PORS tree reuses leaf hash addresses

Algorithms 17 and 21 hash a height-1 PORS leaf for secret index i+s with (treeHeight=0, treeIndex=i). The same tweak is already used for height-0 leaf i, contrary to the specification's distinct-address requirement. Depending on the set, 516 to 95,017 tweaks per instance are reused for two independent secret values.

The collision gives a one-bit generic multi-target advantage on that leaf-preimage path and invalidates the distinct-tweak premise invoked by the security discussion. It also prevents interoperability: the submitted code correctly uses global leaf index i+s, so a literal implementation of the algorithms computes a different PORS root whenever a height-1 leaf is revealed. Both algorithms should use setTreeIndex(i+s).

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py

The reused-addresses column recomputes the collision count for every set.

sign-11-7: The implementation leaves 1 to 4 OTS digest bits unchecked

The code derives OTS digits from the leading 8n-zb digest bits but tests the high zb bits of the final byte. Those regions overlap for seven sets, leaving an equal number of other bits neither encoded nor checked. The effective matched lengths are 157, 159, 252, 255, 384, 382, 511, and 509 bits for 160s through 512f: losses of 3, 1, 4, 1, 0, 2, 1, and 3 bits.

This is not the best known attack because sign-11-1 is cheaper, and injectivity is not lost. It is nevertheless a concrete implementation-level shortfall from the claimed 8n-bit OTS digest path. The verifier must check exactly the zb bits excluded from digit decoding.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py

sign-11-8: Complementary constant-sum rounding breaks interoperability

Algorithm 9, the Section 1.7 prose, and Construction 1 explicitly require the OTS digit sum to be floor(sum_i(w_i-1)/2). The specified signer therefore terminates. For FlexTree-384f and FlexTree-512s, those digit sums are 1169 and 1565.

The code's chain_lengths instead computes the complementary sum sum_i(w_i-1-x_i) and compares it with WANTED_CHECKSUM values 1169 and 1565. Consequently, the code accepts digit sums 1170 and 1566, the ceilings rather than the specified floors. A specification-conformant implementation and the submitted implementation therefore reject each other's OTS signatures for these two sets.

The specification also leaves a “valid counter” predicate undefined, uses non-integral byte slices, disagrees with its tables about the HPORS argument order, and differs from the code's digit window and compressed-address encoding. These are additional interoperability defects, but the previously reported non-termination claim was incorrect.

Reproducing

Commands below run in a checkout of the ngcc-harness repository with the candidate built (see its README).

python3 security/flextree_kudinov_validation.py