legacy-libs/grpc/deps/grpc/third_party/boringssl/crypto/fipsmodule/bn/random.c

   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/type_check.h>
 117
 118 #include "internal.h"
 119 #include "../../internal.h"
 120 #include "../rand/internal.h"
 121
 122
 123 int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) {
 124   uint8_t *buf = NULL;
 125   int ret = 0, bit, bytes, mask;
 126
 127   if (rnd == NULL) {
 128     return 0;
 129   }
 130
 131   if (top != BN_RAND_TOP_ANY && top != BN_RAND_TOP_ONE &&
 132       top != BN_RAND_TOP_TWO) {
 133     OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 134     return 0;
 135   }
 136
 137   if (bottom != BN_RAND_BOTTOM_ANY && bottom != BN_RAND_BOTTOM_ODD) {
 138     OPENSSL_PUT_ERROR(BN, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 139     return 0;
 140   }
 141
 142   if (bits == 0) {
 143     BN_zero(rnd);
 144     return 1;
 145   }
 146
 147   bytes = (bits + 7) / 8;
 148   bit = (bits - 1) % 8;
 149   mask = 0xff << (bit + 1);
 150
 151   buf = OPENSSL_malloc(bytes);
 152   if (buf == NULL) {
 153     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
 154     goto err;
 155   }
 156
 157   // Make a random number and set the top and bottom bits.
 158   RAND_bytes(buf, bytes);
 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   OPENSSL_free(buf);
 188   return ret;
 189 }
 190
 191 int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) {
 192   return BN_rand(rnd, bits, top, bottom);
 193 }
 194
 195 // bn_less_than_word_mask returns a mask of all ones if the number represented
 196 // by |len| words at |a| is less than |b| and zero otherwise. It performs this
 197 // computation in time independent of the value of |a|. |b| is assumed public.
 198 static crypto_word_t bn_less_than_word_mask(const BN_ULONG *a, size_t len,
 199                                             BN_ULONG b) {
 200   if (b == 0) {
 201     return CONSTTIME_FALSE_W;
 202   }
 203   if (len == 0) {
 204     return CONSTTIME_TRUE_W;
 205   }
 206
 207   // |a| < |b| iff a[1..len-1] are all zero and a[0] < b.
 208   OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
 209                          crypto_word_t_too_small);
 210   crypto_word_t mask = 0;
 211   for (size_t i = 1; i < len; i++) {
 212     mask |= a[i];
 213   }
 214   // |mask| is now zero iff a[1..len-1] are all zero.
 215   mask = constant_time_is_zero_w(mask);
 216   mask &= constant_time_lt_w(a[0], b);
 217   return mask;
 218 }
 219
 220 int bn_in_range_words(const BN_ULONG *a, BN_ULONG min_inclusive,
 221                       const BN_ULONG *max_exclusive, size_t len) {
 222   crypto_word_t mask = ~bn_less_than_word_mask(a, len, min_inclusive);
 223   return mask & bn_less_than_words(a, max_exclusive, len);
 224 }
 225
 226 static int bn_range_to_mask(size_t *out_words, BN_ULONG *out_mask,
 227                             size_t min_inclusive, const BN_ULONG *max_exclusive,
 228                             size_t len) {
 229   // The magnitude of |max_exclusive| is assumed public.
 230   size_t words = len;
 231   while (words > 0 && max_exclusive[words - 1] == 0) {
 232     words--;
 233   }
 234   if (words == 0 ||
 235       (words == 1 && max_exclusive[0] <= min_inclusive)) {
 236     OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);
 237     return 0;
 238   }
 239   BN_ULONG mask = max_exclusive[words - 1];
 240   // This sets all bits in |mask| below the most significant bit.
 241   mask |= mask >> 1;
 242   mask |= mask >> 2;
 243   mask |= mask >> 4;
 244   mask |= mask >> 8;
 245   mask |= mask >> 16;
 246 #if defined(OPENSSL_64_BIT)
 247   mask |= mask >> 32;
 248 #endif
 249
 250   *out_words = words;
 251   *out_mask = mask;
 252   return 1;
 253 }
 254
 255 int bn_rand_range_words(BN_ULONG *out, BN_ULONG min_inclusive,
 256                         const BN_ULONG *max_exclusive, size_t len,
 257                         const uint8_t additional_data[32]) {
 258   // This function implements the equivalent of steps 4 through 7 of FIPS 186-4
 259   // appendices B.4.2 and B.5.2. When called in those contexts, |max_exclusive|
 260   // is n and |min_inclusive| is one.
 261
 262   // Compute the bit length of |max_exclusive| (step 1), in terms of a number of
 263   // |words| worth of entropy to fill and a mask of bits to clear in the top
 264   // word.
 265   size_t words;
 266   BN_ULONG mask;
 267   if (!bn_range_to_mask(&words, &mask, min_inclusive, max_exclusive, len)) {
 268     return 0;
 269   }
 270
 271   // Fill any unused words with zero.
 272   OPENSSL_memset(out + words, 0, (len - words) * sizeof(BN_ULONG));
 273
 274   unsigned count = 100;
 275   do {
 276     if (!--count) {
 277       OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);
 278       return 0;
 279     }
 280
 281     // Steps 4 and 5. Use |words| and |mask| together to obtain a string of N
 282     // bits, where N is the bit length of |max_exclusive|.
 283     RAND_bytes_with_additional_data((uint8_t *)out, words * sizeof(BN_ULONG),
 284                                     additional_data);
 285     out[words - 1] &= mask;
 286
 287     // If out >= max_exclusive or out < min_inclusive, retry. This implements
 288     // the equivalent of steps 6 and 7 without leaking the value of |out|.
 289   } while (!bn_in_range_words(out, min_inclusive, max_exclusive, words));
 290   return 1;
 291 }
 292
 293 int BN_rand_range_ex(BIGNUM *r, BN_ULONG min_inclusive,
 294                      const BIGNUM *max_exclusive) {
 295   static const uint8_t kDefaultAdditionalData[32] = {0};
 296   if (!bn_wexpand(r, max_exclusive->width) ||
 297       !bn_rand_range_words(r->d, min_inclusive, max_exclusive->d,
 298                            max_exclusive->width, kDefaultAdditionalData)) {
 299     return 0;
 300   }
 301
 302   r->neg = 0;
 303   r->width = max_exclusive->width;
 304   return 1;
 305 }
 306
 307 int bn_rand_secret_range(BIGNUM *r, int *out_is_uniform, BN_ULONG min_inclusive,
 308                          const BIGNUM *max_exclusive) {
 309   size_t words;
 310   BN_ULONG mask;
 311   if (!bn_range_to_mask(&words, &mask, min_inclusive, max_exclusive->d,
 312                         max_exclusive->width) ||
 313       !bn_wexpand(r, words)) {
 314     return 0;
 315   }
 316
 317   assert(words > 0);
 318   assert(mask != 0);
 319   // The range must be large enough for bit tricks to fix invalid values.
 320   if (words == 1 && min_inclusive > mask >> 1) {
 321     OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);
 322     return 0;
 323   }
 324
 325   // Select a uniform random number with num_bits(max_exclusive) bits.
 326   RAND_bytes((uint8_t *)r->d, words * sizeof(BN_ULONG));
 327   r->d[words - 1] &= mask;
 328
 329   // Check, in constant-time, if the value is in range.
 330   *out_is_uniform =
 331       bn_in_range_words(r->d, min_inclusive, max_exclusive->d, words);
 332   crypto_word_t in_range = *out_is_uniform;
 333   in_range = 0 - in_range;
 334
 335   // If the value is not in range, force it to be in range.
 336   r->d[0] |= constant_time_select_w(in_range, 0, min_inclusive);
 337   r->d[words - 1] &= constant_time_select_w(in_range, BN_MASK2, mask >> 1);
 338   assert(bn_in_range_words(r->d, min_inclusive, max_exclusive->d, words));
 339
 340   r->neg = 0;
 341   r->width = words;
 342   return 1;
 343 }
 344
 345 int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
 346   return BN_rand_range_ex(r, 0, range);
 347 }
 348
 349 int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) {
 350   return BN_rand_range(r, range);
 351 }