Date: Sat, 18 Aug 2018 06:20:46 +0000 (UTC) From: Xin LI <delphij@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r337997 - head/lib/libc/gen Message-ID: <201808180620.w7I6Kk5M050042@repo.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: delphij Date: Sat Aug 18 06:20:45 2018 New Revision: 337997 URL: https://svnweb.freebsd.org/changeset/base/337997 Log: Split arc4random_uniform into it's own file and sync with OpenBSD. PR: 182610 Obtained from: OpenBSD MFC after: 2 weeks Added: head/lib/libc/gen/arc4random_uniform.c (contents, props changed) - copied, changed from r337993, head/lib/libc/gen/arc4random.c Modified: head/lib/libc/gen/Makefile.inc head/lib/libc/gen/arc4random.c Modified: head/lib/libc/gen/Makefile.inc ============================================================================== --- head/lib/libc/gen/Makefile.inc Sat Aug 18 04:23:51 2018 (r337996) +++ head/lib/libc/gen/Makefile.inc Sat Aug 18 06:20:45 2018 (r337997) @@ -16,6 +16,7 @@ SRCS+= __getosreldate.c \ _thread_init.c \ alarm.c \ arc4random.c \ + arc4random_uniform.c \ assert.c \ auxv.c \ basename.c \ Modified: head/lib/libc/gen/arc4random.c ============================================================================== --- head/lib/libc/gen/arc4random.c Sat Aug 18 04:23:51 2018 (r337996) +++ head/lib/libc/gen/arc4random.c Sat Aug 18 06:20:45 2018 (r337997) @@ -244,41 +244,6 @@ arc4random_buf(void *_buf, size_t n) _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 <stdio.h> Copied and modified: head/lib/libc/gen/arc4random_uniform.c (from r337993, head/lib/libc/gen/arc4random.c) ============================================================================== --- head/lib/libc/gen/arc4random.c Sat Aug 18 01:12:44 2018 (r337993, copy source) +++ head/lib/libc/gen/arc4random_uniform.c Sat Aug 18 06:20:45 2018 (r337997) @@ -1,7 +1,6 @@ -/* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */ +/* $OpenBSD: arc4random_uniform.c,v 1.2 2015/09/13 08:31:47 guenther Exp $ */ /* - * Copyright (c) 1996, David Mazieres <dm@uun.org> * Copyright (c) 2008, Damien Miller <djm@openbsd.org> * * Permission to use, copy, modify, and distribute this software for any @@ -15,235 +14,13 @@ * 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. + * $FreeBSD$ */ -#include <sys/cdefs.h> -__FBSDID("$FreeBSD$"); - -#include "namespace.h" -#include <fcntl.h> -#include <limits.h> +#include <sys/types.h> #include <stdlib.h> -#include <unistd.h> -#include <sys/param.h> -#include <sys/sysctl.h> -#include <sys/time.h> -#include <pthread.h> -#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 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; -} - -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 < 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". @@ -254,16 +31,17 @@ arc4random_buf(void *_buf, size_t n) * [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) +uint32_t +arc4random_uniform(uint32_t upper_bound) { - u_int32_t r, min; + uint32_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 @@ -278,24 +56,3 @@ arc4random_uniform(u_int32_t upper_bound) return r % upper_bound; } - -#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; - - v = rdtsc(); - for (i = 0; i < iter; i++) - arc4random(); - v = rdtsc() - v; - v /= iter; - - printf("%qd cycles\n", v); -} -#endif
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201808180620.w7I6Kk5M050042>