ACVP ML-DSA Specification Rejection Cases KATs

[Filippo Valsorda]

Hello,

The ACVP ML-DSA JSON Specification includes a table (Table 1) of KATs which are supposed to each "cover all rejection outcomes." It is extremely useful to have these available! However, it looks like only the ML-DSA-44 vectors actually cover all rejection outcomes, while the ML-DSA-65 and ML-DSA-87 ones cover mostly zero to two rejection outcomes.

Below is a mapping of test vector (with the first few bytes of the seed) to rejection reasons. Note how the ML-DSA-44 vectors cover all four outcomes, while only one ML-DSA-65 vector covers all three outcomes (ct0 rejection is only reachable in ML-DSA-44), and no ML-DSA-87 vector covers the h rejection outcome at all.

ML-DSA-44 5C624FCC... -> (h, r0, z, ct0)

ML-DSA-44 836EABED... -> (z, r0, h, ct0)

ML-DSA-44 CA5A01E1... -> (z, h, r0, ct0)

ML-DSA-44 9C005F15... -> (r0, ct0, h, z)

ML-DSA-44 4FAB5485... -> (z, ct0, r0, h)

ML-DSA-65 CCD61917... -> (z, z)

ML-DSA-65 C6315FC7... -> (z, r0)

ML-DSA-65 F005E473... -> ()

ML-DSA-65 F215BA22... -> (h, z, r0)

ML-DSA-65 A8E6C084... -> (r0, z)

ML-DSA-87 5AC68A41... -> (z)

ML-DSA-87 E45F9CC0... -> ()

ML-DSA-87 5E37A143... -> (r0, z)

ML-DSA-87 51DF520B... -> (z)

ML-DSA-87 6857AF5C... -> (z)

Some discrepancy could be explained by the order in which checks are done (although I believe I "adhere strictly to the pseudocode in Algorithm 7 ML-DSA.Sign_internal() [FIPS204]" as suggested in the document), but there is just no way a vector which never rejects, like ML-DSA-65 F005E473..., is covering any checks.

