diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | Versions | 3 | ||||
| -rw-r--r-- | src/arc4random.3 | 28 | ||||
| -rw-r--r-- | src/arc4random.c | 195 | ||||
| -rw-r--r-- | src/arc4random_buf.3 | 1 | ||||
| -rw-r--r-- | src/arc4random_uniform.3 | 1 |
6 files changed, 167 insertions, 63 deletions
@@ -74,7 +74,9 @@ LIB_MANS_GEN := \ LIB_MANS := \ arc4random.3 \ arc4random_addrandom.3 \ + arc4random_buf.3 \ arc4random_stir.3 \ + arc4random_uniform.3 \ strtonum.3 \ strlcpy.3 \ strlcat.3 \ @@ -60,5 +60,8 @@ LIBBSD_0.2 { pidfile_remove; setproctitle; + + arc4random_buf; + arc4random_uniform; } LIBBSD_0.1; diff --git a/src/arc4random.3 b/src/arc4random.3 index 09c24c6..1043602 100644 --- a/src/arc4random.3 +++ b/src/arc4random.3 @@ -28,13 +28,15 @@ .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" .\" Manual page, using -mandoc macros -.\" $FreeBSD: /repoman/r/ncvs/src/lib/libc/gen/arc4random.3,v 1.16 2003/07/31 06:18:24 das Exp $ +.\" $FreeBSD$ .\" .Dd April 15, 1997 .Dt ARC4RANDOM 3 .Os .Sh NAME .Nm arc4random , +.Nm arc4random_buf , +.Nm arc4random_uniform , .Nm arc4random_stir , .Nm arc4random_addrandom .Nd arc4 random number generator @@ -46,6 +48,10 @@ .Ft u_int32_t .Fn arc4random "void" .Ft void +.Fn arc4random_buf "void *buf" "size_t nbytes" +.Ft u_int32_t +.Fn arc4random_uniform "u_int32_t upper_bound" +.Ft void .Fn arc4random_stir "void" .Ft void .Fn arc4random_addrandom "unsigned char *dat" "int datlen" @@ -69,6 +75,21 @@ and therefore has twice the range of and .Xr random 3 . .Pp +.Fn arc4random_buf +function fills the region +.Fa buf +of length +.Fa nbytes +with ARC4-derived random data. +.Pp +.Fn arc4random_uniform +will return a uniformly distributed random number less than +.Fa upper_bound . +.Fn arc4random_uniform +is recommended over constructions like +.Dq Li arc4random() % upper_bound +as it avoids "modulo bias" when the upper bound is not a power of two. +.Pp The .Fn arc4random_stir function reads data from @@ -79,10 +100,9 @@ and uses it to permute the S-Boxes via There is no need to call .Fn arc4random_stir before using -.Fn arc4random , -since .Fn arc4random -automatically initializes itself. +functions family, since +they automatically initialize themselves. .Sh EXAMPLES The following produces a drop-in replacement for the traditional .Fn rand diff --git a/src/arc4random.c b/src/arc4random.c index 5c1837e..20fce09 100644 --- a/src/arc4random.c +++ b/src/arc4random.c @@ -1,14 +1,23 @@ /* - * Arc4 random number generator for OpenBSD. - * Copyright 1996 David Mazieres <dm@lcs.mit.edu>. + * 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 + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. * - * Modification and redistribution in source and binary forms is - * permitted provided that due credit is given to the author and the - * OpenBSD project (for instance by leaving this copyright notice - * intact). + * 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 @@ -24,7 +33,7 @@ */ #include <sys/cdefs.h> -__FBSDID("$FreeBSD: src/lib/libc/gen/arc4random.c,v 1.10 2004/03/24 14:44:57 green Exp $"); +__FBSDID("$FreeBSD$"); #include <sys/types.h> #include <sys/time.h> @@ -40,6 +49,8 @@ struct arc4_stream { }; #define RANDOMDEV "/dev/urandom" +#define KEYSIZE 128 + #ifdef __REENTRANT static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; #define THREAD_LOCK() pthread_mutex_lock(&arc4random_mtx) @@ -52,58 +63,63 @@ static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER; static struct arc4_stream rs; static int rs_initialized; static int rs_stired; +static int arc4_count; -static inline u_int8_t arc4_getbyte(struct arc4_stream *); -static void arc4_stir(struct arc4_stream *); +static inline u_int8_t arc4_getbyte(void); +static void arc4_stir(void); static inline void -arc4_init(struct arc4_stream *as) +arc4_init(void) { int n; for (n = 0; n < 256; n++) - as->s[n] = n; - as->i = 0; - as->j = 0; + rs.s[n] = n; + rs.i = 0; + rs.j = 0; } static inline void -arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen) +arc4_addrandom(u_char *dat, int datlen) { int n; u_int8_t si; - as->i--; + rs.i--; for (n = 0; n < 256; n++) { - as->i = (as->i + 1); - si = as->s[as->i]; - as->j = (as->j + si + dat[n % datlen]); - as->s[as->i] = as->s[as->j]; - as->s[as->j] = si; + 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 void -arc4_stir(struct arc4_stream *as) +arc4_stir(void) { - int fd, n; + int done, fd, n; struct { - struct timeval tv; - pid_t pid; - u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)]; - } rdat; + struct timeval tv; + pid_t pid; + u_int8_t rnd[KEYSIZE]; + } rdat; - gettimeofday(&rdat.tv, NULL); - rdat.pid = getpid(); fd = open(RANDOMDEV, O_RDONLY, 0); + done = 0; if (fd >= 0) { - (void) read(fd, rdat.rnd, sizeof(rdat.rnd)); - close(fd); + if (read(fd, &rdat, KEYSIZE) == KEYSIZE) + done = 1; + (void)close(fd); } - /* fd < 0? Ah, what the heck. We'll just take whatever was on the - * stack... */ + if (!done) { + (void)gettimeofday(&rdat.tv, NULL); + rdat.pid = getpid(); + /* We'll just take whatever was on the stack too... */ + } - arc4_addrandom(as, (void *) &rdat, sizeof(rdat)); + arc4_addrandom((u_char *)&rdat, KEYSIZE); /* * Throw away the first N bytes of output, as suggested in the @@ -113,33 +129,34 @@ arc4_stir(struct arc4_stream *as) * by Ilya Mironov. */ for (n = 0; n < 1024; n++) - arc4_getbyte(as); + (void) arc4_getbyte(); + arc4_count = 1600000; } static inline u_int8_t -arc4_getbyte(struct arc4_stream *as) +arc4_getbyte(void) { u_int8_t si, sj; - as->i = (as->i + 1); - si = as->s[as->i]; - as->j = (as->j + si); - sj = as->s[as->j]; - as->s[as->i] = sj; - as->s[as->j] = si; + 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 (as->s[(si + sj) & 0xff]); + return (rs.s[(si + sj) & 0xff]); } static inline u_int32_t -arc4_getword(struct arc4_stream *as) +arc4_getword(void) { u_int32_t val; - val = arc4_getbyte(as) << 24; - val |= arc4_getbyte(as) << 16; - val |= arc4_getbyte(as) << 8; - val |= arc4_getbyte(as); + val = arc4_getbyte() << 24; + val |= arc4_getbyte() << 16; + val |= arc4_getbyte() << 8; + val |= arc4_getbyte(); return (val); } @@ -148,55 +165,115 @@ static void arc4_check_init(void) { if (!rs_initialized) { - arc4_init(&rs); + arc4_init(); rs_initialized = 1; } } -static void +static inline void arc4_check_stir(void) { - if (!rs_stired) { - arc4_stir(&rs); + if (!rs_stired || arc4_count <= 0) { + arc4_stir(); rs_stired = 1; } } void -arc4random_stir() +arc4random_stir(void) { THREAD_LOCK(); arc4_check_init(); - arc4_stir(&rs); + arc4_stir(); + rs_stired = 1; THREAD_UNLOCK(); } void -arc4random_addrandom(dat, datlen) - u_char *dat; - int datlen; +arc4random_addrandom(u_char *dat, int datlen) { THREAD_LOCK(); arc4_check_init(); arc4_check_stir(); - arc4_addrandom(&rs, dat, datlen); + arc4_addrandom(dat, datlen); THREAD_UNLOCK(); } u_int32_t -arc4random() +arc4random(void) { u_int32_t rnd; THREAD_LOCK(); arc4_check_init(); arc4_check_stir(); - rnd = arc4_getword(&rs); + rnd = arc4_getword(); + arc4_count -= 4; THREAD_UNLOCK(); return (rnd); } +void +arc4random_buf(void *_buf, size_t n) +{ + u_char *buf = (u_char *)_buf; + + THREAD_LOCK(); + arc4_check_init(); + while (n--) { + arc4_check_stir(); + buf[n] = arc4_getbyte(); + arc4_count--; + } + THREAD_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); + +#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 (r % upper_bound); +} + #if 0 /*-------- Test code for i386 --------*/ #include <stdio.h> diff --git a/src/arc4random_buf.3 b/src/arc4random_buf.3 new file mode 100644 index 0000000..74a34ce --- /dev/null +++ b/src/arc4random_buf.3 @@ -0,0 +1 @@ +.so man3/arc4random.3 diff --git a/src/arc4random_uniform.3 b/src/arc4random_uniform.3 new file mode 100644 index 0000000..74a34ce --- /dev/null +++ b/src/arc4random_uniform.3 @@ -0,0 +1 @@ +.so man3/arc4random.3 |