Add ML-DSA test vectors (FIPS 204 standard).

[gendx]

This PR adds test vectors for ML-DSA, for the FIPS 204 standard. It's a restart of https://github.com/C2SP/wycheproof/pull/112 without the pre-standard versions (round 3, ipd).

These tests aim to cover the following cases:

• Baseline (signing a "Hello world" message).
• Keys and signatures of the wrong length.
• Signature with bit flips.
• Signature hints with a non-canonical encoding:
  • hints that aren't sorted,
  • hints are not strictly sorted (i.e. the same hint is repeated),
  • too many hints (potentially causing a buffer overflow),
  • non-zero padding after the hints.
• Secret keys with the s1 or s2 vectors out of the [-eta, eta] range.
• Public key with the t1 component set to zero (allowing trivial forgeries, but the verification algorithm should still accept signatures for this key).
• Boundary conditions in the signature rejection loop (aiming to detect incorrect comparisons):
  • z_max equals gamma1 - beta - 1 and gamma1 - beta,
  • r0_max equals gamma2 - beta - 1 and gamma2 - beta,
  • h_ones equals omega and omega + 1,
  • in the case of ML-DSA-44, |ct0|_max equals gamma2 - 1 and gamma2.
• A "large" number of SHAKE bytes and of SHAKE blocks generated in the expand_a, expand_s, rej_ntt_poly and rej_bounded_poly functions.
• Boundary conditions in arithmetic functions:
  • power_2_round function: when the remainder (found in t0) is equal to 4096 or -4095,
  • decompose (via high_bits or low_bits): when the condition r_plus - r_0 = q - 1 happens.

Beyond the baseline API, also covered are:

• The context value: empty (default), regular length, or context too long.

What isn't covered:

• The randomized variant (only the deterministic variant is covered).
• The pre-hased variant "HashML-DSA" (only the regular variant is covered).

Notable difference(s) from the previous pull request (https://github.com/C2SP/wycheproof/pull/112):

• The algorithm now includes the level (e.g. "algorithm": "ML-DSA-44") to make it easier to consume without looking at file names.
• The 32-byte seed used to generate the private key is included (privateSeed field) when meaningful and known. It's notably absent for:
  • cases that check for an invalid encoding of the private key (e.g. wrong size, out-of-range values),
  • test vectors of ML-DSA-44 where no seed is known (by construction) for the boundary condition of |ct0|_max (note that it's possible to generate similar vectors with a known seed but using a lot of brute-force).

[cpu]

@gendx Was it intentional to put the test vectors in the schema dir? I think we'd probably want them in testvectors_v1 (?) or another top-level tests directory.

[gendx]

@cpu No that was a typo. Moved them to the suitable directory now :)

[cpu]

@FiloSottile Do you want to take a look at these before merging?

[cpu]

@bwesterb I saw you ref'd these vectors in https://boringssl-review.googlesource.com/c/boringssl/+/79947 Would you be interested in taking a look at the updated branch?

[bwesterb]

@bwesterb I saw you ref'd these vectors in https://boringssl-review.googlesource.com/c/boringssl/+/79947 Would you be interested in taking a look at the updated branch?

What is the ask: reviewing these test vectors independently or updating them in BoringSSL?

[cpu]

reviewing these test vectors independently

That's what I was thinking. Taking a look at the branch, commenting that the vectors worked for your needs previously, and hopefully that the changes I made since are to your liking as both a downstream user and independent reviewer.

I would find that helpful if you had the time!

[bwesterb]

I've tested them against our implementation in Go. These look great. There is one point of discussion: the FIPS spec (nor LAMPS draft) demand rejection of private keys with coefficients out of range. Do we need to reject them? The private key can be badly formed in more ways which we can detect: we can check whether it's all zeroes, or do statistical tests. I don't think it makes sense to check for any of them for security. A more convincing argument is if one implementation would accept them; others reject them; and there are third implementations that generate them. (BTW, these kind of questions are why I pushed for seed-only private keys, but unfortunately we can't have nice things.)

[cpu]

I've https://github.com/cloudflare/circl/pull/552 against our implementation in Go. These look great.

Awesome, thanks for taking a look. I'm going to merge this PR now on the back of my review & your independent cross-ref. We can of course iterate further if there's any new feedback.

There is one point of discussion: the FIPS spec (nor LAMPS draft) demand rejection of private keys with coefficients out of range. Do we need to reject them?

I don't have a strong opinion here as long as the vectors are sufficiently tagged w/ flags to let an implementation decide to handle them differently if they chose.

BTW, these kind of questions are why I pushed for seed-only private keys, but unfortunately we can't have nice things.

Yeahhhhhh :sweat:

[cpu]

Thanks again gendx !

[FiloSottile]

Using these to develop the Go implementation of ML-DSA, thank you @gendx!