From 66c7ef01faabe7ad6293d6b738d4103de77437b4 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Niels=20M=C3=B6ller?= Date: Fri, 5 Jun 2026 19:30:16 +0200 Subject: [PATCH] More randomized tests of ml-kem, add asserts for arithmetic primitives. --- ChangeLog | 12 ++++++++++++ ml-kem-internal.c | 15 ++++++++++++--- testsuite/ml-kem-test.c | 37 ++++++++++++++++++++++++++++--------- 3 files changed, 52 insertions(+), 12 deletions(-) diff --git a/ChangeLog b/ChangeLog index 854d1416..6346a872 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,15 @@ +2026-06-05 Niels Möller + + * ml-kem-internal.c (compress, reduce, mod_sub, mod_add): Use + assert_maybe to back up input and output expectations. + + * testsuite/ml-kem-test.c (test_ml_kem_pairwise): Take randomness + source as argument. + (test_randomized): New function, using test_get_seed for + initializing the pseudo randomness generator. + (test_main) [WITH_EXTRA_ASSERTS]: Skip side-channel tests. + (test_main): Call test_randomized. + 2026-06-04 Niels Möller * nettle-internal.h (assert_maybe): Move macro here, replacing old diff --git a/ml-kem-internal.c b/ml-kem-internal.c index 39c47866..031b7285 100644 --- a/ml-kem-internal.c +++ b/ml-kem-internal.c @@ -35,10 +35,12 @@ # include "config.h" #endif +#include + #include "ml-kem-internal.h" #include "sha3.h" -#include +#include "nettle-internal.h" #define Q 3329 #define Q_BITS 12 @@ -115,6 +117,7 @@ PRF (struct sha3_ctx *ctx, static inline uint16_t compress (uint16_t x, unsigned int d) { + assert_maybe (x < Q); return ((UINT64_C(20642679) * ((x << d) + (Q >> 1)) >> 36) & ((1 << d) - 1)); } @@ -132,11 +135,13 @@ static inline uint16_t reduce (uint64_t a) { uint64_t mask; + assert_maybe (a < Q*Q); a -= ((a * 5039) >> (Q_BITS << 1)) * Q; mask = -(uint64_t) (a >= Q); - - return a - (Q & mask); + a -= (Q & mask); + assert_maybe (a < Q); + return a; } /* Calculate a - b mod Q, where 0 <= a < Q and 0 <= b <= Q */ @@ -144,6 +149,8 @@ static inline uint16_t mod_sub (uint16_t a, uint16_t b) { uint16_t mask; + assert_maybe (a < Q); + assert_maybe (b <= Q); mask = -(uint16_t) (a < b); @@ -154,6 +161,8 @@ mod_sub (uint16_t a, uint16_t b) static inline uint16_t mod_add (uint16_t a, uint16_t b) { + assert_maybe (a < Q); + assert_maybe (b < Q); return mod_sub (a, Q - b); } diff --git a/testsuite/ml-kem-test.c b/testsuite/ml-kem-test.c index 5d1d61c2..15931095 100644 --- a/testsuite/ml-kem-test.c +++ b/testsuite/ml-kem-test.c @@ -141,9 +141,9 @@ test_ml_kem_encap_decap (const struct ml_kem_params *params, } static void -test_ml_kem_pairwise (const struct ml_kem_params *params) +test_ml_kem_pairwise (const struct ml_kem_params *params, + void *random_ctx, nettle_random_func *random) { - struct knuth_lfib_ctx lfib; uint8_t *pub; uint8_t *key; uint8_t *ciphertext; @@ -152,21 +152,18 @@ test_ml_kem_pairwise (const struct ml_kem_params *params) uint8_t secret2[32]; uint16_t *scratch; - knuth_lfib_init(&lfib, 1111); - pub = xalloc (params->public_key_size); key = xalloc (params->private_key_size); ciphertext = xalloc (params->ciphertext_size); scratch = xalloc (ml_kem_generate_keypair_itch (params) * sizeof(uint16_t)); - knuth_lfib_random (&lfib, sizeof (seed), seed); + random (random_ctx, sizeof (seed), seed); ml_kem_generate_keypair (params, pub, key, seed, scratch); free (scratch); scratch = xalloc (ml_kem_encap_itch (params) * sizeof(uint16_t)); ml_kem_encap (params, pub, secret, ciphertext, - &lfib, (nettle_random_func *) knuth_lfib_random, - scratch); + random_ctx, random, scratch); free (scratch); scratch = xalloc (ml_kem_decap_itch (params) * sizeof(uint16_t)); @@ -180,9 +177,32 @@ test_ml_kem_pairwise (const struct ml_kem_params *params) free (ciphertext); } +static void +test_randomized (void) +{ + struct knuth_lfib_ctx lfib; + unsigned count; + unsigned end_count = test_side_channel ? 10 : 1000; + /* FIXME: Use a stronger randomness generator with 64-bit seed. */ + knuth_lfib_init (&lfib, test_get_seed ()); + end_count = test_side_channel ? 10 : 1000; + for (count = 0; count < end_count; count++) + { + test_ml_kem_pairwise (nettle_get_ml_kem_768_params (), + &lfib, (nettle_random_func *) knuth_lfib_random); + test_ml_kem_pairwise (nettle_get_ml_kem_1024_params (), + &lfib, (nettle_random_func *) knuth_lfib_random); + } +} + void test_main (void) { +#if WITH_EXTRA_ASSERTS + if (test_side_channel) + SKIP(); +#endif + /* Test vectors from: https://github.com/usnistgov/ACVP-Server/tree/d98cad66639bf9d0822129c4bcae7a169fcf9ca6/gen-val/json-files/ML-KEM-keyGen-FIPS203 */ /* tcId: 26 */ @@ -217,6 +237,5 @@ test_main (void) read_hex_file ("ml-kem-1024-encapdecap-tc51.ct", ML_KEM_1024_CIPHERTEXT_SIZE), SHEX ("5D537CD0EF7B58F0FE95370473B96878F138ECC259ADFBF77EBD7328B822D9D9")); - test_ml_kem_pairwise (nettle_get_ml_kem_768_params ()); - test_ml_kem_pairwise (nettle_get_ml_kem_1024_params ()); + test_randomized (); } -- 2.47.3