Coverage Report

Created: 2024-11-21 07:03

/src/boringssl/crypto/fipsmodule/bn/bn.c.inc
Line
Count
Source (jump to first uncovered line)
1
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2
 * All rights reserved.
3
 *
4
 * This package is an SSL implementation written
5
 * by Eric Young (eay@cryptsoft.com).
6
 * The implementation was written so as to conform with Netscapes SSL.
7
 *
8
 * This library is free for commercial and non-commercial use as long as
9
 * the following conditions are aheared to.  The following conditions
10
 * apply to all code found in this distribution, be it the RC4, RSA,
11
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
12
 * included with this distribution is covered by the same copyright terms
13
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14
 *
15
 * Copyright remains Eric Young's, and as such any Copyright notices in
16
 * the code are not to be removed.
17
 * If this package is used in a product, Eric Young should be given attribution
18
 * as the author of the parts of the library used.
19
 * This can be in the form of a textual message at program startup or
20
 * in documentation (online or textual) provided with the package.
21
 *
22
 * Redistribution and use in source and binary forms, with or without
23
 * modification, are permitted provided that the following conditions
24
 * are met:
25
 * 1. Redistributions of source code must retain the copyright
26
 *    notice, this list of conditions and the following disclaimer.
27
 * 2. Redistributions in binary form must reproduce the above copyright
28
 *    notice, this list of conditions and the following disclaimer in the
29
 *    documentation and/or other materials provided with the distribution.
30
 * 3. All advertising materials mentioning features or use of this software
31
 *    must display the following acknowledgement:
32
 *    "This product includes cryptographic software written by
33
 *     Eric Young (eay@cryptsoft.com)"
34
 *    The word 'cryptographic' can be left out if the rouines from the library
35
 *    being used are not cryptographic related :-).
36
 * 4. If you include any Windows specific code (or a derivative thereof) from
37
 *    the apps directory (application code) you must include an acknowledgement:
38
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39
 *
40
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50
 * SUCH DAMAGE.
51
 *
52
 * The licence and distribution terms for any publically available version or
53
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
54
 * copied and put under another distribution licence
55
 * [including the GNU Public Licence.] */
56
57
#include <openssl/bn.h>
58
59
#include <assert.h>
60
#include <limits.h>
61
#include <string.h>
62
63
#include <openssl/err.h>
64
#include <openssl/mem.h>
65
66
#include "internal.h"
67
#include "../delocate.h"
68
69
70
// BN_MAX_WORDS is the maximum number of words allowed in a |BIGNUM|. It is
71
// sized so byte and bit counts of a |BIGNUM| always fit in |int|, with room to
72
// spare.
73
228k
#define BN_MAX_WORDS (INT_MAX / (4 * BN_BITS2))
74
75
302k
BIGNUM *BN_new(void) {
76
302k
  BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM));
77
78
302k
  if (bn == NULL) {
79
0
    return NULL;
80
0
  }
81
82
302k
  OPENSSL_memset(bn, 0, sizeof(BIGNUM));
83
302k
  bn->flags = BN_FLG_MALLOCED;
84
85
302k
  return bn;
86
302k
}
87
88
BIGNUM *BN_secure_new(void) { return BN_new(); }
89
90
2.25k
void BN_init(BIGNUM *bn) {
91
2.25k
  OPENSSL_memset(bn, 0, sizeof(BIGNUM));
92
2.25k
}
93
94
69.8k
void BN_free(BIGNUM *bn) {
95
69.8k
  if (bn == NULL) {
96
26.1k
    return;
97
26.1k
  }
98
99
43.6k
  if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
100
43.6k
    OPENSSL_free(bn->d);
101
43.6k
  }
102
103
43.6k
  if (bn->flags & BN_FLG_MALLOCED) {
104
41.4k
    OPENSSL_free(bn);
105
41.4k
  } else {
106
2.23k
    bn->d = NULL;
107
2.23k
  }
108
43.6k
}
109
110
1.01k
void BN_clear_free(BIGNUM *bn) {
111
1.01k
  BN_free(bn);
112
1.01k
}
113
114
3.18k
BIGNUM *BN_dup(const BIGNUM *src) {
115
3.18k
  BIGNUM *copy;
116
117
3.18k
  if (src == NULL) {
118
0
    return NULL;
119
0
  }
120
121
3.18k
  copy = BN_new();
122
3.18k
  if (copy == NULL) {
123
0
    return NULL;
124
0
  }
125
126
3.18k
  if (!BN_copy(copy, src)) {
127
0
    BN_free(copy);
128
0
    return NULL;
129
0
  }
130
131
3.18k
  return copy;
132
3.18k
}
133
134
24.1k
BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) {
135
24.1k
  if (src == dest) {
136
850
    return dest;
137
850
  }
138
139
23.3k
  if (!bn_wexpand(dest, src->width)) {
140
0
    return NULL;
141
0
  }
142
143
23.3k
  OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->width);
144
145
23.3k
  dest->width = src->width;
146
23.3k
  dest->neg = src->neg;
147
23.3k
  return dest;
