Coverage Report

Created: 2024-11-21 07:03

/src/openssl/crypto/bn/bn_lib.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved.
3
 *
4
 * Licensed under the Apache License 2.0 (the "License").  You may not use
5
 * this file except in compliance with the License.  You can obtain a copy
6
 * in the file LICENSE in the source distribution or at
7
 * https://www.openssl.org/source/license.html
8
 */
9
10
#include <assert.h>
11
#include <limits.h>
12
#include "internal/cryptlib.h"
13
#include "internal/endian.h"
14
#include "bn_local.h"
15
#include <openssl/opensslconf.h>
16
#include "internal/constant_time.h"
17
18
/* This stuff appears to be completely unused, so is deprecated */
19
#ifndef OPENSSL_NO_DEPRECATED_0_9_8
20
/*-
21
 * For a 32 bit machine
22
 * 2 -   4 ==  128
23
 * 3 -   8 ==  256
24
 * 4 -  16 ==  512
25
 * 5 -  32 == 1024
26
 * 6 -  64 == 2048
27
 * 7 - 128 == 4096
28
 * 8 - 256 == 8192
29
 */
30
static int bn_limit_bits = 0;
31
static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
32
static int bn_limit_bits_low = 0;
33
static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
34
static int bn_limit_bits_high = 0;
35
static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
36
static int bn_limit_bits_mont = 0;
37
static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
38
39
void BN_set_params(int mult, int high, int low, int mont)
40
0
{
41
0
    if (mult >= 0) {
42
0
        if (mult > (int)(sizeof(int) * 8) - 1)
43
0
            mult = sizeof(int) * 8 - 1;
44
0
        bn_limit_bits = mult;
45
0
        bn_limit_num = 1 << mult;
46
0
    }
47
0
    if (high >= 0) {
48
0
        if (high > (int)(sizeof(int) * 8) - 1)
49
0
            high = sizeof(int) * 8 - 1;
50
0
        bn_limit_bits_high = high;
51
0
        bn_limit_num_high = 1 << high;
52
0
    }
53
0
    if (low >= 0) {
54
0
        if (low > (int)(sizeof(int) * 8) - 1)
55
0
            low = sizeof(int) * 8 - 1;
56
0
        bn_limit_bits_low = low;
57
0
        bn_limit_num_low = 1 << low;
58
0
    }
59
0
    if (mont >= 0) {
60
0
        if (mont > (int)(sizeof(int) * 8) - 1)
61
0
            mont = sizeof(int) * 8 - 1;
62
0
        bn_limit_bits_mont = mont;
63
0
        bn_limit_num_mont = 1 << mont;
64
0
    }
65
0
}
66
67
int BN_get_params(int which)
68
0
{
69
0
    if (which == 0)
70
0
        return bn_limit_bits;
71
0
    else if (which == 1)
72
0
        return bn_limit_bits_high;
73
0
    else if (which == 2)
74
0
        return bn_limit_bits_low;
75
0
    else if (which == 3)
76
0
        return bn_limit_bits_mont;
77
0
    else
78
0
        return 0;
79
0
}
80
#endif
81
82
const BIGNUM *BN_value_one(void)
83
338k
{
84
338k
    static const BN_ULONG data_one = 1L;
85
338k
    static const BIGNUM const_one = {
86
338k
        (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA
87
338k
    };
88
89
338k
    return &const_one;
90
338k
}
91
92
/*
93
 * Old Visual Studio ARM compiler miscompiles BN_num_bits_word()
94
 * https://mta.openssl.org/pipermail/openssl-users/2018-August/008465.html
95
 */
96
#if defined(_MSC_VER) && defined(_ARM_) && defined(_WIN32_WCE) \
97
    && _MSC_VER>=1400 && _MSC_VER<1501
98
# define MS_BROKEN_BN_num_bits_word
99
# pragma optimize("", off)
100
#endif
101
int BN_num_bits_word(BN_ULONG l)
102
56.0M
{
103
56.0M
    BN_ULONG x, mask;
104
56.0M
    int bits = (l != 0);
105
106
56.0M
#if BN_BITS2 > 32
107
56.0M
    x = l >> 32;
108
56.0M
    mask = (0 - x) & BN_MASK2;
109
56.0M
    mask = (0 - (mask >> (BN_BITS2 - 1)));
110
56.0M
    bits += 32 & mask;
111
56.0M
    l ^= (x ^ l) & mask;
112
56.0M
#endif
113
114
56.0M
    x = l >> 16;
115
56.0M
    mask = (0 - x) & BN_MASK2;
116
56.0M
    mask = (0 - (mask >> (BN_BITS2 - 1)));
117
56.0M
    bits += 16 & mask;
118
56.0M
    l ^= (x ^ l) & mask;
119
120
56.0M
    x = l >> 8;
121
56.0M
    mask = (0 - x) & BN_MASK2;
122
56.0M
    mask = (0 - (mask >> (BN_BITS2 - 1)));
123
56.0M
    bits += 8 & mask;
124
56.0M
    l ^= (x ^ l) & mask;
125
126
56.0M
    x = l >> 4;
127
56.0M
    mask = (0 - x) & BN_MASK2;
128
56.0M
    mask = (0 - (mask >> (BN_BITS2 - 1)));
129
56.0M
    bits += 4 & mask;
130
56.0M
    l ^= (x ^ l) & mask;
131
132
56.0M
    x = l >> 2;
133
56.0M
    mask = (0 - x) & BN_MASK2;
134
56.0M
    mask = (0 - (mask >> (BN_BITS2 - 1)));
135
56.0M
    bits += 2 & mask;
136
56.0M
    l ^= (x ^ l) & mask;
137
138
56.0M
    x = l >> 1;
139
56.0M
    mask = (0 - x) & BN_MASK2;
140
56.0M
    mask = (0 - (mask >> (BN_BITS2 - 1)));
141
56.0M
    bits += 1 & mask;
142
143
56.0M
    return bits;
144
56.0M
}
145
#ifdef MS_BROKEN_BN_num_bits_word
146
# pragma optimize("", on)
147
#endif
148
149
/*
150
 * This function still leaks `a->dmax`: it's caller's responsibility to
151
 * expand the input `a` in advance to a public length.
152
 */
153
static ossl_inline
154
int bn_num_bits_consttime(const BIGNUM *a)
155
8.68k
{
156
8.68k
    int j, ret;
157
8.68k
    unsigned int mask, past_i;
158
8.68k
    int i = a->top - 1;
159
8.68k
    bn_check_top(a);
160
161
95.2k
    for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) {
162
86.5k
        mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */
163
164
86.5k
        ret += BN_BITS2 & (~mask & ~past_i);
165
86.5k
        ret += BN_num_bits_word(a->d[j]) & mask;
166
167
86.5k
        past_i |= mask; /* past_i will become 0xff..ff after i==j */
168
86.5k
    }
169
170
    /*
171
     * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the
172
     * final result.
173
     */
174
8.68k
    mask = ~(constant_time_eq_int(i, ((int)-1)));
175
176
8.68k
    return ret & mask;
177
8.68k
}
178
179
int BN_num_bits(const BIGNUM *a)
180
3.45M
{
181
3.45M
    int i = a->top - 1;
182
3.45M
    bn_check_top(a);
183
184
3.45M
    if (a->flags & BN_FLG_CONSTTIME) {
185
        /*
186
         * We assume that BIGNUMs flagged as CONSTTIME have also been expanded
187
         * so that a->dmax is not leaking secret information.
188
         *
189
         * In other words, it's the caller's responsibility to ensure `a` has
190
         * been preallocated in advance to a public length if we hit this
191
         * branch.
192
         *
193
         */
194
8.68k
        return bn_num_bits_consttime(a);
195
8.68k
    }
196
197
3.44M
    if (BN_is_zero(a))
198
8.17k
        return 0;
199
200
3.44M
    return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
201
3.44M
}
202
203
static void bn_free_d(BIGNUM *a, int clear)
204
659k
{
205
659k
    if (BN_get_flags(a, BN_FLG_SECURE))
206
29.1k
        OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0]));
