Unofficial MLDSA KAT vectors

[Kris Kwiatkowski]

Hello,

I’ve updated my MLDSA implementation to FIPS-204 and generated KAT vectors for MLDSA.Sign/Verify and HashML-DSA.Sign/Verify.
As we only have ACVP KAT vectors for *_internal functions, that may be useful.
It would be great to know if those vectors match (or not) some other alternative implementation.

The vectors are here:
https://github.com/post-quantum-cryptography/KAT/tree/main/MLDSA

--
Kris Kwiatkowski
Cryptography Dev

[Stephan Mueller]

Am Mittwoch, 11. September 2024, 12:32:33 GMT-5 schrieb Kris Kwiatkowski:

Hi Kris,

I would be happy to test it, but I do not have a CTR-DRBG at my disposal in my
library [1]. Could I suggest that instead of providing any kind of seed to a
DRBG or something, what about providing the actual data the implementations
ought to get out of the RBG and insert them into the algo?

Just as a note, to not mess up the algo implementation, in my code I have
implemented an "RBG" that simply returns the value you give to it. So, this
"RBG" follows the RBG APIs and thus can be directly called by the algo
implementation without any change, but always returns the seed I gave it. So,
when I know my tested code will make 2 pulls of 32 bytes each, I "seed" the
"RBG" with the 64 bytes that eventually will be handed out. See [2] for the
actual "RBG" implementation - it effectively is a memcpy wrapped into the RBG
API.

Side note: if you are planning to go to NIST's ACVP service, you will get the
actual seed data you have to directly insert into the algos like ML-KEM
instead of having it processed by a "real" RBG.

[1] https://github.com/smuellerDD/leancrypto

[2] https://github.com/smuellerDD/leancrypto/blob/master/drng/src/static_rng.c

Ciao
Stephan

[niux_d...@icloud.com]

Hi all.

On the availability of CTR-DRBG, I have a C implementation at here:
https://github.com/dannyniu/MySuiteA/tree/3ac31f69fcba4cd6dd86532e38ca5cce2d78f774/src/2-prng

> --
> 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 on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/3831727.KQ2X9qPB83%40tauon.atsec.com.

[Stephan Müller]

Am Donnerstag, 12. September 2024, 04:15:12 MESZ schrieb niux_dannyniu via
pqc-forum:

Hi niux_dannyniu,

> Hi all.
>
> On the availability of CTR-DRBG, I have a C implementation at here:
> https://github.com/dannyniu/MySuiteA/tree/3ac31f69fcba4cd6dd86532e38ca5cce2d
> 78f774/src/2-prng

Thank you, but perhaps I was not clear. I have also a CTR DRBG considering
that I wrote the one that is currently in use in the Linux kernel.

But I do not want to add one to my library, especially as I am not fond of it.

Ciao
Stephan

[Kris Kwiatkowski]

Hi Stephan,

Thank you for getting back.
To test against vectors DRBG-AES-CRT is not needed.

> what about providing the actual data the implementations
> ought to get out of the RBG and insert them into the algo?

You can use ‘xi’ and ‘rnd’ values. The ‘xi’ corresponds to the
value generated by Algorithm 1, at line 1 (keygen). It is all
that you need for KeyGen tests. Similarly, the ‘rnd’ value
corresponds to the ‘rnd’ value from Algorithm 2, line 5. That
should be all needed for SigGen tests (randomised).

I believe your RBG should return ‘xi’ value for KeyGen and ‘rnd’
value in the case of randomised SigGen.

The ’seed’ value is useful only if you want to re-generate
those vectors, but you can ignore it otherwise.

Please let me know if you have further questions.

--
Kris Kwiatkowski
Cryptography Dev

[Roy]

[Roy]

Hello Kris,

I tested the provided KATS with the BouncyCastle implementation, I
think you might not be using the listed bytes "xi" and "rnd". The
following tests fail:

"kat_MLDSA_44_det_hashed.rsp", // KeyGen FAILS
"kat_MLDSA_65_det_hashed.rsp", // KeyGen FAILS
"kat_MLDSA_87_det_hashed.rsp", // KeyGen FAILS
"kat_MLDSA_44_det_normal.rsp", // KeyGen FAILS
"kat_MLDSA_65_det_normal.rsp", // KeyGen FAILS
"kat_MLDSA_87_det_normal.rsp", // KeyGen FAILS
"kat_MLDSA_44_det_raw.rsp", // KeyGen FAILS
"kat_MLDSA_65_det_raw.rsp", // KeyGen FAILS
"kat_MLDSA_87_det_raw.rsp", // KeyGen FAILS

"kat_MLDSA_44_hedged_hashed.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_65_hedged_hashed.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_87_hedged_hashed.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_44_hedged_normal.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_65_hedged_normal.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_87_hedged_normal.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_44_hedged_raw.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_65_hedged_raw.rsp", // KeyGen FAILS, Sign FAILS
"kat_MLDSA_87_hedged_raw.rsp" // KeyGen FAILS, Sign FAILS

