Clarification on Using Pseudocode from FIPS 204 for CRYSTALS-Dilithium 3.1 Implementation

[HAFSA SHOAIB]

Dear Forum Members,

I am an undergraduate student working on implementing CRYSTALS-Dilithium. I have thoroughly reviewed both the CRYSTALS-Dilithium 3.1 specification and the FIPS 204 draft. Since CRYSTALS-Dilithium 3.1 is the standardized version and FIPS 204 has been withdrawn, I understand that I should focus on the standardized version.

However, I’ve encountered a challenge. For example, in the key generation algorithm functions like ExpandA, in the CRYSTALS-Dilithium 3.1 specification they are explained theoretically, without accompanying pseudocode. In contrast, FIPS 204 includes pseudocode for functions such as ExpandA etc.

Given this, I wanted to ask: Is it acceptable to reference and use the pseudocode from FIPS 204 for functions like ExpandA while still adhering to the algorithms in CRYSTALS-Dilithium 3.1, or should I strictly stick to the theoretical explanations provided in the standardized document?

Thank you for your guidance.

Best regards,
Hafsa Shoaib

[Moody, Dustin (Fed)]

Hafsa,

To be clear, FIPS 204 has not been withdrawn.  It was published in final form last month:

https://csrc.nist.gov/pubs/fips/204/final

For interoperability, we encourage people to follow FIPS 204, and not the Dilithium round 3 spec.  

Dustin Moody

NIST

---

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> on behalf of HAFSA SHOAIB <hafsash...@gmail.com>
Sent: Wednesday, September 11, 2024 8:01 AM
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [pqc-forum] Clarification on Using Pseudocode from FIPS 204 for CRYSTALS-Dilithium 3.1 Implementation

 

--
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/0702561b-2065-4fdd-a70f-28fa5b538e21n%40list.nist.gov.

[HAFSA SHOAIB]

Dustin Moody, 

Thankyou for the clarification.

[HAFSA SHOAIB]

Dear Forum Members,

I want to ask about the final FIPS 204 specification, which includes two closely related but domain-separated signature schemes: HashML-DSA and ML-DSA. HashML-DSA only adds a pre-hashing step before signing. Since my goal is to implement Dilithium, should I focus solely on implementing ML-DSA, or do I need to include the HashML-DSA algorithm as well?

Thank you for your guidance.

Best regards,
Hafsa Shoaib

On Wednesday 11 September 2024 at 17:09:03 UTC+5 Moody, Dustin (Fed) wrote:

[Stephan Mueller]

Am Samstag, 14. September 2024, 09:12:04 GMT-5 schrieb HAFSA SHOAIB:

Hi HAFSA,

> Dear Forum Members,
>
> I want to ask about the final FIPS 204 specification, which includes two
> closely related but domain-separated signature schemes: HashML-DSA and
> ML-DSA. HashML-DSA only adds a pre-hashing step before signing. Since my
> goal is to implement Dilithium, should I focus solely on implementing
> ML-DSA, or do I need to include the HashML-DSA algorithm as well?
>
> Thank you for your guidance.

This depends on your use case. Commonly you want pure ML-DSA - and that is
also explicitly the preferred method as stated in FIPS 204. But if you have,
say, a smartcard with ML-DSA with a small link to a host where you cannot send
gigabytes of data over, you perhaps want the HashML-DSA where the host hashes
the gigabytes of data and only sends the message digest over the small link to
your smart card.

Ciao
Stephan

[HAFSA SHOAIB]

Dear Forum Members,

As I am currently implementing the Dilithium algorithm at security level 5 (ML-DSA-87), which, as per the specification, requires the use of an approved Random Bit Generator (RBG). Given that SP 800-90C is still in draft form, I would like to ask for guidance regarding the choice between SP 800-90A and SP 800-90B.

Specifically, could you advise whether I should prefer implementing the RBG specified in SP 800-90A or SP 800-90B for this purpose?

Thank you for your assistance.

Best regards,
Hafsa Shoaib

[Markku-Juhani O. Saarinen]

On Wed, Sep 25, 2024 at 9:27 PM HAFSA SHOAIB <hafsash...@gmail.com> wrote:

Dear Forum Members,

As I am currently implementing the Dilithium algorithm at security level 5 (ML-DSA-87), which, as per the specification, requires the use of an approved Random Bit Generator (RBG). Given that SP 800-90C is still in draft form, I would like to ask for guidance regarding the choice between SP 800-90A and SP 800-90B.

Specifically, could you advise whether I should prefer implementing the RBG specified in SP 800-90A or SP 800-90B for this purpose?

Hello Hafsa,

