Coverage Report

Created: 2024-11-21 06:47

/src/mbedtls/library/bignum_core.c
Line
Count
Source (jump to first uncovered line)
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
size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a)
25
147M
{
26
147M
#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
147M
    #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
147M
#endif
35
147M
#if defined(core_clz)
36
147M
    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
147M
}
52
53
size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs)
54
148M
{
55
148M
    int i;
56
148M
    size_t j;
57
58
2.04G
    for (i = ((int) A_limbs) - 1; i >= 0; i--) {
59
2.04G
        if (A[i] != 0) {
60
147M
            j = biL - mbedtls_mpi_core_clz(A[i]);
61
147M
            return (i * biL) + j;
62
147M
        }
63
2.04G
    }
64
65
1.05M
    return 0;
66
148M
}
67
68
static mbedtls_mpi_uint mpi_bigendian_to_host(mbedtls_mpi_uint a)
69
0
{
70
0
    if (MBEDTLS_IS_BIG_ENDIAN) {
71
        /* Nothing to do on bigendian systems. */
72
0
        return a;
73
0
    } else {
74
#if defined(MBEDTLS_HAVE_INT32)
75
        return (mbedtls_mpi_uint) MBEDTLS_BSWAP32(a);
76
#elif defined(MBEDTLS_HAVE_INT64)
77
0
        return (mbedtls_mpi_uint) MBEDTLS_BSWAP64(a);
78
0
#endif
79
0
    }
80
0
}
81
82
void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A,
83
                                        size_t A_limbs)
84
0
{
85
0
    mbedtls_mpi_uint *cur_limb_left;
86
0
    mbedtls_mpi_uint *cur_limb_right;
87
0
    if (A_limbs == 0) {
88
0
        return;
89
0
    }
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
0
    for (cur_limb_left = A, cur_limb_right = A + (A_limbs - 1);
101
0
         cur_limb_left <= cur_limb_right;
102
0
         cur_limb_left++, cur_limb_right--) {
103
0
        mbedtls_mpi_uint tmp;
104
        /* Note that if cur_limb_left == cur_limb_right,
105
         * this code effectively swaps the bytes only once. */
106
0
        tmp             = mpi_bigendian_to_host(*cur_limb_left);
107
0
        *cur_limb_left  = mpi_bigendian_to_host(*cur_limb_right);
108
0
        *cur_limb_right = tmp;
109
0
    }
110
0
}
111
112
/* Whether min <= A, in constant time.
113
 * A_limbs must be at least 1. */
114
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
0
{
118
    /* min <= least significant limb? */
119
0
    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
0
    mbedtls_ct_condition_t msll_mask = MBEDTLS_CT_FALSE;
123
0
    for (size_t i = 1; i < A_limbs; i++) {
124
0
        msll_mask = mbedtls_ct_bool_or(msll_mask, mbedtls_ct_bool(A[i]));
125
0
    }
126
127
    /* min <= A iff the lowest limb of A is >= min or the other limbs
128
     * are not all zero. */
129
0
    return mbedtls_ct_bool_or(msll_mask, min_le_lsl);
130
0
}
131
132
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
0
{
136
0
    mbedtls_ct_condition_t ret = MBEDTLS_CT_FALSE, cond = MBEDTLS_CT_FALSE, done = MBEDTLS_CT_FALSE;
137
138
0
    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
0
        cond = mbedtls_ct_uint_lt(B[i - 1], A[i - 1]);
147
0
        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
0
        cond = mbedtls_ct_uint_lt(A[i - 1], B[i - 1]);
156
0
        ret  = mbedtls_ct_bool_or(ret, mbedtls_ct_bool_and(cond, mbedtls_ct_bool_not(done)));
157
0
        done = mbedtls_ct_bool_or(done, cond);
158
0
    }
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
0
    return ret;
166
0
}
167
168
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
549k
{
173
549k
    if (X == A) {
174
0
        return;
175
0
    }
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
3.34M
    for (size_t i = 0; i < limbs; i++) {
183
2.80M
        X[i] = mbedtls_ct_mpi_uint_if(assign, A[i], X[i]);
184
2.80M
    }
185
549k
}
186
187
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
0
{
192
0
    if (X == Y) {
193
0
        return;
194
0
    }
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
0
    }
