// SPDX-License-Identifier: GPL-2.0-or-later /* * KUnit tests and benchmark for ML-DSA * * Copyright 2025 Google LLC */ #include #include #include #include #define Q 8380417 /* The prime q = 2^23 - 2^13 + 1 */ /* ML-DSA parameters that the tests use */ static const struct { int sig_len; int pk_len; int k; int lambda; int gamma1; int beta; int omega; } params[] = { [MLDSA44] = { .sig_len = MLDSA44_SIGNATURE_SIZE, .pk_len = MLDSA44_PUBLIC_KEY_SIZE, .k = 4, .lambda = 128, .gamma1 = 1 << 17, .beta = 78, .omega = 80, }, [MLDSA65] = { .sig_len = MLDSA65_SIGNATURE_SIZE, .pk_len = MLDSA65_PUBLIC_KEY_SIZE, .k = 6, .lambda = 192, .gamma1 = 1 << 19, .beta = 196, .omega = 55, }, [MLDSA87] = { .sig_len = MLDSA87_SIGNATURE_SIZE, .pk_len = MLDSA87_PUBLIC_KEY_SIZE, .k = 8, .lambda = 256, .gamma1 = 1 << 19, .beta = 120, .omega = 75, }, }; #include "mldsa-testvecs.h" static void do_mldsa_and_assert_success(struct kunit *test, const struct mldsa_testvector *tv) { int err = mldsa_verify(tv->alg, tv->sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len); KUNIT_ASSERT_EQ(test, err, 0); } static u8 *kunit_kmemdup_or_fail(struct kunit *test, const u8 *src, size_t len) { u8 *dst = kunit_kmalloc(test, len, GFP_KERNEL); KUNIT_ASSERT_NOT_NULL(test, dst); return memcpy(dst, src, len); } /* * Test that changing coefficients in a valid signature's z vector results in * the following behavior from mldsa_verify(): * * * -EBADMSG if a coefficient is changed to have an out-of-range value, i.e. * absolute value >= gamma1 - beta, corresponding to the verifier detecting * the out-of-range coefficient and rejecting the signature as malformed * * * -EKEYREJECTED if a coefficient is changed to a different in-range value, * i.e. absolute value < gamma1 - beta, corresponding to the verifier * continuing to the "real" signature check and that check failing */ static void test_mldsa_z_range(struct kunit *test, const struct mldsa_testvector *tv) { u8 *sig = kunit_kmemdup_or_fail(test, tv->sig, tv->sig_len); const int lambda = params[tv->alg].lambda; const s32 gamma1 = params[tv->alg].gamma1; const int beta = params[tv->alg].beta; /* * We just modify the first coefficient. The coefficient is gamma1 * minus either the first 18 or 20 bits of the u32, depending on gamma1. * * The layout of ML-DSA signatures is ctilde || z || h. ctilde is * lambda / 4 bytes, so z starts at &sig[lambda / 4]. */ u8 *z_ptr = &sig[lambda / 4]; const u32 z_data = get_unaligned_le32(z_ptr); const u32 mask = (gamma1 << 1) - 1; /* These are the four boundaries of the out-of-range values. */ const s32 out_of_range_coeffs[] = { -gamma1 + 1, -(gamma1 - beta), gamma1, gamma1 - beta, }; /* * These are the two boundaries of the valid range, along with 0. We * assume that none of these matches the original coefficient. */ const s32 in_range_coeffs[] = { -(gamma1 - beta - 1), 0, gamma1 - beta - 1, }; /* Initially the signature is valid. */ do_mldsa_and_assert_success(test, tv); /* Test some out-of-range coefficients. */ for (int i = 0; i < ARRAY_SIZE(out_of_range_coeffs); i++) { const s32 c = out_of_range_coeffs[i]; put_unaligned_le32((z_data & ~mask) | (mask & (gamma1 - c)), z_ptr); KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); } /* Test some in-range coefficients. */ for (int i = 0; i < ARRAY_SIZE(in_range_coeffs); i++) { const s32 c = in_range_coeffs[i]; put_unaligned_le32((z_data & ~mask) | (mask & (gamma1 - c)), z_ptr); KUNIT_ASSERT_EQ(test, -EKEYREJECTED, mldsa_verify(tv->alg, sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); } } /* Test that mldsa_verify() rejects malformed hint vectors with -EBADMSG. */ static void test_mldsa_bad_hints(struct kunit *test, const struct mldsa_testvector *tv) { const int omega = params[tv->alg].omega; const int k = params[tv->alg].k; u8 *sig = kunit_kmemdup_or_fail(test, tv->sig, tv->sig_len); /* Pointer to the encoded hint vector in the signature */ u8 *hintvec = &sig[tv->sig_len - omega - k]; u8 h; /* Initially the signature is valid. */ do_mldsa_and_assert_success(test, tv); /* Cumulative hint count exceeds omega */ memcpy(sig, tv->sig, tv->sig_len); hintvec[omega + k - 1] = omega + 1; KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); /* Cumulative hint count decreases */ memcpy(sig, tv->sig, tv->sig_len); KUNIT_ASSERT_GE(test, hintvec[omega + k - 2], 1); hintvec[omega + k - 1] = hintvec[omega + k - 2] - 1; KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); /* * Hint indices out of order. To test this, swap hintvec[0] and * hintvec[1]. This assumes that the original valid signature had at * least two nonzero hints in the first element (asserted below). */ memcpy(sig, tv->sig, tv->sig_len); KUNIT_ASSERT_GE(test, hintvec[omega], 2); h = hintvec[0]; hintvec[0] = hintvec[1]; hintvec[1] = h; KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); /* * Extra hint indices given. For this test to work, the original valid * signature must have fewer than omega nonzero hints (asserted below). */ memcpy(sig, tv->sig, tv->sig_len); KUNIT_ASSERT_LT(test, hintvec[omega + k - 1], omega); hintvec[omega - 1] = 0xff; KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); } static void test_mldsa_mutation(struct kunit *test, const struct mldsa_testvector *tv) { const int sig_len = tv->sig_len; const int msg_len = tv->msg_len; const int pk_len = tv->pk_len; const int num_iter = 200; u8 *sig = kunit_kmemdup_or_fail(test, tv->sig, sig_len); u8 *msg = kunit_kmemdup_or_fail(test, tv->msg, msg_len); u8 *pk = kunit_kmemdup_or_fail(test, tv->pk, pk_len); /* Initially the signature is valid. */ do_mldsa_and_assert_success(test, tv); /* Changing any bit in the signature should invalidate the signature */ for (int i = 0; i < num_iter; i++) { size_t pos = get_random_u32_below(sig_len); u8 b = 1 << get_random_u32_below(8); sig[pos] ^= b; KUNIT_ASSERT_NE(test, 0, mldsa_verify(tv->alg, sig, sig_len, msg, msg_len, pk, pk_len)); sig[pos] ^= b; } /* Changing any bit in the message should invalidate the signature */ for (int i = 0; i < num_iter; i++) { size_t pos = get_random_u32_below(msg_len); u8 b = 1 << get_random_u32_below(8); msg[pos] ^= b; KUNIT_ASSERT_NE(test, 0, mldsa_verify(tv->alg, sig, sig_len, msg, msg_len, pk, pk_len)); msg[pos] ^= b; } /* Changing any bit in the public key should invalidate the signature */ for (int i = 0; i < num_iter; i++) { size_t pos = get_random_u32_below(pk_len); u8 b = 1 << get_random_u32_below(8); pk[pos] ^= b; KUNIT_ASSERT_NE(test, 0, mldsa_verify(tv->alg, sig, sig_len, msg, msg_len, pk, pk_len)); pk[pos] ^= b; } /* All changes should have been undone. */ KUNIT_ASSERT_EQ(test, 0, mldsa_verify(tv->alg, sig, sig_len, msg, msg_len, pk, pk_len)); } static void test_mldsa(struct kunit *test, const struct mldsa_testvector *tv) { /* Valid signature */ KUNIT_ASSERT_EQ(test, tv->sig_len, params[tv->alg].sig_len); KUNIT_ASSERT_EQ(test, tv->pk_len, params[tv->alg].pk_len); do_mldsa_and_assert_success(test, tv); /* Signature too short */ KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, tv->sig, tv->sig_len - 1, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); /* Signature too long */ KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, tv->sig, tv->sig_len + 1, tv->msg, tv->msg_len, tv->pk, tv->pk_len)); /* Public key too short */ KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, tv->sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len - 1)); /* Public key too long */ KUNIT_ASSERT_EQ(test, -EBADMSG, mldsa_verify(tv->alg, tv->sig, tv->sig_len, tv->msg, tv->msg_len, tv->pk, tv->pk_len + 1)); /* * Message too short. Error is EKEYREJECTED because it gets rejected by * the "real" signature check rather than the well-formedness checks. */ KUNIT_ASSERT_EQ(test, -EKEYREJECTED, mldsa_verify(tv->alg, tv->sig, tv->sig_len, tv->msg, tv->msg_len - 1, tv->pk, tv->pk_len)); /* * Can't simply try (tv->msg, tv->msg_len + 1) too, as tv->msg would be * accessed out of bounds. However, ML-DSA just hashes the message and * doesn't handle different message lengths differently anyway. */ /* Test the validity checks on the z vector. */ test_mldsa_z_range(test, tv); /* Test the validity checks on the hint vector. */ test_mldsa_bad_hints(test, tv); /* Test randomly mutating the inputs. */ test_mldsa_mutation(test, tv); } static void test_mldsa44(struct kunit *test) { test_mldsa(test, &mldsa44_testvector); } static void test_mldsa65(struct kunit *test) { test_mldsa(test, &mldsa65_testvector); } static void test_mldsa87(struct kunit *test) { test_mldsa(test, &mldsa87_testvector); } static s32 mod(s32 a, s32 m) { a %= m; if (a < 0) a += m; return a; } static s32 symmetric_mod(s32 a, s32 m) { a = mod(a, m); if (a > m / 2) a -= m; return a; } /* Mechanical, inefficient translation of FIPS 204 Algorithm 36, Decompose */ static void decompose_ref(s32 r, s32 gamma2, s32 *r0, s32 *r1) { s32 rplus = mod(r, Q); *r0 = symmetric_mod(rplus, 2 * gamma2); if (rplus - *r0 == Q - 1) { *r1 = 0; *r0 = *r0 - 1; } else { *r1 = (rplus - *r0) / (2 * gamma2); } } /* Mechanical, inefficient translation of FIPS 204 Algorithm 40, UseHint */ static s32 use_hint_ref(u8 h, s32 r, s32 gamma2) { s32 m = (Q - 1) / (2 * gamma2); s32 r0, r1; decompose_ref(r, gamma2, &r0, &r1); if (h == 1 && r0 > 0) return mod(r1 + 1, m); if (h == 1 && r0 <= 0) return mod(r1 - 1, m); return r1; } /* * Test that for all possible inputs, mldsa_use_hint() gives the same output as * a mechanical translation of the pseudocode from FIPS 204. */ static void test_mldsa_use_hint(struct kunit *test) { for (int i = 0; i < 2; i++) { const s32 gamma2 = (Q - 1) / (i == 0 ? 88 : 32); for (u8 h = 0; h < 2; h++) { for (s32 r = 0; r < Q; r++) { KUNIT_ASSERT_EQ(test, mldsa_use_hint(h, r, gamma2), use_hint_ref(h, r, gamma2)); } } } } static void benchmark_mldsa(struct kunit *test, const struct mldsa_testvector *tv) { const int warmup_niter = 200; const int benchmark_niter = 200; u64 t0, t1; if (!IS_ENABLED(CONFIG_CRYPTO_LIB_BENCHMARK)) kunit_skip(test, "not enabled"); for (int i = 0; i < warmup_niter; i++) do_mldsa_and_assert_success(test, tv); t0 = ktime_get_ns(); for (int i = 0; i < benchmark_niter; i++) do_mldsa_and_assert_success(test, tv); t1 = ktime_get_ns(); kunit_info(test, "%llu ops/s", div64_u64((u64)benchmark_niter * NSEC_PER_SEC, t1 - t0 ?: 1)); } static void benchmark_mldsa44(struct kunit *test) { benchmark_mldsa(test, &mldsa44_testvector); } static void benchmark_mldsa65(struct kunit *test) { benchmark_mldsa(test, &mldsa65_testvector); } static void benchmark_mldsa87(struct kunit *test) { benchmark_mldsa(test, &mldsa87_testvector); } static struct kunit_case mldsa_kunit_cases[] = { KUNIT_CASE(test_mldsa44), KUNIT_CASE(test_mldsa65), KUNIT_CASE(test_mldsa87), KUNIT_CASE(test_mldsa_use_hint), KUNIT_CASE(benchmark_mldsa44), KUNIT_CASE(benchmark_mldsa65), KUNIT_CASE(benchmark_mldsa87), {}, }; static struct kunit_suite mldsa_kunit_suite = { .name = "mldsa", .test_cases = mldsa_kunit_cases, }; kunit_test_suite(mldsa_kunit_suite); MODULE_DESCRIPTION("KUnit tests and benchmark for ML-DSA"); MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING"); MODULE_LICENSE("GPL");