207
629k
    else if (clear != 0)
208
401k
        OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0]));
209
228k
    else
210
228k
        OPENSSL_free(a->d);
211
659k
}
212
213
214
void BN_clear_free(BIGNUM *a)
215
304k
{
216
304k
    if (a == NULL)
217
8.56k
        return;
218
295k
    if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA))
219
256k
        bn_free_d(a, 1);
220
295k
    if (BN_get_flags(a, BN_FLG_MALLOCED)) {
221
32.3k
        OPENSSL_cleanse(a, sizeof(*a));
222
32.3k
        OPENSSL_free(a);
223
32.3k
    }
224
295k
}
225
226
void BN_free(BIGNUM *a)
227
361k
{
228
361k
    if (a == NULL)
229
132k
        return;
230
229k
    if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
231
229k
        bn_free_d(a, 0);
232
229k
    if (a->flags & BN_FLG_MALLOCED)
233
228k
        OPENSSL_free(a);
234
229k
}
235
236
void bn_init(BIGNUM *a)
237
616k
{
238
616k
    static BIGNUM nilbn;
239
240
616k
    *a = nilbn;
241
616k
    bn_check_top(a);
242
616k
}
243
244
BIGNUM *BN_new(void)
245
302k
{
246
302k
    BIGNUM *ret;
247
248
302k
    if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
249
0
        return NULL;
250
302k
    ret->flags = BN_FLG_MALLOCED;
251
302k
    bn_check_top(ret);
252
302k
    return ret;
253
302k
}
254
255
 BIGNUM *BN_secure_new(void)
256
938
 {
257
938
     BIGNUM *ret = BN_new();
258
938
     if (ret != NULL)
259
938
         ret->flags |= BN_FLG_SECURE;
260
938
     return ret;
261
938
 }
262
263
/* This is used by bn_expand2() */
264
/* The caller MUST check that words > b->dmax before calling this */
265
static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
266
642k
{
267
642k
    BN_ULONG *a = NULL;
268
269
642k
    if (words > (INT_MAX / (4 * BN_BITS2))) {
270
0
        ERR_raise(ERR_LIB_BN, BN_R_BIGNUM_TOO_LONG);
271
0
        return NULL;
272
0
    }
273
642k
    if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
274
0
        ERR_raise(ERR_LIB_BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
275
0
        return NULL;
276
0
    }
277
642k
    if (BN_get_flags(b, BN_FLG_SECURE))
278
29.1k
        a = OPENSSL_secure_zalloc(words * sizeof(*a));
279
613k
    else
280
613k
        a = OPENSSL_zalloc(words * sizeof(*a));
281
642k
    if (a == NULL)
282
0
        return NULL;
283
284
642k
    assert(b->top <= words);
285
642k
    if (b->top > 0)
286
74.7k
        memcpy(a, b->d, sizeof(*a) * b->top);
287
288
642k
    return a;
289
642k
}
290
291
/*
292
 * This is an internal function that should not be used in applications. It
293
 * ensures that 'b' has enough room for a 'words' word number and initialises
294
 * any unused part of b->d with leading zeros. It is mostly used by the
295
 * various BIGNUM routines. If there is an error, NULL is returned. If not,
296
 * 'b' is returned.
297
 */
