X-Git-Url: https://git.saurik.com/apple/libc.git/blobdiff_plain/1f2f436a38f7ae2d39a943ad2898d8fed4ed2e58..6dccf0e0b5e80b7b6176e8d332e646175431bb3d:/gen/FreeBSD/arc4random.c diff --git a/gen/FreeBSD/arc4random.c b/gen/FreeBSD/arc4random.c index 869effa..d2368d7 100644 --- a/gen/FreeBSD/arc4random.c +++ b/gen/FreeBSD/arc4random.c @@ -35,16 +35,194 @@ #include __FBSDID("$FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $"); -#include "namespace.h" #include #include -#include +#include +#include #include #include #include +#include +#include +#include "string.h" #include "libc_private.h" -#include "un-namespace.h" + +#define CACHE_LENGTH 64 +#define BUFFERSIZE 32 + +#define INITIAL_COUNT 1600000 +#define MAX_BUF_COUNT 4096 + +static os_unfair_lock arc4_lock = OS_UNFAIR_LOCK_INIT; +static int arc4_count; + +uint64_t arc4random64(void); + +#define RANDOMDEV "/dev/random" + +static void +_my_getentropy(uint8_t *buf, size_t size){ + int fd; + ssize_t ret; + if (getentropy(buf, size) == 0) { + return; + } + + // The above should never fail, but we'll try /dev/random anyway + fd = open(RANDOMDEV, O_RDONLY, 0); + if (fd == -1) { +#if !defined(VARIANT_STATIC) + os_crash("arc4random: unable to open /dev/random"); +#else + abort(); +#endif + } +shortread: + ret = read(fd, buf, size); + if (ret == -1) { +#if !defined(VARIANT_STATIC) + os_crash("arc4random: unable to read from /dev/random"); +#else + abort(); +#endif + } else if ((size_t)ret < size) { + size -= (size_t)ret; + buf += ret; + goto shortread; + } + (void)close(fd); +} + +#if defined(__APPLE__) && !defined(VARIANT_STATIC) +#include +#include + +static struct ccdrbg_info rng_info; +static struct ccdrbg_nistctr_custom rng_custom; +static struct ccdrbg_state *rng_state; + +static int cache_pos = CACHE_LENGTH; +static uint32_t rand_buffer[CACHE_LENGTH]; + +static void +arc4_init(void) +{ + if (rng_state != NULL) return; + + uint8_t entropy[BUFFERSIZE]; + int ret; + rng_custom.ctr_info = ccaes_ctr_crypt_mode(); + rng_custom.keylen = 16; + rng_custom.strictFIPS = 0; + rng_custom.use_df = 1; + ccdrbg_factory_nistctr(&rng_info, &rng_custom); + rng_state = malloc(rng_info.size); + os_assert(rng_state != NULL); + + _my_getentropy(entropy, BUFFERSIZE); + + ret = ccdrbg_init(&rng_info, rng_state, + sizeof(entropy), entropy, + 0, NULL, 0, NULL); + os_assert_zero(ret); + + memset_s(entropy, sizeof(entropy), 0, sizeof(entropy)); + + arc4_count = INITIAL_COUNT; +} + +static void +arc4_stir(void) +{ + uint8_t entropy[BUFFERSIZE]; + int ret; + + arc4_init(); + + _my_getentropy(entropy, BUFFERSIZE); + + ret = ccdrbg_reseed(&rng_info, rng_state, + sizeof(entropy), entropy, + 0, NULL); + os_assert_zero(ret); + + memset_s(entropy, sizeof(entropy), 0, sizeof(entropy)); + + arc4_count = INITIAL_COUNT; +} + +void +arc4random_addrandom(__unused u_char *dat, __unused int datlen) +{ + /* NOP - deprecated */ +} + +uint32_t +arc4random(void) +{ + int ret; + os_unfair_lock_lock(&arc4_lock); + arc4_init(); + if (arc4_count <= 0) { + arc4_stir(); + } + if (cache_pos >= CACHE_LENGTH) { + ret = ccdrbg_generate(&rng_info, rng_state, sizeof(rand_buffer), rand_buffer, 0, NULL); + os_assert_zero(ret); + cache_pos = 0; + } + uint32_t rand = rand_buffer[cache_pos]; + // Delete the current random number from buffer + memset_s(rand_buffer+cache_pos, sizeof(rand_buffer[cache_pos]), 0, sizeof(rand_buffer[cache_pos])); + arc4_count--; + cache_pos++; + os_unfair_lock_unlock(&arc4_lock); + return rand; +} + +void +arc4random_buf(void *_buf, size_t buf_size) +{ + uint8_t *buf = _buf; + os_unfair_lock_lock(&arc4_lock); + arc4_init(); + while (buf_size > 0) { + if (arc4_count <= 0 ) { + arc4_stir(); + } + size_t n = MIN(buf_size, (size_t)MIN(MAX_BUF_COUNT, arc4_count) * sizeof(uint32_t)); + int ret = ccdrbg_generate(&rng_info, rng_state, n, buf, 0, NULL); + os_assert_zero(ret); + buf_size -= n; + buf += n; + arc4_count -= n/sizeof(uint32_t); + + if (buf_size > 0) { + os_unfair_lock_unlock(&arc4_lock); + // Give others a chance to get the lock + os_unfair_lock_lock(&arc4_lock); + } + } + os_unfair_lock_unlock(&arc4_lock); +} + +__private_extern__ void +_arc4_fork_child(void) +{ + arc4_lock = OS_UNFAIR_LOCK_INIT; + cache_pos = CACHE_LENGTH; + if (rng_state != NULL) { + arc4_count = 0; + memset_s(rand_buffer, sizeof(rand_buffer), 0, sizeof(rand_buffer)); + memset_s(rng_state, rng_info.size, 0, rng_info.size); + free(rng_state); rng_state = NULL; + bzero(&rng_info, sizeof(rng_info)); + bzero(&rng_custom, sizeof(rng_custom)); + } +} + +#else /* __APPLE__ && !VARIANT_STATIC */ struct arc4_stream { u_int8_t i; @@ -52,23 +230,7 @@ struct arc4_stream { u_int8_t s[256]; }; -static int lock = 0; -extern void spin_lock(int*); -extern void spin_unlock(int*); - -#define RANDOMDEV "/dev/random" #define KEYSIZE 128 -#define THREAD_LOCK() \ - do { \ - if (__isthreaded) \ - spin_lock(&lock); \ - } while (0) - -#define THREAD_UNLOCK() \ - do { \ - if (__isthreaded) \ - spin_unlock(&lock); \ - } while (0) static struct arc4_stream rs = { .i = 0, @@ -92,9 +254,7 @@ static struct arc4_stream rs = { 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255 } }; -static int rs_initialized; static int rs_stired; -static int arc4_count; static inline u_int8_t arc4_getbyte(void); static void arc4_stir(void); @@ -126,19 +286,7 @@ arc4_addrandom(u_char *dat, int datlen) static void arc4_fetch(void) { - int done, fd; - fd = _open(RANDOMDEV, O_RDONLY, 0); - done = 0; - if (fd >= 0) { - if (_read(fd, &rdat, KEYSIZE) == KEYSIZE) - done = 1; - (void)_close(fd); - } - if (!done) { - (void)gettimeofday(&rdat.tv, NULL); - rdat.pid = getpid(); - /* We'll just take whatever was on the stack too... */ - } + _my_getentropy((uint8_t*)&rdat, KEYSIZE); } static void @@ -203,6 +351,7 @@ arc4_getword(void) __private_extern__ void _arc4_fork_child(void) { + arc4_lock = OS_UNFAIR_LOCK_INIT; rs_stired = 0; rs_data_available = 0; } @@ -217,21 +366,13 @@ arc4_check_stir(void) return 0; } -void -arc4random_stir(void) -{ - THREAD_LOCK(); - arc4_stir(); - THREAD_UNLOCK(); -} - void arc4random_addrandom(u_char *dat, int datlen) { - THREAD_LOCK(); + os_unfair_lock_lock(&arc4_lock); arc4_check_stir(); arc4_addrandom(dat, datlen); - THREAD_UNLOCK(); + os_unfair_lock_unlock(&arc4_lock); } u_int32_t @@ -239,13 +380,13 @@ arc4random(void) { u_int32_t rnd; - THREAD_LOCK(); + os_unfair_lock_lock(&arc4_lock); int did_stir = arc4_check_stir(); rnd = arc4_getword(); arc4_count -= 4; - THREAD_UNLOCK(); + os_unfair_lock_unlock(&arc4_lock); if (did_stir) { /* stirring used up our data pool, we need to read in new data outside of the lock */ @@ -263,7 +404,7 @@ arc4random_buf(void *_buf, size_t n) u_char *buf = (u_char *)_buf; int did_stir = 0; - THREAD_LOCK(); + os_unfair_lock_lock(&arc4_lock); while (n--) { if (arc4_check_stir()) @@ -273,8 +414,8 @@ arc4random_buf(void *_buf, size_t n) buf[n] = arc4_getbyte(); arc4_count--; } - - THREAD_UNLOCK(); + + os_unfair_lock_unlock(&arc4_lock); if (did_stir) { /* stirring used up our data pool, we need to read in new data outside of the lock */ @@ -284,68 +425,53 @@ arc4random_buf(void *_buf, size_t n) } } +#endif /* __APPLE__ */ + +void +arc4random_stir(void) +{ + os_unfair_lock_lock(&arc4_lock); + arc4_stir(); + os_unfair_lock_unlock(&arc4_lock); +} + /* * Calculate a uniformly distributed random number less than upper_bound * avoiding "modulo bias". * - * Uniformity is achieved by generating new random numbers until the one - * returned is outside the range [0, 2**32 % upper_bound). This - * guarantees the selected random number will be inside - * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) - * after reduction modulo upper_bound. + * Uniformity is achieved by trying successive ranges of bits from the random + * value, each large enough to hold the desired upper bound, until a range + * holding a value less than the bound is found. */ -u_int32_t -arc4random_uniform(u_int32_t upper_bound) +uint32_t +arc4random_uniform(uint32_t upper_bound) { - u_int32_t r, min; - if (upper_bound < 2) - return (0); - -#if (ULONG_MAX > 0xffffffffUL) - min = 0x100000000UL % upper_bound; -#else - /* Calculate (2**32 % upper_bound) avoiding 64-bit math */ - if (upper_bound > 0x80000000) - min = 1 + ~upper_bound; /* 2**32 - upper_bound */ - else { - /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */ - min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; - } -#endif - - /* - * This could theoretically loop forever but each retry has - * p > 0.5 (worst case, usually far better) of selecting a - * number inside the range we need, so it should rarely need - * to re-roll. - */ - for (;;) { - r = arc4random(); - if (r >= min) - break; - } + return 0; - return (r % upper_bound); -} + // find smallest 2**n -1 >= upper_bound + int zeros = __builtin_clz(upper_bound); + int bits = CHAR_BIT * sizeof(uint32_t) - zeros; + uint32_t mask = 0xFFFFFFFFU >> zeros; -#if 0 -/*-------- Test code for i386 --------*/ -#include -#include -int -main(int argc, char **argv) -{ - const int iter = 1000000; - int i; - pctrval v; + do { + uint32_t value = arc4random(); - v = rdtsc(); - for (i = 0; i < iter; i++) - arc4random(); - v = rdtsc() - v; - v /= iter; + // If low 2**n-1 bits satisfy the requested condition, return result + uint32_t result = value & mask; + if (result < upper_bound) { + return result; + } - printf("%qd cycles\n", v); + // otherwise consume remaining bits of randomness looking for a satisfactory result. + int bits_left = zeros; + while (bits_left >= bits) { + value >>= bits; + result = value & mask; + if (result < upper_bound) { + return result; + } + bits_left -= bits; + } + } while (1); } -#endif