Coverage Report

Created: 2024-11-21 06:47

/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
4.47M
#define BN_MAX_WORDS (INT_MAX / (4 * BN_BITS2))
74
75
3.85M
BIGNUM *BN_new(void) {
76
3.85M
  BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM));
77
78
3.85M
  if (bn == NULL) {
79
0
    return NULL;
80
0
  }
81
82
3.85M
  OPENSSL_memset(bn, 0, sizeof(BIGNUM));
83
3.85M
  bn->flags = BN_FLG_MALLOCED;
84
85
3.85M
  return bn;
86
3.85M
}
87
88
0
BIGNUM *BN_secure_new(void) { return BN_new(); }
89
90
13.2k
void BN_init(BIGNUM *bn) {
91
13.2k
  OPENSSL_memset(bn, 0, sizeof(BIGNUM));
92
13.2k
}
93
94
1.98M
void BN_free(BIGNUM *bn) {
95
1.98M
  if (bn == NULL) {
96
59.0k
    return;
97
59.0k
  }
98
99
1.92M
  if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
100
1.92M
    OPENSSL_free(bn->d);
101
1.92M
  }
102
103
1.92M
  if (bn->flags & BN_FLG_MALLOCED) {
104
1.91M
    OPENSSL_free(bn);
105
1.91M
  } else {
106
13.2k
    bn->d = NULL;
107
13.2k
  }
108
1.92M
}
109
110
void BN_clear_free(BIGNUM *bn) {
111
  BN_free(bn);
112
}
113
114
692k
BIGNUM *BN_dup(const BIGNUM *src) {
115
692k
  BIGNUM *copy;
116
117
692k
  if (src == NULL) {
118
0
    return NULL;
119
0
  }
120
121
692k
  copy = BN_new();
122
692k
  if (copy == NULL) {
123
0
    return NULL;
124
0
  }
125
126
692k
  if (!BN_copy(copy, src)) {
127
0
    BN_free(copy);
128
0
    return NULL;
129
0
  }
130
131
692k
  return copy;
132
692k
}
133
134
787k
BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) {
135
787k
  if (src == dest) {
136
3.58k
    return dest;
137
3.58k
  }
138
139
783k
  if (!bn_wexpand(dest, src->width)) {
140
0
    return NULL;
141
0
  }
142
143
783k
  OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->width);
144
145
783k
  dest->width = src->width;
146
783k
  dest->neg = src->neg;
147
783k
  return dest;
148
783k
}
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
79.2M
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
79.2M
  BN_ULONG x, mask;
175
79.2M
  int bits = (l != 0);
176
177
79.2M
#if BN_BITS2 > 32
178
  // Look at the upper half of |x|. |x| is at most 64 bits long.
179
79.2M
  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
79.2M
  mask = 0u - x;
183
79.2M
  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
79.2M
  bits += 32 & mask;
187
79.2M
  l ^= (x ^ l) & mask;  // |l| is |x| if |mask| and remains |l| otherwise.
188
79.2M
#endif
189
190
  // The remaining blocks are analogous iterations at lower powers of two.
191
79.2M
  x = l >> 16;
192
79.2M
  mask = 0u - x;
193
79.2M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
194
79.2M
  bits += 16 & mask;
195
79.2M
  l ^= (x ^ l) & mask;
196
197
79.2M
  x = l >> 8;
198
79.2M
  mask = 0u - x;
199
79.2M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
200
79.2M
  bits += 8 & mask;
201
79.2M
  l ^= (x ^ l) & mask;
202
203
79.2M
  x = l >> 4;
204
79.2M
  mask = 0u - x;
205
79.2M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
206
79.2M
  bits += 4 & mask;
207
79.2M
  l ^= (x ^ l) & mask;
208
209
79.2M
  x = l >> 2;
210
79.2M
  mask = 0u - x;
211
79.2M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
212
79.2M
  bits += 2 & mask;
213
79.2M
  l ^= (x ^ l) & mask;
214
215
79.2M
  x = l >> 1;
216
79.2M
  mask = 0u - x;
217
79.2M
  mask = (0u - (mask >> (BN_BITS2 - 1)));
218
79.2M
  bits += 1 & mask;
219
220
79.2M
  return bits;
221
79.2M
}
222
223
412k
unsigned BN_num_bits(const BIGNUM *bn) {
224
412k
  const int width = bn_minimal_width(bn);
225
412k
  if (width == 0) {
226
151
    return 0;
227
151
  }
228
229
412k
  return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]);
