openbsd-compat/bsd-arc4random.c

   1 /*
   2  * Copyright (c) 1999,2000,2004 Damien Miller <djm@mindrot.org>
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include "includes.h"
  18
  19 #include <sys/types.h>
  20
  21 #include <string.h>
  22 #include <stdlib.h>
  23 #include <stdarg.h>
  24
  25 #include "log.h"
  26
  27 #ifndef HAVE_ARC4RANDOM
  28
  29 #include <openssl/rand.h>
  30 #include <openssl/rc4.h>
  31 #include <openssl/err.h>
  32
  33 /* Size of key to use */
  34 #define SEED_SIZE 20
  35
  36 /* Number of bytes to reseed after */
  37 #define REKEY_BYTES     (1 << 24)
  38
  39 static int rc4_ready = 0;
  40 static RC4_KEY rc4;
  41
  42 unsigned int
  43 arc4random(void)
  44 {
  45         unsigned int r = 0;
  46         static int first_time = 1;
  47
  48         if (rc4_ready <= 0) {
  49                 if (first_time)
  50                         seed_rng();
  51                 first_time = 0;
  52                 arc4random_stir();
  53         }
  54
  55         RC4(&rc4, sizeof(r), (unsigned char *)&r, (unsigned char *)&r);
  56
  57         rc4_ready -= sizeof(r);
  58
  59         return(r);
  60 }
  61
  62 void
  63 arc4random_stir(void)
  64 {
  65         unsigned char rand_buf[SEED_SIZE];
  66         int i;
  67
  68         memset(&rc4, 0, sizeof(rc4));
  69         if (RAND_bytes(rand_buf, sizeof(rand_buf)) <= 0)
  70                 fatal("Couldn't obtain random bytes (error %ld)",
  71                     ERR_get_error());
  72         RC4_set_key(&rc4, sizeof(rand_buf), rand_buf);
  73
  74         /*
  75          * Discard early keystream, as per recommendations in:
  76          * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
  77          */
  78         for(i = 0; i <= 256; i += sizeof(rand_buf))
  79                 RC4(&rc4, sizeof(rand_buf), rand_buf, rand_buf);
  80
  81         memset(rand_buf, 0, sizeof(rand_buf));
  82
  83         rc4_ready = REKEY_BYTES;
  84 }
  85 #endif /* !HAVE_ARC4RANDOM */
  86
  87 #ifndef HAVE_ARC4RANDOM_BUF
  88 void
  89 arc4random_buf(void *_buf, size_t n)
  90 {
  91         size_t i;
  92         u_int32_t r = 0;
  93         char *buf = (char *)_buf;
  94
  95         for (i = 0; i < n; i++) {
  96                 if (i % 4 == 0)
  97                         r = arc4random();
  98                 buf[i] = r & 0xff;
  99                 r >>= 8;
 100         }
 101         i = r = 0;
 102 }
 103 #endif /* !HAVE_ARC4RANDOM_BUF */
 104
 105 #ifndef HAVE_ARC4RANDOM_UNIFORM
 106 /*
 107  * Calculate a uniformly distributed random number less than upper_bound
 108  * avoiding "modulo bias".
 109  *
 110  * Uniformity is achieved by generating new random numbers until the one
 111  * returned is outside the range [0, 2**32 % upper_bound).  This
 112  * guarantees the selected random number will be inside
 113  * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 114  * after reduction modulo upper_bound.
 115  */
 116 u_int32_t
 117 arc4random_uniform(u_int32_t upper_bound)
 118 {
 119         u_int32_t r, min;
 120
 121         if (upper_bound < 2)
 122                 return 0;
 123
 124 #if (ULONG_MAX > 0xffffffffUL)
 125         min = 0x100000000UL % upper_bound;
 126 #else
 127         /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
 128         if (upper_bound > 0x80000000)
 129                 min = 1 + ~upper_bound;         /* 2**32 - upper_bound */
 130         else {
 131                 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
 132                 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
 133         }
 134 #endif
 135
 136         /*
 137          * This could theoretically loop forever but each retry has
 138          * p > 0.5 (worst case, usually far better) of selecting a
 139          * number inside the range we need, so it should rarely need
 140          * to re-roll.
 141          */
 142         for (;;) {
 143                 r = arc4random();
 144                 if (r >= min)
 145                         break;
 146         }
 147
 148         return r % upper_bound;
 149 }
 150 #endif /* !HAVE_ARC4RANDOM_UNIFORM */