201
0
}
202
203
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
0
{
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
0
    }
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
0
        }
221
0
    }
222
223
0
    return 0;
224
0
}
225
226
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
0
{
231
0
    const size_t limbs = CHARS_TO_LIMBS(input_length);
232
233
0
    if (X_limbs < limbs) {
234
0
        return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
235
0
    }
236
237
    /* If X_limbs is 0, input_length must also be 0 (from previous test).
238
     * Nothing to do. */
239
0
    if (X_limbs == 0) {
240
0
        return 0;
241
0
    }
242
243
0
    memset(X, 0, X_limbs * ciL);
244
245
    /* memcpy() with (NULL, 0) is undefined behaviour */
246
0
    if (input_length != 0) {
247
0
        size_t overhead = (X_limbs * ciL) - input_length;
248
0
        unsigned char *Xp = (unsigned char *) X;
249
0
        memcpy(Xp + overhead, input, input_length);
250
0
    }
251
252
0
    mbedtls_mpi_core_bigendian_to_host(X, X_limbs);
253
254
0
    return 0;
255
0
}
256
257
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
0
{
262
0
    size_t stored_bytes = A_limbs * ciL;
263
0
    size_t bytes_to_copy;
264
265
0
    if (stored_bytes < output_length) {
266
0
        bytes_to_copy = stored_bytes;
267
0
    } 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
0
            }
276
0
        }
277
0
    }
278
279
0
    for (size_t i = 0; i < bytes_to_copy; i++) {
280
0
        output[i] = GET_BYTE(A, i);
281
0
    }
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
0
    }
287
288
0
    return 0;
289
0
}
290
291
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
0
{
296
0
    size_t stored_bytes;
297
0
    size_t bytes_to_copy;
298
0
    unsigned char *p;
299
300
0
    stored_bytes = X_limbs * ciL;
301
302
0
    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
0
    } 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
0
        bytes_to_copy = output_length;
315
0
        p = output;
316
0
        for (size_t i = bytes_to_copy; i < stored_bytes; i++) {
317
0
            if (GET_BYTE(X, i) != 0) {
318
0
                return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
319
0
            }
320
0
        }
321
0
    }
322
323
0
    for (size_t i = 0; i < bytes_to_copy; i++) {
324
0
        p[bytes_to_copy - i - 1] = GET_BYTE(X, i);
325
0
    }
326
327
0
    return 0;
328
0
}
329
330
void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs,
331
                              size_t count)
332
20.3M
{
333
20.3M
    size_t i, v0, v1;
334
20.3M
    mbedtls_mpi_uint r0 = 0, r1;
335
336
20.3M
    v0 = count /  biL;
337
20.3M
    v1 = count & (biL - 1);
338
339
20.3M
    if (v0 > limbs || (v0 == limbs && v1 > 0)) {
340
0
        memset(X, 0, limbs * ciL);
341
0
        return;
342
0
    }
343
344
    /*
345
     * shift by count / limb_size
346
     */
347
20.3M
    if (v0 > 0) {
348
39.1M
        for (i = 0; i < limbs - v0; i++) {
349
19.6M
            X[i] = X[i + v0];
350
19.6M
        }
351
352
88.9M
        for (; i < limbs; i++) {
353
69.3M
            X[i] = 0;
354
69.3M
        }
355
19.5M
    }
356
357
    /*
358
     * shift by count % limb_size
359
     */
360
20.3M
    if (v1 > 0) {
361
2.14M
        for (i = limbs; i > 0; i--) {
362
1.79M
            r1 = X[i - 1] << (biL - v1);
363
1.79M
            X[i - 1] >>= v1;
364
1.79M
            X[i - 1] |= r0;
365
1.79M
            r0 = r1;
366
1.79M
        }
367
349k
    }
368
20.3M
}
369
370
void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs,
371
                              size_t count)