I also doubt I am using the vectors incorrectly, because the signature hashes match (but it's possible I am getting something else wrong!). Were the ML-DSA-65 and ML-DSA-87 vectors generated incorrectly?

Thank you,

Filippo

[Filippo Valsorda]

2025-11-03 17:29 GMT+01:00 Stephan Mueller <smue...@chronox.de>:

Am Montag, 3. November 2025, 17:19:53 Mitteleuropäische Normalzeit schrieb 

Filippo Valsorda:

Hi Filippo,

> I also doubt I am using the vectors incorrectly, because the signature

> hashes match (but it's possible I am getting something else wrong!). Were

> the ML-DSA-65 and ML-DSA-87 vectors generated incorrectly?

For my implementation, I also did not trigger all rejection code paths. But 

that may be possible depending on your actual implementation.

Hi Stephan,

While the rejection reasons can be implementation dependent, the rejection count is not. Some of these vectors reject zero times, so I really think they might be wrong.

Given this is a pretty official document, I think the vectors should be fixed if they are broken.

I have created test vectors that hit all rejection code paths for all types of 

ML-DSA (pure, pre-hash and external mu). Maybe they are of help to you? You 

can find them at [1], look for the files *_rejection_vectors*.

A description on how to get to those vectors is given at [2].

Great! Do you mind contributing them to https://github.com/C2SP/wycheproof, or would you mind me doing so?

I am trying to collect vectors from various sources so implementers don’t have to figure out multiple formats.

> 

> Thank you,

> Filippo

[1] https://github.com/smuellerDD/leancrypto/tree/master/ml-dsa/tests

[2] https://leancrypto.org/leancrypto/debugging_support/index.html#generation-of-ml-dsa-signature-generation-rejection-test-vectors

Ciao

Stephan

[Stephan Mueller]

Am Montag, 3. November 2025, 18:24:03 Mitteleuropäische Normalzeit schrieb

Filippo Valsorda:

Hi Filippo,

> 2025-11-03 17:29 GMT+01:00 Stephan Mueller <smue...@chronox.de>:
> > Am Montag, 3. November 2025, 17:19:53 Mitteleuropäische Normalzeit schrieb
> > Filippo Valsorda:
> >
> > Hi Filippo,
> >
> > > I also doubt I am using the vectors incorrectly, because the signature
> > > hashes match (but it's possible I am getting something else wrong!).
> > > Were
> > > the ML-DSA-65 and ML-DSA-87 vectors generated incorrectly?
> >
> > For my implementation, I also did not trigger all rejection code paths.
> > But
> > that may be possible depending on your actual implementation.
>
> Hi Stephan,
>
> While the rejection reasons can be implementation dependent, the rejection
> count is not. Some of these vectors reject zero times, so I really think
> they might be wrong.
>
> Given this is a pretty official document, I think the vectors should be
> fixed if they are broken.

I do not want to speak on behalf of NIST, but I was told that in their
implementation all rejection code paths were hit.

> > I have created test vectors that hit all rejection code paths for all
> > types of ML-DSA (pure, pre-hash and external mu). Maybe they are of help
> > to you? You can find them at [1], look for the files
> > *_rejection_vectors*.
> >
> > A description on how to get to those vectors is given at [2].
>
> Great! Do you mind contributing them to https://github.com/C2SP/wycheproof,
> or would you mind me doing so?

If you know how to roll in the patches there, I think I would like to ask you
to do that as I am currently in development to get the Linux secure boot using
leancrypto to be covered with PQC.

>
> I am trying to collect vectors from various sources so implementers don’t
> have to figure out multiple formats.

Feel free to take any number of test vectors from the repo.




Ciao
Stephan

[Filippo Valsorda]

2025-11-03 19:19 GMT+01:00 Stephan Mueller <smue...@chronox.de>:

Am Montag, 3. November 2025, 18:24:03 Mitteleuropäische Normalzeit schrieb 

Filippo Valsorda:

Hi Filippo,

> 2025-11-03 17:29 GMT+01:00 Stephan Mueller <smue...@chronox.de>:

> > Am Montag, 3. November 2025, 17:19:53 Mitteleuropäische Normalzeit schrieb

> > Filippo Valsorda:

> > 

> > Hi Filippo,

> > 

> > > I also doubt I am using the vectors incorrectly, because the signature

> > > hashes match (but it's possible I am getting something else wrong!).

> > > Were

> > > the ML-DSA-65 and ML-DSA-87 vectors generated incorrectly?

> > 

> > For my implementation, I also did not trigger all rejection code paths.

> > But

> > that may be possible depending on your actual implementation.

> 

> Hi Stephan,

> 

> While the rejection reasons can be implementation dependent, the rejection

> count is not. Some of these vectors reject zero times, so I really think

> they might be wrong.

> 

> Given this is a pretty official document, I think the vectors should be

> fixed if they are broken.

I do not want to speak on behalf of NIST, but I was told that in their 

implementation all rejection code paths were hit.

If we interpret the text as saying that every vector hits every rejection code paths, I don't think that's possible (unless I have some really non-obvious bug in my test harness). None of the vectors reject more than twice, and the rejection count can't be different between implementations (or the signature hash would come out different).

I also instrumented the code to print all possible rejection reasons at every rejection, and none of the ML-DSA-87 vectors ever produce a hint with more than ω non-zero coefficients, so independently of the implementation, I don't think they can possibly hit that code path.

ML-DSA-87 5AC68A41... -> (z | r0)

ML-DSA-87 E45F9CC0... -> ()

ML-DSA-87 5E37A143... -> (r0, z | r0)

ML-DSA-87 51DF520B... -> (z | r0)

ML-DSA-87 6857AF5C... -> (z | r0)

> > I have created test vectors that hit all rejection code paths for all

> > types of ML-DSA (pure, pre-hash and external mu). Maybe they are of help

> > to you? You can find them at [1], look for the files

> > *_rejection_vectors*.

> > 

> > A description on how to get to those vectors is given at [2].

> 

> Great! Do you mind contributing them to https://github.com/C2SP/wycheproof,

> or would you mind me doing so?

If you know how to roll in the patches there, I think I would like to ask you 

to do that as I am currently in development to get the Linux secure boot using 

leancrypto to be covered with PQC.

> 

> I am trying to collect vectors from various sources so implementers don’t

> have to figure out multiple formats.

Feel free to take any number of test vectors from the repo.

Sweet, thank you. I will credit them to "leancrypto.org".

[Filippo Valsorda]

In case NIST wishes to fix the vectors in the ACVP specification (which is also referenced by IG 10.3.A), here is a set of 5+5 vectors for ML-DSA-65 and ML-DSA-87 in the same format as the broken ones. Each of them hits all three conditions exactly once, and each candidate can only reject due to the one condition, so these will test all paths regardless of implementation details.

They are released in the public domain according to the terms of the CC0 text.

ML-DSA-65

C8CD132C4189AFB14B2109F7983CB9965FA71A187CB83451713597A1DF7E2A81

EC61C5B653203677CA4CF39F537D8B38C7AA777A0B0B46130FCD24540861E79C

A543259C30E2CBB447FCFB59E89101EC1315277EC3E6E7E83323F0B550BFE091

04E59B88AAB5DDC2D12BD12A2C0813ECF57A60072FD4BE854E505E6C4824F19A

ML-DSA-65

0BCAA26794DFA6F1D60384D35BA0F21F825BDF5F166A41ED8E2C34CA4AAF30A6

7D35C0F180F2DF7FB3C74BAB828C463BD05CCFA89404A5CA48C73ED3CD3A69A4

293EB65DAD83EA5832FAAD29720583C7D5A0312EEF48FFD43D08D160AFD3E7AA

3572805E4CA991D7E4B5D3D4B41ECC9594FEFE845F9D80CCABDFEB37940EBFAE

ML-DSA-65

22303A0BC7E4EDCB96845B1F5F42F5B57F03288613F975D80A655B9E7A264A5C

E7E8DF282EB402964B4BDA5DAC119C8C924534DD7EC95F2B68F5B6C3BD126E2E

182DA7B7812AF0CCD24F29922C58999FC2B3F1CBFF0C23EE555F1002A4733135

D14EECC68B5C31EDACA3D75B5914087ABC75C8F641FE144011CE31583EFC023D

ML-DSA-65

CCA957BC619DDB76605B9CDC1A5443F74C2ED85BAAF09F056C7A8EAF0F4098EF

DCB5068283BE5543C0A3CD94DE00E87819F038E20EE9F68E2324535CB9CF317A

D686A4B76A5155E6E1AB4584D53D549460E37297930FB951C764FADE2257230F

84CF78398193FAE7F779CBEB5BDEB39DCFCFFAB0476A9E0D19A03A29A74A2BB3

ML-DSA-65

18C158AA15B652EC8D107B2BB31E0CB3B4AEAC8A930D830E857D7DB16BF5695A

79A12A78857C477563CBA9C531B0BEEE9CD4440DC71565CF6D1820787197AC6A

1F69F6B17E98C20D8EFAE04A278BAB91EC4ABDF50EA30F4053A2D62D1D80E2B6

490F8C844DF590DB470B976D4DB5E691448309981053E7EE5BA6199F545D3823

ML-DSA-87

C2E2A69532BD584B13E5E434FBF3510554E25C512305F814FA02B4882745FED9

AFBB226A0517CF0F1B3E4203B1063272510ECA6F94AE0A91018604C4D7E1BA32

38C4C64C5BEB0332C1F633A600D538A8EE727D5C90DED8F5980C3F83FCE1A506

8863840B0736894C4FEF766417C1A655CDB76D41144C431D2BFBA717C6E1D114

ML-DSA-87

57E3605BB8D4158E4F2E1D266FA403AD1D4155C1E93D6C5944DB62D105AD2938

F6E8A062F9C4FB2E909D0AE04738F68B90B984F6E6FE0289E5100562C3ADD323

1D379548CC6D74DBD4184C730B7229770C6413877A142036748A468AF39A8EA2

C70D8458DB2F22BA832DC702FC5112BE15AD9CAA5E3CC2A7D199E7396A4B8122

ML-DSA-87

B640C6759CBFFCB7A6A22F43061B62692AF25E51303AAD1BDA2097F48156112B

3533BC008B32A9FAE59575A292D343270D98A2C7FF49B5EBFD0DD9DB8E6BED0B

480AE04B33FF212A6BC4FC5B8B33E44F2B89636FB602B2132467DB080585E02E

9F14839E17893F88EA549861F24904225338FA30AB6FDD3FC44378039164D465

ML-DSA-87

3D5BECA6A5497E667B70A42A14A6695454AE20FF4FC967A65E0B91AA3C13FDE6

42C47B5233A6015BF729FC3C7594F5388F546F8457D591C0D06CD3589E5EA391

CDEB18F0DCBE7FBE6A2E3826EE493D2BED386775E60BA6B92BD4F61D79B18889

B1F702BF9D4A23C184F79D7747F0BD0F2402C104D6509D49B9C80DABD264D9A9

ML-DSA-87

ECF3B0C79E39BA49075CC03FB82772973166F64B22DFE56E4D42519E170F6654

37C3F4047B0683044762222999864D1D0E1794A107FFC27F37A906662769594A

A2420EA07028D47F8A61D65030FB9AC052BED30E455F80BCF5A593EE8495E324

87A60CCA24A5C7873F5172EAFD5BE3585CE35D46219F433A55A1BF8279DF8F75

--

You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/2b10b787-a710-480b-8c61-1902e05c7f57%40app.fastmail.com.

[Ben Livelsberger]

Hi Filippo,

I just saw this thread. 

One small note that there is more than one group at NIST involved with PQC. The CT Group develops algorithm standards. The Cryptographic Algorithm Validation Program (CAVP) is generally responsible for creating KATs and for writing conformance tests for those algorithm standards. 

CAVP generally does not follow topics on pqc-...@list.nist.gov closely, whereas the CT Group does. But if you raise a CAVP-related topic on this forum, I'd expect the CT Group would forward that topic onto CAVP. As it happens, the CT Group is shutdown and not working right now, but the CAVP team is working full-time. 

The ACVP ML-DSA JSON Specification is a work-product of the CAVP, but now that I'm looking at it, we're not doing a great job of letting people know who they can contact w/ questions. We'll look into improving that.

I'll forward this conversation to Chris Celi. Chris wrote the CAVP ML-KEM testing and JSON Specification and will be able to answer your question. You'll hear back from us shortly.

Best,

Ben

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.

[Celi, Christopher T. (Fed)]

Hi Filippo,

Thanks for letting us know. From some initial testing, I’m getting the same. The ct0 test cases appear fine but the others are not. We will update this next week at the latest. 

Thanks,

Chris Celi

CAVP Program Manager

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/c7a483b3-ec51-4ac4-9f4e-f5de8ff52167%40app.fastmail.com.