lib/crypto: ML-DSA verification support

Add a KUnit test suite for ML-DSA verification, including the following for each ML-DSA parameter set (ML-DSA-44, ML-DSA-65, and ML-DSA-87):

- Positive test (valid signature), using vector imported from leancrypto
- Various negative tests:
- Wrong length for signature, message, or public key
- Out-of-range coefficients in z vector
- Invalid encoded hint vector
- Any bit flipped in signature, message, or public key
- Unit test for the internal function use_hint()
- A benchmark

ML-DSA inputs and outputs are very large. To keep the size of the tests down, use just one valid test vector per parameter set, and generate the negative tests at runtime by mutating the valid test vector.

I also considered importing the test vectors from Wycheproof. I've tested that mldsa_verify() indeed passes all of Wycheproof's ML-DSA test vectors that use an empty context string. However, importing these permanently would add over 6 MB of source. That's too much to be a reasonable addition to the Linux kernel tree for one algorithm. It also wouldn't actually provide much better test coverage than this commit. Another potential issue is that Wycheproof uses the Apache license.

Similarly, this also differs from the earlier proposal to import a long list of test vectors from leancrypto. I retained only one valid signature for each algorithm, and I also added (runtime-generated) negative tests which were missing. I think this is a better tradeoff.

Reviewed-by David Howells <[email protected]>

Tested-by David Howells <[email protected]>

Signed-off-by Eric Biggers <[email protected]>

lib/crypto/tests/Kconfig +0 -0

@@ -36,10 +36,19 @@ config CRYPTO_LIB_MD5_KUNIT_TEST
        select CRYPTO_LIB_MD5

Quoted 24 lines · Eric Biggers

Add a KUnit test suite for ML-DSA verification, including the following for each ML-DSA parameter set (ML-DSA-44, ML-DSA-65, and ML-DSA-87):

- Positive test (valid signature), using vector imported from leancrypto
- Various negative tests:
- Wrong length for signature, message, or public key
- Out-of-range coefficients in z vector
- Invalid encoded hint vector
- Any bit flipped in signature, message, or public key
- Unit test for the internal function use_hint()
- A benchmark

ML-DSA inputs and outputs are very large. To keep the size of the tests down, use just one valid test vector per parameter set, and generate the negative tests at runtime by mutating the valid test vector.

I also considered importing the test vectors from Wycheproof. I've tested that mldsa_verify() indeed passes all of Wycheproof's ML-DSA test vectors that use an empty context string. However, importing these permanently would add over 6 MB of source. That's too much to be a reasonable addition to the Linux kernel tree for one algorithm. It also wouldn't actually provide much better test coverage than this commit. Another potential issue is that Wycheproof uses the Apache license.

Quoted 8 lines

Similarly, this also differs from the earlier proposal to import a long list of test vectors from leancrypto. I retained only one valid signature for each algorithm, and I also added (runtime-generated) negative tests which were missing. I think this is a better tradeoff.

Reviewed-by David Howells <[email protected]>

Tested-by David Howells <[email protected]>

Signed-off-by Eric Biggers <[email protected]>

Thanks for your patch, which is now commit ed894faccb8de55c ("lib/crypto: tests: Add KUnit tests for ML-DSA verification") in v7.0-rc1.

Quoted 8 lines

lib/crypto/tests/Kconfig +0 -0

@@ -36,10 +36,19 @@ config CRYPTO_LIB_MD5_KUNIT_TEST
        select CRYPTO_LIB_MD5
        help
          KUnit tests for the MD5 cryptographic hash function and its
          corresponding HMAC.
 

lib/crypto/tests/Kconfig config CRYPTO_LIB_MD5_KUNIT_TEST · line 46

Quoted 6 lines

lib/crypto/tests/Kconfig +6 -0

+config CRYPTO_LIB_MLDSA_KUNIT_TEST
+       tristate "KUnit tests for ML-DSA" if !KUNIT_ALL_TESTS
+       depends on KUNIT
+       default KUNIT_ALL_TESTS || CRYPTO_SELFTESTS
+       select CRYPTO_LIB_BENCHMARK_VISIBLE
+       select CRYPTO_LIB_MLDSA

These two selects mean that enabling KUNIT_ALL_TESTS also enables extra functionality, which may not be desirable in a production system. Fortunately CRYPTO_LIB_MLDSA is tristate, so in the modular case the extra functionality is a module, too, and not part of the running system by default. Unfortunately CRYPTO_LIB_MLDSA is invisible, so this cannot just be changed from "select" to "depends on". But as CRYPTO_MLDSA also selects it, perhaps the test can be made dependent on CRYPTO_MLDSA?

Quoted 46 lines · Geert Uytterhoeven

Quoted 24 lines · Eric Biggers

Add a KUnit test suite for ML-DSA verification, including the following for each ML-DSA parameter set (ML-DSA-44, ML-DSA-65, and ML-DSA-87):