372
128M
{
373
128M
    size_t i, v0, v1;
374
128M
    mbedtls_mpi_uint r0 = 0, r1;
375
376
128M
    v0 = count / (biL);
377
128M
    v1 = count & (biL - 1);
378
379
    /*
380
     * shift by count / limb_size
381
     */
382
128M
    if (v0 > 0) {
383
1.35G
        for (i = limbs; i > v0; i--) {
384
1.28G
            X[i - 1] = X[i - v0 - 1];
385
1.28G
        }
386
387
736M
        for (; i > 0; i--) {
388
667M
            X[i - 1] = 0;
389
667M
        }
390
69.3M
    }
391
392
    /*
393
     * shift by count % limb_size
394
     */
395
128M
    if (v1 > 0) {
396
148M
        for (i = v0; i < limbs; i++) {
397
108M
            r1 = X[i] >> (biL - v1);
398
108M
            X[i] <<= v1;
399
108M
            X[i] |= r0;
400
108M
            r0 = r1;
401
108M
        }
402
39.3M
    }
403
128M
}
404
405
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
6.34M
{
410
6.34M
    mbedtls_mpi_uint c = 0;
411
412
12.6M
    for (size_t i = 0; i < limbs; i++) {
413
6.35M
        mbedtls_mpi_uint t = c + A[i];
414
6.35M
        c = (t < A[i]);
415
6.35M
        t += B[i];
416
6.35M
        c += (t < B[i]);
417
6.35M
        X[i] = t;
418
6.35M
    }
419
420
6.34M
    return c;
421
6.34M
}
422
423
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
0
{
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
0
    }
440
441
0
    return c;
442
0
}
443
444
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
70.6M
{
449
70.6M
    mbedtls_mpi_uint c = 0;
450
451
799M
    for (size_t i = 0; i < limbs; i++) {
452
729M
        mbedtls_mpi_uint z = (A[i] < c);
453
729M
        mbedtls_mpi_uint t = A[i] - c;
454
729M
        c = (t < B[i]) + z;
455
729M
        X[i] = t - B[i];
456
729M
    }
457
458
70.6M
    return c;
459
70.6M
}
460
461
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
155M
{
465
155M
    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
155M
    if (d_len < s_len) {
472
0
        s_len = d_len;
473
0
    }
474
155M
    size_t excess_len = d_len - s_len;
475
155M
    size_t steps_x8 = s_len / 8;
476
155M
    size_t steps_x1 = s_len & 7;
477
478
156M
    while (steps_x8--) {
479
279k
        MULADDC_X8_INIT
480
279k
        MULADDC_X8_CORE
481
279k
            MULADDC_X8_STOP
482
279k
    }
483
484
423M
    while (steps_x1--) {
485
268M
        MULADDC_X1_INIT
486
268M
        MULADDC_X1_CORE
487
268M
            MULADDC_X1_STOP
488
268M
    }
489
490
3.80G
    while (excess_len--) {
491
3.64G
        *d += c;
492
3.64G
        c = (*d < c);
493
3.64G
        d++;
494
3.64G
    }
495
496
155M
    return c;
497
155M
}
498
499
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
54.0k
{
503
54.0k
    memset(X, 0, (A_limbs + B_limbs) * ciL);
504
505
125k
    for (size_t i = 0; i < B_limbs; i++) {
506
71.1k
        (void) mbedtls_mpi_core_mla(X + i, A_limbs + 1, A, A_limbs, B[i]);
507
71.1k
    }
508
54.0k
}
509
510
/*
511
 * Fast Montgomery initialization (thanks to Tom St Denis).
512
 */
