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 <string.h>
112 
113 #include <openssl/err.h>
114 #include <openssl/mem.h>
115 #include <openssl/rand.h>
116 #include <openssl/sha.h>
117 
118 #include "../internal.h"
119 
120 
BN_rand(BIGNUM * rnd,int bits,int top,int bottom)121 int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) {
122   uint8_t *buf = NULL;
123   int ret = 0, bit, bytes, mask;
124 
125   if (rnd == NULL) {
126     return 0;
127   }
128 
129   if (top != BN_RAND_TOP_ANY && top != BN_RAND_TOP_ONE &&
130       top != BN_RAND_TOP_TWO) {
131     OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
132     return 0;
133   }
134 
135   if (bottom != BN_RAND_BOTTOM_ANY && bottom != BN_RAND_BOTTOM_ODD) {
136     OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
137     return 0;
138   }
139 
140   if (bits == 0) {
141     BN_zero(rnd);
142     return 1;
143   }
144 
145   bytes = (bits + 7) / 8;
146   bit = (bits - 1) % 8;
147   mask = 0xff << (bit + 1);
148 
149   buf = OPENSSL_malloc(bytes);
150   if (buf == NULL) {
151     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
152     goto err;
153   }
154 
155   /* Make a random number and set the top and bottom bits. */
156   if (!RAND_bytes(buf, bytes)) {
157     goto err;
158   }
159 
160   if (top != BN_RAND_TOP_ANY) {
161     if (top == BN_RAND_TOP_TWO && bits > 1) {
162       if (bit == 0) {
163         buf[0] = 1;
164         buf[1] |= 0x80;
165       } else {
166         buf[0] |= (3 << (bit - 1));
167       }
168     } else {
169       buf[0] |= (1 << bit);
170     }
171   }
172 
173   buf[0] &= ~mask;
174 
175   /* Set the bottom bit if requested, */
176   if (bottom == BN_RAND_BOTTOM_ODD)  {
177     buf[bytes - 1] |= 1;
178   }
179 
180   if (!BN_bin2bn(buf, bytes, rnd)) {
181     goto err;
182   }
183 
184   ret = 1;
185 
186 err:
187   if (buf != NULL) {
188     OPENSSL_cleanse(buf, bytes);
189     OPENSSL_free(buf);
190   }
191   return (ret);
192 }
193 
BN_pseudo_rand(BIGNUM * rnd,int bits,int top,int bottom)194 int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) {
195   return BN_rand(rnd, bits, top, bottom);
196 }
197 
BN_rand_range_ex(BIGNUM * r,BN_ULONG min_inclusive,const BIGNUM * max_exclusive)198 int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive,
199                      const BIGNUM *max_exclusive) {
200   unsigned n;
201   unsigned count = 100;
202 
203   if (BN_cmp_word(max_exclusive, min_inclusive) <= 0) {
204     OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);
205     return 0;
206   }
207 
208   n = BN_num_bits(max_exclusive); /* n > 0 */
209 
210   /* BN_is_bit_set(range, n - 1) always holds */
211   if (n == 1) {
212     BN_zero(r);
213     return 1;
214   }
215 
216   do {
217     if (!--count) {
218       OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);
219       return 0;
220     }
221 
222     if (!BN_is_bit_set(max_exclusive, n - 2) &&
223         !BN_is_bit_set(max_exclusive, n - 3)) {
224       /* range = 100..._2, so 3*range (= 11..._2) is exactly one bit longer
225        * than range. This is a common scenario when generating a random value
226        * modulo an RSA public modulus, e.g. for RSA base blinding. */
227       if (!BN_rand(r, n + 1, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
228         return 0;
229       }
230 
231       /* If r < 3*range, use r := r MOD range (which is either r, r - range, or
232        * r - 2*range). Otherwise, iterate again. Since 3*range = 11..._2, each
233        * iteration succeeds with probability >= .75. */
234       if (BN_cmp(r, max_exclusive) >= 0) {
235         if (!BN_sub(r, r, max_exclusive)) {
236           return 0;
237         }
238         if (BN_cmp(r, max_exclusive) >= 0) {
239           if (!BN_sub(r, r, max_exclusive)) {
240             return 0;
241           }
242         }
243       }
244     } else {
245       /* range = 11..._2  or  range = 101..._2 */
246       if (!BN_rand(r, n, BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) {
247         return 0;
248       }
249     }
250   } while (BN_cmp_word(r, min_inclusive) < 0 ||
251            BN_cmp(r, max_exclusive) >= 0);
252 
253   return 1;
254 }
255 
BN_rand_range(BIGNUM * r,const BIGNUM * range)256 int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
257   return BN_rand_range_ex(r, 0, range);
258 }
259 
BN_pseudo_rand_range(BIGNUM * r,const BIGNUM * range)260 int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) {
261   return BN_rand_range(r, range);
262 }
263 
BN_generate_dsa_nonce(BIGNUM * out,const BIGNUM * range,const BIGNUM * priv,const uint8_t * message,size_t message_len,BN_CTX * ctx)264 int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM *priv,
265                           const uint8_t *message, size_t message_len,
266                           BN_CTX *ctx) {
267   SHA512_CTX sha;
268   /* We use 512 bits of random data per iteration to
269    * ensure that we have at least |range| bits of randomness. */
270   uint8_t random_bytes[64];
271   uint8_t digest[SHA512_DIGEST_LENGTH];
272   size_t done, todo, attempt;
273   const unsigned num_k_bytes = BN_num_bytes(range);
274   const unsigned bits_to_mask = (8 - (BN_num_bits(range) % 8)) % 8;
275   uint8_t private_bytes[96];
276   uint8_t *k_bytes = NULL;
277   int ret = 0;
278 
279   if (out == NULL) {
280     return 0;
281   }
282 
283   if (BN_is_zero(range)) {
284     OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO);
285     goto err;
286   }
287 
288   k_bytes = OPENSSL_malloc(num_k_bytes);
289   if (!k_bytes) {
290     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
291     goto err;
292   }
293 
294   /* We copy |priv| into a local buffer to avoid furthur exposing its
295    * length. */
296   todo = sizeof(priv->d[0]) * priv->top;
297   if (todo > sizeof(private_bytes)) {
298     /* No reasonable DSA or ECDSA key should have a private key
299      * this large and we don't handle this case in order to avoid
300      * leaking the length of the private key. */
301     OPENSSL_PUT_ERROR(BN, BN_R_PRIVATE_KEY_TOO_LARGE);
302     goto err;
303   }
304   OPENSSL_memcpy(private_bytes, priv->d, todo);
305   OPENSSL_memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);
306 
307   for (attempt = 0;; attempt++) {
308     for (done = 0; done < num_k_bytes;) {
309       if (!RAND_bytes(random_bytes, sizeof(random_bytes))) {
310         goto err;
311       }
312       SHA512_Init(&sha);
313       SHA512_Update(&sha, &attempt, sizeof(attempt));
314       SHA512_Update(&sha, &done, sizeof(done));
315       SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
316       SHA512_Update(&sha, message, message_len);
317       SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
318       SHA512_Final(digest, &sha);
319 
320       todo = num_k_bytes - done;
321       if (todo > SHA512_DIGEST_LENGTH) {
322         todo = SHA512_DIGEST_LENGTH;
323       }
324       OPENSSL_memcpy(k_bytes + done, digest, todo);
325       done += todo;
326     }
327 
328     k_bytes[0] &= 0xff >> bits_to_mask;
329 
330     if (!BN_bin2bn(k_bytes, num_k_bytes, out)) {
331       goto err;
332     }
333     if (BN_cmp(out, range) < 0) {
334       break;
335     }
336   }
337 
338   ret = 1;
339 
340 err:
341   OPENSSL_free(k_bytes);
342   return ret;
343 }
344