Coverage Report

Created: 2024-11-21 07:03

/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
7.56M
{
26
7.56M
#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
7.56M
    #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
7.56M
#endif
35
7.56M
#if defined(core_clz)
36
7.56M
    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
7.56M
}
52
53
size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs)
54
7.56M
{
55
7.56M
    int i;
56
7.56M
    size_t j;
57
58
34.9M
    for (i = ((int) A_limbs) - 1; i >= 0; i--) {
59
34.9M
        if (A[i] != 0) {
60
7.56M
            j = biL - mbedtls_mpi_core_clz(A[i]);
61
7.56M
            return (i * biL) + j;
62
7.56M
        }
63
34.9M
    }
64
65
2.10k
    return 0;
66
7.56M
}
67
68
static mbedtls_mpi_uint mpi_bigendian_to_host(mbedtls_mpi_uint a)
69
12.0k
{
70
12.0k
    if (MBEDTLS_IS_BIG_ENDIAN) {
71
        /* Nothing to do on bigendian systems. */
72
0
        return a;
73
12.0k
    } else {
74
#if defined(MBEDTLS_HAVE_INT32)
75
        return (mbedtls_mpi_uint) MBEDTLS_BSWAP32(a);
76
#elif defined(MBEDTLS_HAVE_INT64)
77
12.0k
        return (mbedtls_mpi_uint) MBEDTLS_BSWAP64(a);
78
12.0k
#endif
79
12.0k
    }
80
12.0k
}
81
82
void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A,
83
                                        size_t A_limbs)
84
2.50k
{
85
2.50k
    mbedtls_mpi_uint *cur_limb_left;
86
2.50k
    mbedtls_mpi_uint *cur_limb_right;
87
2.50k
    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
2.50k
    for (cur_limb_left = A, cur_limb_right = A + (A_limbs - 1);
101
8.50k
         cur_limb_left <= cur_limb_right;
102
6.00k
         cur_limb_left++, cur_limb_right--) {
103
6.00k
        mbedtls_mpi_uint tmp;
104
        /* Note that if cur_limb_left == cur_limb_right,
105
         * this code effectively swaps the bytes only once. */
106
6.00k
        tmp             = mpi_bigendian_to_host(*cur_limb_left);
107
6.00k
        *cur_limb_left  = mpi_bigendian_to_host(*cur_limb_right);
108
6.00k
        *cur_limb_right = tmp;
109
6.00k
    }
110
2.50k
}
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
2.02k
{
118
    /* min <= least significant limb? */
119
2.02k
    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
2.02k
    mbedtls_ct_condition_t msll_mask = MBEDTLS_CT_FALSE;
123
10.1k
    for (size_t i = 1; i < A_limbs; i++) {
124
8.07k
        msll_mask = mbedtls_ct_bool_or(msll_mask, mbedtls_ct_bool(A[i]));
125
8.07k
    }
126
127
    /* min <= A iff the lowest limb of A is >= min or the other limbs
128
     * are not all zero. */
129
2.02k
    return mbedtls_ct_bool_or(msll_mask, min_le_lsl);
130
2.02k
}
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
2.04k
{
136
2.04k
    mbedtls_ct_condition_t ret = MBEDTLS_CT_FALSE, cond = MBEDTLS_CT_FALSE, done = MBEDTLS_CT_FALSE;
137
138
12.1k
    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
10.1k
        cond = mbedtls_ct_uint_lt(B[i - 1], A[i - 1]);
147
10.1k
        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
10.1k
        cond = mbedtls_ct_uint_lt(A[i - 1], B[i - 1]);
156
10.1k
        ret  = mbedtls_ct_bool_or(ret, mbedtls_ct_bool_and(cond, mbedtls_ct_bool_not(done)));
157
10.1k
        done = mbedtls_ct_bool_or(done, cond);
158
10.1k
    }
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
2.04k
    return ret;