298
299
BIGNUM *bn_expand2(BIGNUM *b, int words)
300
642k
{
301
642k
    if (words > b->dmax) {
302
642k
        BN_ULONG *a = bn_expand_internal(b, words);
303
642k
        if (!a)
304
0
            return NULL;
305
642k
        if (b->d != NULL)
306
173k
            bn_free_d(b, 1);
307
642k
        b->d = a;
308
642k
        b->dmax = words;
309
642k
    }
310
311
642k
    return b;
312
642k
}
313
314
BIGNUM *BN_dup(const BIGNUM *a)
315
14.8k
{
316
14.8k
    BIGNUM *t;
317
318
14.8k
    if (a == NULL)
319
0
        return NULL;
320
14.8k
    bn_check_top(a);
321
322
14.8k
    t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
323
14.8k
    if (t == NULL)
324
0
        return NULL;
325
14.8k
    if (!BN_copy(t, a)) {
326
0
        BN_free(t);
327
0
        return NULL;
328
0
    }
329
14.8k
    bn_check_top(t);
330
14.8k
    return t;
331
14.8k
}
332
333
BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
334
3.12M
{
335
3.12M
    int bn_words;
336
337
3.12M
    bn_check_top(b);
338
339
3.12M
    bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top;
340
341
3.12M
    if (a == b)
342
46
        return a;
343
3.12M
    if (bn_wexpand(a, bn_words) == NULL)
344
0
        return NULL;
345
346
3.12M
    if (b->top > 0)
347
3.10M
        memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words);
348
349
3.12M
    a->neg = b->neg;
350
3.12M
    a->top = b->top;
351
3.12M
    a->flags |= b->flags & BN_FLG_FIXED_TOP;
352
3.12M
    bn_check_top(a);
353
3.12M
    return a;
354
3.12M
}
355
356
0
#define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
357
0
                                    | BN_FLG_CONSTTIME   \
358
0
                                    | BN_FLG_SECURE      \
359
0
                                    | BN_FLG_FIXED_TOP))
360
0
#define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
361
362
void BN_swap(BIGNUM *a, BIGNUM *b)
363
0
{
364
0
    int flags_old_a, flags_old_b;
365
0
    BN_ULONG *tmp_d;
366
0
    int tmp_top, tmp_dmax, tmp_neg;
367
368
0
    bn_check_top(a);
369
0
    bn_check_top(b);
370
371
0
    flags_old_a = a->flags;
372
0
    flags_old_b = b->flags;
373
374
0
    tmp_d = a->d;
375
0
    tmp_top = a->top;
376
0
    tmp_dmax = a->dmax;
377
0
    tmp_neg = a->neg;
378
379
0
    a->d = b->d;
380
0
    a->top = b->top;
381
0
    a->dmax = b->dmax;
382
0
    a->neg = b->neg;
383
384
0
    b->d = tmp_d;
385
0
    b->top = tmp_top;
386
0
    b->dmax = tmp_dmax;
387
0
    b->neg = tmp_neg;
388
389
0
    a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b);
390
0
    b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a);
391
0
    bn_check_top(a);
392
0
    bn_check_top(b);
393
0
}
394
395
void BN_clear(BIGNUM *a)
396
191k
{
397
191k
    if (a == NULL)
398
46
        return;
399
191k
    bn_check_top(a);
400
191k
    if (a->d != NULL)
401
185k
        OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
402
191k
    a->neg = 0;
403
191k
    a->top = 0;
404
191k
    a->flags &= ~BN_FLG_FIXED_TOP;
405
191k
}
406
407
BN_ULONG BN_get_word(const BIGNUM *a)
408
0
{
409
0
    if (a->top > 1)
410
0
        return BN_MASK2;
411
0
    else if (a->top == 1)
412
0
        return a->d[0];
413
    /* a->top == 0 */
414
0
    return 0;
415
0
}
416
417
int BN_set_word(BIGNUM *a, BN_ULONG w)
418
233k
{
419
233k
    bn_check_top(a);
420
233k
    if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
421
0
        return 0;
422
233k
    a->neg = 0;
423
233k
    a->d[0] = w;
424
233k
    a->top = (w ? 1 : 0);
425
233k
    a->flags &= ~BN_FLG_FIXED_TOP;
426
233k
    bn_check_top(a);
427
233k
    return 1;
428
233k
}
429
430
typedef enum {BIG, LITTLE} endianness_t;
431
typedef enum {SIGNED, UNSIGNED} signedness_t;
432
433
static BIGNUM *bin2bn(const unsigned char *s, int len, BIGNUM *ret,
434
                      endianness_t endianness, signedness_t signedness)
