diff options
author | Otto Moerbeek <otto@cvs.openbsd.org> | 2008-03-16 19:47:44 +0000 |
---|---|---|
committer | Otto Moerbeek <otto@cvs.openbsd.org> | 2008-03-16 19:47:44 +0000 |
commit | 184652f0aac51db18e318953058474a7ac4493b6 (patch) | |
tree | 6e7242d79cb5d0773cd151043408f25fec5d6fb9 /lib | |
parent | 75714c460fcad691f65aac83a88aa5e47478871f (diff) |
diff from djm@ committed at his request:
introduce two new APIs for requesting strong random numbers:
arc4random_buf() - fill an arbitrary memory range with random numbers
arc4random_uniform() - return a uniformly distributed random number
below
a specified upper bound, avoiding the bias that comes from a naive
"arc4random() % upper_bound" construction.
these mirror similarly-named functions in the kernel;
lots of discussion deraadt@ mcbride@
Diffstat (limited to 'lib')
-rw-r--r-- | lib/libc/crypt/arc4random.3 | 23 | ||||
-rw-r--r-- | lib/libc/crypt/arc4random.c | 64 |
2 files changed, 84 insertions, 3 deletions
diff --git a/lib/libc/crypt/arc4random.3 b/lib/libc/crypt/arc4random.3 index 31da5ec7ec0..d32ea4a9519 100644 --- a/lib/libc/crypt/arc4random.3 +++ b/lib/libc/crypt/arc4random.3 @@ -1,4 +1,4 @@ -.\" $OpenBSD: arc4random.3,v 1.22 2007/05/31 19:19:27 jmc Exp $ +.\" $OpenBSD: arc4random.3,v 1.23 2008/03/16 19:47:43 otto Exp $ .\" .\" Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de> .\" All rights reserved. @@ -30,7 +30,7 @@ .\" .\" Manual page, using -mandoc macros .\" -.Dd $Mdocdate: May 31 2007 $ +.Dd $Mdocdate: March 16 2008 $ .Dt ARC4RANDOM 3 .Os .Sh NAME @@ -43,6 +43,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 "u_char *dat" "int datlen" @@ -73,6 +77,21 @@ versus the fast but poor quality interfaces described in and .Xr drand48 3 . .Pp +.Fn arc4random_buf +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 +.Do Li arc4random() % upper_bound Dc +as it avoids "modulo bias" when the upper bound is not a power of two. +.Pp The .Fn arc4random_stir function reads data from diff --git a/lib/libc/crypt/arc4random.c b/lib/libc/crypt/arc4random.c index 8604548f3fc..bbe42bd204d 100644 --- a/lib/libc/crypt/arc4random.c +++ b/lib/libc/crypt/arc4random.c @@ -1,7 +1,8 @@ -/* $OpenBSD: arc4random.c,v 1.17 2008/01/01 00:43:39 kurt Exp $ */ +/* $OpenBSD: arc4random.c,v 1.18 2008/03/16 19:47:43 otto 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 * purpose with or without fee is hereby granted, provided that the above @@ -34,6 +35,7 @@ */ #include <fcntl.h> +#include <limits.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> @@ -188,6 +190,66 @@ arc4random(void) return val; } +void +arc4random_buf(void *_buf, size_t n) +{ + u_char *buf = (u_char *)_buf; + _ARC4_LOCK(); + if (!rs_initialized || arc4_stir_pid != getpid()) + arc4_stir(); + 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; + +#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> |