166
2.04k
}
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
6.59M
{
173
6.59M
    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
156M
    for (size_t i = 0; i < limbs; i++) {
183
150M
        X[i] = mbedtls_ct_mpi_uint_if(assign, A[i], X[i]);
184
150M
    }
185
6.59M
}
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
25
{
192
25
    if (X == Y) {
193
0
        return;
194
0
    }
195
196
577
    for (size_t i = 0; i < limbs; i++) {
197
552
        mbedtls_mpi_uint tmp = X[i];
198
552
        X[i] = mbedtls_ct_mpi_uint_if(swap, Y[i], X[i]);
199
552
        Y[i] = mbedtls_ct_mpi_uint_if(swap, tmp, Y[i]);
200
552
    }
201
25
}
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
476
{
231
476
    const size_t limbs = CHARS_TO_LIMBS(input_length);
232
233
476
    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
476
    if (X_limbs == 0) {
240
0
        return 0;
241
0
    }
242
243
476
    memset(X, 0, X_limbs * ciL);
244
245
    /* memcpy() with (NULL, 0) is undefined behaviour */
246
476
    if (input_length != 0) {
247
476
        size_t overhead = (X_limbs * ciL) - input_length;
248
476
        unsigned char *Xp = (unsigned char *) X;
249
476
        memcpy(Xp + overhead, input, input_length);
250
476
    }
251
252
476
    mbedtls_mpi_core_bigendian_to_host(X, X_limbs);
253
254
476
    return 0;
255
476
}
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
246
{
262
246
    size_t stored_bytes = A_limbs * ciL;
263
246
    size_t bytes_to_copy;
264
265
246
    if (stored_bytes < output_length) {
266
0
        bytes_to_copy = stored_bytes;
267
246
    } else {
268
246
        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
1.65k
        for (size_t i = bytes_to_copy; i < stored_bytes; i++) {
273
1.50k
            if (GET_BYTE(A, i) != 0) {
274
98
                return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
275
98
            }
276
1.50k
        }
277
246
    }
278
279
920
    for (size_t i = 0; i < bytes_to_copy; i++) {
280
772
        output[i] = GET_BYTE(A, i);
281
772
    }
282
283
148
    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
148
    return 0;
289
246
}
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
3.50k
{
296
3.50k
    size_t stored_bytes;
297
3.50k
    size_t bytes_to_copy;
298
3.50k
    unsigned char *p;
299
300
3.50k
    stored_bytes = X_limbs * ciL;
301
302
3.50k
    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
3.25k
        bytes_to_copy = stored_bytes;
309
3.25k
        p = output + output_length - stored_bytes;
310
3.25k
        memset(output, 0, output_length - stored_bytes);
311
3.25k
    } 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
245
        bytes_to_copy = output_length;
315
245
        p = output;
316
551
        for (size_t i = bytes_to_copy; i < stored_bytes; i++) {
317
539
            if (GET_BYTE(X, i) != 0) {
318
233
                return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
319
233
            }
320
539
        }
321
245
    }
322
323
902k
    for (size_t i = 0; i < bytes_to_copy; i++) {
324
899k
        p[bytes_to_copy - i - 1] = GET_BYTE(X, i);
325
899k
    }
326
327
3.26k
    return 0;
328
3.50k
}
329
330
void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs,
331
                              size_t count)
332
19.7M
{
333
19.7M
    size_t i, v0, v1;
334
19.7M
    mbedtls_mpi_uint r0 = 0, r1;
335
336
19.7M
    v0 = count /  biL;
337
19.7M
    v1 = count & (biL - 1);
338
339
19.7M
    if (v0 > limbs || (v0 == limbs && v1 > 0)) {
340
9
        memset(X, 0, limbs * ciL);
341
9
        return;
342
9
    }
343
344
    /*
345
     * shift by count / limb_size
346
     */
347
19.7M
    if (v0 > 0) {
348
2.72M
        for (i = 0; i < limbs - v0; i++) {
349
2.31M
            X[i] = X[i + v0];
350
2.31M
        }
351
352
2.72M
        for (; i < limbs; i++) {
353
2.31M
            X[i] = 0;
354
2.31M
        }
355
415k
    }
356
357
    /*
358
     * shift by count % limb_size
359
     */
360
19.7M
    if (v1 > 0) {
361
851M
        for (i = limbs; i > 0; i--) {
362
836M
            r1 = X[i - 1] << (biL - v1);
363
836M
            X[i - 1] >>= v1;
364
836M
            X[i - 1] |= r0;
365
836M
            r0 = r1;
366
836M
        }
367
15.2M
    }
368
19.7M
}
369
370
void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs,
371
                              size_t count)