435
1.10M
{
436
1.10M
    int inc;
437
1.10M
    const unsigned char *s2;
438
1.10M
    int inc2;
439
1.10M
    int neg = 0, xor = 0, carry = 0;
440
1.10M
    unsigned int i;
441
1.10M
    unsigned int n;
442
1.10M
    BIGNUM *bn = NULL;
443
444
    /* Negative length is not acceptable */
445
1.10M
    if (len < 0)
446
0
        return NULL;
447
448
1.10M
    if (ret == NULL)
449
25.2k
        ret = bn = BN_new();
450
1.10M
    if (ret == NULL)
451
0
        return NULL;
452
1.10M
    bn_check_top(ret);
453
454
    /*
455
     * If the input has no bits, the number is considered zero.
456
     * This makes calls with s==NULL and len==0 safe.
457
     */
458
1.10M
    if (len == 0) {
459
1.27k
        BN_clear(ret);
460
1.27k
        return ret;
461
1.27k
    }
462
463
    /*
464
     * The loop that does the work iterates from least to most
465
     * significant BIGNUM chunk, so we adapt parameters to transfer
466
     * input bytes accordingly.
467
     */
468
1.10M
    if (endianness == LITTLE) {
469
0
        s2 = s + len - 1;
470
0
        inc2 = -1;
471
0
        inc = 1;
472
1.10M
    } else {
473
1.10M
        s2 = s;
474
1.10M
        inc2 = 1;
475
1.10M
        inc = -1;
476
1.10M
        s += len - 1;
477
1.10M
    }
478
479
    /* Take note of the signedness of the input bytes*/
480
1.10M
    if (signedness == SIGNED) {
481
0
        neg = !!(*s2 & 0x80);
482
0
        xor = neg ? 0xff : 0x00;
483
0
        carry = neg;
484
0
    }
485
486
    /*
487
     * Skip leading sign extensions (the value of |xor|).
488
     * This is the only spot where |s2| and |inc2| are used.
489
     */
490
1.15M
    for ( ; len > 0 && *s2 == xor; s2 += inc2, len--)
491
52.4k
        continue;
492
493
    /*
494
     * If there was a set of 0xff, we backtrack one byte unless the next
495
     * one has a sign bit, as the last 0xff is then part of the actual
496
     * number, rather then a mere sign extension.
497
     */
498
1.10M
    if (xor == 0xff) {
499
0
        if (len == 0 || !(*s2 & 0x80))
500
0
            len++;
501
0
    }
502
    /* If it was all zeros, we're done */
503
1.10M
    if (len == 0) {
504
3.32k
        ret->top = 0;
505
3.32k
        return ret;
506
3.32k
    }
507
1.09M
    n = ((len - 1) / BN_BYTES) + 1; /* Number of resulting bignum chunks */
508
1.09M
    if (bn_wexpand(ret, (int)n) == NULL) {
509
0
        BN_free(bn);
510
0
        return NULL;
511
0
    }
512
1.09M
    ret->top = n;
513
1.09M
    ret->neg = neg;
514
5.52M
    for (i = 0; n-- > 0; i++) {
515
4.42M
        BN_ULONG l = 0;        /* Accumulator */
516
4.42M
        unsigned int m = 0;    /* Offset in a bignum chunk, in bits */
517
518
35.6M
        for (; len > 0 && m < BN_BYTES * 8; len--, s += inc, m += 8) {
519
31.2M
            BN_ULONG byte_xored = *s ^ xor;
520
31.2M
            BN_ULONG byte = (byte_xored + carry) & 0xff;
521
522
31.2M
            carry = byte_xored > byte; /* Implicit 1 or 0 */
523
31.2M
            l |= (byte << m);
524
31.2M
        }
525
4.42M
        ret->d[i] = l;
526
4.42M
    }
527
    /*
528
     * need to call this due to clear byte at top if avoiding having the top
529
     * bit set (-ve number)
530
     */
531
1.09M
    bn_correct_top(ret);
532
1.09M
    return ret;
533
1.09M
}
534
535
BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
536
1.10M
{
537
1.10M
    return bin2bn(s, len, ret, BIG, UNSIGNED);
538
1.10M
}
539
540
BIGNUM *BN_signed_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
541
0
{
542
0
    return bin2bn(s, len, ret, BIG, SIGNED);
543
0
}
544
545
static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen,
546
                     endianness_t endianness, signedness_t signedness)
