bsd-arc4random.c revision 256281
1209878Snwhitehorn/* 2209878Snwhitehorn * Copyright (c) 1999,2000,2004 Damien Miller <djm@mindrot.org> 3209878Snwhitehorn * 4209878Snwhitehorn * Permission to use, copy, modify, and distribute this software for any 5209878Snwhitehorn * purpose with or without fee is hereby granted, provided that the above 6209878Snwhitehorn * copyright notice and this permission notice appear in all copies. 7209878Snwhitehorn * 8209878Snwhitehorn * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 9209878Snwhitehorn * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 10209878Snwhitehorn * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 11209878Snwhitehorn * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 12209878Snwhitehorn * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 13209878Snwhitehorn * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 14209878Snwhitehorn * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 15209878Snwhitehorn */ 16209878Snwhitehorn 17209878Snwhitehorn#include "includes.h" 18209878Snwhitehorn 19209878Snwhitehorn#include <sys/types.h> 20209878Snwhitehorn 21209878Snwhitehorn#include <string.h> 22209878Snwhitehorn#include <stdlib.h> 23209878Snwhitehorn#include <stdarg.h> 24209878Snwhitehorn 25209878Snwhitehorn#include "log.h" 26209878Snwhitehorn 27209878Snwhitehorn#ifndef HAVE_ARC4RANDOM 28209878Snwhitehorn 29209878Snwhitehorn#include <openssl/rand.h> 30209878Snwhitehorn#include <openssl/rc4.h> 31209878Snwhitehorn#include <openssl/err.h> 32209878Snwhitehorn 33209878Snwhitehorn/* Size of key to use */ 34209878Snwhitehorn#define SEED_SIZE 20 35209878Snwhitehorn 36209878Snwhitehorn/* Number of bytes to reseed after */ 37209878Snwhitehorn#define REKEY_BYTES (1 << 24) 38209878Snwhitehorn 39209878Snwhitehornstatic int rc4_ready = 0; 40209878Snwhitehornstatic RC4_KEY rc4; 41209878Snwhitehorn 42209878Snwhitehornunsigned int 43209878Snwhitehornarc4random(void) 44209878Snwhitehorn{ 45209878Snwhitehorn unsigned int r = 0; 46209878Snwhitehorn static int first_time = 1; 47209878Snwhitehorn 48209878Snwhitehorn if (rc4_ready <= 0) { 49209878Snwhitehorn if (first_time) 50209878Snwhitehorn seed_rng(); 51209878Snwhitehorn first_time = 0; 52209878Snwhitehorn arc4random_stir(); 53209878Snwhitehorn } 54209878Snwhitehorn 55209878Snwhitehorn RC4(&rc4, sizeof(r), (unsigned char *)&r, (unsigned char *)&r); 56209878Snwhitehorn 57209878Snwhitehorn rc4_ready -= sizeof(r); 58209878Snwhitehorn 59209878Snwhitehorn return(r); 60209878Snwhitehorn} 61209878Snwhitehorn 62209878Snwhitehornvoid 63209878Snwhitehornarc4random_stir(void) 64209878Snwhitehorn{ 65209878Snwhitehorn unsigned char rand_buf[SEED_SIZE]; 66209878Snwhitehorn int i; 67209878Snwhitehorn 68209878Snwhitehorn memset(&rc4, 0, sizeof(rc4)); 69209878Snwhitehorn if (RAND_bytes(rand_buf, sizeof(rand_buf)) <= 0) 70209878Snwhitehorn fatal("Couldn't obtain random bytes (error %ld)", 71209878Snwhitehorn ERR_get_error()); 72209878Snwhitehorn RC4_set_key(&rc4, sizeof(rand_buf), rand_buf); 73209878Snwhitehorn 74209878Snwhitehorn /* 75209878Snwhitehorn * Discard early keystream, as per recommendations in: 76209878Snwhitehorn * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps 77209878Snwhitehorn */ 78209878Snwhitehorn for(i = 0; i <= 256; i += sizeof(rand_buf)) 79209878Snwhitehorn RC4(&rc4, sizeof(rand_buf), rand_buf, rand_buf); 80209878Snwhitehorn 81209878Snwhitehorn memset(rand_buf, 0, sizeof(rand_buf)); 82209878Snwhitehorn 83209878Snwhitehorn rc4_ready = REKEY_BYTES; 84209878Snwhitehorn} 85209878Snwhitehorn#endif /* !HAVE_ARC4RANDOM */ 86209878Snwhitehorn 87209878Snwhitehorn#ifndef HAVE_ARC4RANDOM_BUF 88209878Snwhitehornvoid 89209878Snwhitehornarc4random_buf(void *_buf, size_t n) 90209878Snwhitehorn{ 91209878Snwhitehorn size_t i; 92209878Snwhitehorn u_int32_t r = 0; 93209878Snwhitehorn char *buf = (char *)_buf; 94209878Snwhitehorn 95209878Snwhitehorn for (i = 0; i < n; i++) { 96231044Sandreast if (i % 4 == 0) 97209878Snwhitehorn r = arc4random(); 98209878Snwhitehorn buf[i] = r & 0xff; 99209878Snwhitehorn r >>= 8; 100209878Snwhitehorn } 101209878Snwhitehorn i = r = 0; 102209878Snwhitehorn} 103209878Snwhitehorn#endif /* !HAVE_ARC4RANDOM_BUF */ 104209878Snwhitehorn 105209878Snwhitehorn#ifndef HAVE_ARC4RANDOM_UNIFORM 106209878Snwhitehorn/* 107209878Snwhitehorn * Calculate a uniformly distributed random number less than upper_bound 108209878Snwhitehorn * avoiding "modulo bias". 109209878Snwhitehorn * 110209878Snwhitehorn * Uniformity is achieved by generating new random numbers until the one 111209878Snwhitehorn * returned is outside the range [0, 2**32 % upper_bound). This 112209878Snwhitehorn * guarantees the selected random number will be inside 113209878Snwhitehorn * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) 114209878Snwhitehorn * after reduction modulo upper_bound. 115209878Snwhitehorn */ 116209878Snwhitehornu_int32_t 117209878Snwhitehornarc4random_uniform(u_int32_t upper_bound) 118209878Snwhitehorn{ 119209878Snwhitehorn u_int32_t r, min; 120209878Snwhitehorn 121209878Snwhitehorn if (upper_bound < 2) 122209878Snwhitehorn return 0; 123209878Snwhitehorn 124209878Snwhitehorn#if (ULONG_MAX > 0xffffffffUL) 125209878Snwhitehorn min = 0x100000000UL % upper_bound; 126209878Snwhitehorn#else 127209878Snwhitehorn /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ 128209878Snwhitehorn if (upper_bound > 0x80000000) 129209878Snwhitehorn min = 1 + ~upper_bound; /* 2**32 - upper_bound */ 130209878Snwhitehorn else { 131209878Snwhitehorn /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ 132209878Snwhitehorn min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; 133209878Snwhitehorn } 134209878Snwhitehorn#endif 135209878Snwhitehorn 136217398Skib /* 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