Debugging Support

The leancrypto library offers various types of debugging support outlined in the following sections.

Kyber / Dilithium: Print Results of Intermediate Calculation Steps

An implementation that is compliant with the NIST implementation that complies with FIPS 203 draft as well as additional changes expressed by NIST at the PQC-Forum 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. Execute the test tool providing the output of Kyber, ML-KEM-768: build/kem/tests/kyber_768_kem_tester_c

  6. Execute the test tool providing the output of Kyber, ML-KEM-512: build/kem/tests/kyber_512_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. Execute the test tool providing the output of Dilithium, ML-DSA-65: build/signature/tests/dilithium_65_tester_c

  6. Execute the test tool providing the output of Dilithium, ML-DSA-44: build/signature/tests/dilithium_44_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.

During the course of the development of both Kyber and Dilithium reference implementations, NIST developers reached out to compare intermediate results of both algorithms with the ones produced by leancrypto. 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.

Side-Channel Analysis

Side channels is a recurring problem which can inadvertently leak sensitive data where the leak may be visible not just locally, but possibly also remotely. Thus, finding side channels based on sensitive data is important.

The leancrypto library has built-in support for finding side-channels (or the lack thereof) by marking memory holding sensitive data and using Valgrind to identify any possible side channels. The concept is summarized on the Timecop web page as follows:

Even though modern CPUs and operating systems have various methods to separate processes from one another, some side-channels can remain that allow attackers to extract information across process, CPU, or even network boundaries.

One such side-channel can open up when the execution time of a piece of code depends on secret data. This class of vulnerabilities has been used succesfully in the past to extract encryption keys from AES, private keys from RSA, and other kinds of attacks.

Timing side-channels can be hard to spot in the wild, but they can be detected automatically to some degree with dynamic analysis.

How it works

Most timing side-channels are rooted in one of the following three causes:

  • Conditional jumps based on secret data [1] e.g. if (key[i] == 0)

  • Table lookups at secret indices [2], [3], [4], [5] e.g. s[i] = substitution_table[key[i]]

  • Variable-time CPU instructions operating on secret data [6], e.g. key[i] / c On Intel Pentium 4, the number of cycles for a division instruction depends on the arguments.

Adam Langley described in 2010 how the first two types can be detected automatically using Valgrind.

Valgrind is a framework for dynamic code analysis that comes with a large range of tools for specific analysis tasks. One of those tools checks memory usage to identify memory leaks, use of uninitialized memory, read after free, and other common problems related to memory management.

When Valgrind checks for the use of uninitialized memory, it performs exactly the checks necessary to spot timing side-channels. By flagging secret data as uninitialized for Valgrind, it will report any cases where conditional jumps or table lookups are based on secret data.

Limitations

Valgrind cannot spot cases where variable-time code is caused by variable-time CPU instructions.

Testing Instructions

To perform such a side channel analysis, apply the following steps:

  1. Configure leancrypto with the following option: meson configure build -Dtimecop=enabled

  2. Compile the code

  3. Execute different test cases with Valgrind as follows: valgrind --track-origins=yes build/kem/tests/kyber_kem_tester_common

  4. A side channel is present if Valgrind reports an issue like the following where it reports a “Conditional jump or move depends on uninitialised value(s)” based on “Uninitialised value was created by a client request”:

==13317== Conditional jump or move depends on uninitialised value(s)
==13317==    at 0x4851A2E: bcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==13317==    by 0x10A86F: lc_compare (../internal/src/compare.c:52)
==13317==    by 0x10A6A8: _kmac_256_tester (../kmac/tests/kmac_256_tester.c:912)
==13317==    by 0x10A410: kmac_tester (../kmac/tests/kmac_256_tester.c:942)
==13317==    by 0x10A410: main (???:956)
==13317==  Uninitialised value was created by a client request
==13317==    at 0x48A0E7A: lc_kmac_init (../kmac/src/kmac.c:119)
==13317==    by 0x10A665: _kmac_256_tester (../kmac/tests/kmac_256_tester.c:909)
==13317==    by 0x10A410: kmac_tester (../kmac/tests/kmac_256_tester.c:942)
==13317==    by 0x10A410: main (???:956)

References

[1] Onur Acıiçmez, Çetin Kaya Koç, Jean-Pierre Seifert, Predicting secret keys via branch prediction. In Proceedings of the 7th Cryptographers’ Track at the RSA Conference on Topics in Cryptology

[2] Yuval Yarom, Katrina Falkner, FLUSH+RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack.

[3] Daniel J. Bernstein, Cache-timing attacks on AES.

[4] Paul C. Kocher, Timing Attacks in Implementations of Diffie-Hellman, RSA, DSS, and Other Systems.