547
17.2k
{
548
17.2k
    int inc;
549
17.2k
    int n, n8;
550
17.2k
    int xor = 0, carry = 0, ext = 0;
551
17.2k
    size_t i, lasti, j, atop, mask;
552
17.2k
    BN_ULONG l;
553
554
    /*
555
     * In case |a| is fixed-top, BN_num_bits can return bogus length,
556
     * but it's assumed that fixed-top inputs ought to be "nominated"
557
     * even for padded output, so it works out...
558
     */
559
17.2k
    n8 = BN_num_bits(a);
560
17.2k
    n = (n8 + 7) / 8;           /* This is what BN_num_bytes() does */
561
562
    /* Take note of the signedness of the bignum */
563
17.2k
    if (signedness == SIGNED) {
564
0
        xor = a->neg ? 0xff : 0x00;
565
0
        carry = a->neg;
566
567
        /*
568
         * if |n * 8 == n|, then the MSbit is set, otherwise unset.
569
         * We must compensate with one extra byte if that doesn't
570
         * correspond to the signedness of the bignum with regards
571
         * to 2's complement.
572
         */
573
0
        ext = (n * 8 == n8)
574
0
            ? !a->neg            /* MSbit set on nonnegative bignum */
575
0
            : a->neg;            /* MSbit unset on negative bignum */
576
0
    }
577
578
17.2k
    if (tolen == -1) {
579
16.0k
        tolen = n + ext;
580
16.0k
    } else if (tolen < n + ext) { /* uncommon/unlike case */
581
16
        BIGNUM temp = *a;
582
583
16
        bn_correct_top(&temp);
584
16
        n8 = BN_num_bits(&temp);
585
16
        n = (n8 + 7) / 8;       /* This is what BN_num_bytes() does */
586
16
        if (tolen < n + ext)
587
16
            return -1;
588
16
    }
589
590
    /* Swipe through whole available data and don't give away padded zero. */
591
17.2k
    atop = a->dmax * BN_BYTES;
592
17.2k
    if (atop == 0) {
593
2.16k
        if (tolen != 0)
594
61
            memset(to, '\0', tolen);
595
2.16k
        return tolen;
596
2.16k
    }
597
598
    /*
599
     * The loop that does the work iterates from least significant
600
     * to most significant BIGNUM limb, so we adapt parameters to
601
     * transfer output bytes accordingly.
602
     */
603
15.0k
    if (endianness == LITTLE) {
604
0
        inc = 1;
605
15.0k
    } else {
606
15.0k
        inc = -1;
607
15.0k
        to += tolen - 1;         /* Move to the last byte, not beyond */
608
15.0k
    }
609
610
15.0k
    lasti = atop - 1;
611
15.0k
    atop = a->top * BN_BYTES;
612
2.26M
    for (i = 0, j = 0; j < (size_t)tolen; j++) {
613
2.24M
        unsigned char byte, byte_xored;
614
615
2.24M
        l = a->d[i / BN_BYTES];
616
2.24M
        mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
617
2.24M
        byte = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
618
2.24M
        byte_xored = byte ^ xor;
619
2.24M
        *to = (unsigned char)(byte_xored + carry);
620
2.24M
        carry = byte_xored > *to; /* Implicit 1 or 0 */
621
2.24M
        to += inc;
622
2.24M
        i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
623
2.24M
    }
624
625
15.0k
    return tolen;
626
17.2k
}
627
628
int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
629
1.21k
{
630
1.21k
    if (tolen < 0)
631
0
        return -1;
632
1.21k
    return bn2binpad(a, to, tolen, BIG, UNSIGNED);
633
1.21k
}
634
635
int BN_signed_bn2bin(const BIGNUM *a, unsigned char *to, int tolen)
636
0
{
637
0
    if (tolen < 0)
638
0
        return -1;
639
0
    return bn2binpad(a, to, tolen, BIG, SIGNED);
640
0
}
641
642
int BN_bn2bin(const BIGNUM *a, unsigned char *to)
643
21.0k
{
644
21.0k
    return bn2binpad(a, to, -1, BIG, UNSIGNED);
645
21.0k
}
646
647
BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
648
0
{
649
0
    return bin2bn(s, len, ret, LITTLE, UNSIGNED);
650
0
}
651
652
BIGNUM *BN_signed_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
653
0
{
654
0
    return bin2bn(s, len, ret, LITTLE, SIGNED);
655
0
}
656
657
int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
658
0
{
659
0
    if (tolen < 0)
660
0
        return -1;
661
0
    return bn2binpad(a, to, tolen, LITTLE, UNSIGNED);
662
0
}
663
664
int BN_signed_bn2lebin(const BIGNUM *a, unsigned char *to, int tolen)
665
0
{
666
0
    if (tolen < 0)
667
0
        return -1;
668
0
    return bn2binpad(a, to, tolen, LITTLE, SIGNED);
669
0
}
670
671
BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret)
672
0
{
673
0
    DECLARE_IS_ENDIAN;
674
675
0
    if (IS_LITTLE_ENDIAN)
676
0
        return BN_lebin2bn(s, len, ret);
677
0
    return BN_bin2bn(s, len, ret);
678
0
}
679
680
BIGNUM *BN_signed_native2bn(const unsigned char *s, int len, BIGNUM *ret)
681
0
{
682
0
    DECLARE_IS_ENDIAN;
683
684
0
    if (IS_LITTLE_ENDIAN)
685
0
        return BN_signed_lebin2bn(s, len, ret);
686
0
    return BN_signed_bin2bn(s, len, ret);
687
0
}
688
689
int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen)
690
0
{
691
0
    DECLARE_IS_ENDIAN;
692
693
0
    if (IS_LITTLE_ENDIAN)
694
0
        return BN_bn2lebinpad(a, to, tolen);
695
0
    return BN_bn2binpad(a, to, tolen);
696
0
}
697
698
int BN_signed_bn2native(const BIGNUM *a, unsigned char *to, int tolen)
699
0
{
700
0
    DECLARE_IS_ENDIAN;
701
702
0
    if (IS_LITTLE_ENDIAN)
703
0
        return BN_signed_bn2lebin(a, to, tolen);
704
0
    return BN_signed_bn2bin(a, to, tolen);
705
0
}
706
707
int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
708
12.5M
{
709
12.5M
    int i;
710
12.5M
    BN_ULONG t1, t2, *ap, *bp;
711
712
12.5M
    ap = a->d;
713
12.5M
    bp = b->d;
714
715
12.5M
    if (BN_get_flags(a, BN_FLG_CONSTTIME)
716
12.5M
            && a->top == b->top) {
717
448k
        int res = 0;
718
719
4.16M
        for (i = 0; i < b->top; i++) {
720
3.71M
            res = constant_time_select_int(constant_time_lt_bn(ap[i], bp[i]),
721
3.71M
                                           -1, res);
722
3.71M
            res = constant_time_select_int(constant_time_lt_bn(bp[i], ap[i]),
723
3.71M
                                           1, res);
724
3.71M
        }
725
448k
        return res;
726
448k
    }
727
728
12.1M
    bn_check_top(a);
729
12.1M
    bn_check_top(b);
730
731
12.1M
    i = a->top - b->top;
732
12.1M
    if (i != 0)
733
3.60M
        return i;
734
735
8.63M
    for (i = a->top - 1; i >= 0; i--) {
736
8.60M
        t1 = ap[i];
737
8.60M
        t2 = bp[i];
738
8.60M
        if (t1 != t2)
739
8.48M
            return ((t1 > t2) ? 1 : -1);
740
8.60M
    }
741
39.1k
    return 0;
742
8.52M
}
743
744
int BN_cmp(const BIGNUM *a, const BIGNUM *b)
745
2.20M
{
746
2.20M
    int i;
747
2.20M
    int gt, lt;
748
2.20M
    BN_ULONG t1, t2;
749
750
2.20M
    if ((a == NULL) || (b == NULL)) {
751
0
        if (a != NULL)
752
0
            return -1;
753
0
        else if (b != NULL)
754
0
            return 1;
755
0
        else
756
0
            return 0;
757
0
    }
758
759
2.20M
    bn_check_top(a);
760
2.20M
    bn_check_top(b);
761
762
2.20M
    if (a->neg != b->neg) {
763
0
        if (a->neg)
764
0
            return -1;
765
0
        else
766
0
            return 1;
767
0
    }
768
2.20M
    if (a->neg == 0) {
769
2.20M
        gt = 1;
770
2.20M
        lt = -1;
771
2.20M
    } else {
772
0
        gt = -1;
773
0
        lt = 1;
774
0
    }
775
776
2.20M
    if (a->top > b->top)
777
794k
        return gt;
778
1.40M
    if (a->top < b->top)
779
38.7k
        return lt;
780
1.71M
    for (i = a->top - 1; i >= 0; i--) {
781
1.68M
        t1 = a->d[i];
782
1.68M
        t2 = b->d[i];
783
1.68M
        if (t1 > t2)
784
407k
            return gt;
785
1.27M
        if (t1 < t2)
786
922k
            return lt;
787
1.27M
    }
788
37.0k
    return 0;
789
1.36M
}
790
791
int BN_set_bit(BIGNUM *a, int n)
792
66.6k
{
793
66.6k
    int i, j, k;
794
795
66.6k
    if (n < 0)
796
0
        return 0;
797
798
66.6k
    i = n / BN_BITS2;
799
66.6k
    j = n % BN_BITS2;
800
66.6k
    if (a->top <= i) {
801
66.6k
        if (bn_wexpand(a, i + 1) == NULL)
802
0
            return 0;
803
1.05M
        for (k = a->top; k < i + 1; k++)
804
991k
            a->d[k] = 0;
805
66.6k
        a->top = i + 1;
806
66.6k
        a->flags &= ~BN_FLG_FIXED_TOP;
807
66.6k
    }
808
809
66.6k
    a->d[i] |= (((BN_ULONG)1) << j);
810
66.6k
    bn_check_top(a);
811
66.6k
    return 1;
812
66.6k
}
813
814
int BN_clear_bit(BIGNUM *a, int n)
815
106
{
816
106
    int i, j;
817
818
106
    bn_check_top(a);
819
106
    if (n < 0)
820
0
        return 0;
821
822
106
    i = n / BN_BITS2;
823
106
    j = n % BN_BITS2;
824
106
    if (a->top <= i)
825
0
        return 0;
826
827
106
    a->d[i] &= (~(((BN_ULONG)1) << j));
828
106
    bn_correct_top(a);
829
106
    return 1;
830
106
}
831
832
int BN_is_bit_set(const BIGNUM *a, int n)
833
71.3M
{
834
71.3M
    int i, j;
835
836
71.3M
    bn_check_top(a);
837
71.3M
    if (n < 0)
838
182
        return 0;
839
71.3M
    i = n / BN_BITS2;
840
71.3M
    j = n % BN_BITS2;
841
71.3M
    if (a->top <= i)
842
171k
        return 0;
843
71.2M
    return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
844
71.3M
}
845
846
int ossl_bn_mask_bits_fixed_top(BIGNUM *a, int n)
847
134k
{
848
134k
    int b, w;
849
850
134k
    if (n < 0)
851
0
        return 0;
852
853
134k
    w = n / BN_BITS2;
854
134k
    b = n % BN_BITS2;
855
134k
    if (w >= a->top)
856
0
        return 0;
857
134k
    if (b == 0)
858
245
        a->top = w;
859
134k
    else {
860
134k
        a->top = w + 1;
861
134k
        a->d[w] &= ~(BN_MASK2 << b);
862
134k
    }
863
134k
    a->flags |= BN_FLG_FIXED_TOP;
864
134k
    return 1;
865
134k
}
866
867
int BN_mask_bits(BIGNUM *a, int n)
868
134k
{
869
134k
    int ret;
870
871
134k
    bn_check_top(a);
872
134k
    ret = ossl_bn_mask_bits_fixed_top(a, n);
873
134k
    if (ret)
874
134k
        bn_correct_top(a);
875
134k
    return ret;
876
134k
}
877
878
void BN_set_negative(BIGNUM *a, int b)
879
4.27k
{
880
4.27k
    if (b && !BN_is_zero(a))
881
132
        a->neg = 1;
882
4.13k
    else
883
4.13k
        a->neg = 0;
884
4.27k
}
885
886
int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
887
91.8M
{
888
91.8M
    int i;
889
91.8M
    BN_ULONG aa, bb;
890
891
91.8M
    if (n == 0)
892
0
        return 0;
893
894
91.8M
    aa = a[n - 1];
895
91.8M
    bb = b[n - 1];
896
91.8M
    if (aa != bb)
897
91.1M
        return ((aa > bb) ? 1 : -1);
898
6.57M
    for (i = n - 2; i >= 0; i--) {
899
6.19M
        aa = a[i];
900
6.19M
        bb = b[i];
901
6.19M
        if (aa != bb)
902
333k
            return ((aa > bb) ? 1 : -1);
903
6.19M
    }
904
379k
    return 0;
905
712k
}
906
907
/*
908
 * Here follows a specialised variants of bn_cmp_words().  It has the
909
 * capability of performing the operation on arrays of different sizes. The
910
 * sizes of those arrays is expressed through cl, which is the common length
911
 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
912
 * two lengths, calculated as len(a)-len(b). All lengths are the number of
913
 * BN_ULONGs...
914
 */
