Index: head/lib/libc/gen/arc4random.c =================================================================== --- head/lib/libc/gen/arc4random.c (revision 315224) +++ head/lib/libc/gen/arc4random.c (revision 315225) @@ -1,302 +1,302 @@ /* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */ /* * Copyright (c) 1996, David Mazieres * Copyright (c) 2008, Damien Miller * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ /* * Arc4 random number generator for OpenBSD. * * This code is derived from section 17.1 of Applied Cryptography, * second edition, which describes a stream cipher allegedly * compatible with RSA Labs "RC4" cipher (the actual description of * which is a trade secret). The same algorithm is used as a stream * cipher called "arcfour" in Tatu Ylonen's ssh package. * * RC4 is a registered trademark of RSA Laboratories. */ #include __FBSDID("$FreeBSD$"); #include "namespace.h" #include #include #include #include #include #include #include #include #include "libc_private.h" #include "un-namespace.h" #ifdef __GNUC__ #define inline __inline #else /* !__GNUC__ */ #define inline #endif /* !__GNUC__ */ struct arc4_stream { u_int8_t i; u_int8_t j; u_int8_t s[256]; }; static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; #define RANDOMDEV "/dev/random" #define KEYSIZE 128 #define _ARC4_LOCK() \ do { \ if (__isthreaded) \ _pthread_mutex_lock(&arc4random_mtx); \ } while (0) #define _ARC4_UNLOCK() \ do { \ if (__isthreaded) \ _pthread_mutex_unlock(&arc4random_mtx); \ } while (0) static int rs_initialized; static struct arc4_stream rs; static pid_t arc4_stir_pid; static int arc4_count; extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp, void *newp, size_t newlen); static inline u_int8_t arc4_getbyte(void); static void arc4_stir(void); static inline void arc4_init(void) { int n; for (n = 0; n < 256; n++) rs.s[n] = n; rs.i = 0; rs.j = 0; } static inline void arc4_addrandom(u_char *dat, int datlen) { int n; u_int8_t si; rs.i--; for (n = 0; n < 256; n++) { rs.i = (rs.i + 1); si = rs.s[rs.i]; rs.j = (rs.j + si + dat[n % datlen]); rs.s[rs.i] = rs.s[rs.j]; rs.s[rs.j] = si; } rs.j = rs.i; } static size_t arc4_sysctl(u_char *buf, size_t size) { int mib[2]; size_t len, done; mib[0] = CTL_KERN; mib[1] = KERN_ARND; done = 0; do { len = size; if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1) return (done); done += len; buf += len; size -= len; } while (size > 0); return (done); } static void arc4_stir(void) { u_char rdat[KEYSIZE]; int i; if (!rs_initialized) { arc4_init(); rs_initialized = 1; } if (arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) { /* * The sysctl cannot fail. If it does fail on some FreeBSD * derivative or after some future change, just abort so that * the problem will be found and fixed. abort is not normally * suitable for a library but makes sense here. */ abort(); } arc4_addrandom(rdat, KEYSIZE); /* * Discard early keystream, as per recommendations in: * "(Not So) Random Shuffles of RC4" by Ilya Mironov. */ - for (i = 0; i < 1024; i++) + for (i = 0; i < 3072; i++) (void)arc4_getbyte(); arc4_count = 1600000; } static void arc4_stir_if_needed(void) { pid_t pid = getpid(); if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) { arc4_stir_pid = pid; arc4_stir(); } } static inline u_int8_t arc4_getbyte(void) { u_int8_t si, sj; rs.i = (rs.i + 1); si = rs.s[rs.i]; rs.j = (rs.j + si); sj = rs.s[rs.j]; rs.s[rs.i] = sj; rs.s[rs.j] = si; return (rs.s[(si + sj) & 0xff]); } static inline u_int32_t arc4_getword(void) { u_int32_t val; val = arc4_getbyte() << 24; val |= arc4_getbyte() << 16; val |= arc4_getbyte() << 8; val |= arc4_getbyte(); return val; } void arc4random_stir(void) { _ARC4_LOCK(); arc4_stir(); _ARC4_UNLOCK(); } void arc4random_addrandom(u_char *dat, int datlen) { _ARC4_LOCK(); if (!rs_initialized) arc4_stir(); arc4_addrandom(dat, datlen); _ARC4_UNLOCK(); } u_int32_t arc4random(void) { u_int32_t val; _ARC4_LOCK(); arc4_count -= 4; arc4_stir_if_needed(); val = arc4_getword(); _ARC4_UNLOCK(); return val; } void arc4random_buf(void *_buf, size_t n) { u_char *buf = (u_char *)_buf; _ARC4_LOCK(); arc4_stir_if_needed(); while (n--) { if (--arc4_count <= 0) arc4_stir(); buf[n] = arc4_getbyte(); } _ARC4_UNLOCK(); } /* * 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. */ u_int32_t arc4random_uniform(u_int32_t upper_bound) { u_int32_t r, min; if (upper_bound < 2) return 0; /* 2**32 % x == (2**32 - x) % x */ min = -upper_bound % upper_bound; /* * 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 r % upper_bound; } #if 0 /*-------- Test code for i386 --------*/ #include #include int main(int argc, char **argv) { const int iter = 1000000; int i; pctrval v; v = rdtsc(); for (i = 0; i < iter; i++) arc4random(); v = rdtsc() - v; v /= iter; printf("%qd cycles\n", v); } #endif Index: head/sys/libkern/arc4random.c =================================================================== --- head/sys/libkern/arc4random.c (revision 315224) +++ head/sys/libkern/arc4random.c (revision 315225) @@ -1,193 +1,193 @@ /*- * THE BEER-WARE LICENSE * * wrote this file. As long as you retain this notice you * can do whatever you want with this stuff. If we meet some day, and you * think this stuff is worth it, you can buy me a beer in return. * * Dan Moschuk */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include #include #include #include #include #define ARC4_RESEED_BYTES 65536 #define ARC4_RESEED_SECONDS 300 #define ARC4_KEYBYTES 256 int arc4rand_iniseed_state = ARC4_ENTR_NONE; MALLOC_DEFINE(M_ARC4RANDOM, "arc4random", "arc4random structures"); struct arc4_s { struct mtx mtx; u_int8_t i, j; int numruns; u_int8_t sbox[256]; time_t t_reseed; } __aligned(CACHE_LINE_SIZE); static struct arc4_s *arc4inst = NULL; #define ARC4_FOREACH(_arc4) \ for (_arc4 = &arc4inst[0]; _arc4 <= &arc4inst[mp_maxid]; _arc4++) static u_int8_t arc4_randbyte(struct arc4_s *arc4); static __inline void arc4_swap(u_int8_t *a, u_int8_t *b) { u_int8_t c; c = *a; *a = *b; *b = c; } /* * Stir our S-box. */ static void arc4_randomstir(struct arc4_s* arc4) { u_int8_t key[ARC4_KEYBYTES]; int n; struct timeval tv_now; /* * XXX: FIX!! This isn't brilliant. Need more confidence. * This returns zero entropy before random(4) is seeded. */ (void)read_random(key, ARC4_KEYBYTES); getmicrouptime(&tv_now); mtx_lock(&arc4->mtx); for (n = 0; n < 256; n++) { arc4->j = (arc4->j + arc4->sbox[n] + key[n]) % 256; arc4_swap(&arc4->sbox[n], &arc4->sbox[arc4->j]); } arc4->i = arc4->j = 0; /* Reset for next reseed cycle. */ arc4->t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS; arc4->numruns = 0; /* * Throw away the first N words of output, as suggested in the * paper "Weaknesses in the Key Scheduling Algorithm of RC4" - * by Fluher, Mantin, and Shamir. (N = 256 in our case.) + * by Fluher, Mantin, and Shamir. (N = 768 in our case.) * * http://dl.acm.org/citation.cfm?id=646557.694759 */ - for (n = 0; n < 256*4; n++) + for (n = 0; n < 768*4; n++) arc4_randbyte(arc4); mtx_unlock(&arc4->mtx); } /* * Initialize our S-box to its beginning defaults. */ static void arc4_init(void) { struct arc4_s *arc4; int n; arc4inst = malloc((mp_maxid + 1) * sizeof(struct arc4_s), M_ARC4RANDOM, M_NOWAIT | M_ZERO); KASSERT(arc4inst != NULL, ("arc4_init: memory allocation error")); ARC4_FOREACH(arc4) { mtx_init(&arc4->mtx, "arc4_mtx", NULL, MTX_DEF); arc4->i = arc4->j = 0; for (n = 0; n < 256; n++) arc4->sbox[n] = (u_int8_t) n; arc4->t_reseed = -1; arc4->numruns = 0; } } SYSINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL); static void arc4_uninit(void) { struct arc4_s *arc4; ARC4_FOREACH(arc4) { mtx_destroy(&arc4->mtx); } free(arc4inst, M_ARC4RANDOM); } SYSUNINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_uninit, NULL); /* * Generate a random byte. */ static u_int8_t arc4_randbyte(struct arc4_s *arc4) { u_int8_t arc4_t; arc4->i = (arc4->i + 1) % 256; arc4->j = (arc4->j + arc4->sbox[arc4->i]) % 256; arc4_swap(&arc4->sbox[arc4->i], &arc4->sbox[arc4->j]); arc4_t = (arc4->sbox[arc4->i] + arc4->sbox[arc4->j]) % 256; return arc4->sbox[arc4_t]; } /* * MPSAFE */ void arc4rand(void *ptr, u_int len, int reseed) { u_char *p; struct timeval tv; struct arc4_s *arc4; if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state, ARC4_ENTR_HAVE, ARC4_ENTR_SEED)) { ARC4_FOREACH(arc4) arc4_randomstir(arc4); } arc4 = &arc4inst[curcpu]; getmicrouptime(&tv); if ((arc4->numruns > ARC4_RESEED_BYTES) || (tv.tv_sec > arc4->t_reseed)) arc4_randomstir(arc4); mtx_lock(&arc4->mtx); arc4->numruns += len; p = ptr; while (len--) *p++ = arc4_randbyte(arc4); mtx_unlock(&arc4->mtx); } uint32_t arc4random(void) { uint32_t ret; arc4rand(&ret, sizeof ret, 0); return ret; }