Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 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 | |
| 8 | #include "mbedtls/bignum.h" |
| 9 | #include "mbedtls/entropy.h" |
| 10 | #include "bignum_core.h" |
Gilles Peskine | a57cf98 | 2022-12-06 22:54:09 +0100 | [diff] [blame^] | 11 | #include "bignum_mod_raw.h" |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 12 | #include "constant_time_internal.h" |
| 13 | |
| 14 | /* This test suite only manipulates non-negative bignums. */ |
| 15 | static int sign_is_valid( const mbedtls_mpi *X ) |
| 16 | { |
| 17 | return( X->s == 1 ); |
| 18 | } |
| 19 | |
Gilles Peskine | acdefdd | 2022-12-15 15:10:36 +0100 | [diff] [blame] | 20 | /* A common initializer for test functions that should generate the same |
| 21 | * sequences for reproducibility and good coverage. */ |
| 22 | const mbedtls_test_rnd_pseudo_info rnd_pseudo_seed = { |
| 23 | /* 16-word key */ |
| 24 | {'T', 'h', 'i', 's', ' ', 'i', 's', ' ', |
| 25 | 'a', ' ', 's', 'e', 'e', 'd', '!', 0}, |
| 26 | /* 2-word initial state, should be zero */ |
| 27 | 0, 0}; |
| 28 | |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 29 | /* Test whether bytes represents (in big-endian base 256) a number b that |
| 30 | * is significantly above a power of 2. That is, b must not have a long run |
| 31 | * of unset bits after the most significant bit. |
| 32 | * |
| 33 | * Let n be the bit-size of b, i.e. the integer such that 2^n <= b < 2^{n+1}. |
| 34 | * This function returns 1 if, when drawing a number between 0 and b, |
| 35 | * the probability that this number is at least 2^n is not negligible. |
| 36 | * This probability is (b - 2^n) / b and this function checks that this |
| 37 | * number is above some threshold A. The threshold value is heuristic and |
| 38 | * based on the needs of mpi_random_many(). |
| 39 | */ |
| 40 | static int is_significantly_above_a_power_of_2( data_t *bytes ) |
| 41 | { |
| 42 | const uint8_t *p = bytes->x; |
| 43 | size_t len = bytes->len; |
| 44 | unsigned x; |
| 45 | |
| 46 | /* Skip leading null bytes */ |
| 47 | while( len > 0 && p[0] == 0 ) |
| 48 | { |
| 49 | ++p; |
| 50 | --len; |
| 51 | } |
| 52 | /* 0 is not significantly above a power of 2 */ |
| 53 | if( len == 0 ) |
| 54 | return( 0 ); |
| 55 | /* Extract the (up to) 2 most significant bytes */ |
| 56 | if( len == 1 ) |
| 57 | x = p[0]; |
| 58 | else |
| 59 | x = ( p[0] << 8 ) | p[1]; |
| 60 | |
| 61 | /* Shift the most significant bit of x to position 8 and mask it out */ |
| 62 | while( ( x & 0xfe00 ) != 0 ) |
| 63 | x >>= 1; |
| 64 | x &= 0x00ff; |
| 65 | |
| 66 | /* At this point, x = floor((b - 2^n) / 2^(n-8)). b is significantly above |
| 67 | * a power of 2 iff x is significantly above 0 compared to 2^8. |
| 68 | * Testing x >= 2^4 amounts to picking A = 1/16 in the function |
| 69 | * description above. */ |
| 70 | return( x >= 0x10 ); |
| 71 | } |
| 72 | |
| 73 | /* END_HEADER */ |
| 74 | |
| 75 | /* BEGIN_DEPENDENCIES |
| 76 | * depends_on:MBEDTLS_BIGNUM_C |
| 77 | * END_DEPENDENCIES |
| 78 | */ |
| 79 | |
| 80 | /* BEGIN_CASE */ |
| 81 | void mpi_core_random_basic( int min, char *bound_bytes, int expected_ret ) |
| 82 | { |
| 83 | /* Same RNG as in mpi_random_values */ |
Gilles Peskine | acdefdd | 2022-12-15 15:10:36 +0100 | [diff] [blame] | 84 | mbedtls_test_rnd_pseudo_info rnd = rnd_pseudo_seed; |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 85 | size_t limbs; |
| 86 | mbedtls_mpi_uint *lower_bound = NULL; |
| 87 | mbedtls_mpi_uint *upper_bound = NULL; |
| 88 | mbedtls_mpi_uint *result = NULL; |
| 89 | |
| 90 | TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &upper_bound, &limbs, |
| 91 | bound_bytes ) ); |
Gilles Peskine | 8781dd0 | 2022-12-06 23:05:06 +0100 | [diff] [blame] | 92 | ASSERT_ALLOC( lower_bound, limbs ); |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 93 | lower_bound[0] = min; |
Gilles Peskine | 8781dd0 | 2022-12-06 23:05:06 +0100 | [diff] [blame] | 94 | ASSERT_ALLOC( result, limbs ); |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 95 | |
| 96 | TEST_EQUAL( expected_ret, |
| 97 | mbedtls_mpi_core_random( result, min, upper_bound, limbs, |
| 98 | mbedtls_test_rnd_pseudo_rand, &rnd ) ); |
| 99 | |
| 100 | if( expected_ret == 0 ) |
| 101 | { |
| 102 | TEST_EQUAL( 0, mbedtls_mpi_core_lt_ct( result, lower_bound, limbs ) ); |
| 103 | TEST_EQUAL( 1, mbedtls_mpi_core_lt_ct( result, upper_bound, limbs ) ); |
| 104 | } |
| 105 | |
| 106 | exit: |
| 107 | mbedtls_free( lower_bound ); |
| 108 | mbedtls_free( upper_bound ); |
| 109 | mbedtls_free( result ); |
| 110 | } |
| 111 | /* END_CASE */ |
| 112 | |
| 113 | /* BEGIN_CASE */ |
Gilles Peskine | 8c32b24 | 2022-12-07 23:01:44 +0100 | [diff] [blame] | 114 | void mpi_legacy_random_values( int min, char *max_hex ) |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 115 | { |
| 116 | /* Same RNG as in mpi_core_random_basic */ |
Gilles Peskine | acdefdd | 2022-12-15 15:10:36 +0100 | [diff] [blame] | 117 | mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed; |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 118 | mbedtls_test_rnd_pseudo_info rnd_legacy; |
| 119 | memcpy( &rnd_legacy, &rnd_core, sizeof( rnd_core ) ); |
| 120 | mbedtls_mpi max_legacy; |
| 121 | mbedtls_mpi_init( &max_legacy ); |
| 122 | mbedtls_mpi_uint *R_core = NULL; |
| 123 | mbedtls_mpi R_legacy; |
| 124 | mbedtls_mpi_init( &R_legacy ); |
| 125 | |
| 126 | TEST_EQUAL( 0, mbedtls_test_read_mpi( &max_legacy, max_hex ) ); |
| 127 | size_t limbs = max_legacy.n; |
Gilles Peskine | 8781dd0 | 2022-12-06 23:05:06 +0100 | [diff] [blame] | 128 | ASSERT_ALLOC( R_core, limbs ); |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 129 | |
| 130 | /* Call the legacy function and the core function with the same random |
| 131 | * stream. */ |
| 132 | int core_ret = mbedtls_mpi_core_random( R_core, min, max_legacy.p, limbs, |
| 133 | mbedtls_test_rnd_pseudo_rand, |
| 134 | &rnd_core ); |
| 135 | int legacy_ret = mbedtls_mpi_random( &R_legacy, min, &max_legacy, |
| 136 | mbedtls_test_rnd_pseudo_rand, |
| 137 | &rnd_legacy ); |
| 138 | |
| 139 | /* They must return the same status, and, on success, output the |
| 140 | * same number, with the same limb count. */ |
| 141 | TEST_EQUAL( core_ret, legacy_ret ); |
| 142 | if( core_ret == 0 ) |
| 143 | { |
| 144 | ASSERT_COMPARE( R_core, limbs * ciL, |
| 145 | R_legacy.p, R_legacy.n * ciL ); |
| 146 | } |
| 147 | |
| 148 | /* Also check that they have consumed the RNG in the same way. */ |
| 149 | /* This may theoretically fail on rare platforms with padding in |
| 150 | * the structure! If this is a problem in practice, change to a |
| 151 | * field-by-field comparison. */ |
| 152 | ASSERT_COMPARE( &rnd_core, sizeof( rnd_core ), |
| 153 | &rnd_legacy, sizeof( rnd_legacy ) ); |
| 154 | |
| 155 | exit: |
| 156 | mbedtls_mpi_free( &max_legacy ); |
| 157 | mbedtls_free( R_core ); |
| 158 | mbedtls_mpi_free( &R_legacy ); |
| 159 | } |
| 160 | /* END_CASE */ |
| 161 | |
| 162 | /* BEGIN_CASE */ |
Gilles Peskine | a57cf98 | 2022-12-06 22:54:09 +0100 | [diff] [blame^] | 163 | void mpi_mod_random_values( int min, char *max_hex ) |
| 164 | { |
| 165 | /* Same RNG as in mpi_core_random_basic */ |
| 166 | mbedtls_test_rnd_pseudo_info rnd_core = { |
| 167 | {'T', 'h', 'i', 's', ' ', 'i', ',', 'a', |
| 168 | 's', 'e', 'e', 'd', '!', 0}, |
| 169 | 0, 0}; |
| 170 | mbedtls_test_rnd_pseudo_info rnd_mod_raw; |
| 171 | memcpy( &rnd_mod_raw, &rnd_core, sizeof( rnd_core ) ); |
| 172 | mbedtls_mpi_uint *R_core = NULL; |
| 173 | mbedtls_mpi_uint *R_mod_raw = NULL; |
| 174 | mbedtls_mpi_mod_modulus N; |
| 175 | mbedtls_mpi_mod_modulus_init( &N ); |
| 176 | |
| 177 | TEST_EQUAL( mbedtls_test_read_mpi_modulus( &N, max_hex, |
| 178 | MBEDTLS_MPI_MOD_REP_MONTGOMERY ), |
| 179 | 0 ); |
| 180 | ASSERT_ALLOC( R_core, N.limbs ); |
| 181 | ASSERT_ALLOC( R_mod_raw, N.limbs ); |
| 182 | |
| 183 | /* Call the core and mod random() functions with the same random stream. */ |
| 184 | int core_ret = mbedtls_mpi_core_random( R_core, |
| 185 | min, N.p, N.limbs, |
| 186 | mbedtls_test_rnd_pseudo_rand, |
| 187 | &rnd_core ); |
| 188 | int mod_raw_ret = mbedtls_mpi_mod_raw_random( R_mod_raw, |
| 189 | min, &N, |
| 190 | mbedtls_test_rnd_pseudo_rand, |
| 191 | &rnd_mod_raw ); |
| 192 | |
| 193 | /* They must return the same status, and, on success, output the |
| 194 | * same number, with the same limb count. */ |
| 195 | TEST_EQUAL( core_ret, mod_raw_ret ); |
| 196 | if( core_ret == 0 ) |
| 197 | { |
| 198 | TEST_EQUAL( mbedtls_mpi_mod_raw_from_mont_rep( R_mod_raw, &N ), 0 ); |
| 199 | ASSERT_COMPARE( R_core, N.limbs * ciL, |
| 200 | R_mod_raw, N.limbs * ciL ); |
| 201 | } |
| 202 | |
| 203 | /* Also check that they have consumed the RNG in the same way. */ |
| 204 | /* This may theoretically fail on rare platforms with padding in |
| 205 | * the structure! If this is a problem in practice, change to a |
| 206 | * field-by-field comparison. */ |
| 207 | ASSERT_COMPARE( &rnd_core, sizeof( rnd_core ), |
| 208 | &rnd_mod_raw, sizeof( rnd_mod_raw ) ); |
| 209 | |
| 210 | exit: |
| 211 | mbedtls_mpi_mod_modulus_free( &N ); |
| 212 | mbedtls_free( R_core ); |
| 213 | mbedtls_free( R_mod_raw ); |
| 214 | } |
| 215 | /* END_CASE */ |
| 216 | |
| 217 | /* BEGIN_CASE */ |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 218 | void mpi_random_many( int min, char *bound_hex, int iterations ) |
| 219 | { |
| 220 | /* Generate numbers in the range 1..bound-1. Do it iterations times. |
| 221 | * This function assumes that the value of bound is at least 2 and |
| 222 | * that iterations is large enough that a one-in-2^iterations chance |
| 223 | * effectively never occurs. |
| 224 | */ |
| 225 | |
| 226 | data_t bound_bytes = {NULL, 0}; |
| 227 | mbedtls_mpi_uint *upper_bound = NULL; |
| 228 | size_t limbs; |
| 229 | size_t n_bits; |
| 230 | mbedtls_mpi_uint *result = NULL; |
| 231 | size_t b; |
| 232 | /* If upper_bound is small, stats[b] is the number of times the value b |
| 233 | * has been generated. Otherwise stats[b] is the number of times a |
| 234 | * value with bit b set has been generated. */ |
| 235 | size_t *stats = NULL; |
| 236 | size_t stats_len; |
| 237 | int full_stats; |
| 238 | size_t i; |
| 239 | |
| 240 | TEST_EQUAL( 0, mbedtls_test_read_mpi_core( &upper_bound, &limbs, |
| 241 | bound_hex ) ); |
Gilles Peskine | 8781dd0 | 2022-12-06 23:05:06 +0100 | [diff] [blame] | 242 | ASSERT_ALLOC( result, limbs ); |
Gilles Peskine | de09ddd | 2022-12-06 13:20:55 +0100 | [diff] [blame] | 243 | |
| 244 | n_bits = mbedtls_mpi_core_bitlen( upper_bound, limbs ); |
| 245 | /* Consider a bound "small" if it's less than 2^5. This value is chosen |
| 246 | * to be small enough that the probability of missing one value is |
| 247 | * negligible given the number of iterations. It must be less than |
| 248 | * 256 because some of the code below assumes that "small" values |
| 249 | * fit in a byte. */ |
| 250 | if( n_bits <= 5 ) |
| 251 | { |
| 252 | full_stats = 1; |
| 253 | stats_len = (uint8_t) upper_bound[0]; |
| 254 | } |
| 255 | else |
| 256 | { |
| 257 | full_stats = 0; |
| 258 | stats_len = n_bits; |
| 259 | } |
| 260 | ASSERT_ALLOC( stats, stats_len ); |
| 261 | |
| 262 | for( i = 0; i < (size_t) iterations; i++ ) |
| 263 | { |
| 264 | mbedtls_test_set_step( i ); |
| 265 | TEST_EQUAL( 0, mbedtls_mpi_core_random( result, |
| 266 | min, upper_bound, limbs, |
| 267 | mbedtls_test_rnd_std_rand, NULL ) ); |
| 268 | |
| 269 | /* Temporarily use a legacy MPI for analysis, because the |
| 270 | * necessary auxiliary functions don't exist yet in core. */ |
| 271 | mbedtls_mpi B = {1, limbs, upper_bound}; |
| 272 | mbedtls_mpi R = {1, limbs, result}; |
| 273 | |
| 274 | TEST_ASSERT( mbedtls_mpi_cmp_mpi( &R, &B ) < 0 ); |
| 275 | TEST_ASSERT( mbedtls_mpi_cmp_int( &R, min ) >= 0 ); |
| 276 | if( full_stats ) |
| 277 | { |
| 278 | uint8_t value; |
| 279 | TEST_EQUAL( 0, mbedtls_mpi_write_binary( &R, &value, 1 ) ); |
| 280 | TEST_ASSERT( value < stats_len ); |
| 281 | ++stats[value]; |
| 282 | } |
| 283 | else |
| 284 | { |
| 285 | for( b = 0; b < n_bits; b++ ) |
| 286 | stats[b] += mbedtls_mpi_get_bit( &R, b ); |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | if( full_stats ) |
| 291 | { |
| 292 | for( b = min; b < stats_len; b++ ) |
| 293 | { |
| 294 | mbedtls_test_set_step( 1000000 + b ); |
| 295 | /* Assert that each value has been reached at least once. |
| 296 | * This is almost guaranteed if the iteration count is large |
| 297 | * enough. This is a very crude way of checking the distribution. |
| 298 | */ |
| 299 | TEST_ASSERT( stats[b] > 0 ); |
| 300 | } |
| 301 | } |
| 302 | else |
| 303 | { |
| 304 | bound_bytes.len = limbs * sizeof( mbedtls_mpi_uint ); |
| 305 | ASSERT_ALLOC( bound_bytes.x, bound_bytes.len ); |
| 306 | mbedtls_mpi_core_write_be( upper_bound, limbs, |
| 307 | bound_bytes.x, bound_bytes.len ); |
| 308 | int statistically_safe_all_the_way = |
| 309 | is_significantly_above_a_power_of_2( &bound_bytes ); |
| 310 | for( b = 0; b < n_bits; b++ ) |
| 311 | { |
| 312 | mbedtls_test_set_step( 1000000 + b ); |
| 313 | /* Assert that each bit has been set in at least one result and |
| 314 | * clear in at least one result. Provided that iterations is not |
| 315 | * too small, it would be extremely unlikely for this not to be |
| 316 | * the case if the results are uniformly distributed. |
| 317 | * |
| 318 | * As an exception, the top bit may legitimately never be set |
| 319 | * if bound is a power of 2 or only slightly above. |
| 320 | */ |
| 321 | if( statistically_safe_all_the_way || b != n_bits - 1 ) |
| 322 | { |
| 323 | TEST_ASSERT( stats[b] > 0 ); |
| 324 | } |
| 325 | TEST_ASSERT( stats[b] < (size_t) iterations ); |
| 326 | } |
| 327 | } |
| 328 | |
| 329 | exit: |
| 330 | mbedtls_free( bound_bytes.x ); |
| 331 | mbedtls_free( upper_bound ); |
| 332 | mbedtls_free( result ); |
| 333 | mbedtls_free( stats ); |
| 334 | } |
| 335 | /* END_CASE */ |
| 336 | |
| 337 | /* BEGIN_CASE */ |
| 338 | void mpi_random_sizes( int min, data_t *bound_bytes, int nlimbs, int before ) |
| 339 | { |
| 340 | mbedtls_mpi upper_bound; |
| 341 | mbedtls_mpi result; |
| 342 | |
| 343 | mbedtls_mpi_init( &upper_bound ); |
| 344 | mbedtls_mpi_init( &result ); |
| 345 | |
| 346 | if( before != 0 ) |
| 347 | { |
| 348 | /* Set result to sign(before) * 2^(|before|-1) */ |
| 349 | TEST_ASSERT( mbedtls_mpi_lset( &result, before > 0 ? 1 : -1 ) == 0 ); |
| 350 | if( before < 0 ) |
| 351 | before = - before; |
| 352 | TEST_ASSERT( mbedtls_mpi_shift_l( &result, before - 1 ) == 0 ); |
| 353 | } |
| 354 | |
| 355 | TEST_EQUAL( 0, mbedtls_mpi_grow( &result, nlimbs ) ); |
| 356 | TEST_EQUAL( 0, mbedtls_mpi_read_binary( &upper_bound, |
| 357 | bound_bytes->x, bound_bytes->len ) ); |
| 358 | TEST_EQUAL( 0, mbedtls_mpi_random( &result, min, &upper_bound, |
| 359 | mbedtls_test_rnd_std_rand, NULL ) ); |
| 360 | TEST_ASSERT( sign_is_valid( &result ) ); |
| 361 | TEST_ASSERT( mbedtls_mpi_cmp_mpi( &result, &upper_bound ) < 0 ); |
| 362 | TEST_ASSERT( mbedtls_mpi_cmp_int( &result, min ) >= 0 ); |
| 363 | |
| 364 | exit: |
| 365 | mbedtls_mpi_free( &upper_bound ); |
| 366 | mbedtls_mpi_free( &result ); |
| 367 | } |
| 368 | /* END_CASE */ |
| 369 | |
| 370 | /* BEGIN_CASE */ |
| 371 | void mpi_random_fail( int min, data_t *bound_bytes, int expected_ret ) |
| 372 | { |
| 373 | mbedtls_mpi upper_bound; |
| 374 | mbedtls_mpi result; |
| 375 | int actual_ret; |
| 376 | |
| 377 | mbedtls_mpi_init( &upper_bound ); |
| 378 | mbedtls_mpi_init( &result ); |
| 379 | |
| 380 | TEST_EQUAL( 0, mbedtls_mpi_read_binary( &upper_bound, |
| 381 | bound_bytes->x, bound_bytes->len ) ); |
| 382 | actual_ret = mbedtls_mpi_random( &result, min, &upper_bound, |
| 383 | mbedtls_test_rnd_std_rand, NULL ); |
| 384 | TEST_EQUAL( expected_ret, actual_ret ); |
| 385 | |
| 386 | exit: |
| 387 | mbedtls_mpi_free( &upper_bound ); |
| 388 | mbedtls_mpi_free( &result ); |
| 389 | } |
| 390 | /* END_CASE */ |