blob: a837e1b04b5fd79d8288f2783315d4f978763956 [file] [log] [blame]
Gilles Peskinede09ddd2022-12-06 13:20:55 +01001/* 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 Peskinea57cf982022-12-06 22:54:09 +010011#include "bignum_mod_raw.h"
Gilles Peskinede09ddd2022-12-06 13:20:55 +010012#include "constant_time_internal.h"
13
14/* This test suite only manipulates non-negative bignums. */
15static int sign_is_valid( const mbedtls_mpi *X )
16{
17 return( X->s == 1 );
18}
19
Gilles Peskineacdefdd2022-12-15 15:10:36 +010020/* A common initializer for test functions that should generate the same
21 * sequences for reproducibility and good coverage. */
22const 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 Peskinede09ddd2022-12-06 13:20:55 +010029/* 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 */
40static 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 */
81void mpi_core_random_basic( int min, char *bound_bytes, int expected_ret )
82{
83 /* Same RNG as in mpi_random_values */
Gilles Peskineacdefdd2022-12-15 15:10:36 +010084 mbedtls_test_rnd_pseudo_info rnd = rnd_pseudo_seed;
Gilles Peskinede09ddd2022-12-06 13:20:55 +010085 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 Peskine8781dd02022-12-06 23:05:06 +010092 ASSERT_ALLOC( lower_bound, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +010093 lower_bound[0] = min;
Gilles Peskine8781dd02022-12-06 23:05:06 +010094 ASSERT_ALLOC( result, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +010095
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
106exit:
107 mbedtls_free( lower_bound );
108 mbedtls_free( upper_bound );
109 mbedtls_free( result );
110}
111/* END_CASE */
112
113/* BEGIN_CASE */
Gilles Peskine8c32b242022-12-07 23:01:44 +0100114void mpi_legacy_random_values( int min, char *max_hex )
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100115{
116 /* Same RNG as in mpi_core_random_basic */
Gilles Peskineacdefdd2022-12-15 15:10:36 +0100117 mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed;
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100118 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 Peskine8781dd02022-12-06 23:05:06 +0100128 ASSERT_ALLOC( R_core, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100129
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
155exit:
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 Peskinea57cf982022-12-06 22:54:09 +0100163void 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
210exit:
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 Peskinede09ddd2022-12-06 13:20:55 +0100218void 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 Peskine8781dd02022-12-06 23:05:06 +0100242 ASSERT_ALLOC( result, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100243
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
329exit:
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 */
338void 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
364exit:
365 mbedtls_mpi_free( &upper_bound );
366 mbedtls_mpi_free( &result );
367}
368/* END_CASE */
369
370/* BEGIN_CASE */
371void 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
386exit:
387 mbedtls_mpi_free( &upper_bound );
388 mbedtls_mpi_free( &result );
389}
390/* END_CASE */