513
mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N)
514
1.49k
{
515
1.49k
    mbedtls_mpi_uint x = N[0];
516
517
1.49k
    x += ((N[0] + 2) & 4) << 1;
518
519
7.45k
    for (unsigned int i = biL; i >= 8; i /= 2) {
520
5.96k
        x *= (2 - (N[0] * x));
521
5.96k
    }
522
523
1.49k
    return ~x + 1;
524
1.49k
}
525
526
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
287k
{
535
287k
    memset(T, 0, (2 * AN_limbs + 1) * ciL);
536
537
1.75M
    for (size_t i = 0; i < AN_limbs; i++) {
538
        /* T = (T + u0*B + u1*N) / 2^biL */
539
1.46M
        mbedtls_mpi_uint u0 = A[i];
540
1.46M
        mbedtls_mpi_uint u1 = (T[0] + u0 * B[0]) * mm;
541
542
1.46M
        (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, B, B_limbs, u0);
543
1.46M
        (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, N, AN_limbs, u1);
544
545
1.46M
        T++;
546
1.46M
    }
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
287k
    mbedtls_mpi_uint carry  = T[AN_limbs];
559
287k
    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
287k
    mbedtls_ct_memcpy_if(mbedtls_ct_bool(carry ^ borrow),
576
287k
                         (unsigned char *) X,
577
287k
                         (unsigned char *) T,
578
287k
                         NULL,
579
287k
                         AN_limbs * sizeof(mbedtls_mpi_uint));
580
287k
}
581
582
int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X,
583
                                        const mbedtls_mpi *N)
584
745
{
585
745
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
586
587
745
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1));
588
745
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, N->n * 2 * biL));
589
745
    MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
590
745
    MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(X, N->n));
591
592
745
cleanup:
593
745
    return ret;
594
745
}
595
596
MBEDTLS_STATIC_TESTABLE
597
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
74.5k
{
603
623k
    for (size_t i = 0; i < count; i++, table += limbs) {
604
549k
        mbedtls_ct_condition_t assign = mbedtls_ct_uint_eq(i, index);
605
549k
        mbedtls_mpi_core_cond_assign(dest, table, limbs, assign);
606
549k
    }
607
74.5k
}
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
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
0
{
620
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
621
0
    const size_t limbs = CHARS_TO_LIMBS(n_bytes);
622
0
    const size_t overhead = (limbs * ciL) - n_bytes;
623
624
0
    if (X_limbs < limbs) {
625
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
626
0
    }
627
628
0
    memset(X, 0, overhead);
629
0
    memset((unsigned char *) X + limbs * ciL, 0, (X_limbs - limbs) * ciL);
630
0
    MBEDTLS_MPI_CHK(f_rng(p_rng, (unsigned char *) X + overhead, n_bytes));
631
0
    mbedtls_mpi_core_bigendian_to_host(X, limbs);
632
633
0
cleanup:
634
0
    return ret;
635
0
}
636
637
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
0
{
644
0
    mbedtls_ct_condition_t ge_lower = MBEDTLS_CT_TRUE, lt_upper = MBEDTLS_CT_FALSE;
645
0
    size_t n_bits = mbedtls_mpi_core_bitlen(N, limbs);
646
0
    size_t n_bytes = (n_bits + 7) / 8;
647
0
    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
0
    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
0
    do {
677
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_core_fill_random(X, limbs,
678
0
                                                     n_bytes,
679
0
                                                     f_rng, p_rng));
680
0
        mbedtls_mpi_core_shift_r(X, limbs, 8 * n_bytes - n_bits);
681
682
0
        if (--count == 0) {
683
0
            ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
684
0
            goto cleanup;
685
0
        }
686
687
0
        ge_lower = mbedtls_mpi_core_uint_le_mpi(min, X, limbs);
688
0
        lt_upper = mbedtls_mpi_core_lt_ct(X, N, limbs);
689
0
    } while (mbedtls_ct_bool_and(ge_lower, lt_upper) == MBEDTLS_CT_FALSE);
690
691
0
cleanup:
692
0
    return ret;