230
412k
}
231
232
3.05k
unsigned BN_num_bytes(const BIGNUM *bn) {
233
3.05k
  return (BN_num_bits(bn) + 7) / 8;
234
3.05k
}
235
236
5.25M
void BN_zero(BIGNUM *bn) {
237
5.25M
  bn->width = bn->neg = 0;
238
5.25M
}
239
240
2.76k
int BN_one(BIGNUM *bn) {
241
2.76k
  return BN_set_word(bn, 1);
242
2.76k
}
243
244
935k
int BN_set_word(BIGNUM *bn, BN_ULONG value) {
245
935k
  if (value == 0) {
246
5.21k
    BN_zero(bn);
247
5.21k
    return 1;
248
5.21k
  }
249
250
929k
  if (!bn_wexpand(bn, 1)) {
251
0
    return 0;
252
0
  }
253
254
929k
  bn->neg = 0;
255
929k
  bn->d[0] = value;
256
929k
  bn->width = 1;
257
929k
  return 1;
258
929k
}
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
5.29k
int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
283
5.29k
  if (!bn_wexpand(bn, num)) {
284
0
    return 0;
285
0
  }
286
5.29k
  OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG));
287
  // |bn_wexpand| verified that |num| isn't too large.
288
5.29k
  bn->width = (int)num;
289
5.29k
  bn->neg = 0;
290
5.29k
  return 1;
291
5.29k
}
292
293
0
void bn_set_static_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
294
0
  if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
295
0
    OPENSSL_free(bn->d);
296
0
  }
297
0
  bn->d = (BN_ULONG *)words;
298
299
0
  assert(num <= BN_MAX_WORDS);
300
0
  bn->width = (int)num;
301
0
  bn->dmax = (int)num;
302
0
  bn->neg = 0;
303
0
  bn->flags |= BN_FLG_STATIC_DATA;
304
0
}
305
306
11.5M
int bn_fits_in_words(const BIGNUM *bn, size_t num) {
307
  // All words beyond |num| must be zero.
308
11.5M
  BN_ULONG mask = 0;
309
46.7M
  for (size_t i = num; i < (size_t)bn->width; i++) {
310
35.1M
    mask |= bn->d[i];
311
35.1M
  }
312
11.5M
  return mask == 0;
313
11.5M
}
314
315
147k
int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) {
316
147k
  if (bn->neg) {
317
0
    OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
318
0
    return 0;
319
0
  }
320
321
147k
  size_t width = (size_t)bn->width;
322
147k
  if (width > num) {
323
0
    if (!bn_fits_in_words(bn, num)) {
324
0
      OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
325
0
      return 0;
326
0
    }
327
0
    width = num;
328
0
  }
329
330
147k
  OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num);
331
147k
  OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width);
332
147k
  return 1;
333
147k
}
334
335
1.55M
int BN_is_negative(const BIGNUM *bn) {
336
1.55M
  return bn->neg != 0;
337
1.55M
}
338
339
275k
void BN_set_negative(BIGNUM *bn, int sign) {
340
275k
  if (sign && !BN_is_zero(bn)) {
341
275k
    bn->neg = 1;
342
275k
  } else {
343
0
    bn->neg = 0;
344
0
  }
345
275k
}
346
347
17.1M
int bn_wexpand(BIGNUM *bn, size_t words) {
348
17.1M
  BN_ULONG *a;
349
350
17.1M
  if (words <= (size_t)bn->dmax) {
351
12.6M
    return 1;
352
12.6M
  }
353
354
4.47M
  if (words > BN_MAX_WORDS) {
355
0
    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
356
0
    return 0;
357
0
  }
358
359
4.47M
  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
4.47M
  a = OPENSSL_calloc(words, sizeof(BN_ULONG));
365
4.47M
  if (a == NULL) {
366
0
    return 0;
367
0
  }
368
369
4.47M
  OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->width);
370
371
4.47M
  OPENSSL_free(bn->d);
372
4.47M
  bn->d = a;
373
4.47M
  bn->dmax = (int)words;
374
375
4.47M
  return 1;
376
4.47M
}
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
1.54M
int bn_resize_words(BIGNUM *bn, size_t words) {
387
1.54M
  if ((size_t)bn->width <= words) {
388
1.54M
    if (!bn_wexpand(bn, words)) {
389
0
      return 0;
390
0
    }
391
1.54M
    OPENSSL_memset(bn->d + bn->width, 0,
392
1.54M
                   (words - bn->width) * sizeof(BN_ULONG));
393
1.54M
    bn->width = (int)words;
394
1.54M
    return 1;
395
1.54M
  }
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
14.5M
                     const BN_ULONG *b, size_t num) {
408
82.8M
  for (size_t i = 0; i < num; i++) {
409
68.2M
    static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
410
68.2M
                  "crypto_word_t is too small");
411
68.2M
    r[i] = constant_time_select_w(mask, a[i], b[i]);
412
68.2M
  }
413
14.5M
}
414
415
10.7M
int bn_minimal_width(const BIGNUM *bn) {
416
10.7M
  int ret = bn->width;
417
22.8M
  while (ret > 0 && bn->d[ret - 1] == 0) {
418
12.1M
    ret--;
419
12.1M
  }
420
10.7M
  return ret;
421
10.7M
}
422
423
10.2M
void bn_set_minimal_width(BIGNUM *bn) {
424
10.2M
  bn->width = bn_minimal_width(bn);
425
10.2M
  if (bn->width == 0) {
426
762k
    bn->neg = 0;
427
762k
  }
428
10.2M
}