/src/boringssl/crypto/fipsmodule/bn/random.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 | | /* ==================================================================== |
58 | | * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. |
59 | | * |
60 | | * Redistribution and use in source and binary forms, with or without |
61 | | * modification, are permitted provided that the following conditions |
62 | | * are met: |
63 | | * |
64 | | * 1. Redistributions of source code must retain the above copyright |
65 | | * notice, this list of conditions and the following disclaimer. |
66 | | * |
67 | | * 2. Redistributions in binary form must reproduce the above copyright |
68 | | * notice, this list of conditions and the following disclaimer in |
69 | | * the documentation and/or other materials provided with the |
70 | | * distribution. |
71 | | * |
72 | | * 3. All advertising materials mentioning features or use of this |
73 | | * software must display the following acknowledgment: |
74 | | * "This product includes software developed by the OpenSSL Project |
75 | | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
76 | | * |
77 | | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
78 | | * endorse or promote products derived from this software without |
79 | | * prior written permission. For written permission, please contact |
80 | | * openssl-core@openssl.org. |
81 | | * |
82 | | * 5. Products derived from this software may not be called "OpenSSL" |
83 | | * nor may "OpenSSL" appear in their names without prior written |
84 | | * permission of the OpenSSL Project. |
85 | | * |
86 | | * 6. Redistributions of any form whatsoever must retain the following |
87 | | * acknowledgment: |
88 | | * "This product includes software developed by the OpenSSL Project |
89 | | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
90 | | * |
91 | | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
92 | | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
93 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
94 | | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
95 | | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
96 | | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
97 | | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
98 | | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
99 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
100 | | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
101 | | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
102 | | * OF THE POSSIBILITY OF SUCH DAMAGE. |
103 | | * ==================================================================== |
104 | | * |
105 | | * This product includes cryptographic software written by Eric Young |
106 | | * (eay@cryptsoft.com). This product includes software written by Tim |
107 | | * Hudson (tjh@cryptsoft.com). */ |
108 | | |
109 | | #include <openssl/bn.h> |
110 | | |
111 | | #include <assert.h> |
112 | | #include <limits.h> |
113 | | #include <string.h> |
114 | | |
115 | | #include <openssl/err.h> |
116 | | |
117 | | #include "../../internal.h" |
118 | | #include "../bcm_interface.h" |
119 | | #include "../service_indicator/internal.h" |
120 | | #include "internal.h" |
121 | | |
122 | | |
123 | 8 | int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) { |
124 | 8 | if (rnd == NULL) { |
125 | 0 | return 0; |
126 | 0 | } |
127 | | |
128 | 8 | if (top != BN_RAND_TOP_ANY && top != BN_RAND_TOP_ONE && |
129 | 8 | top != BN_RAND_TOP_TWO) { |
130 | 8 | OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); |
131 | 8 | return 0; |
132 | 8 | } |
133 | | |
134 | 0 | if (bottom != BN_RAND_BOTTOM_ANY && bottom != BN_RAND_BOTTOM_ODD) { |
135 | 0 | OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); |
136 | 0 | return 0; |
137 | 0 | } |
138 | | |
139 | 0 | if (bits == 0) { |
140 | 0 | BN_zero(rnd); |
141 | 0 | return 1; |
142 | 0 | } |
143 | | |
144 | 0 | if (bits > INT_MAX - (BN_BITS2 - 1)) { |
145 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
146 | 0 | return 0; |
147 | 0 | } |
148 | | |
149 | 0 | int words = (bits + BN_BITS2 - 1) / BN_BITS2; |
150 | 0 | int bit = (bits - 1) % BN_BITS2; |
151 | 0 | const BN_ULONG kOne = 1; |
152 | 0 | const BN_ULONG kThree = 3; |
153 | 0 | BN_ULONG mask = bit < BN_BITS2 - 1 ? (kOne << (bit + 1)) - 1 : BN_MASK2; |
154 | 0 | if (!bn_wexpand(rnd, words)) { |
155 | 0 | return 0; |
156 | 0 | } |
157 | | |
158 | 0 | FIPS_service_indicator_lock_state(); |
159 | 0 | BCM_rand_bytes((uint8_t *)rnd->d, words * sizeof(BN_ULONG)); |
160 | 0 | FIPS_service_indicator_unlock_state(); |
161 | |
|
162 | 0 | rnd->d[words - 1] &= mask; |
163 | 0 | if (top != BN_RAND_TOP_ANY) { |
164 | 0 | if (top == BN_RAND_TOP_TWO && bits > 1) { |
165 | 0 | if (bit == 0) { |
166 | 0 | rnd->d[words - 1] |= 1; |
167 | 0 | rnd->d[words - 2] |= kOne << (BN_BITS2 - 1); |
168 | 0 | } else { |
169 | 0 | rnd->d[words - 1] |= kThree << (bit - 1); |
170 | 0 | } |
171 | 0 | } else { |
172 | 0 | rnd->d[words - 1] |= kOne << bit; |
173 | 0 | } |
174 | 0 | } |
175 | 0 | if (bottom == BN_RAND_BOTTOM_ODD) { |
176 | 0 | rnd->d[0] |= 1; |
177 | 0 | } |
178 | |
|
179 | 0 | rnd->neg = 0; |
180 | 0 | rnd->width = words; |
181 | 0 | return 1; |
182 | 0 | } |
183 | | |
184 | 8 | int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) { |
185 | 8 | return BN_rand(rnd, bits, top, bottom); |
186 | 8 | } |
187 | | |
188 | | // bn_less_than_word_mask returns a mask of all ones if the number represented |
189 | | // by |len| words at |a| is less than |b| and zero otherwise. It performs this |
190 | | // computation in time independent of the value of |a|. |b| is assumed public. |
191 | | static crypto_word_t bn_less_than_word_mask(const BN_ULONG *a, size_t len, |
192 | 7.95k | BN_ULONG b) { |
193 | 7.95k | if (b == 0) { |
194 | 18 | return CONSTTIME_FALSE_W; |
195 | 18 | } |
196 | 7.93k | if (len == 0) { |
197 | 0 | return CONSTTIME_TRUE_W; |
198 | 0 | } |
199 | | |
200 | | // |a| < |b| iff a[1..len-1] are all zero and a[0] < b. |
201 | 7.93k | static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), |
202 | 7.93k | "crypto_word_t is too small"); |
203 | 7.93k | crypto_word_t mask = 0; |
204 | 45.6k | for (size_t i = 1; i < len; i++) { |
205 | 37.7k | mask |= a[i]; |
206 | 37.7k | } |
207 | | // |mask| is now zero iff a[1..len-1] are all zero. |
208 | 7.93k | mask = constant_time_is_zero_w(mask); |
209 | 7.93k | mask &= constant_time_lt_w(a[0], b); |
210 | 7.93k | return mask; |
211 | 7.93k | } |
212 | | |
213 | | int bn_in_range_words(const BN_ULONG *a, BN_ULONG min_inclusive, |
214 | 7.95k | const BN_ULONG *max_exclusive, size_t len) { |
215 | 7.95k | crypto_word_t mask = ~bn_less_than_word_mask(a, len, min_inclusive); |
216 | 7.95k | return mask & bn_less_than_words(a, max_exclusive, len); |
217 | 7.95k | } |
218 | | |
219 | | static int bn_range_to_mask(size_t *out_words, BN_ULONG *out_mask, |
220 | | size_t min_inclusive, const BN_ULONG *max_exclusive, |
221 | 3.99k | size_t len) { |
222 | | // The magnitude of |max_exclusive| is assumed public. |
223 | 3.99k | size_t words = len; |
224 | 3.99k | while (words > 0 && max_exclusive[words - 1] == 0) { |
225 | 1 | words--; |
226 | 1 | } |
227 | 3.99k | if (words == 0 || (words == 1 && max_exclusive[0] <= min_inclusive)) { |
228 | 1 | OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE); |
229 | 1 | return 0; |
230 | 1 | } |
231 | 3.99k | BN_ULONG mask = max_exclusive[words - 1]; |
232 | | // This sets all bits in |mask| below the most significant bit. |
233 | 3.99k | mask |= mask >> 1; |
234 | 3.99k | mask |= mask >> 2; |
235 | 3.99k | mask |= mask >> 4; |
236 | 3.99k | mask |= mask >> 8; |
237 | 3.99k | mask |= mask >> 16; |
238 | 3.99k | #if defined(OPENSSL_64_BIT) |
239 | 3.99k | mask |= mask >> 32; |
240 | 3.99k | #endif |
241 | | |
242 | 3.99k | *out_words = words; |
243 | 3.99k | *out_mask = mask; |
244 | 3.99k | return 1; |
245 | 3.99k | } |
246 | | |
247 | | int bn_rand_range_words(BN_ULONG *out, BN_ULONG min_inclusive, |
248 | | const BN_ULONG *max_exclusive, size_t len, |
249 | 61 | const uint8_t additional_data[32]) { |
250 | | // This function implements the equivalent of steps 4 through 7 of FIPS 186-4 |
251 | | // appendices B.4.2 and B.5.2. When called in those contexts, |max_exclusive| |
252 | | // is n and |min_inclusive| is one. |
253 | | |
254 | | // Compute the bit length of |max_exclusive| (step 1), in terms of a number of |
255 | | // |words| worth of entropy to fill and a mask of bits to clear in the top |
256 | | // word. |
257 | 61 | size_t words; |
258 | 61 | BN_ULONG mask; |
259 | 61 | if (!bn_range_to_mask(&words, &mask, min_inclusive, max_exclusive, len)) { |
260 | 1 | return 0; |
261 | 1 | } |
262 | | |
263 | | // Fill any unused words with zero. |
264 | 60 | OPENSSL_memset(out + words, 0, (len - words) * sizeof(BN_ULONG)); |
265 | | |
266 | 60 | unsigned count = 100; |
267 | 81 | do { |
268 | 81 | if (!--count) { |
269 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS); |
270 | 0 | return 0; |
271 | 0 | } |
272 | | |
273 | | // Steps 4 and 5. Use |words| and |mask| together to obtain a string of N |
274 | | // bits, where N is the bit length of |max_exclusive|. |
275 | 81 | FIPS_service_indicator_lock_state(); |
276 | 81 | BCM_rand_bytes_with_additional_data( |
277 | 81 | (uint8_t *)out, words * sizeof(BN_ULONG), additional_data); |
278 | 81 | FIPS_service_indicator_unlock_state(); |
279 | 81 | out[words - 1] &= mask; |
280 | | |
281 | | // If out >= max_exclusive or out < min_inclusive, retry. This implements |
282 | | // the equivalent of steps 6 and 7 without leaking the value of |out|. The |
283 | | // result of this comparison may be treated as public. It only reveals how |
284 | | // many attempts were needed before we found a value in range. This is |
285 | | // independent of the final secret output, and has a distribution that |
286 | | // depends only on |min_inclusive| and |max_exclusive|, both of which are |
287 | | // public. |
288 | 81 | } while (!constant_time_declassify_int( |
289 | 81 | bn_in_range_words(out, min_inclusive, max_exclusive, words))); |
290 | 60 | return 1; |
291 | 60 | } |
292 | | |
293 | | int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive, |
294 | 55 | const BIGNUM *max_exclusive) { |
295 | 55 | static const uint8_t kDefaultAdditionalData[32] = {0}; |
296 | 55 | if (!bn_wexpand(r, max_exclusive->width) || |
297 | 55 | !bn_rand_range_words(r->d, min_inclusive, max_exclusive->d, |
298 | 55 | max_exclusive->width, kDefaultAdditionalData)) { |
299 | 1 | return 0; |
300 | 1 | } |
301 | | |
302 | 54 | r->neg = 0; |
303 | 54 | r->width = max_exclusive->width; |
304 | 54 | return 1; |
305 | 55 | } |
306 | | |
307 | | int bn_rand_secret_range(BIGNUM *r, int *out_is_uniform, BN_ULONG min_inclusive, |
308 | 3.93k | const BIGNUM *max_exclusive) { |
309 | 3.93k | size_t words; |
310 | 3.93k | BN_ULONG mask; |
311 | 3.93k | if (!bn_range_to_mask(&words, &mask, min_inclusive, max_exclusive->d, |
312 | 3.93k | max_exclusive->width) || |
313 | 3.93k | !bn_wexpand(r, words)) { |
314 | 0 | return 0; |
315 | 0 | } |
316 | | |
317 | 3.93k | assert(words > 0); |
318 | 3.93k | assert(mask != 0); |
319 | | // The range must be large enough for bit tricks to fix invalid values. |
320 | 3.93k | if (words == 1 && min_inclusive > mask >> 1) { |
321 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE); |
322 | 0 | return 0; |
323 | 0 | } |
324 | | |
325 | | // Select a uniform random number with num_bits(max_exclusive) bits. |
326 | 3.93k | FIPS_service_indicator_lock_state(); |
327 | 3.93k | BCM_rand_bytes((uint8_t *)r->d, words * sizeof(BN_ULONG)); |
328 | 3.93k | FIPS_service_indicator_unlock_state(); |
329 | 3.93k | r->d[words - 1] &= mask; |
330 | | |
331 | | // Check, in constant-time, if the value is in range. |
332 | 3.93k | *out_is_uniform = |
333 | 3.93k | bn_in_range_words(r->d, min_inclusive, max_exclusive->d, words); |
334 | 3.93k | crypto_word_t in_range = *out_is_uniform; |
335 | 3.93k | in_range = 0 - in_range; |
336 | | |
337 | | // If the value is not in range, force it to be in range. |
338 | 3.93k | r->d[0] |= constant_time_select_w(in_range, 0, min_inclusive); |
339 | 3.93k | r->d[words - 1] &= constant_time_select_w(in_range, BN_MASK2, mask >> 1); |
340 | 3.93k | declassify_assert( |
341 | 3.93k | bn_in_range_words(r->d, min_inclusive, max_exclusive->d, words)); |
342 | | |
343 | 3.93k | r->neg = 0; |
344 | 3.93k | r->width = (int)words; |
345 | 3.93k | return 1; |
346 | 3.93k | } |
347 | | |
348 | 24 | int BN_rand_range(BIGNUM *r, const BIGNUM *range) { |
349 | 24 | return BN_rand_range_ex(r, 0, range); |
350 | 24 | } |
351 | | |
352 | 9 | int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) { |
353 | 9 | return BN_rand_range(r, range); |
354 | 9 | } |