693
0
}
694
695
static size_t exp_mod_get_window_size(size_t Ebits)
696
1.49k
{
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
1.49k
    return (Ebits >  79) ? MBEDTLS_MPI_WINDOW_SIZE : 1;
703
#else
704
    (void) Ebits;
705
    return 1;
706
#endif
707
1.49k
}
708
709
size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs)
710
745
{
711
745
    const size_t wsize = exp_mod_get_window_size(E_limbs * biL);
712
745
    const size_t welem = ((size_t) 1) << wsize;
713
714
    /* How big does each part of the working memory pool need to be? */
715
745
    const size_t table_limbs   = welem * AN_limbs;
716
745
    const size_t select_limbs  = AN_limbs;
717
745
    const size_t temp_limbs    = 2 * AN_limbs + 1;
718
719
745
    return table_limbs + select_limbs + temp_limbs;
720
745
}
721
722
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
745
{
731
    /* W[0] = 1 (in Montgomery presentation) */
732
745
    memset(Wtable, 0, AN_limbs * ciL);
733
745
    Wtable[0] = 1;
734
745
    mbedtls_mpi_core_montmul(Wtable, Wtable, RR, AN_limbs, N, AN_limbs, mm, temp);
735
736
    /* W[1] = A (already in Montgomery presentation) */
737
745
    mbedtls_mpi_uint *W1 = Wtable + AN_limbs;
738
745
    memcpy(W1, A, AN_limbs * ciL);
739
740
    /* W[i+1] = W[i] * W[1], i >= 2 */
741
745
    mbedtls_mpi_uint *Wprev = W1;
742
4.48k
    for (size_t i = 2; i < welem; i++) {
743
3.73k
        mbedtls_mpi_uint *Wcur = Wprev + AN_limbs;
744
3.73k
        mbedtls_mpi_core_montmul(Wcur, Wprev, W1, AN_limbs, N, AN_limbs, mm, temp);
745
3.73k
        Wprev = Wcur;
746
3.73k
    }
747
745
}
748
749
#if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
750
void (*mbedtls_safe_codepath_hook)(void) = NULL;
751
void (*mbedtls_unsafe_codepath_hook)(void) = NULL;
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
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
745
{
767
745
    if (E_public == MBEDTLS_MPI_IS_PUBLIC) {
768
        /*
769
         * Skip leading zero bits.
770
         */
771
0
        size_t E_bits = mbedtls_mpi_core_bitlen(E, E_limbs);
772
0
        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
0
        }
779
780
0
        *E_limb_index = E_bits / biL;
781
0
        *E_bit_index = E_bits % biL;
782
783
#if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
784
        if (mbedtls_unsafe_codepath_hook != NULL) {
785
            mbedtls_unsafe_codepath_hook();
786
        }
787
#endif
788
745
    } else {
789
        /*
790
         * Here we need to be constant time with respect to E and can't do anything better than
791
         * start at the first allocated bit.
792
         */
793
745
        *E_limb_index = E_limbs;
794
745
        *E_bit_index = 0;
795
#if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
796
        if (mbedtls_safe_codepath_hook != NULL) {
797
            mbedtls_safe_codepath_hook();
798
        }
799
#endif
800
745
    }
801
745
}
802
803
/*
804
 * Warning! If the parameter window_public has MBEDTLS_MPI_IS_PUBLIC as its value, this function is
805
 * not constant time with respect to the window parameter and consequently the exponent of the
806
 * exponentiation (parameter E of mbedtls_mpi_core_exp_mod_optionally_safe).
807
 */
808
static inline void exp_mod_table_lookup_optionally_safe(mbedtls_mpi_uint *Wselect,
809
                                                        mbedtls_mpi_uint *Wtable,
810
                                                        size_t AN_limbs, size_t welem,
811
                                                        mbedtls_mpi_uint window,
812
                                                        int window_public)
813
74.5k
{
814
74.5k
    if (window_public == MBEDTLS_MPI_IS_PUBLIC) {
815
0
        memcpy(Wselect, Wtable + window * AN_limbs, AN_limbs * ciL);
816
#if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
817
        if (mbedtls_unsafe_codepath_hook != NULL) {
818
            mbedtls_unsafe_codepath_hook();
819
        }
820
#endif
821
74.5k
    } else {
822
        /* Select Wtable[window] without leaking window through
823
         * memory access patterns. */
824
74.5k
        mbedtls_mpi_core_ct_uint_table_lookup(Wselect, Wtable,
825
74.5k
                                              AN_limbs, welem, window);
826
#if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
827
        if (mbedtls_safe_codepath_hook != NULL) {
828
            mbedtls_safe_codepath_hook();
829
        }
830
#endif
831
74.5k
    }
832
74.5k
}
833
834
/* Exponentiation: X := A^E mod N.
835
 *
836
 * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value,
837
 * this function is not constant time with respect to the exponent (parameter E).
838
 *
839
 * A must already be in Montgomery form.
840
 *
841
 * As in other bignum functions, assume that AN_limbs and E_limbs are nonzero.
842
 *
843
 * RR must contain 2^{2*biL} mod N.
844
 *
845
 * The algorithm is a variant of Left-to-right k-ary exponentiation: HAC 14.82
846
 * (The difference is that the body in our loop processes a single bit instead
847
 * of a full window.)
848
 */
