diff options
Diffstat (limited to 'tests/suites/test_suite_bignum_random.function')
| -rw-r--r-- | tests/suites/test_suite_bignum_random.function | 479 |
1 files changed, 479 insertions, 0 deletions
diff --git a/tests/suites/test_suite_bignum_random.function b/tests/suites/test_suite_bignum_random.function new file mode 100644 index 00000000000..b43b1e713b2 --- /dev/null +++ b/tests/suites/test_suite_bignum_random.function @@ -0,0 +1,479 @@ +/* BEGIN_HEADER */ +/* Dedicated test suite for mbedtls_mpi_core_random() and the upper-layer + * functions. Due to the complexity of how these functions are tested, + * we test all the layers in a single test suite, unlike the way other + * functions are tested with each layer in its own test suite. + * + * Test strategy + * ============= + * + * There are three main goals for testing random() functions: + * - Parameter validation. + * - Correctness of outputs (well-formed, in range). + * - Distribution of outputs. + * + * We test parameter validation in a standard way, with unit tests with + * positive and negative cases: + * - mbedtls_mpi_core_random(): negative cases for mpi_core_random_basic. + * - mbedtls_mpi_mod_raw_random(), mbedtls_mpi_mod_random(): negative + * cases for mpi_mod_random_validation. + * - mbedtls_mpi_random(): mpi_random_fail. + * + * We test the correctness of outputs in positive tests: + * - mbedtls_mpi_core_random(): positive cases for mpi_core_random_basic, + * and mpi_random_many. + * - mbedtls_mpi_mod_raw_random(), mbedtls_mpi_mod_random(): tested indirectly + * via mpi_mod_random_values. + * - mbedtls_mpi_random(): mpi_random_sizes, plus indirectly via + * mpi_random_values. + * + * We test the distribution of outputs only for mbedtls_mpi_core_random(), + * in mpi_random_many, which runs the function multiple times. This also + * helps in validating the output range, through test cases with a small + * range where any output out of range would be very likely to lead to a + * test failure. For the other functions, we validate the distribution + * indirectly by testing that these functions consume the random generator + * in the same way as mbedtls_mpi_core_random(). This is done in + * mpi_mod_random_values and mpi_legacy_random_values. + */ + +#include "mbedtls/bignum.h" +#include "mbedtls/entropy.h" +#include "bignum_core.h" +#include "bignum_mod_raw.h" +#include "constant_time_internal.h" + +/* This test suite only manipulates non-negative bignums. */ +static int sign_is_valid(const mbedtls_mpi *X) +{ + return X->s == 1; +} + +/* A common initializer for test functions that should generate the same + * sequences for reproducibility and good coverage. */ +const mbedtls_test_rnd_pseudo_info rnd_pseudo_seed = { + /* 16-word key */ + { 'T', 'h', 'i', 's', ' ', 'i', 's', ' ', + 'a', ' ', 's', 'e', 'e', 'd', '!', 0 }, + /* 2-word initial state, should be zero */ + 0, 0 +}; + +/* Test whether bytes represents (in big-endian base 256) a number b that + * is significantly above a power of 2. That is, b must not have a long run + * of unset bits after the most significant bit. + * + * Let n be the bit-size of b, i.e. the integer such that 2^n <= b < 2^{n+1}. + * This function returns 1 if, when drawing a number between 0 and b, + * the probability that this number is at least 2^n is not negligible. + * This probability is (b - 2^n) / b and this function checks that this + * number is above some threshold A. The threshold value is heuristic and + * based on the needs of mpi_random_many(). + */ +static int is_significantly_above_a_power_of_2(data_t *bytes) +{ + const uint8_t *p = bytes->x; + size_t len = bytes->len; + unsigned x; + + /* Skip leading null bytes */ + while (len > 0 && p[0] == 0) { + ++p; + --len; + } + /* 0 is not significantly above a power of 2 */ + if (len == 0) { + return 0; + } + /* Extract the (up to) 2 most significant bytes */ + if (len == 1) { + x = p[0]; + } else { + x = (p[0] << 8) | p[1]; + } + + /* Shift the most significant bit of x to position 8 and mask it out */ + while ((x & 0xfe00) != 0) { + x >>= 1; + } + x &= 0x00ff; + + /* At this point, x = floor((b - 2^n) / 2^(n-8)). b is significantly above + * a power of 2 iff x is significantly above 0 compared to 2^8. + * Testing x >= 2^4 amounts to picking A = 1/16 in the function + * description above. */ + return x >= 0x10; +} + +/* END_HEADER */ + +/* BEGIN_DEPENDENCIES + * depends_on:MBEDTLS_BIGNUM_C + * END_DEPENDENCIES + */ + +/* BEGIN_CASE */ +void mpi_core_random_basic(int min, char *bound_bytes, int expected_ret) +{ + /* Same RNG as in mpi_random_values */ + mbedtls_test_rnd_pseudo_info rnd = rnd_pseudo_seed; + size_t limbs; + mbedtls_mpi_uint *lower_bound = NULL; + mbedtls_mpi_uint *upper_bound = NULL; + mbedtls_mpi_uint *result = NULL; + + TEST_EQUAL(0, mbedtls_test_read_mpi_core(&upper_bound, &limbs, + bound_bytes)); + TEST_CALLOC(lower_bound, limbs); + lower_bound[0] = min; + TEST_CALLOC(result, limbs); + + TEST_EQUAL(expected_ret, + mbedtls_mpi_core_random(result, min, upper_bound, limbs, + mbedtls_test_rnd_pseudo_rand, &rnd)); + + if (expected_ret == 0) { + TEST_EQUAL(0, mbedtls_mpi_core_lt_ct(result, lower_bound, limbs)); + TEST_ASSERT(0 != mbedtls_mpi_core_lt_ct(result, upper_bound, limbs)); + } + +exit: + mbedtls_free(lower_bound); + mbedtls_free(upper_bound); + mbedtls_free(result); +} +/* END_CASE */ + +/* BEGIN_CASE */ +void mpi_legacy_random_values(int min, char *max_hex) +{ + /* Same RNG as in mpi_core_random_basic */ + mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed; + mbedtls_test_rnd_pseudo_info rnd_legacy; + memcpy(&rnd_legacy, &rnd_core, sizeof(rnd_core)); + mbedtls_mpi max_legacy; + mbedtls_mpi_init(&max_legacy); + mbedtls_mpi_uint *R_core = NULL; + mbedtls_mpi R_legacy; + mbedtls_mpi_init(&R_legacy); + + TEST_EQUAL(0, mbedtls_test_read_mpi(&max_legacy, max_hex)); + size_t limbs = max_legacy.n; + TEST_CALLOC(R_core, limbs); + + /* Call the legacy function and the core function with the same random + * stream. */ + int core_ret = mbedtls_mpi_core_random(R_core, min, max_legacy.p, limbs, + mbedtls_test_rnd_pseudo_rand, + &rnd_core); + int legacy_ret = mbedtls_mpi_random(&R_legacy, min, &max_legacy, + mbedtls_test_rnd_pseudo_rand, + &rnd_legacy); + + /* They must return the same status, and, on success, output the + * same number, with the same limb count. */ + TEST_EQUAL(core_ret, legacy_ret); + if (core_ret == 0) { + TEST_MEMORY_COMPARE(R_core, limbs * ciL, + R_legacy.p, R_legacy.n * ciL); + } + + /* Also check that they have consumed the RNG in the same way. */ + /* This may theoretically fail on rare platforms with padding in + * the structure! If this is a problem in practice, change to a + * field-by-field comparison. */ + TEST_MEMORY_COMPARE(&rnd_core, sizeof(rnd_core), + &rnd_legacy, sizeof(rnd_legacy)); + +exit: + mbedtls_mpi_free(&max_legacy); + mbedtls_free(R_core); + mbedtls_mpi_free(&R_legacy); +} +/* END_CASE */ + +/* BEGIN_CASE depends_on:MBEDTLS_ECP_WITH_MPI_UINT */ +void mpi_mod_random_values(int min, char *max_hex, int rep) +{ + /* Same RNG as in mpi_core_random_basic */ + mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed; + mbedtls_test_rnd_pseudo_info rnd_mod_raw; + memcpy(&rnd_mod_raw, &rnd_core, sizeof(rnd_core)); + mbedtls_test_rnd_pseudo_info rnd_mod; + memcpy(&rnd_mod, &rnd_core, sizeof(rnd_core)); + mbedtls_mpi_uint *R_core = NULL; + mbedtls_mpi_uint *R_mod_raw = NULL; + mbedtls_mpi_uint *R_mod_digits = NULL; + mbedtls_mpi_mod_residue R_mod; + mbedtls_mpi_mod_modulus N; + mbedtls_mpi_mod_modulus_init(&N); + + TEST_EQUAL(mbedtls_test_read_mpi_modulus(&N, max_hex, rep), 0); + TEST_CALLOC(R_core, N.limbs); + TEST_CALLOC(R_mod_raw, N.limbs); + TEST_CALLOC(R_mod_digits, N.limbs); + TEST_EQUAL(mbedtls_mpi_mod_residue_setup(&R_mod, &N, + R_mod_digits, N.limbs), + 0); + + /* Call the core and mod random() functions with the same random stream. */ + int core_ret = mbedtls_mpi_core_random(R_core, + min, N.p, N.limbs, + mbedtls_test_rnd_pseudo_rand, + &rnd_core); + int mod_raw_ret = mbedtls_mpi_mod_raw_random(R_mod_raw, + min, &N, + mbedtls_test_rnd_pseudo_rand, + &rnd_mod_raw); + int mod_ret = mbedtls_mpi_mod_random(&R_mod, + min, &N, + mbedtls_test_rnd_pseudo_rand, + &rnd_mod); + + /* They must return the same status, and, on success, output the + * same number, with the same limb count. */ + TEST_EQUAL(core_ret, mod_raw_ret); + TEST_EQUAL(core_ret, mod_ret); + if (core_ret == 0) { + TEST_EQUAL(mbedtls_mpi_mod_raw_modulus_to_canonical_rep(R_mod_raw, &N), + 0); + TEST_MEMORY_COMPARE(R_core, N.limbs * ciL, + R_mod_raw, N.limbs * ciL); + TEST_EQUAL(mbedtls_mpi_mod_raw_modulus_to_canonical_rep(R_mod_digits, &N), + 0); + TEST_MEMORY_COMPARE(R_core, N.limbs * ciL, + R_mod_digits, N.limbs * ciL); + } + + /* Also check that they have consumed the RNG in the same way. */ + /* This may theoretically fail on rare platforms with padding in + * the structure! If this is a problem in practice, change to a + * field-by-field comparison. */ + TEST_MEMORY_COMPARE(&rnd_core, sizeof(rnd_core), + &rnd_mod_raw, sizeof(rnd_mod_raw)); + TEST_MEMORY_COMPARE(&rnd_core, sizeof(rnd_core), + &rnd_mod, sizeof(rnd_mod)); + +exit: + mbedtls_test_mpi_mod_modulus_free_with_limbs(&N); + mbedtls_free(R_core); + mbedtls_free(R_mod_raw); + mbedtls_free(R_mod_digits); +} +/* END_CASE */ + +/* BEGIN_CASE */ +void mpi_random_many(int min, char *bound_hex, int iterations) +{ + /* Generate numbers in the range 1..bound-1. Do it iterations times. + * This function assumes that the value of bound is at least 2 and + * that iterations is large enough that a one-in-2^iterations chance + * effectively never occurs. + */ + + data_t bound_bytes = { NULL, 0 }; + mbedtls_mpi_uint *upper_bound = NULL; + size_t limbs; + size_t n_bits; + mbedtls_mpi_uint *result = NULL; + size_t b; + /* If upper_bound is small, stats[b] is the number of times the value b + * has been generated. Otherwise stats[b] is the number of times a + * value with bit b set has been generated. */ + size_t *stats = NULL; + size_t stats_len; + int full_stats; + size_t i; + + TEST_EQUAL(0, mbedtls_test_read_mpi_core(&upper_bound, &limbs, + bound_hex)); + TEST_CALLOC(result, limbs); + + n_bits = mbedtls_mpi_core_bitlen(upper_bound, limbs); + /* Consider a bound "small" if it's less than 2^5. This value is chosen + * to be small enough that the probability of missing one value is + * negligible given the number of iterations. It must be less than + * 256 because some of the code below assumes that "small" values + * fit in a byte. */ + if (n_bits <= 5) { + full_stats = 1; + stats_len = (uint8_t) upper_bound[0]; + } else { + full_stats = 0; + stats_len = n_bits; + } + TEST_CALLOC(stats, stats_len); + + for (i = 0; i < (size_t) iterations; i++) { + mbedtls_test_set_step(i); + TEST_EQUAL(0, mbedtls_mpi_core_random(result, + min, upper_bound, limbs, + mbedtls_test_rnd_std_rand, NULL)); + + /* Temporarily use a legacy MPI for analysis, because the + * necessary auxiliary functions don't exist yet in core. */ + mbedtls_mpi B = { .s = 1, .n = limbs, .p = upper_bound }; + mbedtls_mpi R = { .s = 1, .n = limbs, .p = result }; + + TEST_ASSERT(mbedtls_mpi_cmp_mpi(&R, &B) < 0); + TEST_ASSERT(mbedtls_mpi_cmp_int(&R, min) >= 0); + if (full_stats) { + uint8_t value; + TEST_EQUAL(0, mbedtls_mpi_write_binary(&R, &value, 1)); + TEST_ASSERT(value < stats_len); + ++stats[value]; + } else { + for (b = 0; b < n_bits; b++) { + stats[b] += mbedtls_mpi_get_bit(&R, b); + } + } + } + + if (full_stats) { + for (b = min; b < stats_len; b++) { + mbedtls_test_set_step(1000000 + b); + /* Assert that each value has been reached at least once. + * This is almost guaranteed if the iteration count is large + * enough. This is a very crude way of checking the distribution. + */ + TEST_ASSERT(stats[b] > 0); + } + } else { + bound_bytes.len = limbs * sizeof(mbedtls_mpi_uint); + TEST_CALLOC(bound_bytes.x, bound_bytes.len); + mbedtls_mpi_core_write_be(upper_bound, limbs, + bound_bytes.x, bound_bytes.len); + int statistically_safe_all_the_way = + is_significantly_above_a_power_of_2(&bound_bytes); + for (b = 0; b < n_bits; b++) { + mbedtls_test_set_step(1000000 + b); + /* Assert that each bit has been set in at least one result and + * clear in at least one result. Provided that iterations is not + * too small, it would be extremely unlikely for this not to be + * the case if the results are uniformly distributed. + * + * As an exception, the top bit may legitimately never be set + * if bound is a power of 2 or only slightly above. + */ + if (statistically_safe_all_the_way || b != n_bits - 1) { + TEST_ASSERT(stats[b] > 0); + } + TEST_ASSERT(stats[b] < (size_t) iterations); + } + } + +exit: + mbedtls_free(bound_bytes.x); + mbedtls_free(upper_bound); + mbedtls_free(result); + mbedtls_free(stats); +} +/* END_CASE */ + +/* BEGIN_CASE */ +void mpi_random_sizes(int min, data_t *bound_bytes, int nlimbs, int before) +{ + mbedtls_mpi upper_bound; + mbedtls_mpi result; + + mbedtls_mpi_init(&upper_bound); + mbedtls_mpi_init(&result); + + if (before != 0) { + /* Set result to sign(before) * 2^(|before|-1) */ + TEST_ASSERT(mbedtls_mpi_lset(&result, before > 0 ? 1 : -1) == 0); + if (before < 0) { + before = -before; + } + TEST_ASSERT(mbedtls_mpi_shift_l(&result, before - 1) == 0); + } + + TEST_EQUAL(0, mbedtls_mpi_grow(&result, nlimbs)); + TEST_EQUAL(0, mbedtls_mpi_read_binary(&upper_bound, + bound_bytes->x, bound_bytes->len)); + TEST_EQUAL(0, mbedtls_mpi_random(&result, min, &upper_bound, + mbedtls_test_rnd_std_rand, NULL)); + TEST_ASSERT(sign_is_valid(&result)); + TEST_ASSERT(mbedtls_mpi_cmp_mpi(&result, &upper_bound) < 0); + TEST_ASSERT(mbedtls_mpi_cmp_int(&result, min) >= 0); + +exit: + mbedtls_mpi_free(&upper_bound); + mbedtls_mpi_free(&result); +} +/* END_CASE */ + +/* BEGIN_CASE depends_on:MBEDTLS_ECP_WITH_MPI_UINT */ +void mpi_mod_random_validation(int min, char *bound_hex, + int result_limbs_delta, + int expected_ret) +{ + mbedtls_mpi_uint *result_digits = NULL; + mbedtls_mpi_mod_modulus N; + mbedtls_mpi_mod_modulus_init(&N); + + TEST_EQUAL(mbedtls_test_read_mpi_modulus(&N, bound_hex, + MBEDTLS_MPI_MOD_REP_OPT_RED), + 0); + size_t result_limbs = N.limbs + result_limbs_delta; + TEST_CALLOC(result_digits, result_limbs); + /* Build a reside that might not match the modulus, to test that + * the library function rejects that as expected. */ + mbedtls_mpi_mod_residue result = { result_digits, result_limbs }; + + TEST_EQUAL(mbedtls_mpi_mod_random(&result, min, &N, + mbedtls_test_rnd_std_rand, NULL), + expected_ret); + if (expected_ret == 0) { + /* Success should only be expected when the result has the same + * size as the modulus, otherwise it's a mistake in the test data. */ + TEST_EQUAL(result_limbs, N.limbs); + /* Sanity check: check that the result is in range */ + TEST_ASSERT(0 != mbedtls_mpi_core_lt_ct(result_digits, N.p, N.limbs)); + /* Check result >= min (changes result) */ + TEST_EQUAL(mbedtls_mpi_core_sub_int(result_digits, result_digits, min, + result_limbs), + 0); + } + + /* When the result has the right number of limbs, also test mod_raw + * (for which this is an unchecked precondition). */ + if (result_limbs_delta == 0) { + TEST_EQUAL(mbedtls_mpi_mod_raw_random(result_digits, min, &N, + mbedtls_test_rnd_std_rand, NULL), + expected_ret); + if (expected_ret == 0) { + TEST_ASSERT(0 != mbedtls_mpi_core_lt_ct(result_digits, N.p, N.limbs)); + TEST_EQUAL(mbedtls_mpi_core_sub_int(result_digits, result.p, min, + result_limbs), + 0); + } + } + +exit: + mbedtls_test_mpi_mod_modulus_free_with_limbs(&N); + mbedtls_free(result_digits); +} +/* END_CASE */ + +/* BEGIN_CASE */ +void mpi_random_fail(int min, data_t *bound_bytes, int expected_ret) +{ + mbedtls_mpi upper_bound; + mbedtls_mpi result; + int actual_ret; + + mbedtls_mpi_init(&upper_bound); + mbedtls_mpi_init(&result); + + TEST_EQUAL(0, mbedtls_mpi_read_binary(&upper_bound, + bound_bytes->x, bound_bytes->len)); + actual_ret = mbedtls_mpi_random(&result, min, &upper_bound, + mbedtls_test_rnd_std_rand, NULL); + TEST_EQUAL(expected_ret, actual_ret); + +exit: + mbedtls_mpi_free(&upper_bound); + mbedtls_mpi_free(&result); +} +/* END_CASE */ |