Basically one needs both. SP 800-90B is a standard for Entropy Sources (ES) and does not define an RBG per se. But one needs bits from an ES to initialize and reseed almost any RBG. In practice most current implementations use DRBGs, i.e. those defined in SP 800-90A. Indeed SP 800-90C will define additional ones, and is late draft stage.

The RBG is not conceptually part of ML-DSA itself, and is validated separately. Any approved RBG will do, as long as its security strength meets that of ML-DSA parameter set (the overall security of the combination is defined as a minimum of the two -- see Sect 3.6.1 of FIPS 204).

This is just on a very high level. Since FIPS standards tend to leave some aspects up to interpretation, one should check out the Implementation Guidance document ( https://csrc.nist.gov/CSRC/media/Projects/cryptographic-module-validation-program/documents/fips%20140-3/FIPS%20140-3%20IG.pdf ). There is quite a lot of detail about acceptable RBG implementations in there. Not so much about ML-DSA yet, but this document is much more frequently updated than the FIPS standards themselves.

Best Regards,

-markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

 

Thank you for your assistance.

Best regards,
Hafsa Shoaib

On Saturday 14 September 2024 at 19:19:16 UTC+5 Stephan Mueller wrote:

Am Samstag, 14. September 2024, 09:12:04 GMT-5 schrieb HAFSA SHOAIB:

Hi HAFSA,

> Dear Forum Members,
>
> I want to ask about the final FIPS 204 specification, which includes two
> closely related but domain-separated signature schemes: HashML-DSA and
> ML-DSA. HashML-DSA only adds a pre-hashing step before signing. Since my
> goal is to implement Dilithium, should I focus solely on implementing
> ML-DSA, or do I need to include the HashML-DSA algorithm as well?
>
> Thank you for your guidance.

This depends on your use case. Commonly you want pure ML-DSA - and that is
also explicitly the preferred method as stated in FIPS 204. But if you have,
say, a smartcard with ML-DSA with a small link to a host where you cannot send
gigabytes of data over, you perhaps want the HashML-DSA where the host hashes
the gigabytes of data and only sends the message digest over the small link to
your smart card.

Ciao
Stephan

--
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/36d4509a-89b6-4020-a53a-a1236b510295n%40list.nist.gov.

[Stephan Mueller]

Am Donnerstag, 26. September 2024, 07:06:35 MESZ schrieb Markku-Juhani O.
Saarinen:

Hello Hafsa,

Perhaps a small hint:

SP800-90C == combination specification of a DRBG (SP800-90A) and one or more
entropy sources (SP800-90B).


Ciao
Stephan

[HAFSA SHOAIB]

Yes, I understand that SP 800-90C specifies the combination of a DRBG (from SP 800-90A) and entropy sources (from SP 800-90B). However, since SP 800-90C is still in draft form, I need to work with the standardized versions for now. :)

[Stephan Mueller]

Am Donnerstag, 26. September 2024, 14:00:18 MESZ schrieb HAFSA SHOAIB:

Hi HAFSA,

> Yes, I understand that SP 800-90C specifies the combination of a DRBG (from
> SP 800-90A) and entropy sources (from SP 800-90B). However, since SP
> 800-90C is still in draft form, I need to work with the standardized
> versions for now. :)

Then FIPS 140 IG D.K is your friend :-)


Ciao
Stephan

[HAFSA SHOAIB]

Dear Forum Members,

I've implemented the key generation algorithm of Dilithum/ml-dsa in Python and now want to verify if it's correct. Are there any benchmarks or ways to check this? The lengths of the public and secret keys match the FIPS 204 final standard

Thank you for your assistance.

Best regards,
Hafsa Shoaib

[Stephan Mueller]

Am Sonntag, 6. Oktober 2024, 20:49:07 MESZ schrieb HAFSA SHOAIB:

Hi HAFSA,

> Dear Forum Members,
>
> I've implemented the key generation algorithm of Dilithum/ml-dsa in Python
> and now want to verify if it's correct. Are there any benchmarks or ways to
> check this? The lengths of the public and secret keys match the FIPS 204
> final standard

See [1] for a list of vectors from NIST. See [2] for additional vectors
confirmed by several different implementations [2].

[1] https://github.com/usnistgov/ACVP-Server/tree/master/gen-val/json-files/
ML-DSA-keyGen-FIPS204

[2] https://github.com/post-quantum-cryptography/KAT/tree/main/MLDSA

Ciao
Stephan

[HAFSA SHOAIB]

Hi Stephan,

Thank you for your response and for sharing the links to the test vectors...I follow the [1] a list of vectors from NIST.