849
static void mbedtls_mpi_core_exp_mod_optionally_safe(mbedtls_mpi_uint *X,
850
                                                     const mbedtls_mpi_uint *A,
851
                                                     const mbedtls_mpi_uint *N,
852
                                                     size_t AN_limbs,
853
                                                     const mbedtls_mpi_uint *E,
854
                                                     size_t E_limbs,
855
                                                     int E_public,
856
                                                     const mbedtls_mpi_uint *RR,
857
                                                     mbedtls_mpi_uint *T)
858
745
{
859
    /* We'll process the bits of E from most significant
860
     * (limb_index=E_limbs-1, E_bit_index=biL-1) to least significant
861
     * (limb_index=0, E_bit_index=0). */
862
745
    size_t E_limb_index = E_limbs;
863
745
    size_t E_bit_index = 0;
864
745
    exp_mod_calc_first_bit_optionally_safe(E, E_limbs, E_public,
865
745
                                           &E_limb_index, &E_bit_index);
866
867
745
    const size_t wsize = exp_mod_get_window_size(E_limb_index * biL);
868
745
    const size_t welem = ((size_t) 1) << wsize;
869
870
    /* This is how we will use the temporary storage T, which must have space
871
     * for table_limbs, select_limbs and (2 * AN_limbs + 1) for montmul. */
872
745
    const size_t table_limbs  = welem * AN_limbs;
873
745
    const size_t select_limbs = AN_limbs;
874
875
    /* Pointers to specific parts of the temporary working memory pool */
876
745
    mbedtls_mpi_uint *const Wtable  = T;
877
745
    mbedtls_mpi_uint *const Wselect = Wtable  +  table_limbs;
878
745
    mbedtls_mpi_uint *const temp    = Wselect + select_limbs;
879
880
    /*
881
     * Window precomputation
882
     */
883
884
745
    const mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N);
885
886
    /* Set Wtable[i] = A^i (in Montgomery representation) */
887
745
    exp_mod_precompute_window(A, N, AN_limbs,
888
745
                              mm, RR,
889
745
                              welem, Wtable, temp);
890
891
    /*
892
     * Fixed window exponentiation
893
     */
894
895
    /* X = 1 (in Montgomery presentation) initially */
896
745
    memcpy(X, Wtable, AN_limbs * ciL);
897
898
    /* At any given time, window contains window_bits bits from E.
899
     * window_bits can go up to wsize. */
900
745
    size_t window_bits = 0;
901
745
    mbedtls_mpi_uint window = 0;
902
903
207k
    do {
904
        /* Square */
905
207k
        mbedtls_mpi_core_montmul(X, X, X, AN_limbs, N, AN_limbs, mm, temp);
906
907
        /* Move to the next bit of the exponent */
908
207k
        if (E_bit_index == 0) {
909
3.24k
            --E_limb_index;
910
3.24k
            E_bit_index = biL - 1;
911
204k
        } else {
912
204k
            --E_bit_index;
913
204k
        }
914
        /* Insert next exponent bit into window */
915
207k
        ++window_bits;
916
207k
        window <<= 1;
917
207k
        window |= (E[E_limb_index] >> E_bit_index) & 1;
918
919
        /* Clear window if it's full. Also clear the window at the end,
920
         * when we've finished processing the exponent. */
921
207k
        if (window_bits == wsize ||
922
207k
            (E_bit_index == 0 && E_limb_index == 0)) {
923
924
74.5k
            exp_mod_table_lookup_optionally_safe(Wselect, Wtable, AN_limbs, welem,
925
74.5k
                                                 window, E_public);
926
            /* Multiply X by the selected element. */
927
74.5k
            mbedtls_mpi_core_montmul(X, X, Wselect, AN_limbs, N, AN_limbs, mm,
928
74.5k
                                     temp);
929
74.5k
            window = 0;
930
74.5k
            window_bits = 0;
931
74.5k
        }
932
207k
    } while (!(E_bit_index == 0 && E_limb_index == 0));
