1 /* 2 * Copyright (c) 1999,2000,2004 Damien Miller <djm (at) 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 */ 151