915
916
int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
917
35.4M
{
918
35.4M
    int n, i;
919
35.4M
    n = cl - 1;
920
921
35.4M
    if (dl < 0) {
922
1.11M
        for (i = dl; i < 0; i++) {
923
1.10M
            if (b[n - i] != 0)
924
975k
                return -1;      /* a < b */
925
1.10M
        }
926
987k
    }
927
34.4M
    if (dl > 0) {
928
1.12M
        for (i = dl; i > 0; i--) {
929
1.10M
            if (a[n + i] != 0)
930
976k
                return 1;       /* a > b */
931
1.10M
        }
932
988k
    }
933
33.4M
    return bn_cmp_words(a, b, cl);
934
34.4M
}
935
936
/*-
937
 * Constant-time conditional swap of a and b.
938
 * a and b are swapped if condition is not 0.
939
 * nwords is the number of words to swap.
940
 * Assumes that at least nwords are allocated in both a and b.
941
 * Assumes that no more than nwords are used by either a or b.
942
 */
943
void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
944
2.23M
{
945
2.23M
    BN_ULONG t;
946
2.23M
    int i;
947
948
2.23M
    bn_wcheck_size(a, nwords);
949
2.23M
    bn_wcheck_size(b, nwords);
950
951
2.23M
    condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1;
952
953
2.23M
    t = (a->top ^ b->top) & condition;
954
2.23M
    a->top ^= t;
955
2.23M
    b->top ^= t;
956
957
2.23M
    t = (a->neg ^ b->neg) & condition;
958
2.23M
    a->neg ^= t;
959
2.23M
    b->neg ^= t;
960
961
    /*-
962
     * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention
963
     * is actually to treat it as it's read-only data, and some (if not most)
964
     * of it does reside in read-only segment. In other words observation of
965
     * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal
966
     * condition. It would either cause SEGV or effectively cause data
967
     * corruption.
968
     *
969
     * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be
970
     * preserved.
971
     *
972
     * BN_FLG_SECURE: must be preserved, because it determines how x->d was
973
     * allocated and hence how to free it.
974
     *
975
     * BN_FLG_CONSTTIME: sufficient to mask and swap
976
     *
977
     * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on
978
     * the data, so the d array may be padded with additional 0 values (i.e.
979
     * top could be greater than the minimal value that it could be). We should
980
     * be swapping it
981
     */
982
983
2.23M
#define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP)
984
985
2.23M
    t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition;
986
2.23M
    a->flags ^= t;
987
2.23M
    b->flags ^= t;
988
989
    /* conditionally swap the data */
990
70.4M
    for (i = 0; i < nwords; i++) {
991
68.2M
        t = (a->d[i] ^ b->d[i]) & condition;
992
68.2M
        a->d[i] ^= t;
993
68.2M
        b->d[i] ^= t;
994
68.2M
    }
995
2.23M
}
996
997
#undef BN_CONSTTIME_SWAP_FLAGS
998
999
/* Bits of security, see SP800-57 */
1000
1001
int BN_security_bits(int L, int N)
1002
0
{
1003
0
    int secbits, bits;
1004
0
    if (L >= 15360)
1005
0
        secbits = 256;
1006
0
    else if (L >= 7680)
1007
0
        secbits = 192;
1008
0
    else if (L >= 3072)
1009
0
        secbits = 128;
1010
0
    else if (L >= 2048)
1011
0
        secbits = 112;
1012
0
    else if (L >= 1024)
1013
0
        secbits = 80;
1014
0
    else
1015
0
        return 0;
1016
0
    if (N == -1)
1017
0
        return secbits;
1018
0
    bits = N / 2;
1019
0
    if (bits < 80)
1020
0
        return 0;
1021
0
    return bits >= secbits ? secbits : bits;
1022
0
}
1023
1024
void BN_zero_ex(BIGNUM *a)
1025
107M
{
1026
107M
    a->neg = 0;
1027
107M
    a->top = 0;
1028
107M
    a->flags &= ~BN_FLG_FIXED_TOP;
1029
107M
}
1030
1031
int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
1032
1.10M
{
1033
1.10M
    return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
1034
1.10M
}
1035
1036
int BN_is_zero(const BIGNUM *a)
1037
11.9M
{
1038
11.9M
    return a->top == 0;
1039
11.9M
}
1040
1041
int BN_is_one(const BIGNUM *a)
1042
498k
{
1043
498k
    return BN_abs_is_word(a, 1) && !a->neg;
1044
498k
}
1045
1046
int BN_is_word(const BIGNUM *a, const BN_ULONG w)
1047
567k
{
1048
567k
    return BN_abs_is_word(a, w) && (!w || !a->neg);
1049
567k
}
1050
1051
int ossl_bn_is_word_fixed_top(const BIGNUM *a, const BN_ULONG w)
1052
462
{
1053
462
    int res, i;
1054
462
    const BN_ULONG *ap = a->d;
1055
1056
462
    if (a->neg || a->top == 0)
1057
0
        return 0;
1058
1059
462
    res = constant_time_select_int(constant_time_eq_bn(ap[0], w), 1, 0);
1060
1061
6.42k
    for (i = 1; i < a->top; i++)
1062
5.96k
        res = constant_time_select_int(constant_time_is_zero_bn(ap[i]),
1063
5.96k
                                       res, 0);
1064
462
    return res;
1065
462
}
1066
1067
int BN_is_odd(const BIGNUM *a)
1068
2.66M
{
1069
2.66M
    return (a->top > 0) && (a->d[0] & 1);
1070
2.66M
}
1071
1072
int BN_is_negative(const BIGNUM *a)
1073
2.17M
{
1074
2.17M
    return (a->neg != 0);
1075
2.17M
}
1076
1077
int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
1078
                     BN_CTX *ctx)
