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