PQC: Kyber and Dilithium - State of the (Draft) Standards

by Stephan Mueller

 


On August 24 2023 NIST published the first drafts of:

• FIPS 203 specifying Module-Lattice-based Key-Encapsulation Mechanism (ML-KEM) which is based on CRYSTALS Kyber;
• FIPS 204 specifying Module-Lattice-Based Digital Signature (ML-DSA) which is based on CRYSTALS Dilithium; and
• FIPS 205 specifying Stateless Hash-Based Digital Signature (SLH-DSA) which is based on SPHINCS+.

On November 15 2023 NIST announced that the three algorithms will be available for testing at the ACVP Demo service. During the course of the development of both Kyber and Dilithium reference implementations, NIST developers reached out to atsec to compare intermediate results of both algorithms with implementations available to atsec. This comparison covered all data calculated during the intermediate steps of the processing, including:

Kyber:

• all steps of the key generation processing of ML-KEM.Keygen and K-PKE.KeyGen;
• all steps of the key encapsulation processing of ML-KEM.Encaps and K-PKE.Encrypt;
• all steps of the key decapsulation processing of ML-KEM.Decaps and K-PKE.Decrypt;
• ensuring that all Kyber types of ML-KEM-512, ML-KEM-768, and ML-KEM-1024 are subject to the comparison work.

Dilithium:

• all steps of the key generation processing of ML-DSA.Keygen;
• all steps of the key encapsulation processing of ML-DSA.Sign;
• all steps of the key decapsulation processing of ML-DSA.Verify;
• ensuring that all Dilithium types of ML-DSA-44, ML-DSA-65, and ML-DSA-87 are covered by the comparison analysis.

The implementation used by atsec was leancrypto, which was based on the Round 3 submission for CRYSTALS Kyber and CRYSTALS Dilithium at the time the collaboration with NIST was conducted. The NIST team as well as atsec identified several issues in the FIPS 203 and FIPS 204 draft standards, which are listed in their entirety below. The NIST team acknowledged that the respective issues will be eliminated in updates to both standards. This implies that developers using the current draft standards should be aware of those issues and upcoming modifications when basing their implementation on the respective FIPS draft standards.

The list of issues also shows their resolution at the time of writing. Please note that these updates are neither specified by the current standards nor endorsed by NIST yet. These changes were implemented in leancrypto and lead to consistent results compared to the implementations developed by NIST that are likely to be used as the ACVP reference implementations.

Kyber:

• Algorithm 12 step 19 shows the dot-multiplication of the final part of the key generation: t = As + e. Step 19 specifies that AHat has to be used for the operation. However, in this step, the transposed version of AHat has to be used. This modification brings the FIPS 203 specification in line with the Round 3 submission of the CRYSTALS Kyber algorithm.

Dilithium:

• The size of the private key for Dilithium types is by 256 bits larger. This is due to the enlargement of the size of the hash of the public key referenced as tr, which was not taken into account by the draft FIPS 204.
• The size of the signature for ML-DSA-65 is larger by 128 bits and for ML-DSA-87 is larger by 256 bits. This is due to increase of the size of c-tilde in FIPS 204, which was not considered for the calculation of the signature size.
• Algorithm 2 specifies the size of the signature as output to be B^(32....) which needs actually is B^((lambda / 4)...) due to the increase of the c-tilde variable. Note, this change is already applied to the auxiliary algorithm specifications given in chapter 8 of FIPS 204.
• Algorithm 3 requires the same change for the specification of the input signature as given for Algorithm 2 above.

An implementation that is compliant with the NIST implementation that includes all the mentioned fixes is provided with leancrypto. It allows developers to compile both Kyber and Dilithium in a debug mode where the calculation results of each step of the key generation, Kyber encapsulation and decapsulation, as well as the Dilithium signature generation and verification can be displayed. This allows other developers to compare their implementation to match with leancrypto. The following steps have to be taken to obtain the debug output after fetching the library from the provided link and making sure the meson build system is available:

Kyber:

1. Setup of the build directory: meson setup build
2. Configure Kyber debug mode: meson configure build -Dkyber_debug=enabled
3. Compile the code: meson compile -C build
4. Execute the test tool providing the output of Kyber, ML-KEM-1024: build/kem/tests/kyber_kem_tester_c
5. To obtain the output for ML-KEM-768, enable it: meson configure build -Dkyber_strength=3
6. Compile the code: meson compile -C build
7. Execute the test tool providing the output of Kyber, ML-KEM-768: build/kem/tests/kyber_kem_tester_c
8. To obtain the output for ML-KEM-512, enable it: meson configure build -Dkyber_strength=2
9. Compile the code: meson compile -C build
10. Execute the test tool providing the output of Kyber, ML-KEM-512: build/kem/tests/kyber_kem_tester_c

Dilithium

1. Setup of the build directory (if it was not already set up for the Kyber tests): meson setup build
2. Configure Dilithium debug mode: meson configure build -Ddilithium_debug=enabled
3. Compile the code: meson compile -C build
4. Execute the test tool providing the output of Dilithium, ML-DSA-87: build/signature/tests/dilithium_tester_c
5. To obtain the output for ML-DSA-65, enable it: meson configure build -Ddilithium_strength=3
6. Compile the code: meson compile -C build
7. Execute the test tool providing the output of Dilithium, ML-DSA-65: build/signature/tests/dilithium_tester_c
8. To obtain the output for ML-DSA-44, enable it: meson configure build -Ddilithium_strength=2
9. Compile the code: meson compile -C build
10. Execute the test tool providing the output of Dilithium, ML-DSA-44: build/signature/tests/dilithium_tester_c

The test tool outputs is segmented into the key generation steps, Dilithium signature generation and verification steps, as well as Kyber encapsulation and decapsulation steps. The output specifies the mathematical operation whose result is shown. When displaying the output of a vector, one line is used. When displaying a matrix, the output of one row of the matrix is displayed per line. This implies that as many lines are printed as rows are present in the matrix.

The debug logging information was used as a basis for the discussion with the NIST development team to verify that both implementations i.e. the NIST reference implementation as well as leancrypto, correspond.

Considering that the FIPS 203 draft also specifies a minimum input validation in sections 6.2 and 6.3, those checks are implemented with leancrypto in the function kyber_kem_iv_sk_modulus. The other checks requiring the size verification of the input data are implicit due to the used data types forcing the caller to provide exactly the required amount of data.

leancrypto can be found here: https://github.com/smuellerDD/leancrypto