1079
22.7k
{
1080
22.7k
    return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
1081
22.7k
}
1082
1083
void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
1084
176k
{
1085
176k
    dest->d = b->d;
1086
176k
    dest->top = b->top;
1087
176k
    dest->dmax = b->dmax;
1088
176k
    dest->neg = b->neg;
1089
176k
    dest->flags = ((dest->flags & BN_FLG_MALLOCED)
1090
176k
                   | (b->flags & ~BN_FLG_MALLOCED)
1091
176k
                   | BN_FLG_STATIC_DATA | flags);
1092
176k
}
1093
1094
BN_GENCB *BN_GENCB_new(void)
1095
0
{
1096
0
    BN_GENCB *ret;
1097
1098
0
    if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
1099
0
        return NULL;
1100
1101
0
    return ret;
1102
0
}
1103
1104
void BN_GENCB_free(BN_GENCB *cb)
1105
0
{
1106
0
    if (cb == NULL)
1107
0
        return;
1108
0
    OPENSSL_free(cb);
1109
0
}
1110
1111
void BN_set_flags(BIGNUM *b, int n)
1112
53.6k
{
1113
53.6k
    b->flags |= n;
1114
53.6k
}
1115
1116
int BN_get_flags(const BIGNUM *b, int n)
1117
18.8M
{
1118
18.8M
    return b->flags & n;
1119
18.8M
}
1120
1121
/* Populate a BN_GENCB structure with an "old"-style callback */
1122
void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
1123
                      void *cb_arg)