~ Roy Basmacier

[Kris Kwiatkowski]

Thank you Roy,

Indeed seems I maybe have a problem with xi and rnd. Let me double check.
Can you confirm that verification works OK?

Kind regards,
Kris

[Roy]

Hey Kris,

For the deterministic KATS signature generation and verification works.
For the hedged KATS only the verification works.

~ Roy Basmacier

[Stephan Mueller]

Am Donnerstag, 12. September 2024, 15:27:28 GMT-5 schrieb Roy:

Hi Roy,

ML-DSA 87 and 65 prehash: I cannot verify those with my unmodified
implementation as the used SHA-256 hash is not allowed to be used with 87 and
65 (the digest size is not 2 * lambda). When lifting the restriction, I can
validate the data.

For the hedged and det, I can successfully perform sigver for all types (when
disabling the aforementioned limitation).

Siggen fails, because I cannot generate the keys from xi.

When I use the provided SK, siggen will still fail with the hedged, but pass
with the deterministic.


Ciao
Stephan

[Stephan Mueller]

Am Donnerstag, 12. September 2024, 21:05:58 GMT-5 schrieb Stephan Mueller:

Hi Kris,

> Am Donnerstag, 12. September 2024, 15:27:28 GMT-5 schrieb Roy:
>
> Hi Roy,
>
> > Hey Kris,
> >
> > For the deterministic KATS signature generation and verification works.
> > For the hedged KATS only the verification works.
> >
> > ~ Roy Basmacier
>
> ML-DSA 87 and 65 prehash: I cannot verify those with my unmodified
> implementation as the used SHA-256 hash is not allowed to be used with 87
> and 65 (the digest size is not 2 * lambda). When lifting the restriction, I
> can validate the data.

To clarify the check the code applies, see:

https://github.com/smuellerDD/leancrypto/blob/master/ml-dsa/src/
dilithium_domain_separation.c#L77

Ciao
Stephan

[Roy]

Hello Kris,

Thanks for updating the KATS, everything now works!
It might also be worth replacing the digest used for the hashed vectors
with SHA512 (to make it aligned with NIST OIDS)

~ Roy Basmacier

[Kris Kwiatkowski]

Great, Thank you both!

I've uploaded new set of vectors. Hopefully it fixes a problem with
generating random values and for pre-hash now uses SHA2-256 for MLDSA-44,
SHA2-384 for MLDSA-65 and SHA2-512 for MLDSA-87.

Feel free to give it a try again and let me know if it works or not.

@Roy: Amazing! I didn't even need to ask for retest :)

Thank you,
Kris

[Stephan Müller]

Am Samstag, 14. September 2024, 11:57:19 MESZ schrieb Kris Kwiatkowski:

Hi Kris,

> Great, Thank you both!
>
> I've uploaded new set of vectors. Hopefully it fixes a problem with
> generating random values and for pre-hash now uses SHA2-256 for MLDSA-44,
> SHA2-384 for MLDSA-65 and SHA2-512 for MLDSA-87.
>
> Feel free to give it a try again and let me know if it works or not.
>
> @Roy: Amazing! I didn't even need to ask for retest :)

Thanks for the update. I can now verify all test vectors.

For the sake of completeness, the code and its usage instructions are given in
[1].

To compile the code, see [2].

[1] https://github.com/smuellerDD/leancrypto/blob/master/internal/tests/
tester_kat.c#L26

[2] https://github.com/smuellerDD/leancrypto/blob/master/README.md#library-build

Ciao
Stephan

[Stephan Müller]

Am Samstag, 14. September 2024, 14:44:36 MESZ schrieb Stephan Müller:

Hi Kris,

> Am Samstag, 14. September 2024, 11:57:19 MESZ schrieb Kris Kwiatkowski:
>
> Hi Kris,
>
> > Great, Thank you both!
> >
> > I've uploaded new set of vectors. Hopefully it fixes a problem with
> > generating random values and for pre-hash now uses SHA2-256 for MLDSA-44,
> > SHA2-384 for MLDSA-65 and SHA2-512 for MLDSA-87.
> >
> > Feel free to give it a try again and let me know if it works or not.
> >
> > @Roy: Amazing! I didn't even need to ask for retest :)
>
> Thanks for the update. I can now verify all test vectors.

One more: as the library also is covered by official NIST CAVP certificates
including those for ML-DSA (see [1]), I think we can have a high confidence
that the test vectors are correct.

[1] https://csrc.nist.gov/projects/cryptographic-algorithm-validation-program/
validation-search?
searchMode=implementation&product=leancrypto&productType=-1&dateFrom=08%2F15%2F2024&dateTo=08%2F17%2F2024&ipp=25

Ciao
Stephan

[Kris Kwiatkowski]

Great,
Thank you Stephan.

> On 14 Sep 2024, at 13:49, Stephan Müller <smue...@chronox.de> wrote:
>
> One more: as the library also is covered by official NIST CAVP certificates
> including those for ML-DSA (see [1]), I think we can have a high confidence
> that the test vectors are correct.

