From owner-svn-src-head@freebsd.org Sat Aug 18 06:20:47 2018 Return-Path: Delivered-To: svn-src-head@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 288EC1086EEE; Sat, 18 Aug 2018 06:20:47 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id CC24983DED; Sat, 18 Aug 2018 06:20:46 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id AD48B13B8E; Sat, 18 Aug 2018 06:20:46 +0000 (UTC) (envelope-from delphij@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w7I6Kkil050045; Sat, 18 Aug 2018 06:20:46 GMT (envelope-from delphij@FreeBSD.org) Received: (from delphij@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w7I6Kk5M050042; Sat, 18 Aug 2018 06:20:46 GMT (envelope-from delphij@FreeBSD.org) Message-Id: <201808180620.w7I6Kk5M050042@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: delphij set sender to delphij@FreeBSD.org using -f From: Xin LI Date: Sat, 18 Aug 2018 06:20:46 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r337997 - head/lib/libc/gen X-SVN-Group: head X-SVN-Commit-Author: delphij X-SVN-Commit-Paths: head/lib/libc/gen X-SVN-Commit-Revision: 337997 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.27 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 18 Aug 2018 06:20:47 -0000 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 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 * Copyright (c) 2008, Damien Miller * * 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 -__FBSDID("$FreeBSD$"); - -#include "namespace.h" -#include -#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 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 -#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