148
23.3k
}
149
150
void BN_clear(BIGNUM *bn) {
151
  if (bn->d != NULL) {
152
    OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0]));
153
  }
154
155
  bn->width = 0;
156
  bn->neg = 0;
157
}
158
159
2
DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) {
160
2
  static const BN_ULONG kOneLimbs[1] = { 1 };
161
2
  out->d = (BN_ULONG*) kOneLimbs;
162
2
  out->width = 1;
163
2
  out->dmax = 1;
164
2
  out->neg = 0;
165
2
  out->flags = BN_FLG_STATIC_DATA;
166
2
}
167
168
// BN_num_bits_word returns the minimum number of bits needed to represent the
169
// value in |l|.
170
56.0M
unsigned BN_num_bits_word(BN_ULONG l) {
171
  // |BN_num_bits| is often called on RSA prime factors. These have public bit
172
  // lengths, but all bits beyond the high bit are secret, so count bits in
173
  // constant time.
174
56.0M
  BN_ULONG x, mask;
175
56.0M
  int bits = (l != 0);
176
177
56.0M
#if BN_BITS2 > 32
178
  // Look at the upper half of |x|. |x| is at most 64 bits long.
179
56.0M
  x = l >> 32;
180
  // Set |mask| to all ones if |x| (the top 32 bits of |l|) is non-zero and all
181
  // all zeros otherwise.
182
56.0M
  mask = 0u - x;
183
56.0M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
184
  // If |x| is non-zero, the lower half is included in the bit count in full,
185
  // and we count the upper half. Otherwise, we count the lower half.
186
56.0M
  bits += 32 & mask;
187
56.0M
  l ^= (x ^ l) & mask;  // |l| is |x| if |mask| and remains |l| otherwise.
188
56.0M
#endif
189
190
  // The remaining blocks are analogous iterations at lower powers of two.
191
56.0M
  x = l >> 16;
192
56.0M
  mask = 0u - x;
193
56.0M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
194
56.0M
  bits += 16 & mask;
195
56.0M
  l ^= (x ^ l) & mask;
196
197
56.0M
  x = l >> 8;
198
56.0M
  mask = 0u - x;
199
56.0M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
200
56.0M
  bits += 8 & mask;
201
56.0M
  l ^= (x ^ l) & mask;
202
203
56.0M
  x = l >> 4;
204
56.0M
  mask = 0u - x;
205
56.0M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
206
56.0M
  bits += 4 & mask;
207
56.0M
  l ^= (x ^ l) & mask;
208
209
56.0M
  x = l >> 2;
210
56.0M
  mask = 0u - x;
211
56.0M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
212
56.0M
  bits += 2 & mask;
213
56.0M
  l ^= (x ^ l) & mask;
214
215
56.0M
  x = l >> 1;
216
56.0M
  mask = 0u - x;
217
56.0M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
218
56.0M
  bits += 1 & mask;
219
220
56.0M
  return bits;
221
56.0M
}
222
223
422k
unsigned BN_num_bits(const BIGNUM *bn) {
224
422k
  const int width = bn_minimal_width(bn);
225
422k
  if (width == 0) {
226
5.01k
    return 0;
227
5.01k
  }
228
229
417k
  return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]);
230
422k
}
231
232
14.9k
unsigned BN_num_bytes(const BIGNUM *bn) {
233
14.9k
  return (BN_num_bits(bn) + 7) / 8;
234
14.9k
}
235
236
6.97M
void BN_zero(BIGNUM *bn) {
237
6.97M
  bn->width = bn->neg = 0;
238
6.97M
}
239
240
364
int BN_one(BIGNUM *bn) {
241
364
  return BN_set_word(bn, 1);
242
364
}
243
244
9.51k
int BN_set_word(BIGNUM *bn, BN_ULONG value) {
245
9.51k
  if (value == 0) {
246
1
    BN_zero(bn);
247
1
    return 1;
248
1
  }
249
250
9.51k
  if (!bn_wexpand(bn, 1)) {
251
0
    return 0;
252
0
  }
253
254
9.51k
  bn->neg = 0;
255
9.51k
  bn->d[0] = value;
256
9.51k
  bn->width = 1;
257
9.51k
  return 1;
258
9.51k
}
259
260
0
int BN_set_u64(BIGNUM *bn, uint64_t value) {
261
0
#if BN_BITS2 == 64
262
0
  return BN_set_word(bn, value);
263
#elif BN_BITS2 == 32
264
  if (value <= BN_MASK2) {
265
    return BN_set_word(bn, (BN_ULONG)value);
266
  }
267
268
  if (!bn_wexpand(bn, 2)) {
269
    return 0;
270
  }
271
272
  bn->neg = 0;
273
  bn->d[0] = (BN_ULONG)value;
274
  bn->d[1] = (BN_ULONG)(value >> 32);
275
  bn->width = 2;
276
  return 1;
277
#else
278
#error "BN_BITS2 must be 32 or 64."
279
#endif
280
0
}
281
282
48
int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
283
48
  if (!bn_wexpand(bn, num)) {
284
0
    return 0;
285
0
  }
286
48
  OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG));