I have a follow-up question regarding the key generation process for verification purposes. As the key generation algorithm involves generating a seed through an RBG (Random Bit Generator), I understand that for testing, a predefined seed is used along with the expected public and secret keys.

However, I am wondering how the output of the key generation algorithm will match the expected output, given that the algorithm includes hashing operations (such as through SHAKE) which are sensitive to even small changes in input. Could you clarify how the randomized process ensures that the outputs (public and secret keys) are identical to the expected ones in the provided test vectors?

Best regards,
Hafsa

[Stephan Müller]

Am Montag, 7. Oktober 2024, 21:29:12 MESZ schrieb HAFSA SHOAIB:

Hi HAFSA,

> Hi Stephan,
>
> Thank you for your response and for sharing the links to the test
> vectors...I follow the [1] a list of vectors from NIST.
>
> I have a follow-up question regarding the key generation process for
> verification purposes. As the key generation algorithm involves generating
> a seed through an RBG (Random Bit Generator), I understand that for
> testing, a predefined seed is used along with the expected public and
> secret keys.
>
> However, I am wondering how the output of the key generation algorithm will
> match the expected output, given that the algorithm includes hashing
> operations (such as through SHAKE) which are sensitive to even small
> changes in input. Could you clarify how the randomized process ensures that
> the outputs (public and secret keys) are identical to the expected ones in
> the provided test vectors?

The test vector gives you a sk_seed, sk_prf, and pk_seed. Those values have to
be used as the key gen parameters. I.e. you do not generate values from an
RBG, but you use the provided values as input.

Ciao
Stephan

[Guillaume Endignoux]

In addition to the test vectors mentioned by Stephan (that only test random keys and signatures as far as I'm aware), see [3] for a set of test vectors specifically crafted to test the many edge cases of the ML-DSA algorithm.

[3] https://github.com/C2SP/wycheproof/pull/112

--
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/10131766.37r6zqXVbV%40tauon.atsec.com.

[HAFSA SHOAIB]

Thank you again for your helpful insights.

I’ve been focusing on this folder:
https://github.com/usnistgov/ACVP-Server/blob/master/gen-val/json-files/ML-DSA-keyGen-FIPS204/
However, I’m unable to locate fields such as sk_seed, sk_prf, and pk_seed in the files within this directory.

Interestingly, I did find these values in the following folder:
https://github.com/usnistgov/ACVP-Server/tree/master/gen-val/json-files/SLH-DSA-keyGen-FIPS205

Could you please clarify if there is another recommended approach to retrieve these key generation parameters?

I appreciate your guidance.

Best regards,
Hafsa

[Stephan Mueller]

Am Dienstag, 8. Oktober 2024, 14:22:19 MESZ schrieb HAFSA SHOAIB:

Hi HAFSA,

> Thank you again for your helpful insights.
>
> I’ve been focusing on this folder:
> https://github.com/usnistgov/ACVP-Server/blob/master/gen-val/json-files/ML-D

> SA-keyGen-FIPS204/ However, I’m unable to locate fields such as sk_seed,

> sk_prf, and pk_seed in the files within this directory.

Sorry, my bad - I was working on SLH-DSA and thus implied your question was
for it :-)

For ML-DSA, you only have a seed that is the value to be used directly by the
ML-DSA.Keygen_internal as the "random number".

>
> Interestingly, I did find these values in the following folder:
> https://github.com/usnistgov/ACVP-Server/tree/master/gen-val/json-files/SLH-> DSA-keyGen-FIPS205
>
> Could you please clarify if there is another recommended approach to
> retrieve these key generation parameters?

As said, for SLH-DSA the three values are to be used as direct input for the
slh_keygen.

Ciao
Stephan

[HAFSA SHOAIB]

Hi Stephan,

Its Ok, 

For ML-DSA, we have a seed that used directly by the ML-DSA.Keygen_internal as the "random number".

However, I am wondering how the output of the key generation algorithm will match the expected output, given that the algorithm includes hashing operations (such as through SHAKE) which are sensitive to even small changes in input. Could you clarify how the randomized process ensures that the outputs (public and secret keys) are identical to the expected ones in the provided test vectors?.. or whats your thought on that?

Best regards,
Hafsa

[Stephan Müller]

Am Dienstag, 8. Oktober 2024, 15:59:47 MESZ schrieb HAFSA SHOAIB:

Hi HAFSA,

> Hi Stephan,
>
> Its Ok,
>
> For ML-DSA, we have a seed that used directly by the ML-DSA.Keygen_internal
> as the "random number".
>
> However, I am wondering how the output of the key generation algorithm will
> match the expected output, given that the algorithm includes hashing
> operations (such as through SHAKE) which are sensitive to even small
> changes in input. Could you clarify how the randomized process ensures that
> the outputs (public and secret keys) are identical to the expected ones in
> the provided test vectors?.. or whats your thought on that?

