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.