#include <sys/cdefs.h>
__FBSDID("$FreeBSD: src/lib/libc/gen/arc4random.c,v 1.25 2008/09/09 09:46:36 ache Exp $");
-#include "namespace.h"
#include <sys/types.h>
#include <sys/time.h>
-#include <stdlib.h>
+#include <sys/param.h>
+#include <sys/random.h>
#include <fcntl.h>
#include <unistd.h>
#include <pthread.h>
+#include <os/assumes.h>
+#include <os/lock.h>
+#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 <corecrypto/ccdrbg.h>
+#include <corecrypto/ccaes.h>
+
+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;
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,
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);
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
__private_extern__ void
_arc4_fork_child(void)
{
+ arc4_lock = OS_UNFAIR_LOCK_INIT;
rs_stired = 0;
rs_data_available = 0;
}
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
{
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 */
u_char *buf = (u_char *)_buf;
int did_stir = 0;
- THREAD_LOCK();
+ os_unfair_lock_lock(&arc4_lock);
while (n--) {
if (arc4_check_stir())
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 */
}
}
+#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 <stdio.h>
-#include <machine/pctr.h>
-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
projects / apple / libc.git / blobdiff