- Positive test (valid signature), using vector imported from leancrypto
- Various negative tests:
- Wrong length for signature, message, or public key
- Out-of-range coefficients in z vector
- Invalid encoded hint vector
- Any bit flipped in signature, message, or public key
- Unit test for the internal function use_hint()
- A benchmark

ML-DSA inputs and outputs are very large. To keep the size of the tests down, use just one valid test vector per parameter set, and generate the negative tests at runtime by mutating the valid test vector.

I also considered importing the test vectors from Wycheproof. I've tested that mldsa_verify() indeed passes all of Wycheproof's ML-DSA test vectors that use an empty context string. However, importing these permanently would add over 6 MB of source. That's too much to be a reasonable addition to the Linux kernel tree for one algorithm. It also wouldn't actually provide much better test coverage than this commit. Another potential issue is that Wycheproof uses the Apache license.

Quoted 8 lines

Similarly, this also differs from the earlier proposal to import a long list of test vectors from leancrypto. I retained only one valid signature for each algorithm, and I also added (runtime-generated) negative tests which were missing. I think this is a better tradeoff.

Reviewed-by David Howells <[email protected]>

Tested-by David Howells <[email protected]>

Signed-off-by Eric Biggers <[email protected]>

Thanks for your patch, which is now commit ed894faccb8de55c ("lib/crypto: tests: Add KUnit tests for ML-DSA verification") in v7.0-rc1.

Quoted 8 lines

lib/crypto/tests/Kconfig +0 -0

@@ -36,10 +36,19 @@ config CRYPTO_LIB_MD5_KUNIT_TEST
        select CRYPTO_LIB_MD5
        help
          KUnit tests for the MD5 cryptographic hash function and its
          corresponding HMAC.
 

Quoted 14 lines

lib/crypto/tests/Kconfig config CRYPTO_LIB_MD5_KUNIT_TEST · line 46

Quoted 6 lines

lib/crypto/tests/Kconfig +6 -0

+config CRYPTO_LIB_MLDSA_KUNIT_TEST
+       tristate "KUnit tests for ML-DSA" if !KUNIT_ALL_TESTS
+       depends on KUNIT
+       default KUNIT_ALL_TESTS || CRYPTO_SELFTESTS
+       select CRYPTO_LIB_BENCHMARK_VISIBLE
+       select CRYPTO_LIB_MLDSA

These two selects mean that enabling KUNIT_ALL_TESTS also enables extra functionality, which may not be desirable in a production system. Fortunately CRYPTO_LIB_MLDSA is tristate, so in the modular case the extra functionality is a module, too, and not part of the running system by default. Unfortunately CRYPTO_LIB_MLDSA is invisible, so this cannot just be changed from "select" to "depends on". But as CRYPTO_MLDSA also selects it, perhaps the test can be made dependent on CRYPTO_MLDSA?

"depends on CRYPTO_MLDSA" doesn't make sense, since the test is for the code in CRYPTO_LIB_MLDSA, not CRYPTO_MLDSA. CRYPTO_MLDSA just happens to be one of the users of CRYPTO_LIB_MLDSA. In this case the names happen to be similar, but consider e.g. CRYPTO_LIB_AESGCM which is selected by AMD_MEM_ENCRYPT. If we added a test for CRYPTO_LIB_AESGCM, it clearly shouldn't use "depends on AMD_MEM_ENCRYPT".

So, "depends on CRYPTO_LIB_MLDSA" would be the correct way to switch it from a selection to a dependency.

It's just a bit annoying to do this for hidden symbols, given that it makes it so that anyone who wants to unconditionally enable the test, like what I do to test all the crypto library code, has to find and enable some other random kconfig symbol that enables the code.

Also, the series that originally added CRYPTO_LIB_MLDSA and its test
(https://lore.kernel.org/linux-crypto/[email protected]/)
didn't add any user of CRYPTO_LIB_MLDSA besides the test, as the real user came a bit later. So if I had used "depends on CRYPTO_LIB_MLDSA", my series wouldn't have received any build bot coverage, and I'd have needed to temporarily carry local patches to build and test the code.

But if this is really the convention for KUnit, as it seems to be, I will follow it and work around it for my own testing. So I'll plan to change the crypto library and CRC tests to use "depends on".

But any thoughts from the KUnit maintainers would also be appreciated. Is it indeed intended that the tests for library modules depend on those modules rather than selecting them, despite their symbols being hidden?

This series can also be retrieved from:

git fetch https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git mldsa-v4

This series adds support for verifying ML-DSA signatures to lib/crypto/. Patch 1 is the ML-DSA implementation itself. See that for full details. Patch 2 adds the KUnit test suite.

The initial use case for this will be kernel module signature verification. For more details, see David Howells' patchset
https://lore.kernel.org/linux-crypto/[email protected]/

Note: I'm planning to apply this to libcrypto-next for 6.20.