372
4.52M
{
373
4.52M
    size_t i, v0, v1;
374
4.52M
    mbedtls_mpi_uint r0 = 0, r1;
375
376
4.52M
    v0 = count / (biL);
377
4.52M
    v1 = count & (biL - 1);
378
379
    /*
380
     * shift by count / limb_size
381
     */
382
4.52M
    if (v0 > 0) {
383
29.8M
        for (i = limbs; i > v0; i--) {
384
27.5M
            X[i - 1] = X[i - v0 - 1];
385
27.5M
        }
386
387
12.7M
        for (; i > 0; i--) {
388
10.4M
            X[i - 1] = 0;
389
10.4M
        }
390
2.31M
    }
391
392
    /*
393
     * shift by count % limb_size
394
     */
395
4.52M
    if (v1 > 0) {
396
19.3M
        for (i = v0; i < limbs; i++) {
397
17.6M
            r1 = X[i] >> (biL - v1);
398
17.6M
            X[i] <<= v1;
399
17.6M
            X[i] |= r0;
400
17.6M
            r0 = r1;
401
17.6M
        }
402
1.78M
    }
403
4.52M
}
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
11.4M
{
410
11.4M
    mbedtls_mpi_uint c = 0;
411
412
207M
    for (size_t i = 0; i < limbs; i++) {
413
196M
        mbedtls_mpi_uint t = c + A[i];
414
196M
        c = (t < A[i]);
415
196M
        t += B[i];
416
196M
        c += (t < B[i]);
417
196M
        X[i] = t;
418
196M
    }
419
420
11.4M
    return c;
421
11.4M
}
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
17.1M
{
449
17.1M
    mbedtls_mpi_uint c = 0;
450
451
435M
    for (size_t i = 0; i < limbs; i++) {
452
418M
        mbedtls_mpi_uint z = (A[i] < c);
453
418M
        mbedtls_mpi_uint t = A[i] - c;
454
418M
        c = (t < B[i]) + z;
455
418M
        X[i] = t - B[i];
456
418M
    }
457
458
17.1M
    return c;
459
17.1M
}
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
167M
{
465
167M
    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
167M
    if (d_len < s_len) {
472
0
        s_len = d_len;
473
0
    }
474
167M
    size_t excess_len = d_len - s_len;
475
167M
    size_t steps_x8 = s_len / 8;
476
167M
    size_t steps_x1 = s_len & 7;
477
478
1.54G
    while (steps_x8--) {
479
1.38G
        MULADDC_X8_INIT
480
1.38G
        MULADDC_X8_CORE
481
1.38G
            MULADDC_X8_STOP
482
1.38G
    }
483
484
519M
    while (steps_x1--) {
485
352M
        MULADDC_X1_INIT
486
352M
        MULADDC_X1_CORE
487
352M
            MULADDC_X1_STOP
488
352M
    }
489
490
538M
    while (excess_len--) {
491
371M
        *d += c;
492
371M
        c = (*d < c);
493
371M
        d++;
494
371M
    }
495
496
167M
    return c;
497
167M
}
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
3.21M
{
503
3.21M
    memset(X, 0, (A_limbs + B_limbs) * ciL);
504
505
18.5M
    for (size_t i = 0; i < B_limbs; i++) {
506
15.3M
        (void) mbedtls_mpi_core_mla(X + i, A_limbs + 1, A, A_limbs, B[i]);
507
15.3M
    }
508
3.21M
}
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
3.38k
{
515
3.38k
    mbedtls_mpi_uint x = N[0];
516
517
3.38k
    x += ((N[0] + 2) & 4) << 1;
518
519
16.9k
    for (unsigned int i = biL; i >= 8; i /= 2) {
520
13.5k
        x *= (2 - (N[0] * x));
521
13.5k
    }
522
523
3.38k
    return ~x + 1;
524
3.38k
}
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
1.59M
{
535
1.59M
    memset(T, 0, (2 * AN_limbs + 1) * ciL);
536
537
67.7M
    for (size_t i = 0; i < AN_limbs; i++) {
538
        /* T = (T + u0*B + u1*N) / 2^biL */
539
66.1M
        mbedtls_mpi_uint u0 = A[i];
540
66.1M
        mbedtls_mpi_uint u1 = (T[0] + u0 * B[0]) * mm;
541
542
66.1M
        (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, B, B_limbs, u0);
543
66.1M
        (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, N, AN_limbs, u1);
544
545
66.1M
        T++;
546
66.1M
    }
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
1.59M
    mbedtls_mpi_uint carry  = T[AN_limbs];
559
1.59M
    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
1.59M
    mbedtls_ct_memcpy_if(mbedtls_ct_bool(carry ^ borrow),
576
1.59M
                         (unsigned char *) X,
577
1.59M
                         (unsigned char *) T,
578
1.59M
                         NULL,
579
1.59M
                         AN_limbs * sizeof(mbedtls_mpi_uint));
580
1.59M
}
581
582
int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X,
583
                                        const mbedtls_mpi *N)
584
1.69k
{
585
1.69k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
586
587
1.69k
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1));
588
1.69k
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, N->n * 2 * biL));
589
1.69k
    MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
590
1.69k
    MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(X, N->n));
591
592
1.69k
cleanup:
593
1.69k
    return ret;
