Line data Source code
1 : /*
2 : * Core bignum functions
3 : *
4 : * Copyright The Mbed TLS Contributors
5 : * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 : */
7 :
8 : #include "common.h"
9 :
10 : #if defined(MBEDTLS_BIGNUM_C)
11 :
12 : #include <string.h>
13 :
14 : #include "mbedtls/error.h"
15 : #include "mbedtls/platform_util.h"
16 : #include "constant_time_internal.h"
17 :
18 : #include "mbedtls/platform.h"
19 :
20 : #include "bignum_core.h"
21 : #include "bn_mul.h"
22 : #include "constant_time_internal.h"
23 :
24 8596435 : size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a)
25 : {
26 : #if defined(__has_builtin)
27 : #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_clz)
28 : #define core_clz __builtin_clz
29 : #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_clzl)
30 : #define core_clz __builtin_clzl
31 : #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_clzll)
32 : #define core_clz __builtin_clzll
33 : #endif
34 : #endif
35 : #if defined(core_clz)
36 8596435 : return (size_t) core_clz(a);
37 : #else
38 : size_t j;
39 : mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
40 :
41 : for (j = 0; j < biL; j++) {
42 : if (a & mask) {
43 : break;
44 : }
45 :
46 : mask >>= 1;
47 : }
48 :
49 : return j;
50 : #endif
51 : }
52 :
53 8596437 : size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs)
54 : {
55 : int i;
56 : size_t j;
57 :
58 27272411 : for (i = ((int) A_limbs) - 1; i >= 0; i--) {
59 27272409 : if (A[i] != 0) {
60 8596435 : j = biL - mbedtls_mpi_core_clz(A[i]);
61 8596435 : return (i * biL) + j;
62 : }
63 : }
64 :
65 2 : return 0;
66 : }
67 :
68 215950 : static mbedtls_mpi_uint mpi_bigendian_to_host(mbedtls_mpi_uint a)
69 : {
70 : if (MBEDTLS_IS_BIG_ENDIAN) {
71 : /* Nothing to do on bigendian systems. */
72 : return a;
73 : } else {
74 : #if defined(MBEDTLS_HAVE_INT32)
75 : return (mbedtls_mpi_uint) MBEDTLS_BSWAP32(a);
76 : #elif defined(MBEDTLS_HAVE_INT64)
77 215950 : return (mbedtls_mpi_uint) MBEDTLS_BSWAP64(a);
78 : #endif
79 : }
80 : }
81 :
82 32875 : void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A,
83 : size_t A_limbs)
84 : {
85 : mbedtls_mpi_uint *cur_limb_left;
86 : mbedtls_mpi_uint *cur_limb_right;
87 32875 : if (A_limbs == 0) {
88 0 : return;
89 : }
90 :
91 : /*
92 : * Traverse limbs and
93 : * - adapt byte-order in each limb
94 : * - swap the limbs themselves.
95 : * For that, simultaneously traverse the limbs from left to right
96 : * and from right to left, as long as the left index is not bigger
97 : * than the right index (it's not a problem if limbs is odd and the
98 : * indices coincide in the last iteration).
99 : */
100 32875 : for (cur_limb_left = A, cur_limb_right = A + (A_limbs - 1);
101 140850 : cur_limb_left <= cur_limb_right;
102 107975 : cur_limb_left++, cur_limb_right--) {
103 : mbedtls_mpi_uint tmp;
104 : /* Note that if cur_limb_left == cur_limb_right,
105 : * this code effectively swaps the bytes only once. */
106 107975 : tmp = mpi_bigendian_to_host(*cur_limb_left);
107 107975 : *cur_limb_left = mpi_bigendian_to_host(*cur_limb_right);
108 107975 : *cur_limb_right = tmp;
109 : }
110 : }
111 :
112 : /* Whether min <= A, in constant time.
113 : * A_limbs must be at least 1. */
114 1244 : mbedtls_ct_condition_t mbedtls_mpi_core_uint_le_mpi(mbedtls_mpi_uint min,
115 : const mbedtls_mpi_uint *A,
116 : size_t A_limbs)
117 : {
118 : /* min <= least significant limb? */
119 1244 : mbedtls_ct_condition_t min_le_lsl = mbedtls_ct_uint_ge(A[0], min);
120 :
121 : /* limbs other than the least significant one are all zero? */
122 1244 : mbedtls_ct_condition_t msll_mask = MBEDTLS_CT_FALSE;
123 5032 : for (size_t i = 1; i < A_limbs; i++) {
124 3788 : msll_mask = mbedtls_ct_bool_or(msll_mask, mbedtls_ct_bool(A[i]));
125 : }
126 :
127 : /* min <= A iff the lowest limb of A is >= min or the other limbs
128 : * are not all zero. */
129 1244 : return mbedtls_ct_bool_or(msll_mask, min_le_lsl);
130 : }
131 :
132 1244 : mbedtls_ct_condition_t mbedtls_mpi_core_lt_ct(const mbedtls_mpi_uint *A,
133 : const mbedtls_mpi_uint *B,
134 : size_t limbs)
135 : {
136 1244 : mbedtls_ct_condition_t ret = MBEDTLS_CT_FALSE, cond = MBEDTLS_CT_FALSE, done = MBEDTLS_CT_FALSE;
137 :
138 6276 : for (size_t i = limbs; i > 0; i--) {
139 : /*
140 : * If B[i - 1] < A[i - 1] then A < B is false and the result must
141 : * remain 0.
142 : *
143 : * Again even if we can make a decision, we just mark the result and
144 : * the fact that we are done and continue looping.
145 : */
146 5032 : cond = mbedtls_ct_uint_lt(B[i - 1], A[i - 1]);
147 5032 : done = mbedtls_ct_bool_or(done, cond);
148 :
149 : /*
150 : * If A[i - 1] < B[i - 1] then A < B is true.
151 : *
152 : * Again even if we can make a decision, we just mark the result and
153 : * the fact that we are done and continue looping.
154 : */
155 5032 : cond = mbedtls_ct_uint_lt(A[i - 1], B[i - 1]);
156 5032 : ret = mbedtls_ct_bool_or(ret, mbedtls_ct_bool_and(cond, mbedtls_ct_bool_not(done)));
157 5032 : done = mbedtls_ct_bool_or(done, cond);
158 : }
159 :
160 : /*
161 : * If all the limbs were equal, then the numbers are equal, A < B is false
162 : * and leaving the result 0 is correct.
163 : */
164 :
165 1244 : return ret;
166 : }
167 :
168 5141172 : void mbedtls_mpi_core_cond_assign(mbedtls_mpi_uint *X,
169 : const mbedtls_mpi_uint *A,
170 : size_t limbs,
171 : mbedtls_ct_condition_t assign)
172 : {
173 5141172 : if (X == A) {
174 0 : return;
175 : }
176 :
177 : /* This function is very performance-sensitive for RSA. For this reason
178 : * we have the loop below, instead of calling mbedtls_ct_memcpy_if
179 : * (this is more optimal since here we don't have to handle the case where
180 : * we copy awkwardly sized data).
181 : */
182 30130308 : for (size_t i = 0; i < limbs; i++) {
183 24989136 : X[i] = mbedtls_ct_mpi_uint_if(assign, A[i], X[i]);
184 : }
185 : }
186 :
187 0 : void mbedtls_mpi_core_cond_swap(mbedtls_mpi_uint *X,
188 : mbedtls_mpi_uint *Y,
189 : size_t limbs,
190 : mbedtls_ct_condition_t swap)
191 : {
192 0 : if (X == Y) {
193 0 : return;
194 : }
195 :
196 0 : for (size_t i = 0; i < limbs; i++) {
197 0 : mbedtls_mpi_uint tmp = X[i];
198 0 : X[i] = mbedtls_ct_mpi_uint_if(swap, Y[i], X[i]);
199 0 : Y[i] = mbedtls_ct_mpi_uint_if(swap, tmp, Y[i]);
200 : }
201 : }
202 :
203 0 : int mbedtls_mpi_core_read_le(mbedtls_mpi_uint *X,
204 : size_t X_limbs,
205 : const unsigned char *input,
206 : size_t input_length)
207 : {
208 0 : const size_t limbs = CHARS_TO_LIMBS(input_length);
209 :
210 0 : if (X_limbs < limbs) {
211 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
212 : }
213 :
214 0 : if (X != NULL) {
215 0 : memset(X, 0, X_limbs * ciL);
216 :
217 0 : for (size_t i = 0; i < input_length; i++) {
218 0 : size_t offset = ((i % ciL) << 3);
219 0 : X[i / ciL] |= ((mbedtls_mpi_uint) input[i]) << offset;
220 : }
221 : }
222 :
223 0 : return 0;
224 : }
225 :
226 31479 : int mbedtls_mpi_core_read_be(mbedtls_mpi_uint *X,
227 : size_t X_limbs,
228 : const unsigned char *input,
229 : size_t input_length)
230 : {
231 31479 : const size_t limbs = CHARS_TO_LIMBS(input_length);
232 :
233 31479 : if (X_limbs < limbs) {
234 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
235 : }
236 :
237 : /* If X_limbs is 0, input_length must also be 0 (from previous test).
238 : * Nothing to do. */
239 31479 : if (X_limbs == 0) {
240 0 : return 0;
241 : }
242 :
243 31479 : memset(X, 0, X_limbs * ciL);
244 :
245 : /* memcpy() with (NULL, 0) is undefined behaviour */
246 31479 : if (input_length != 0) {
247 31479 : size_t overhead = (X_limbs * ciL) - input_length;
248 31479 : unsigned char *Xp = (unsigned char *) X;
249 31479 : memcpy(Xp + overhead, input, input_length);
250 : }
251 :
252 31479 : mbedtls_mpi_core_bigendian_to_host(X, X_limbs);
253 :
254 31479 : return 0;
255 : }
256 :
257 0 : int mbedtls_mpi_core_write_le(const mbedtls_mpi_uint *A,
258 : size_t A_limbs,
259 : unsigned char *output,
260 : size_t output_length)
261 : {
262 0 : size_t stored_bytes = A_limbs * ciL;
263 : size_t bytes_to_copy;
264 :
265 0 : if (stored_bytes < output_length) {
266 0 : bytes_to_copy = stored_bytes;
267 : } else {
268 0 : bytes_to_copy = output_length;
269 :
270 : /* The output buffer is smaller than the allocated size of A.
271 : * However A may fit if its leading bytes are zero. */
272 0 : for (size_t i = bytes_to_copy; i < stored_bytes; i++) {
273 0 : if (GET_BYTE(A, i) != 0) {
274 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
275 : }
276 : }
277 : }
278 :
279 0 : for (size_t i = 0; i < bytes_to_copy; i++) {
280 0 : output[i] = GET_BYTE(A, i);
281 : }
282 :
283 0 : if (stored_bytes < output_length) {
284 : /* Write trailing 0 bytes */
285 0 : memset(output + stored_bytes, 0, output_length - stored_bytes);
286 : }
287 :
288 0 : return 0;
289 : }
290 :
291 1117 : int mbedtls_mpi_core_write_be(const mbedtls_mpi_uint *X,
292 : size_t X_limbs,
293 : unsigned char *output,
294 : size_t output_length)
295 : {
296 : size_t stored_bytes;
297 : size_t bytes_to_copy;
298 : unsigned char *p;
299 :
300 1117 : stored_bytes = X_limbs * ciL;
301 :
302 1117 : if (stored_bytes < output_length) {
303 : /* There is enough space in the output buffer. Write initial
304 : * null bytes and record the position at which to start
305 : * writing the significant bytes. In this case, the execution
306 : * trace of this function does not depend on the value of the
307 : * number. */
308 0 : bytes_to_copy = stored_bytes;
309 0 : p = output + output_length - stored_bytes;
310 0 : memset(output, 0, output_length - stored_bytes);
311 : } else {
312 : /* The output buffer is smaller than the allocated size of X.
313 : * However X may fit if its leading bytes are zero. */
314 1117 : bytes_to_copy = output_length;
315 1117 : p = output;
316 40630 : for (size_t i = bytes_to_copy; i < stored_bytes; i++) {
317 39513 : if (GET_BYTE(X, i) != 0) {
318 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
319 : }
320 : }
321 : }
322 :
323 189180 : for (size_t i = 0; i < bytes_to_copy; i++) {
324 188063 : p[bytes_to_copy - i - 1] = GET_BYTE(X, i);
325 : }
326 :
327 1117 : return 0;
328 : }
329 :
330 15955145 : void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs,
331 : size_t count)
332 : {
333 : size_t i, v0, v1;
334 15955145 : mbedtls_mpi_uint r0 = 0, r1;
335 :
336 15955145 : v0 = count / biL;
337 15955145 : v1 = count & (biL - 1);
338 :
339 15955145 : if (v0 > limbs || (v0 == limbs && v1 > 0)) {
340 0 : memset(X, 0, limbs * ciL);
341 0 : return;
342 : }
343 :
344 : /*
345 : * shift by count / limb_size
346 : */
347 15955145 : if (v0 > 0) {
348 47814 : for (i = 0; i < limbs - v0; i++) {
349 43891 : X[i] = X[i + v0];
350 : }
351 :
352 45685 : for (; i < limbs; i++) {
353 41762 : X[i] = 0;
354 : }
355 : }
356 :
357 : /*
358 : * shift by count % limb_size
359 : */
360 15955145 : if (v1 > 0) {
361 83275315 : for (i = limbs; i > 0; i--) {
362 69994748 : r1 = X[i - 1] << (biL - v1);
363 69994748 : X[i - 1] >>= v1;
364 69994748 : X[i - 1] |= r0;
365 69994748 : r0 = r1;
366 : }
367 : }
368 : }
369 :
370 2222245 : void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs,
371 : size_t count)
372 : {
373 : size_t i, v0, v1;
374 2222245 : mbedtls_mpi_uint r0 = 0, r1;
375 :
376 2222245 : v0 = count / (biL);
377 2222245 : v1 = count & (biL - 1);
378 :
379 : /*
380 : * shift by count / limb_size
381 : */
382 2222245 : if (v0 > 0) {
383 2276843 : for (i = limbs; i > v0; i--) {
384 2234628 : X[i - 1] = X[i - v0 - 1];
385 : }
386 :
387 842028 : for (; i > 0; i--) {
388 799813 : X[i - 1] = 0;
389 : }
390 : }
391 :
392 : /*
393 : * shift by count % limb_size
394 : */
395 2222245 : if (v1 > 0) {
396 21724436 : for (i = v0; i < limbs; i++) {
397 19557887 : r1 = X[i] >> (biL - v1);
398 19557887 : X[i] <<= v1;
399 19557887 : X[i] |= r0;
400 19557887 : r0 = r1;
401 : }
402 : }
403 2222245 : }
404 :
405 3968293 : mbedtls_mpi_uint mbedtls_mpi_core_add(mbedtls_mpi_uint *X,
406 : const mbedtls_mpi_uint *A,
407 : const mbedtls_mpi_uint *B,
408 : size_t limbs)
409 : {
410 3968293 : mbedtls_mpi_uint c = 0;
411 :
412 22865010 : for (size_t i = 0; i < limbs; i++) {
413 18896717 : mbedtls_mpi_uint t = c + A[i];
414 18896717 : c = (t < A[i]);
415 18896717 : t += B[i];
416 18896717 : c += (t < B[i]);
417 18896717 : X[i] = t;
418 : }
419 :
420 3968293 : return c;
421 : }
422 :
423 0 : mbedtls_mpi_uint mbedtls_mpi_core_add_if(mbedtls_mpi_uint *X,
424 : const mbedtls_mpi_uint *A,
425 : size_t limbs,
426 : unsigned cond)
427 : {
428 0 : mbedtls_mpi_uint c = 0;
429 :
430 0 : mbedtls_ct_condition_t do_add = mbedtls_ct_bool(cond);
431 :
432 0 : for (size_t i = 0; i < limbs; i++) {
433 0 : mbedtls_mpi_uint add = mbedtls_ct_mpi_uint_if_else_0(do_add, A[i]);
434 0 : mbedtls_mpi_uint t = c + X[i];
435 0 : c = (t < X[i]);
436 0 : t += add;
437 0 : c += (t < add);
438 0 : X[i] = t;
439 : }
440 :
441 0 : return c;
442 : }
443 :
444 20725295 : mbedtls_mpi_uint mbedtls_mpi_core_sub(mbedtls_mpi_uint *X,
445 : const mbedtls_mpi_uint *A,
446 : const mbedtls_mpi_uint *B,
447 : size_t limbs)
448 : {
449 20725295 : mbedtls_mpi_uint c = 0;
450 :
451 107903385 : for (size_t i = 0; i < limbs; i++) {
452 87178090 : mbedtls_mpi_uint z = (A[i] < c);
453 87178090 : mbedtls_mpi_uint t = A[i] - c;
454 87178090 : c = (t < B[i]) + z;
455 87178090 : X[i] = t - B[i];
456 : }
457 :
458 20725295 : return c;
459 : }
460 :
461 33278313 : mbedtls_mpi_uint mbedtls_mpi_core_mla(mbedtls_mpi_uint *d, size_t d_len,
462 : const mbedtls_mpi_uint *s, size_t s_len,
463 : mbedtls_mpi_uint b)
464 : {
465 33278313 : mbedtls_mpi_uint c = 0; /* carry */
466 : /*
467 : * It is a documented precondition of this function that d_len >= s_len.
468 : * If that's not the case, we swap these round: this turns what would be
469 : * a buffer overflow into an incorrect result.
470 : */
471 33278313 : if (d_len < s_len) {
472 0 : s_len = d_len;
473 : }
474 33278313 : size_t excess_len = d_len - s_len;
475 33278313 : size_t steps_x8 = s_len / 8;
476 33278313 : size_t steps_x1 = s_len & 7;
477 :
478 59730159 : while (steps_x8--) {
479 26451846 : MULADDC_X8_INIT
480 : MULADDC_X8_CORE
481 : MULADDC_X8_STOP
482 : }
483 :
484 137435395 : while (steps_x1--) {
485 104157082 : MULADDC_X1_INIT
486 : MULADDC_X1_CORE
487 : MULADDC_X1_STOP
488 : }
489 :
490 82516519 : while (excess_len--) {
491 49238206 : *d += c;
492 49238206 : c = (*d < c);
493 49238206 : d++;
494 : }
495 :
496 33278313 : return c;
497 : }
498 :
499 6325187 : void mbedtls_mpi_core_mul(mbedtls_mpi_uint *X,
500 : const mbedtls_mpi_uint *A, size_t A_limbs,
501 : const mbedtls_mpi_uint *B, size_t B_limbs)
502 : {
503 6325187 : memset(X, 0, (A_limbs + B_limbs) * ciL);
504 :
505 31567867 : for (size_t i = 0; i < B_limbs; i++) {
506 25242680 : (void) mbedtls_mpi_core_mla(X + i, A_limbs + 1, A, A_limbs, B[i]);
507 : }
508 6325187 : }
509 :
510 : /*
511 : * Fast Montgomery initialization (thanks to Tom St Denis).
512 : */
513 1046 : mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N)
514 : {
515 1046 : mbedtls_mpi_uint x = N[0];
516 :
517 1046 : x += ((N[0] + 2) & 4) << 1;
518 :
519 5230 : for (unsigned int i = biL; i >= 8; i /= 2) {
520 4184 : x *= (2 - (N[0] * x));
521 : }
522 :
523 1046 : return ~x + 1;
524 : }
525 :
526 169860 : void mbedtls_mpi_core_montmul(mbedtls_mpi_uint *X,
527 : const mbedtls_mpi_uint *A,
528 : const mbedtls_mpi_uint *B,
529 : size_t B_limbs,
530 : const mbedtls_mpi_uint *N,
531 : size_t AN_limbs,
532 : mbedtls_mpi_uint mm,
533 : mbedtls_mpi_uint *T)
534 : {
535 169860 : memset(T, 0, (2 * AN_limbs + 1) * ciL);
536 :
537 3886397 : for (size_t i = 0; i < AN_limbs; i++) {
538 : /* T = (T + u0*B + u1*N) / 2^biL */
539 3716537 : mbedtls_mpi_uint u0 = A[i];
540 3716537 : mbedtls_mpi_uint u1 = (T[0] + u0 * B[0]) * mm;
541 :
542 3716537 : (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, B, B_limbs, u0);
543 3716537 : (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, N, AN_limbs, u1);
544 :
545 3716537 : T++;
546 : }
547 :
548 : /*
549 : * The result we want is (T >= N) ? T - N : T.
550 : *
551 : * For better constant-time properties in this function, we always do the
552 : * subtraction, with the result in X.
553 : *
554 : * We also look to see if there was any carry in the final additions in the
555 : * loop above.
556 : */
557 :
558 169860 : mbedtls_mpi_uint carry = T[AN_limbs];
559 169860 : mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub(X, T, N, AN_limbs);
560 :
561 : /*
562 : * Using R as the Montgomery radix (auxiliary modulus) i.e. 2^(biL*AN_limbs):
563 : *
564 : * T can be in one of 3 ranges:
565 : *
566 : * 1) T < N : (carry, borrow) = (0, 1): we want T
567 : * 2) N <= T < R : (carry, borrow) = (0, 0): we want X
568 : * 3) T >= R : (carry, borrow) = (1, 1): we want X
569 : *
570 : * and (carry, borrow) = (1, 0) can't happen.
571 : *
572 : * So the correct return value is already in X if (carry ^ borrow) = 0,
573 : * but is in (the lower AN_limbs limbs of) T if (carry ^ borrow) = 1.
574 : */
575 169860 : mbedtls_ct_memcpy_if(mbedtls_ct_bool(carry ^ borrow),
576 : (unsigned char *) X,
577 : (unsigned char *) T,
578 : NULL,
579 : AN_limbs * sizeof(mbedtls_mpi_uint));
580 169860 : }
581 :
582 453 : int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X,
583 : const mbedtls_mpi *N)
584 : {
585 453 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
586 :
587 453 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1));
588 453 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, N->n * 2 * biL));
589 453 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
590 453 : MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(X, N->n));
591 :
592 453 : cleanup:
593 453 : return ret;
594 : }
595 :
596 : MBEDTLS_STATIC_TESTABLE
597 41456 : void mbedtls_mpi_core_ct_uint_table_lookup(mbedtls_mpi_uint *dest,
598 : const mbedtls_mpi_uint *table,
599 : size_t limbs,
600 : size_t count,
601 : size_t index)
602 : {
603 343920 : for (size_t i = 0; i < count; i++, table += limbs) {
604 302464 : mbedtls_ct_condition_t assign = mbedtls_ct_uint_eq(i, index);
605 302464 : mbedtls_mpi_core_cond_assign(dest, table, limbs, assign);
606 : }
607 41456 : }
608 :
609 : /* Fill X with n_bytes random bytes.
610 : * X must already have room for those bytes.
611 : * The ordering of the bytes returned from the RNG is suitable for
612 : * deterministic ECDSA (see RFC 6979 §3.3 and the specification of
613 : * mbedtls_mpi_core_random()).
614 : */
615 1396 : int mbedtls_mpi_core_fill_random(
616 : mbedtls_mpi_uint *X, size_t X_limbs,
617 : size_t n_bytes,
618 : int (*f_rng)(void *, unsigned char *, size_t), void *p_rng)
619 : {
620 1396 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
621 1396 : const size_t limbs = CHARS_TO_LIMBS(n_bytes);
622 1396 : const size_t overhead = (limbs * ciL) - n_bytes;
623 :
624 1396 : if (X_limbs < limbs) {
625 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
626 : }
627 :
628 1396 : memset(X, 0, overhead);
629 1396 : memset((unsigned char *) X + limbs * ciL, 0, (X_limbs - limbs) * ciL);
630 1396 : MBEDTLS_MPI_CHK(f_rng(p_rng, (unsigned char *) X + overhead, n_bytes));
631 1396 : mbedtls_mpi_core_bigendian_to_host(X, limbs);
632 :
633 1396 : cleanup:
634 1396 : return ret;
635 : }
636 :
637 1244 : int mbedtls_mpi_core_random(mbedtls_mpi_uint *X,
638 : mbedtls_mpi_uint min,
639 : const mbedtls_mpi_uint *N,
640 : size_t limbs,
641 : int (*f_rng)(void *, unsigned char *, size_t),
642 : void *p_rng)
643 : {
644 1244 : mbedtls_ct_condition_t ge_lower = MBEDTLS_CT_TRUE, lt_upper = MBEDTLS_CT_FALSE;
645 1244 : size_t n_bits = mbedtls_mpi_core_bitlen(N, limbs);
646 1244 : size_t n_bytes = (n_bits + 7) / 8;
647 1244 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
648 :
649 : /*
650 : * When min == 0, each try has at worst a probability 1/2 of failing
651 : * (the msb has a probability 1/2 of being 0, and then the result will
652 : * be < N), so after 30 tries failure probability is a most 2**(-30).
653 : *
654 : * When N is just below a power of 2, as is the case when generating
655 : * a random scalar on most elliptic curves, 1 try is enough with
656 : * overwhelming probability. When N is just above a power of 2,
657 : * as when generating a random scalar on secp224k1, each try has
658 : * a probability of failing that is almost 1/2.
659 : *
660 : * The probabilities are almost the same if min is nonzero but negligible
661 : * compared to N. This is always the case when N is crypto-sized, but
662 : * it's convenient to support small N for testing purposes. When N
663 : * is small, use a higher repeat count, otherwise the probability of
664 : * failure is macroscopic.
665 : */
666 1244 : int count = (n_bytes > 4 ? 30 : 250);
667 :
668 : /*
669 : * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
670 : * when f_rng is a suitably parametrized instance of HMAC_DRBG:
671 : * - use the same byte ordering;
672 : * - keep the leftmost n_bits bits of the generated octet string;
673 : * - try until result is in the desired range.
674 : * This also avoids any bias, which is especially important for ECDSA.
675 : */
676 : do {
677 1244 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_fill_random(X, limbs,
678 : n_bytes,
679 : f_rng, p_rng));
680 1244 : mbedtls_mpi_core_shift_r(X, limbs, 8 * n_bytes - n_bits);
681 :
682 1244 : if (--count == 0) {
683 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
684 0 : goto cleanup;
685 : }
686 :
687 1244 : ge_lower = mbedtls_mpi_core_uint_le_mpi(min, X, limbs);
688 1244 : lt_upper = mbedtls_mpi_core_lt_ct(X, N, limbs);
689 1244 : } while (mbedtls_ct_bool_and(ge_lower, lt_upper) == MBEDTLS_CT_FALSE);
690 :
691 1244 : cleanup:
692 1244 : return ret;
693 : }
694 :
695 1008 : static size_t exp_mod_get_window_size(size_t Ebits)
696 : {
697 : #if MBEDTLS_MPI_WINDOW_SIZE >= 6
698 : return (Ebits > 671) ? 6 : (Ebits > 239) ? 5 : (Ebits > 79) ? 4 : 1;
699 : #elif MBEDTLS_MPI_WINDOW_SIZE == 5
700 : return (Ebits > 239) ? 5 : (Ebits > 79) ? 4 : 1;
701 : #elif MBEDTLS_MPI_WINDOW_SIZE > 1
702 1008 : return (Ebits > 79) ? MBEDTLS_MPI_WINDOW_SIZE : 1;
703 : #else
704 : (void) Ebits;
705 : return 1;
706 : #endif
707 : }
708 :
709 504 : size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs)
710 : {
711 504 : const size_t wsize = exp_mod_get_window_size(E_limbs * biL);
712 504 : const size_t welem = ((size_t) 1) << wsize;
713 :
714 : /* How big does each part of the working memory pool need to be? */
715 504 : const size_t table_limbs = welem * AN_limbs;
716 504 : const size_t select_limbs = AN_limbs;
717 504 : const size_t temp_limbs = 2 * AN_limbs + 1;
718 :
719 504 : return table_limbs + select_limbs + temp_limbs;
720 : }
721 :
722 504 : static void exp_mod_precompute_window(const mbedtls_mpi_uint *A,
723 : const mbedtls_mpi_uint *N,
724 : size_t AN_limbs,
725 : mbedtls_mpi_uint mm,
726 : const mbedtls_mpi_uint *RR,
727 : size_t welem,
728 : mbedtls_mpi_uint *Wtable,
729 : mbedtls_mpi_uint *temp)
730 : {
731 : /* W[0] = 1 (in Montgomery presentation) */
732 504 : memset(Wtable, 0, AN_limbs * ciL);
733 504 : Wtable[0] = 1;
734 504 : mbedtls_mpi_core_montmul(Wtable, Wtable, RR, AN_limbs, N, AN_limbs, mm, temp);
735 :
736 : /* W[1] = A (already in Montgomery presentation) */
737 504 : mbedtls_mpi_uint *W1 = Wtable + AN_limbs;
738 504 : memcpy(W1, A, AN_limbs * ciL);
739 :
740 : /* W[i+1] = W[i] * W[1], i >= 2 */
741 504 : mbedtls_mpi_uint *Wprev = W1;
742 996 : for (size_t i = 2; i < welem; i++) {
743 492 : mbedtls_mpi_uint *Wcur = Wprev + AN_limbs;
744 492 : mbedtls_mpi_core_montmul(Wcur, Wprev, W1, AN_limbs, N, AN_limbs, mm, temp);
745 492 : Wprev = Wcur;
746 : }
747 504 : }
748 :
749 : #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
750 : // Set to a default that is neither MBEDTLS_MPI_IS_PUBLIC nor MBEDTLS_MPI_IS_SECRET
751 : int mbedtls_mpi_optionally_safe_codepath = MBEDTLS_MPI_IS_PUBLIC + MBEDTLS_MPI_IS_SECRET + 1;
752 : #endif
753 :
754 : /*
755 : * This function calculates the indices of the exponent where the exponentiation algorithm should
756 : * start processing.
757 : *
758 : * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value,
759 : * this function is not constant time with respect to the exponent (parameter E).
760 : */
761 504 : static inline void exp_mod_calc_first_bit_optionally_safe(const mbedtls_mpi_uint *E,
762 : size_t E_limbs,
763 : int E_public,
764 : size_t *E_limb_index,
765 : size_t *E_bit_index)
766 : {
767 504 : if (E_public == MBEDTLS_MPI_IS_PUBLIC) {
768 : /*
769 : * Skip leading zero bits.
770 : */
771 346 : size_t E_bits = mbedtls_mpi_core_bitlen(E, E_limbs);
772 346 : if (E_bits == 0) {
773 : /*
774 : * If E is 0 mbedtls_mpi_core_bitlen() returns 0. Even if that is the case, we will want
775 : * to represent it as a single 0 bit and as such the bitlength will be 1.
776 : */
777 0 : E_bits = 1;
778 : }
779 :
780 346 : *E_limb_index = E_bits / biL;
781 346 : *E_bit_index = E_bits % biL;
782 :
783 : #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
784 : mbedtls_mpi_optionally_safe_codepath = MBEDTLS_MPI_IS_PUBLIC;
785 : #endif
786 : } else {
787 : /*
788 : * Here we need to be constant time with respect to E and can't do anything better than
789 : * start at the first allocated bit.
790 : */
791 158 : *E_limb_index = E_limbs;
792 158 : *E_bit_index = 0;
793 : #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
794 : // Only mark the codepath safe if there wasn't an unsafe codepath before
795 : if (mbedtls_mpi_optionally_safe_codepath != MBEDTLS_MPI_IS_PUBLIC) {
796 : mbedtls_mpi_optionally_safe_codepath = MBEDTLS_MPI_IS_SECRET;
797 : }
798 : #endif
799 : }
800 504 : }
801 :
802 : /*
803 : * Warning! If the parameter window_public has MBEDTLS_MPI_IS_PUBLIC as its value, this function is
804 : * not constant time with respect to the window parameter and consequently the exponent of the
805 : * exponentiation (parameter E of mbedtls_mpi_core_exp_mod_optionally_safe).
806 : */
807 47338 : static inline void exp_mod_table_lookup_optionally_safe(mbedtls_mpi_uint *Wselect,
808 : mbedtls_mpi_uint *Wtable,
809 : size_t AN_limbs, size_t welem,
810 : mbedtls_mpi_uint window,
811 : int window_public)
812 : {
813 47338 : if (window_public == MBEDTLS_MPI_IS_PUBLIC) {
814 5882 : memcpy(Wselect, Wtable + window * AN_limbs, AN_limbs * ciL);
815 : #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
816 : mbedtls_mpi_optionally_safe_codepath = MBEDTLS_MPI_IS_PUBLIC;
817 : #endif
818 : } else {
819 : /* Select Wtable[window] without leaking window through
820 : * memory access patterns. */
821 41456 : mbedtls_mpi_core_ct_uint_table_lookup(Wselect, Wtable,
822 : AN_limbs, welem, window);
823 : #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
824 : // Only mark the codepath safe if there wasn't an unsafe codepath before
825 : if (mbedtls_mpi_optionally_safe_codepath != MBEDTLS_MPI_IS_PUBLIC) {
826 : mbedtls_mpi_optionally_safe_codepath = MBEDTLS_MPI_IS_SECRET;
827 : }
828 : #endif
829 : }
830 47338 : }
831 :
832 : /* Exponentiation: X := A^E mod N.
833 : *
834 : * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value,
835 : * this function is not constant time with respect to the exponent (parameter E).
836 : *
837 : * A must already be in Montgomery form.
838 : *
839 : * As in other bignum functions, assume that AN_limbs and E_limbs are nonzero.
840 : *
841 : * RR must contain 2^{2*biL} mod N.
842 : *
843 : * The algorithm is a variant of Left-to-right k-ary exponentiation: HAC 14.82
844 : * (The difference is that the body in our loop processes a single bit instead
845 : * of a full window.)
846 : */
847 504 : static void mbedtls_mpi_core_exp_mod_optionally_safe(mbedtls_mpi_uint *X,
848 : const mbedtls_mpi_uint *A,
849 : const mbedtls_mpi_uint *N,
850 : size_t AN_limbs,
851 : const mbedtls_mpi_uint *E,
852 : size_t E_limbs,
853 : int E_public,
854 : const mbedtls_mpi_uint *RR,
855 : mbedtls_mpi_uint *T)
856 : {
857 : /* We'll process the bits of E from most significant
858 : * (limb_index=E_limbs-1, E_bit_index=biL-1) to least significant
859 : * (limb_index=0, E_bit_index=0). */
860 : size_t E_limb_index;
861 : size_t E_bit_index;
862 504 : exp_mod_calc_first_bit_optionally_safe(E, E_limbs, E_public,
863 : &E_limb_index, &E_bit_index);
864 :
865 504 : const size_t wsize = exp_mod_get_window_size(E_limb_index * biL);
866 504 : const size_t welem = ((size_t) 1) << wsize;
867 :
868 : /* This is how we will use the temporary storage T, which must have space
869 : * for table_limbs, select_limbs and (2 * AN_limbs + 1) for montmul. */
870 504 : const size_t table_limbs = welem * AN_limbs;
871 504 : const size_t select_limbs = AN_limbs;
872 :
873 : /* Pointers to specific parts of the temporary working memory pool */
874 504 : mbedtls_mpi_uint *const Wtable = T;
875 504 : mbedtls_mpi_uint *const Wselect = Wtable + table_limbs;
876 504 : mbedtls_mpi_uint *const temp = Wselect + select_limbs;
877 :
878 : /*
879 : * Window precomputation
880 : */
881 :
882 504 : const mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N);
883 :
884 : /* Set Wtable[i] = A^i (in Montgomery representation) */
885 504 : exp_mod_precompute_window(A, N, AN_limbs,
886 : mm, RR,
887 : welem, Wtable, temp);
888 :
889 : /*
890 : * Fixed window exponentiation
891 : */
892 :
893 : /* X = 1 (in Montgomery presentation) initially */
894 504 : memcpy(X, Wtable, AN_limbs * ciL);
895 :
896 : /* At any given time, window contains window_bits bits from E.
897 : * window_bits can go up to wsize. */
898 504 : size_t window_bits = 0;
899 504 : mbedtls_mpi_uint window = 0;
900 :
901 : do {
902 : /* Square */
903 120442 : mbedtls_mpi_core_montmul(X, X, X, AN_limbs, N, AN_limbs, mm, temp);
904 :
905 : /* Move to the next bit of the exponent */
906 120442 : if (E_bit_index == 0) {
907 1790 : --E_limb_index;
908 1790 : E_bit_index = biL - 1;
909 : } else {
910 118652 : --E_bit_index;
911 : }
912 : /* Insert next exponent bit into window */
913 120442 : ++window_bits;
914 120442 : window <<= 1;
915 120442 : window |= (E[E_limb_index] >> E_bit_index) & 1;
916 :
917 : /* Clear window if it's full. Also clear the window at the end,
918 : * when we've finished processing the exponent. */
919 120442 : if (window_bits == wsize ||
920 73184 : (E_bit_index == 0 && E_limb_index == 0)) {
921 :
922 47338 : exp_mod_table_lookup_optionally_safe(Wselect, Wtable, AN_limbs, welem,
923 : window, E_public);
924 : /* Multiply X by the selected element. */
925 47338 : mbedtls_mpi_core_montmul(X, X, Wselect, AN_limbs, N, AN_limbs, mm,
926 : temp);
927 47338 : window = 0;
928 47338 : window_bits = 0;
929 : }
930 120442 : } while (!(E_bit_index == 0 && E_limb_index == 0));
931 504 : }
932 :
933 158 : void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X,
934 : const mbedtls_mpi_uint *A,
935 : const mbedtls_mpi_uint *N, size_t AN_limbs,
936 : const mbedtls_mpi_uint *E, size_t E_limbs,
937 : const mbedtls_mpi_uint *RR,
938 : mbedtls_mpi_uint *T)
939 : {
940 158 : mbedtls_mpi_core_exp_mod_optionally_safe(X,
941 : A,
942 : N,
943 : AN_limbs,
944 : E,
945 : E_limbs,
946 : MBEDTLS_MPI_IS_SECRET,
947 : RR,
948 : T);
949 158 : }
950 :
951 346 : void mbedtls_mpi_core_exp_mod_unsafe(mbedtls_mpi_uint *X,
952 : const mbedtls_mpi_uint *A,
953 : const mbedtls_mpi_uint *N, size_t AN_limbs,
954 : const mbedtls_mpi_uint *E, size_t E_limbs,
955 : const mbedtls_mpi_uint *RR,
956 : mbedtls_mpi_uint *T)
957 : {
958 346 : mbedtls_mpi_core_exp_mod_optionally_safe(X,
959 : A,
960 : N,
961 : AN_limbs,
962 : E,
963 : E_limbs,
964 : MBEDTLS_MPI_IS_PUBLIC,
965 : RR,
966 : T);
967 346 : }
968 :
969 4508045 : mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X,
970 : const mbedtls_mpi_uint *A,
971 : mbedtls_mpi_uint c, /* doubles as carry */
972 : size_t limbs)
973 : {
974 25496584 : for (size_t i = 0; i < limbs; i++) {
975 20988539 : mbedtls_mpi_uint s = A[i];
976 20988539 : mbedtls_mpi_uint t = s - c;
977 20988539 : c = (t > s);
978 20988539 : X[i] = t;
979 : }
980 :
981 4508045 : return c;
982 : }
983 :
984 0 : mbedtls_ct_condition_t mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A,
985 : size_t limbs)
986 : {
987 0 : volatile const mbedtls_mpi_uint *force_read_A = A;
988 0 : mbedtls_mpi_uint bits = 0;
989 :
990 0 : for (size_t i = 0; i < limbs; i++) {
991 0 : bits |= force_read_A[i];
992 : }
993 :
994 0 : return mbedtls_ct_bool(bits);
995 : }
996 :
997 542 : void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X,
998 : const mbedtls_mpi_uint *A,
999 : const mbedtls_mpi_uint *N,
1000 : size_t AN_limbs,
1001 : mbedtls_mpi_uint mm,
1002 : const mbedtls_mpi_uint *rr,
1003 : mbedtls_mpi_uint *T)
1004 : {
1005 542 : mbedtls_mpi_core_montmul(X, A, rr, AN_limbs, N, AN_limbs, mm, T);
1006 542 : }
1007 :
1008 504 : void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X,
1009 : const mbedtls_mpi_uint *A,
1010 : const mbedtls_mpi_uint *N,
1011 : size_t AN_limbs,
1012 : mbedtls_mpi_uint mm,
1013 : mbedtls_mpi_uint *T)
1014 : {
1015 504 : const mbedtls_mpi_uint Rinv = 1; /* 1/R in Mont. rep => 1 */
1016 :
1017 504 : mbedtls_mpi_core_montmul(X, A, &Rinv, 1, N, AN_limbs, mm, T);
1018 504 : }
1019 :
1020 : #endif /* MBEDTLS_BIGNUM_C */
|