933
745
}
934
935
void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X,
936
                              const mbedtls_mpi_uint *A,
937
                              const mbedtls_mpi_uint *N, size_t AN_limbs,
938
                              const mbedtls_mpi_uint *E, size_t E_limbs,
939
                              const mbedtls_mpi_uint *RR,
940
                              mbedtls_mpi_uint *T)
941
745
{
942
745
    mbedtls_mpi_core_exp_mod_optionally_safe(X,
943
745
                                             A,
944
745
                                             N,
945
745
                                             AN_limbs,
946
745
                                             E,
947
745
                                             E_limbs,
948
745
                                             MBEDTLS_MPI_IS_SECRET,
949
745
                                             RR,
950
745
                                             T);
951
745
}
952
953
void mbedtls_mpi_core_exp_mod_unsafe(mbedtls_mpi_uint *X,
954
                                     const mbedtls_mpi_uint *A,
955
                                     const mbedtls_mpi_uint *N, size_t AN_limbs,
956
                                     const mbedtls_mpi_uint *E, size_t E_limbs,
957
                                     const mbedtls_mpi_uint *RR,
958
                                     mbedtls_mpi_uint *T)
959
0
{
960
0
    mbedtls_mpi_core_exp_mod_optionally_safe(X,
961
0
                                             A,
962
0
                                             N,
963
0
                                             AN_limbs,
964
0
                                             E,
965
0
                                             E_limbs,
966
0
                                             MBEDTLS_MPI_IS_PUBLIC,
967
0
                                             RR,
968
0
                                             T);
969
0
}
970
971
mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X,
972
                                          const mbedtls_mpi_uint *A,
973
                                          mbedtls_mpi_uint c,  /* doubles as carry */
974
                                          size_t limbs)
975
131k
{
976
282k
    for (size_t i = 0; i < limbs; i++) {
977
151k
        mbedtls_mpi_uint s = A[i];
978
151k
        mbedtls_mpi_uint t = s - c;
979
151k
        c = (t > s);
980
151k
        X[i] = t;
981
151k
    }
982
983
131k
    return c;
984
131k
}
985
986
mbedtls_ct_condition_t mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A,
987
                                                      size_t limbs)
988
0
{
989
0
    volatile const mbedtls_mpi_uint *force_read_A = A;
990
0
    mbedtls_mpi_uint bits = 0;
991
992
0
    for (size_t i = 0; i < limbs; i++) {
993
0
        bits |= force_read_A[i];
994
0
    }
995
996
0
    return mbedtls_ct_bool(bits);
997
0
}
998
999
void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X,
1000
                                  const mbedtls_mpi_uint *A,
1001
                                  const mbedtls_mpi_uint *N,
1002
                                  size_t AN_limbs,
1003
                                  mbedtls_mpi_uint mm,
1004
                                  const mbedtls_mpi_uint *rr,
1005
                                  mbedtls_mpi_uint *T)
1006
745
{
1007
745
    mbedtls_mpi_core_montmul(X, A, rr, AN_limbs, N, AN_limbs, mm, T);
1008
745
}
1009
1010
void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X,
1011
                                    const mbedtls_mpi_uint *A,
1012
                                    const mbedtls_mpi_uint *N,
1013
                                    size_t AN_limbs,
1014
                                    mbedtls_mpi_uint mm,
1015
                                    mbedtls_mpi_uint *T)
1016
745
{
1017
745
    const mbedtls_mpi_uint Rinv = 1;    /* 1/R in Mont. rep => 1 */
1018
1019
745
    mbedtls_mpi_core_montmul(X, A, &Rinv, 1, N, AN_limbs, mm, T);
1020
745
}
1021
1022
#endif /* MBEDTLS_BIGNUM_C */