All but the random number at the beginning of the key gen process is fully
deterministic. So, I do not understand what your concern is.

I successfully verified my implementations of ML-KEM/ML-DSA and SLH-DSA with
this approach defined by NIST.

Ciao
Stephan

[HAFSA SHOAIB]

Hi Stephan,

Hi Stephan,

Hmm I understand.

However, it would be helpful if the test vectors provided intermediate outputs at various steps of the algorithm, rather than just the final public and secret keys. This would allow for better debugging and diagnosing of any issues during failed test cases, making it easier to identify where things might go wrong.

What are your thoughts on this?

Best regards,
Hafsa

[niux_d...@icloud.com]

Let me drop in on this.

Yes, intermediate values as well as other form of detailed information are very much preferred for testing - automated or not. NIST does provide this kind of vectors on their website, but the team in charge of this said in another thread that they need some time - roughly around October.

-- 
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/6f1e6436-9908-4a18-9781-4200eaadbe2cn%40list.nist.gov.

[Stephan Mueller]

Am Mittwoch, 9. Oktober 2024, 11:41:38 MESZ schrieb HAFSA SHOAIB:

Hi HAFSA,

> Hi Stephan,
>

> Hi Stephan,
>
> Hmm I understand.
>
> However, it would be helpful if the test vectors provided intermediate
> outputs at various steps of the algorithm, rather than just the final
> public and secret keys. This would allow for better debugging and
> diagnosing of any issues during failed test cases, making it easier to
> identify where things might go wrong.

NIST is not providing this. But you can get intermediate values from my
library as documented in [1]. As this library has received ACVP certificates
from NIST, it is expected to calculate correctly.

[1] https://leancrypto.org/leancrypto/debugging_support/index.html

Ciao
Stephan

[Stephan Mueller]

Am Mittwoch, 9. Oktober 2024, 12:09:16 MESZ schrieb niux_dannyniu via pqc-
forum:

Hi niux_dannyniu,

> Let me drop in on this.
>
> Yes, intermediate values as well as other form of detailed information are
> very much preferred for testing - automated or not. NIST does provide this
> kind of vectors on their website, but the team in charge of this said in
> another thread that they need some time - roughly around October.

To my knowledge, in October they will add test vectors for HashML-DSA as well
as ML-DSA.Sign and .Verify. I am not aware that intermediate values will be
provided.

Ciao
Stephan

[niux_d...@icloud.com]

NIST provides intermediate values at https://csrc.nist.gov/projects/cryptographic-standards-and-guidelines/example-values As for the PQC algorithms, I've been exhaustedly waiting and unable to commit and push my codes online for quite some time.

--
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/3039966.hnj0FZ9ARc%40tauon.atsec.com.

[HAFSA SHOAIB]

Thankyou fo your guidance 

[M Asfiyan]

Dear Forum Members,

I'm also in the group of Hafsa Shoaib, we have verified our software code for Dilithium (Key Algorithm) using the ACVP Server JSON files ACVP-Server and PyCryptodome for SHAKE256. 

As we are developing a hardware accelerator for Dilithium, and our hardware SHAKE256 implementation matches the NIST standard. But the Python-based SHAKE256 outputs differ when testing a 0-bit message with SHAKE256 (as per this NIST example), the output does not match the NIST document.. How can I verify my hardware if the Python output is inconsistent with NIST?

Best regards,
Asfiyan

[김광조]

Did you check the compatibilty between sw and hw in bit ordering rule such as big endian or little endian?

======================================================

President  Kwangjo Kim

Emeritus Prof.@KAIST,  IACR Fellow, Adjunct Prof.@CSU, USA

International Research ins. for  Cyber Security(IRCS)

#1202 Sungji Heights-tel, 2 Seohyeon-ro 210 Beon-gil,  Bundang-gu, Seongnam-si, 

Gyeonggi-do, 13591, Rep. of Korea

Tel: +82-703-1386 Mobile: +82-10-9414-1386 E-mail : k...@kaist.ac.kr

Web : https://ircs.re.kr

=====================================================

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/8d437dc8-9a10-4166-b071-ccb44eab7b62n%40list.nist.gov.

[M Asfiyan]

Yes I know this rule between HW and SW, that’s why I’m checking 0 bit message, means empty message so there’s no issue will raise in little endian or big endian

[M Asfiyan]

And also, I'm not checking our HW SHAKE with  PyCryptodome, I'm just verifying the NIST documents with  PyCryptodome in python, so I think that there will be no rule for little or big endian compatability