594
1.69k
}
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
412k
{
603
3.52M
    for (size_t i = 0; i < count; i++, table += limbs) {
604
3.10M
        mbedtls_ct_condition_t assign = mbedtls_ct_uint_eq(i, index);
605
3.10M
        mbedtls_mpi_core_cond_assign(dest, table, limbs, assign);
606
3.10M
    }
607
412k
}
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
2.43k
{
620
2.43k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
621
2.43k
    const size_t limbs = CHARS_TO_LIMBS(n_bytes);
622
2.43k
    const size_t overhead = (limbs * ciL) - n_bytes;
623
624
2.43k
    if (X_limbs < limbs) {
625
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
626
0
    }
627
628
2.43k
    memset(X, 0, overhead);
629
2.43k
    memset((unsigned char *) X + limbs * ciL, 0, (X_limbs - limbs) * ciL);
630
2.43k
    MBEDTLS_MPI_CHK(f_rng(p_rng, (unsigned char *) X + overhead, n_bytes));
631
2.02k
    mbedtls_mpi_core_bigendian_to_host(X, limbs);
632
633
2.43k
cleanup:
634
2.43k
    return ret;
635
2.02k
}
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
2.26k
{
644
2.26k
    mbedtls_ct_condition_t ge_lower = MBEDTLS_CT_TRUE, lt_upper = MBEDTLS_CT_FALSE;
645
2.26k
    size_t n_bits = mbedtls_mpi_core_bitlen(N, limbs);
646
2.26k
    size_t n_bytes = (n_bits + 7) / 8;
647
2.26k
    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
2.26k
    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
2.43k
    do {
677
2.43k
        MBEDTLS_MPI_CHK(mbedtls_mpi_core_fill_random(X, limbs,
678
2.43k
                                                     n_bytes,
679
2.43k
                                                     f_rng, p_rng));
680
2.02k
        mbedtls_mpi_core_shift_r(X, limbs, 8 * n_bytes - n_bits);
681
682
2.02k
        if (--count == 0) {
683
0
            ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
684
0
            goto cleanup;
685
0
        }
686
687
2.02k
        ge_lower = mbedtls_mpi_core_uint_le_mpi(min, X, limbs);
688
2.02k
        lt_upper = mbedtls_mpi_core_lt_ct(X, N, limbs);
689
2.02k
    } while (mbedtls_ct_bool_and(ge_lower, lt_upper) == MBEDTLS_CT_FALSE);
690
691
2.26k
cleanup:
692
2.26k
    return ret;
693
2.26k
}
694
695
static size_t exp_mod_get_window_size(size_t Ebits)
696
3.38k
{
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
3.38k
    return (Ebits >  79) ? MBEDTLS_MPI_WINDOW_SIZE : 1;
703
#else
704
    (void) Ebits;
705
    return 1;
706
#endif
707
3.38k
}
708
709
size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs)
710
1.69k
{
711
1.69k
    const size_t wsize = exp_mod_get_window_size(E_limbs * biL);
712
1.69k
    const size_t welem = ((size_t) 1) << wsize;
713
714
    /* How big does each part of the working memory pool need to be? */
715
1.69k
    const size_t table_limbs   = welem * AN_limbs;
716
1.69k
    const size_t select_limbs  = AN_limbs;
717
1.69k
    const size_t temp_limbs    = 2 * AN_limbs + 1;
718
719
1.69k
    return table_limbs + select_limbs + temp_limbs;
720
1.69k
}
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
1.69k
{
731
    /* W[0] = 1 (in Montgomery presentation) */
732
1.69k
    memset(Wtable, 0, AN_limbs * ciL);
733
1.69k
    Wtable[0] = 1;
734
1.69k
    mbedtls_mpi_core_montmul(Wtable, Wtable, RR, AN_limbs, N, AN_limbs, mm, temp);
735
736
    /* W[1] = A (already in Montgomery presentation) */
737
1.69k
    mbedtls_mpi_uint *W1 = Wtable + AN_limbs;
738
1.69k
    memcpy(W1, A, AN_limbs * ciL);
739
740
    /* W[i+1] = W[i] * W[1], i >= 2 */
741
1.69k
    mbedtls_mpi_uint *Wprev = W1;
742
8.90k
    for (size_t i = 2; i < welem; i++) {
743
7.21k
        mbedtls_mpi_uint *Wcur = Wprev + AN_limbs;
744
7.21k
        mbedtls_mpi_core_montmul(Wcur, Wprev, W1, AN_limbs, N, AN_limbs, mm, temp);
745
7.21k
        Wprev = Wcur;
746
7.21k
    }
747
1.69k
}
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
1.69k
{
767
1.69k
    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
1.69k
    } 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