[5] Mehmet Sinan İnci, Berk Gülmezoğlu, Gorka Irazoqui, Thomas Eisenbarth, Berk Sunar, Seriously, get off my cloud! Cross-VM RSA Key Recovery in a Public Cloud.

[6] Thierry Kaufmann, Hervé Pelletier, Serge Vaudenay, and Karine Villegas When Constant-time Source Yields Variable-time Binary: Exploiting Curve25519-donna Built with MSVC 2015.

Generation of ML-DSA Signature Generation Rejection Test Vectors

The ML-DSA signature generation contains rejection code paths which are probabilistically triggered during production use. According to FIPS IG 10.3.A and also to ensure proper implementation, the rejection code paths should all be tested.

According to FIPS IG 10.3.A, for ML-DSA 87 and 65, three of the four possible rejection code paths are to be triggered (z, r0 and h). For ML-DSA 44, in addition the ct0 rejection code path is to be tested.

TODO: The tests are not able to trigger all four rejection code paths for ML-DSA 44 - this needs to be checked with NIST.

To generate ML-DSA signature generation test vectors that trigger all required code paths as mentioned above, leancrypto contains a test generator to generate such test vectors for pure, pre-hash and external MU interfaces. The test vector for the internal interface is derived from [1] and thus not generated by leancrypto.

The following steps have to be followed if test vectors shall be generated anew:

  1. In the file dilithium_signature_impl.h the macro REJECTION_TEST_SAMPLING must be defined.

  2. In the file dilithium_edge_case_tester.c the macro GENERATE_KEYS must be defined.

  3. Ensure that SHA2-256 is enabled, i.e. the meson option sha2-256 must be enabled (which is active by default)

  4. Compile leancrypto - WARNING, the ML-DSA44 test invocation will litterally take days to generate even one test vector due to the rarity of ct0 rejection path triggers

  5. Generate pure ML-DSA vectors by executing:

    • ML-DSA 87: build/ml-dsa/tests/dilithium_pure_edge_case_tester_c > ml-dsa/tests/dilithium_pure_rejection_vectors_87.h

    • ML-DSA 65: build/ml-dsa/tests/dilithium_65_pure_edge_case_tester_c > ml-dsa/tests/dilithium_pure_rejection_vectors_65.h

    • ML-DSA 44: stdbuf -i 0 -o 0 build/ml-dsa/tests/dilithium_44_pure_edge_case_tester_c > ml-dsa/tests/dilithium_pure_rejection_vectors_44.h

  6. Generate pre-hash ML-DSA vectors by executing:

    • ML-DSA 87: build/ml-dsa/tests/dilithium_prehash_edge_case_tester_c > ml-dsa/tests/dilithium_prehash_rejection_vectors_87.h

    • ML-DSA 65: build/ml-dsa/tests/dilithium_65_prehash_edge_case_tester_c > ml-dsa/tests/dilithium_prehash_rejection_vectors_65.h

    • ML-DSA 44: stdbuf -i 0 -o 0 build/ml-dsa/tests/dilithium_44_prehash_edge_case_tester_c > ml-dsa/tests/dilithium_prehash_rejection_vectors_44.h

  7. Generate external-Mu ML-DSA vectors by executing:

    • ML-DSA 87: build/ml-dsa/tests/dilithium_external_mu_edge_case_tester_c > ml-dsa/tests/dilithium_external_mu_rejection_vectors_87.h

    • ML-DSA 65: build/ml-dsa/tests/dilithium_65_external_mu_edge_case_tester_c > ml-dsa/tests/dilithium_external_mu_rejection_vectors_65.h

    • ML-DSA 44: stdbuf -i 0 -o 0 build/ml-dsa/tests/dilithium_44_external_mu_edge_case_tester_c > ml-dsa/tests/dilithium_external_mu_rejection_vectors_44.h

  8. Do not forget to undefine the macros set in steps 1 and 2.

References

[1] https://pages.nist.gov/ACVP/draft-celi-acvp-ml-dsa.html#name-known-answer-tests

Verification of ML-DSA Signature Generation Rejection Test Vectors

The (ML-DSA signature generation rejection test vectors)[Generation of ML-DSA Signature Generation Rejection Test Vectors] can be verified to indeed trigger all rejection code paths as follows:

  1. Enable ML-DSA debug output: meson configure build -Ddilithium_debug=enabled

  2. Compile leancrypto

  3. Verify the triggering of the rejection code paths by invoking build/ml-dsa/tests/dilithium_edge_case_tester_c | less and check the presence of the following logging output depending on which rejection code path you are interested in:

    • For z rejectin: Siggen - z rejection

    • For r1 rejection: Siggen - r0 rejection

    • For h rejection: Siggen - h rejection

    • For ct0 rejection: Siggen - ct0 rejection