Indeed, the vectors are generated by PQCryptoLib which I developed in PQShield.
With your leancrypto and Roy’s BouncyCastle we have 3 independent implementations
correctly passing those vectors, so I also feel confident they are correct.

Cheers,
Kris

[Mitch Lindgren]

Hi Kris,

Thank you very much for providing these test vectors; they're very helpful since the NIST test vectors don't currently include test cases for the external functions. I have a couple issues/questions:

1. I wasn't able to get the hashed variants to work with the implementations I am testing. Your readme says "In this case the message is pre-hashed before signing. ... We use SHA2-256 for MLDSA-44, SHA2-384 for MLDSA-65 and SHA2-512 for MLDSA-87." So I tried hashing the msg parameter using the corresponding hash functions, but I don't get a matching signature. Can you clarify what the inputs are to HashML-DSA.Sign (Algorithm 4) in these test vectors?

2. If these test vectors are intended to be permissively licensed so that they can be included as test cases in other implementations, could you please add a license to the GitHub repo?

Thanks much,

Mitch Lindgren

[Stephan Mueller]

Am Freitag, 8. November 2024, 02:08:18 Mitteleuropäische Normalzeit schrieb
Mitch Lindgren:

Hi Mitch,

> Hi Kris,
> Thank you very much for providing these test vectors; they're very helpful
> since the NIST test vectors don't currently include test cases for the
> external functions. I have a couple issues/questions:
>
> 1. I wasn't able to get the hashed variants to work with the
> implementations I am testing. Your readme says "In this case the message is
> pre-hashed before signing. ... We use SHA2-256 for MLDSA-44, SHA2-384 for
> MLDSA-65 and SHA2-512 for MLDSA-87." So I tried hashing the msg parameter
> using the corresponding hash functions, but I don't get a matching
> signature. Can you clarify what the inputs are to HashML-DSA.Sign
> (Algorithm 4) in these test vectors?

Are you applying the concatenation of the hashed message with the OIDs of the
hash types and the context data as defined in Algorithm 5 of FIPS 204?


Ciao
Stephan

[Kris Kwiatkowski]

Hi Mitch

> 1. I wasn't able to get the hashed variants to work with the implementations I am testing. Your readme says "In this case the message is pre-hashed before signing. ... We use SHA2-256 for MLDSA-44, SHA2-384 for MLDSA-65 and SHA2-512 for MLDSA-87." So I tried hashing the msg parameter using the corresponding hash functions, but I don't get a matching signature. Can you clarify what the inputs are to HashML-DSA.Sign (Algorithm 4) in these test vectors?

See Stephan’s email.

> 2. If these test vectors are intended to be permissively licensed so that they can be included as test cases in other implementations, could you please add a license to the GitHub repo?

I didn’t think about it initially. It has MIT license now.

Cheers,
Kris

>
> Thanks much,
> Mitch Lindgren
>
> On Saturday, September 14, 2024 at 3:06:38 PM UTC-7 Kris Kwiatkowski wrote:
> Great,
> Thank you Stephan.
>
>
> > On 14 Sep 2024, at 13:49, Stephan Müller <smue...@chronox.de> wrote:
> >
> > One more: as the library also is covered by official NIST CAVP certificates
> > including those for ML-DSA (see [1]), I think we can have a high confidence
> > that the test vectors are correct.
>
> Indeed, the vectors are generated by PQCryptoLib which I developed in PQShield.
> With your leancrypto and Roy’s BouncyCastle we have 3 independent implementations
> correctly passing those vectors, so I also feel confident they are correct.
>
> Cheers,
> Kris
>
>

> --
> 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/efc729c5-be2b-4e86-bc8c-17c17941b379n%40list.nist.gov.

[Mitch Lindgren]

Turns out there was a bug in the other implementation that I was testing mine against ( mjosaarinen/py-acvp-pqc: Python implementations of FIPS 203,204,205 + Local python access to NIST's ACVP-Server "Golden Reference" crypto code ) . It was not including the context string in M'. Having fixed that, the KATs now work. I have submitted a pull request with a fix to the repo.

Thanks,

Mitch

[Markku-Juhani O. Saarinen]

Yup, that HashML-DSA code ignored the context parameter; now fixed. Thanks Mitch.

As a reminder to those who don't track this: The "external" (user-facing) functions of ML-DSA and SLH-DSA still don't have NIST test vectors and hence are effectively untested. And even with "community" or "peer" test vectors (thanks Kris & Co for the effort), testing coverage probably isn't full in anyone's implementation, especially with SLH-DSA. This includes those commercial implementations that already have a CAVP/FIPS algorithm certificate (!) -- they could well have trivial bugs like this.

Anyway, hopefully the coverage will improve soon.

Cheers,

Markku

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/82721f62-bbcd-4ab3-baeb-a774dfe65f61n%40list.nist.gov.