1.69k
        *E_limb_index = E_limbs;
794
1.69k
        *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
1.69k
    }
801
1.69k
}
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
412k
{
814
412k
    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
412k
    } else {
822
        /* Select Wtable[window] without leaking window through
823
         * memory access patterns. */
824
412k
        mbedtls_mpi_core_ct_uint_table_lookup(Wselect, Wtable,
825
412k
                                              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
412k
    }
832
412k
}
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
1.69k
{
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
1.69k
    size_t E_limb_index = E_limbs;
863
1.69k
    size_t E_bit_index = 0;
864
1.69k
    exp_mod_calc_first_bit_optionally_safe(E, E_limbs, E_public,
865
1.69k
                                           &E_limb_index, &E_bit_index);
866
867
1.69k
    const size_t wsize = exp_mod_get_window_size(E_limb_index * biL);
868
1.69k
    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
1.69k
    const size_t table_limbs  = welem * AN_limbs;
873
1.69k
    const size_t select_limbs = AN_limbs;
874
875
    /* Pointers to specific parts of the temporary working memory pool */
876
1.69k
    mbedtls_mpi_uint *const Wtable  = T;
877
1.69k
    mbedtls_mpi_uint *const Wselect = Wtable  +  table_limbs;
878
1.69k
    mbedtls_mpi_uint *const temp    = Wselect + select_limbs;
879
880
    /*
881
     * Window precomputation
882
     */
883
884
1.69k
    const mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N);
885
886
    /* Set Wtable[i] = A^i (in Montgomery representation) */
887
1.69k
    exp_mod_precompute_window(A, N, AN_limbs,
888
1.69k
                              mm, RR,
889
1.69k
                              welem, Wtable, temp);
890
891
    /*
892
     * Fixed window exponentiation
893
     */
894
895
    /* X = 1 (in Montgomery presentation) initially */
896
1.69k
    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
1.69k
    size_t window_bits = 0;
901
1.69k
    mbedtls_mpi_uint window = 0;
902
903
1.17M
    do {
904
        /* Square */
905
1.17M
        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
1.17M
        if (E_bit_index == 0) {
909
18.3k
            --E_limb_index;
910
18.3k
            E_bit_index = biL - 1;
911
1.15M
        } else {
912
1.15M
            --E_bit_index;
913
1.15M
        }
914
        /* Insert next exponent bit into window */
915
1.17M
        ++window_bits;
916
1.17M
        window <<= 1;
917
1.17M
        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
1.17M
        if (window_bits == wsize ||
922
1.17M
            (E_bit_index == 0 && E_limb_index == 0)) {
923
924
412k
            exp_mod_table_lookup_optionally_safe(Wselect, Wtable, AN_limbs, welem,
925
412k
                                                 window, E_public);
926
            /* Multiply X by the selected element. */
927
412k
            mbedtls_mpi_core_montmul(X, X, Wselect, AN_limbs, N, AN_limbs, mm,
928
412k
                                     temp);
929
412k
            window = 0;
930
412k
            window_bits = 0;
931
412k
        }
932
1.17M
    } while (!(E_bit_index == 0 && E_limb_index == 0));
933
1.69k
}
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
1.69k
{
942
1.69k
    mbedtls_mpi_core_exp_mod_optionally_safe(X,
943
1.69k
                                             A,
944
1.69k
                                             N,
945
1.69k
                                             AN_limbs,
946
1.69k
                                             E,
947
1.69k
                                             E_limbs,
948
1.69k
                                             MBEDTLS_MPI_IS_SECRET,
949
1.69k
                                             RR,
950
1.69k
                                             T);
951
1.69k
}
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
2.04M
{
976
16.6M
    for (size_t i = 0; i < limbs; i++) {
977
14.6M
        mbedtls_mpi_uint s = A[i];
978
14.6M
        mbedtls_mpi_uint t = s - c;
979
14.6M
        c = (t > s);
980
14.6M
        X[i] = t;
981
14.6M
    }
982
983
2.04M
    return c;
984
2.04M
}
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
1.69k
{
1007
1.69k
    mbedtls_mpi_core_montmul(X, A, rr, AN_limbs, N, AN_limbs, mm, T);
1008
1.69k
}
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
1.69k
{
1017
1.69k
    const mbedtls_mpi_uint Rinv = 1;    /* 1/R in Mont. rep => 1 */
1018
1019
1.69k
    mbedtls_mpi_core_montmul(X, A, &Rinv, 1, N, AN_limbs, mm, T);
1020
1.69k
}
1021
1022
#endif /* MBEDTLS_BIGNUM_C */