1124
0
{
1125
0
    BN_GENCB *tmp_gencb = gencb;
1126
0
    tmp_gencb->ver = 1;
1127
0
    tmp_gencb->arg = cb_arg;
1128
0
    tmp_gencb->cb.cb_1 = callback;
1129
0
}
1130
1131
/* Populate a BN_GENCB structure with a "new"-style callback */
1132
void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1133
                  void *cb_arg)
1134
0
{
1135
0
    BN_GENCB *tmp_gencb = gencb;
1136
0
    tmp_gencb->ver = 2;
1137
0
    tmp_gencb->arg = cb_arg;
1138
0
    tmp_gencb->cb.cb_2 = callback;
1139
0
}
1140
1141
void *BN_GENCB_get_arg(BN_GENCB *cb)
1142
0
{
1143
0
    return cb->arg;
1144
0
}
1145
1146
BIGNUM *bn_wexpand(BIGNUM *a, int words)
1147
241M
{
1148
241M
    return (words <= a->dmax) ? a : bn_expand2(a, words);
1149
241M
}
1150
1151
void bn_correct_top_consttime(BIGNUM *a)
1152
0
{
1153
0
    int j, atop;
1154
0
    BN_ULONG limb;
1155
0
    unsigned int mask;
1156
1157
0
    for (j = 0, atop = 0; j < a->dmax; j++) {
1158
0
        limb = a->d[j];
1159
0
        limb |= 0 - limb;
1160
0
        limb >>= BN_BITS2 - 1;
1161
0
        limb = 0 - limb;
1162
0
        mask = (unsigned int)limb;
1163
0
        mask &= constant_time_msb(j - a->top);
1164
0
        atop = constant_time_select_int(mask, j + 1, atop);
1165
0
    }
1166
1167
0
    mask = constant_time_eq_int(atop, 0);
1168
0
    a->top = atop;
1169
0
    a->neg = constant_time_select_int(mask, 0, a->neg);
1170
0
    a->flags &= ~BN_FLG_FIXED_TOP;
1171
0
}
1172
1173
void bn_correct_top(BIGNUM *a)
1174
21.6M
{
1175
21.6M
    BN_ULONG *ftl;
1176
21.6M
    int tmp_top = a->top;
1177
1178
21.6M
    if (tmp_top > 0) {
1179
29.1M
        for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
1180
29.0M
            ftl--;
1181
29.0M
            if (*ftl != 0)
1182
21.5M
                break;
1183
29.0M
        }
1184
21.6M
        a->top = tmp_top;
1185
21.6M
    }
1186
21.6M
    if (a->top == 0)
1187
107k
        a->neg = 0;
1188
21.6M
    a->flags &= ~BN_FLG_FIXED_TOP;
1189
21.6M
    bn_pollute(a);
1190
21.6M
}