blob: 184de5a4055fff3a654254d65fa4914452bbec68 [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"
11#include "constant_time_internal.h"
12
13/* This test suite only manipulates non-negative bignums. */
14static int sign_is_valid( const mbedtls_mpi *X )
15{
16 return( X->s == 1 );
17}
18
Gilles Peskineacdefdd2022-12-15 15:10:36 +010019/* A common initializer for test functions that should generate the same
20 * sequences for reproducibility and good coverage. */
21const 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 Peskinede09ddd2022-12-06 13:20:55 +010028/* 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 */
39static 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 */
80void mpi_core_random_basic( int min, char *bound_bytes, int expected_ret )
81{
82 /* Same RNG as in mpi_random_values */
Gilles Peskineacdefdd2022-12-15 15:10:36 +010083 mbedtls_test_rnd_pseudo_info rnd = rnd_pseudo_seed;
Gilles Peskinede09ddd2022-12-06 13:20:55 +010084 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 Peskine8781dd02022-12-06 23:05:06 +010091 ASSERT_ALLOC( lower_bound, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +010092 lower_bound[0] = min;
Gilles Peskine8781dd02022-12-06 23:05:06 +010093 ASSERT_ALLOC( result, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +010094
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
105exit:
106 mbedtls_free( lower_bound );
107 mbedtls_free( upper_bound );
108 mbedtls_free( result );
109}
110/* END_CASE */
111
112/* BEGIN_CASE */
113void mpi_random_values( int min, char *max_hex )
114{
115 /* Same RNG as in mpi_core_random_basic */
Gilles Peskineacdefdd2022-12-15 15:10:36 +0100116 mbedtls_test_rnd_pseudo_info rnd_core = rnd_pseudo_seed;
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100117 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 Peskine8781dd02022-12-06 23:05:06 +0100127 ASSERT_ALLOC( R_core, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100128
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
154exit:
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 */
162void 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 Peskine8781dd02022-12-06 23:05:06 +0100186 ASSERT_ALLOC( result, limbs );
Gilles Peskinede09ddd2022-12-06 13:20:55 +0100187
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
273exit:
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 */
282void 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
308exit:
309 mbedtls_mpi_free( &upper_bound );
310 mbedtls_mpi_free( &result );
311}
312/* END_CASE */
313
314/* BEGIN_CASE */
315void 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
330exit:
331 mbedtls_mpi_free( &upper_bound );
332 mbedtls_mpi_free( &result );
333}
334/* END_CASE */