test_suite_bignum_random.function (18120B)
1 /* BEGIN_HEADER */ 2 /* Dedicated test suite for mbedtls_mpi_core_random() and the upper-layer 3 * functions. Due to the complexity of how these functions are tested, 4 * we test all the layers in a single test suite, unlike the way other 5 * functions are tested with each layer in its own test suite. 6 * 7 * Test strategy 8 * ============= 9 * 10 * There are three main goals for testing random() functions: 11 * - Parameter validation. 12 * - Correctness of outputs (well-formed, in range). 13 * - Distribution of outputs. 14 * 15 * We test parameter validation in a standard way, with unit tests with 16 * positive and negative cases: 17 * - mbedtls_mpi_core_random(): negative cases for mpi_core_random_basic. 18 * - mbedtls_mpi_mod_raw_random(), mbedtls_mpi_mod_random(): negative 19 * cases for mpi_mod_random_validation. 20 * - mbedtls_mpi_random(): mpi_random_fail. 21 * 22 * We test the correctness of outputs in positive tests: 23 * - mbedtls_mpi_core_random(): positive cases for mpi_core_random_basic, 24 * and mpi_random_many. 25 * - mbedtls_mpi_mod_raw_random(), mbedtls_mpi_mod_random(): tested indirectly 26 * via mpi_mod_random_values. 27 * - mbedtls_mpi_random(): mpi_random_sizes, plus indirectly via 28 * mpi_random_values. 29 * 30 * We test the distribution of outputs only for mbedtls_mpi_core_random(), 31 * in mpi_random_many, which runs the function multiple times. This also 32 * helps in validating the output range, through test cases with a small 33 * range where any output out of range would be very likely to lead to a 34 * test failure. For the other functions, we validate the distribution 35 * indirectly by testing that these functions consume the random generator 36 * in the same way as mbedtls_mpi_core_random(). This is done in 37 * mpi_mod_random_values and mpi_legacy_random_values. 38 */ 39 40 #include "mbedtls/bignum.h" 41 #include "mbedtls/entropy.h" 42 #include "bignum_core.h" 43 #include "bignum_mod_raw.h" 44 #include "constant_time_internal.h" 45 46 /* This test suite only manipulates non-negative bignums. */ 47 static int sign_is_valid(const mbedtls_mpi *X) 48 { 49 return X->s == 1; 50 } 51 52 /* A common initializer for test functions that should generate the same 53 * sequences for reproducibility and good coverage. */ 54 const mbedtls_test_rnd_pseudo_info rnd_pseudo_seed = { 55 /* 16-word key */ 56 { 'T', 'h', 'i', 's', ' ', 'i', 's', ' ', 57 'a', ' ', 's', 'e', 'e', 'd', '!', 0 }, 58 /* 2-word initial state, should be zero */ 59 0, 0 60 }; 61 62 /* Test whether bytes represents (in big-endian base 256) a number b that 63 * is significantly above a power of 2. That is, b must not have a long run 64 * of unset bits after the most significant bit. 65 * 66 * Let n be the bit-size of b, i.e. the integer such that 2^n <= b < 2^{n+1}. 67 * This function returns 1 if, when drawing a number between 0 and b, 68 * the probability that this number is at least 2^n is not negligible. 69 * This probability is (b - 2^n) / b and this function checks that this 70 * number is above some threshold A. The threshold value is heuristic and 71 * based on the needs of mpi_random_many(). 72 */ 73 static int is_significantly_above_a_power_of_2(data_t *bytes) 74 { 75 const uint8_t *p = bytes->x; 76 size_t len = bytes->len; 77 unsigned x; 78 79 /* Skip leading null bytes */ 80 while (len > 0 && p[0] == 0) { 81 ++p; 82 --len; 83 } 84 /* 0 is not significantly above a power of 2 */ 85 if (len == 0) { 86 return 0; 87 } 88 /* Extract the (up to) 2 most significant bytes */ 89 if (len == 1) { 90 x = p[0]; 91 } else { 92 x = (p[0] << 8) | p[1]; 93 } 94 95 /* Shift the most significant bit of x to position 8 and mask it out */ 96 while ((x & 0xfe00) != 0) { 97 x >>= 1; 98 } 99 x &= 0x00ff; 100 101 /* At this point, x = floor((b - 2^n) / 2^(n-8)). b is significantly above 102 * a power of 2 iff x is significantly above 0 compared to 2^8. 103 * Testing x >= 2^4 amounts to picking A = 1/16 in the function 104 * description above. */ 105 return x >= 0x10; 106 } 107 108 /* END_HEADER */ 109 110 /* BEGIN_DEPENDENCIES 111 * depends_on:MBEDTLS_BIGNUM_C 112 * END_DEPENDENCIES 113 */ 114 115 /* BEGIN_CASE */ 116 void mpi_core_random_basic(int min, char *bound_bytes, int expected_ret) 117 { 118 /* Same RNG as in mpi_random_values */ 119 mbedtls_test_rnd_pseudo_info rnd = rnd_pseudo_seed; 120 size_t limbs; 121 mbedtls_mpi_uint *lower_bound = NULL; 122 mbedtls_mpi_uint *upper_bound = NULL; 123 mbedtls_mpi_uint *result = NULL; 124 125 TEST_EQUAL(0, mbedtls_test_read_mpi_core(&upper_bound, &limbs, 126 bound_bytes)); 127 TEST_CALLOC(lower_bound, limbs); 128 lower_bound[0] = min; 129 TEST_CALLOC(result, limbs); 130 131 TEST_EQUAL(expected_ret, 132 mbedtls_mpi_core_random(result, min, upper_bound, limbs, 133 mbedtls_test_rnd_pseudo_rand, &rnd)); 134 135 if (expected_ret == 0) { 136 TEST_EQUAL(0, mbedtls_mpi_core_lt_ct(result, lower_bound, limbs)); 137 TEST_ASSERT(0 != mbedtls_mpi_core_lt_ct(result, upper_bound, limbs)); 138 } 139 140 exit: 141 mbedtls_free(lower_bound); 142 mbedtls_free(upper_bound); 143 mbedtls_free(result); 144 } 145 /* END_CASE */ 146 147 /* BEGIN_CASE */ 148 void mpi_legacy_random_values(int min, char *max_hex) 149 { 150 /* Same RNG as in mpi_core_random_basic */ 151 mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed; 152 mbedtls_test_rnd_pseudo_info rnd_legacy; 153 memcpy(&rnd_legacy, &rnd_core, sizeof(rnd_core)); 154 mbedtls_mpi max_legacy; 155 mbedtls_mpi_init(&max_legacy); 156 mbedtls_mpi_uint *R_core = NULL; 157 mbedtls_mpi R_legacy; 158 mbedtls_mpi_init(&R_legacy); 159 160 TEST_EQUAL(0, mbedtls_test_read_mpi(&max_legacy, max_hex)); 161 size_t limbs = max_legacy.n; 162 TEST_CALLOC(R_core, limbs); 163 164 /* Call the legacy function and the core function with the same random 165 * stream. */ 166 int core_ret = mbedtls_mpi_core_random(R_core, min, max_legacy.p, limbs, 167 mbedtls_test_rnd_pseudo_rand, 168 &rnd_core); 169 int legacy_ret = mbedtls_mpi_random(&R_legacy, min, &max_legacy, 170 mbedtls_test_rnd_pseudo_rand, 171 &rnd_legacy); 172 173 /* They must return the same status, and, on success, output the 174 * same number, with the same limb count. */ 175 TEST_EQUAL(core_ret, legacy_ret); 176 if (core_ret == 0) { 177 TEST_MEMORY_COMPARE(R_core, limbs * ciL, 178 R_legacy.p, R_legacy.n * ciL); 179 } 180 181 /* Also check that they have consumed the RNG in the same way. */ 182 /* This may theoretically fail on rare platforms with padding in 183 * the structure! If this is a problem in practice, change to a 184 * field-by-field comparison. */ 185 TEST_MEMORY_COMPARE(&rnd_core, sizeof(rnd_core), 186 &rnd_legacy, sizeof(rnd_legacy)); 187 188 exit: 189 mbedtls_mpi_free(&max_legacy); 190 mbedtls_free(R_core); 191 mbedtls_mpi_free(&R_legacy); 192 } 193 /* END_CASE */ 194 195 /* BEGIN_CASE depends_on:MBEDTLS_ECP_WITH_MPI_UINT */ 196 void mpi_mod_random_values(int min, char *max_hex, int rep) 197 { 198 /* Same RNG as in mpi_core_random_basic */ 199 mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed; 200 mbedtls_test_rnd_pseudo_info rnd_mod_raw; 201 memcpy(&rnd_mod_raw, &rnd_core, sizeof(rnd_core)); 202 mbedtls_test_rnd_pseudo_info rnd_mod; 203 memcpy(&rnd_mod, &rnd_core, sizeof(rnd_core)); 204 mbedtls_mpi_uint *R_core = NULL; 205 mbedtls_mpi_uint *R_mod_raw = NULL; 206 mbedtls_mpi_uint *R_mod_digits = NULL; 207 mbedtls_mpi_mod_residue R_mod; 208 mbedtls_mpi_mod_modulus N; 209 mbedtls_mpi_mod_modulus_init(&N); 210 211 TEST_EQUAL(mbedtls_test_read_mpi_modulus(&N, max_hex, rep), 0); 212 TEST_CALLOC(R_core, N.limbs); 213 TEST_CALLOC(R_mod_raw, N.limbs); 214 TEST_CALLOC(R_mod_digits, N.limbs); 215 TEST_EQUAL(mbedtls_mpi_mod_residue_setup(&R_mod, &N, 216 R_mod_digits, N.limbs), 217 0); 218 219 /* Call the core and mod random() functions with the same random stream. */ 220 int core_ret = mbedtls_mpi_core_random(R_core, 221 min, N.p, N.limbs, 222 mbedtls_test_rnd_pseudo_rand, 223 &rnd_core); 224 int mod_raw_ret = mbedtls_mpi_mod_raw_random(R_mod_raw, 225 min, &N, 226 mbedtls_test_rnd_pseudo_rand, 227 &rnd_mod_raw); 228 int mod_ret = mbedtls_mpi_mod_random(&R_mod, 229 min, &N, 230 mbedtls_test_rnd_pseudo_rand, 231 &rnd_mod); 232 233 /* They must return the same status, and, on success, output the 234 * same number, with the same limb count. */ 235 TEST_EQUAL(core_ret, mod_raw_ret); 236 TEST_EQUAL(core_ret, mod_ret); 237 if (core_ret == 0) { 238 TEST_EQUAL(mbedtls_mpi_mod_raw_modulus_to_canonical_rep(R_mod_raw, &N), 239 0); 240 TEST_MEMORY_COMPARE(R_core, N.limbs * ciL, 241 R_mod_raw, N.limbs * ciL); 242 TEST_EQUAL(mbedtls_mpi_mod_raw_modulus_to_canonical_rep(R_mod_digits, &N), 243 0); 244 TEST_MEMORY_COMPARE(R_core, N.limbs * ciL, 245 R_mod_digits, N.limbs * ciL); 246 } 247 248 /* Also check that they have consumed the RNG in the same way. */ 249 /* This may theoretically fail on rare platforms with padding in 250 * the structure! If this is a problem in practice, change to a 251 * field-by-field comparison. */ 252 TEST_MEMORY_COMPARE(&rnd_core, sizeof(rnd_core), 253 &rnd_mod_raw, sizeof(rnd_mod_raw)); 254 TEST_MEMORY_COMPARE(&rnd_core, sizeof(rnd_core), 255 &rnd_mod, sizeof(rnd_mod)); 256 257 exit: 258 mbedtls_test_mpi_mod_modulus_free_with_limbs(&N); 259 mbedtls_free(R_core); 260 mbedtls_free(R_mod_raw); 261 mbedtls_free(R_mod_digits); 262 } 263 /* END_CASE */ 264 265 /* BEGIN_CASE */ 266 void mpi_random_many(int min, char *bound_hex, int iterations) 267 { 268 /* Generate numbers in the range 1..bound-1. Do it iterations times. 269 * This function assumes that the value of bound is at least 2 and 270 * that iterations is large enough that a one-in-2^iterations chance 271 * effectively never occurs. 272 */ 273 274 data_t bound_bytes = { NULL, 0 }; 275 mbedtls_mpi_uint *upper_bound = NULL; 276 size_t limbs; 277 size_t n_bits; 278 mbedtls_mpi_uint *result = NULL; 279 size_t b; 280 /* If upper_bound is small, stats[b] is the number of times the value b 281 * has been generated. Otherwise stats[b] is the number of times a 282 * value with bit b set has been generated. */ 283 size_t *stats = NULL; 284 size_t stats_len; 285 int full_stats; 286 size_t i; 287 288 TEST_EQUAL(0, mbedtls_test_read_mpi_core(&upper_bound, &limbs, 289 bound_hex)); 290 TEST_CALLOC(result, limbs); 291 292 n_bits = mbedtls_mpi_core_bitlen(upper_bound, limbs); 293 /* Consider a bound "small" if it's less than 2^5. This value is chosen 294 * to be small enough that the probability of missing one value is 295 * negligible given the number of iterations. It must be less than 296 * 256 because some of the code below assumes that "small" values 297 * fit in a byte. */ 298 if (n_bits <= 5) { 299 full_stats = 1; 300 stats_len = (uint8_t) upper_bound[0]; 301 } else { 302 full_stats = 0; 303 stats_len = n_bits; 304 } 305 TEST_CALLOC(stats, stats_len); 306 307 for (i = 0; i < (size_t) iterations; i++) { 308 mbedtls_test_set_step(i); 309 TEST_EQUAL(0, mbedtls_mpi_core_random(result, 310 min, upper_bound, limbs, 311 mbedtls_test_rnd_std_rand, NULL)); 312 313 /* Temporarily use a legacy MPI for analysis, because the 314 * necessary auxiliary functions don't exist yet in core. */ 315 mbedtls_mpi B = { .s = 1, .n = limbs, .p = upper_bound }; 316 mbedtls_mpi R = { .s = 1, .n = limbs, .p = result }; 317 318 TEST_ASSERT(mbedtls_mpi_cmp_mpi(&R, &B) < 0); 319 TEST_ASSERT(mbedtls_mpi_cmp_int(&R, min) >= 0); 320 if (full_stats) { 321 uint8_t value; 322 TEST_EQUAL(0, mbedtls_mpi_write_binary(&R, &value, 1)); 323 TEST_ASSERT(value < stats_len); 324 ++stats[value]; 325 } else { 326 for (b = 0; b < n_bits; b++) { 327 stats[b] += mbedtls_mpi_get_bit(&R, b); 328 } 329 } 330 } 331 332 if (full_stats) { 333 for (b = min; b < stats_len; b++) { 334 mbedtls_test_set_step(1000000 + b); 335 /* Assert that each value has been reached at least once. 336 * This is almost guaranteed if the iteration count is large 337 * enough. This is a very crude way of checking the distribution. 338 */ 339 TEST_ASSERT(stats[b] > 0); 340 } 341 } else { 342 bound_bytes.len = limbs * sizeof(mbedtls_mpi_uint); 343 TEST_CALLOC(bound_bytes.x, bound_bytes.len); 344 mbedtls_mpi_core_write_be(upper_bound, limbs, 345 bound_bytes.x, bound_bytes.len); 346 int statistically_safe_all_the_way = 347 is_significantly_above_a_power_of_2(&bound_bytes); 348 for (b = 0; b < n_bits; b++) { 349 mbedtls_test_set_step(1000000 + b); 350 /* Assert that each bit has been set in at least one result and 351 * clear in at least one result. Provided that iterations is not 352 * too small, it would be extremely unlikely for this not to be 353 * the case if the results are uniformly distributed. 354 * 355 * As an exception, the top bit may legitimately never be set 356 * if bound is a power of 2 or only slightly above. 357 */ 358 if (statistically_safe_all_the_way || b != n_bits - 1) { 359 TEST_ASSERT(stats[b] > 0); 360 } 361 TEST_ASSERT(stats[b] < (size_t) iterations); 362 } 363 } 364 365 exit: 366 mbedtls_free(bound_bytes.x); 367 mbedtls_free(upper_bound); 368 mbedtls_free(result); 369 mbedtls_free(stats); 370 } 371 /* END_CASE */ 372 373 /* BEGIN_CASE */ 374 void mpi_random_sizes(int min, data_t *bound_bytes, int nlimbs, int before) 375 { 376 mbedtls_mpi upper_bound; 377 mbedtls_mpi result; 378 379 mbedtls_mpi_init(&upper_bound); 380 mbedtls_mpi_init(&result); 381 382 if (before != 0) { 383 /* Set result to sign(before) * 2^(|before|-1) */ 384 TEST_ASSERT(mbedtls_mpi_lset(&result, before > 0 ? 1 : -1) == 0); 385 if (before < 0) { 386 before = -before; 387 } 388 TEST_ASSERT(mbedtls_mpi_shift_l(&result, before - 1) == 0); 389 } 390 391 TEST_EQUAL(0, mbedtls_mpi_grow(&result, nlimbs)); 392 TEST_EQUAL(0, mbedtls_mpi_read_binary(&upper_bound, 393 bound_bytes->x, bound_bytes->len)); 394 TEST_EQUAL(0, mbedtls_mpi_random(&result, min, &upper_bound, 395 mbedtls_test_rnd_std_rand, NULL)); 396 TEST_ASSERT(sign_is_valid(&result)); 397 TEST_ASSERT(mbedtls_mpi_cmp_mpi(&result, &upper_bound) < 0); 398 TEST_ASSERT(mbedtls_mpi_cmp_int(&result, min) >= 0); 399 400 exit: 401 mbedtls_mpi_free(&upper_bound); 402 mbedtls_mpi_free(&result); 403 } 404 /* END_CASE */ 405 406 /* BEGIN_CASE depends_on:MBEDTLS_ECP_WITH_MPI_UINT */ 407 void mpi_mod_random_validation(int min, char *bound_hex, 408 int result_limbs_delta, 409 int expected_ret) 410 { 411 mbedtls_mpi_uint *result_digits = NULL; 412 mbedtls_mpi_mod_modulus N; 413 mbedtls_mpi_mod_modulus_init(&N); 414 415 TEST_EQUAL(mbedtls_test_read_mpi_modulus(&N, bound_hex, 416 MBEDTLS_MPI_MOD_REP_OPT_RED), 417 0); 418 size_t result_limbs = N.limbs + result_limbs_delta; 419 TEST_CALLOC(result_digits, result_limbs); 420 /* Build a reside that might not match the modulus, to test that 421 * the library function rejects that as expected. */ 422 mbedtls_mpi_mod_residue result = { result_digits, result_limbs }; 423 424 TEST_EQUAL(mbedtls_mpi_mod_random(&result, min, &N, 425 mbedtls_test_rnd_std_rand, NULL), 426 expected_ret); 427 if (expected_ret == 0) { 428 /* Success should only be expected when the result has the same 429 * size as the modulus, otherwise it's a mistake in the test data. */ 430 TEST_EQUAL(result_limbs, N.limbs); 431 /* Sanity check: check that the result is in range */ 432 TEST_ASSERT(0 != mbedtls_mpi_core_lt_ct(result_digits, N.p, N.limbs)); 433 /* Check result >= min (changes result) */ 434 TEST_EQUAL(mbedtls_mpi_core_sub_int(result_digits, result_digits, min, 435 result_limbs), 436 0); 437 } 438 439 /* When the result has the right number of limbs, also test mod_raw 440 * (for which this is an unchecked precondition). */ 441 if (result_limbs_delta == 0) { 442 TEST_EQUAL(mbedtls_mpi_mod_raw_random(result_digits, min, &N, 443 mbedtls_test_rnd_std_rand, NULL), 444 expected_ret); 445 if (expected_ret == 0) { 446 TEST_ASSERT(0 != mbedtls_mpi_core_lt_ct(result_digits, N.p, N.limbs)); 447 TEST_EQUAL(mbedtls_mpi_core_sub_int(result_digits, result.p, min, 448 result_limbs), 449 0); 450 } 451 } 452 453 exit: 454 mbedtls_test_mpi_mod_modulus_free_with_limbs(&N); 455 mbedtls_free(result_digits); 456 } 457 /* END_CASE */ 458 459 /* BEGIN_CASE */ 460 void mpi_random_fail(int min, data_t *bound_bytes, int expected_ret) 461 { 462 mbedtls_mpi upper_bound; 463 mbedtls_mpi result; 464 int actual_ret; 465 466 mbedtls_mpi_init(&upper_bound); 467 mbedtls_mpi_init(&result); 468 469 TEST_EQUAL(0, mbedtls_mpi_read_binary(&upper_bound, 470 bound_bytes->x, bound_bytes->len)); 471 actual_ret = mbedtls_mpi_random(&result, min, &upper_bound, 472 mbedtls_test_rnd_std_rand, NULL); 473 TEST_EQUAL(expected_ret, actual_ret); 474 475 exit: 476 mbedtls_mpi_free(&upper_bound); 477 mbedtls_mpi_free(&result); 478 } 479 /* END_CASE */