287
  // |bn_wexpand| verified that |num| isn't too large.
288
48
  bn->width = (int)num;
289
48
  bn->neg = 0;
290
48
  return 1;
291
48
}
292
293
32
void bn_set_static_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
294
32
  if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
295
32
    OPENSSL_free(bn->d);
296
32
  }
297
32
  bn->d = (BN_ULONG *)words;
298
299
32
  assert(num <= BN_MAX_WORDS);
300
32
  bn->width = (int)num;
301
32
  bn->dmax = (int)num;
302
32
  bn->neg = 0;
303
32
  bn->flags |= BN_FLG_STATIC_DATA;
304
32
}
305
306
937k
int bn_fits_in_words(const BIGNUM *bn, size_t num) {
307
  // All words beyond |num| must be zero.
308
937k
  BN_ULONG mask = 0;
309
43.3M
  for (size_t i = num; i < (size_t)bn->width; i++) {
310
42.4M
    mask |= bn->d[i];
311
42.4M
  }
312
937k
  return mask == 0;
313
937k
}
314
315
94.9k
int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) {
316
94.9k
  if (bn->neg) {
317
0
    OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
318
0
    return 0;
319
0
  }
320
321
94.9k
  size_t width = (size_t)bn->width;
322
94.9k
  if (width > num) {
323
35
    if (!bn_fits_in_words(bn, num)) {
324
31
      OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
325
31
      return 0;
326
31
    }
327
4
    width = num;
328
4
  }
329
330
94.8k
  OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num);
331
94.8k
  OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width);
332
94.8k
  return 1;
333
94.9k
}
334
335
2.17M
int BN_is_negative(const BIGNUM *bn) {
336
2.17M
  return bn->neg != 0;
337
2.17M
}
338
339
4.27k
void BN_set_negative(BIGNUM *bn, int sign) {
340
4.27k
  if (sign && !BN_is_zero(bn)) {
341
132
    bn->neg = 1;
342
4.13k
  } else {
343
4.13k
    bn->neg = 0;
344
4.13k
  }
345
4.27k
}
346
347
13.0M
int bn_wexpand(BIGNUM *bn, size_t words) {
348
13.0M
  BN_ULONG *a;
349
350
13.0M
  if (words <= (size_t)bn->dmax) {
351
12.8M
    return 1;
352
12.8M
  }
353
354
228k
  if (words > BN_MAX_WORDS) {
355
0
    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
356
0
    return 0;
357
0
  }
358
359
228k
  if (bn->flags & BN_FLG_STATIC_DATA) {
360
0
    OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
361
0
    return 0;
362
0
  }
363
364
228k
  a = OPENSSL_calloc(words, sizeof(BN_ULONG));
365
228k
  if (a == NULL) {
366
0
    return 0;
367
0
  }
368
369
228k
  OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->width);
370
371
228k
  OPENSSL_free(bn->d);
372
228k
  bn->d = a;
373
228k
  bn->dmax = (int)words;
374
375
228k
  return 1;
376
228k
}
377
378
0
int bn_expand(BIGNUM *bn, size_t bits) {
379
0
  if (bits + BN_BITS2 - 1 < bits) {
380
0
    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
381
0
    return 0;
382
0
  }
383
0
  return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
384
0
}
385
386
2.32M
int bn_resize_words(BIGNUM *bn, size_t words) {
387
2.32M
  if ((size_t)bn->width <= words) {
388
2.32M
    if (!bn_wexpand(bn, words)) {
389
0
      return 0;
390
0
    }
391
2.32M
    OPENSSL_memset(bn->d + bn->width, 0,
392
2.32M
                   (words - bn->width) * sizeof(BN_ULONG));
393
2.32M
    bn->width = (int)words;
394
2.32M
    return 1;
395
2.32M
  }
396
397
  // All words beyond the new width must be zero.
398
0
  if (!bn_fits_in_words(bn, words)) {
399
0
    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
400
0
    return 0;
401
0
  }
402
0
  bn->width = (int)words;
403
0
  return 1;
404
0
}
405
406
void bn_select_words(BN_ULONG *r, BN_ULONG mask, const BN_ULONG *a,
407
39.3M
                     const BN_ULONG *b, size_t num) {
408
975M
  for (size_t i = 0; i < num; i++) {
409
936M
    static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
410
936M
                  "crypto_word_t is too small");
411
936M
    r[i] = constant_time_select_w(mask, a[i], b[i]);
412
936M
  }
413
39.3M
}
414
415
3.58M
int bn_minimal_width(const BIGNUM *bn) {
416
3.58M
  int ret = bn->width;
417
55.1M
  while (ret > 0 && bn->d[ret - 1] == 0) {
418
51.5M
    ret--;
419
51.5M
  }
420
3.58M
  return ret;
421
3.58M
}
422
423
3.15M
void bn_set_minimal_width(BIGNUM *bn) {
424
3.15M
  bn->width = bn_minimal_width(bn);
425
3.15M
  if (bn->width == 0) {
426
4.82k
    bn->neg = 0;
427
4.82k
  }
428
3.15M
}