From a4be7c23fdcf8a1da5420068dc4bd4db45af9c9c Mon Sep 17 00:00:00 2001 From: Damien Miller Date: Mon, 19 May 2008 14:47:37 +1000 Subject: - (djm) [openbsd-compat/bsd-arc4random.c openbsd-compat/openbsd-compat.c] [configure.ac] Implement arc4random_buf(), import implementation of arc4random_uniform() from OpenBSD --- openbsd-compat/bsd-arc4random.c | 65 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) (limited to 'openbsd-compat/bsd-arc4random.c') diff --git a/openbsd-compat/bsd-arc4random.c b/openbsd-compat/bsd-arc4random.c index d45fb182a..8bf31e5d3 100644 --- a/openbsd-compat/bsd-arc4random.c +++ b/openbsd-compat/bsd-arc4random.c @@ -82,3 +82,68 @@ arc4random_stir(void) rc4_ready = REKEY_BYTES; } #endif /* !HAVE_ARC4RANDOM */ + +#ifndef ARC4RANDOM_BUF +void +arc4random_buf(void *_buf, size_t n) +{ + size_t i; + u_int32_t r; + char *buf = (char *)_buf; + + for (i = 0; i < n; i++) { + if (i % 4 == 0) + r = arc4random(); + buf[i] = r & 0xff; + r >>= 8; + } + i = r = 0; +} +#endif /* !HAVE_ARC4RANDOM_BUF */ + +#ifndef ARC4RANDOM_UNIFORM +/* + * 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; +} +#endif /* !HAVE_ARC4RANDOM_UNIFORM */ -- cgit v1.2.3 From caaed01e90edc41d43334868f14f4f994927b2cd Mon Sep 17 00:00:00 2001 From: Damien Miller Date: Mon, 19 May 2008 15:26:54 +1000 Subject: - (djm) [openbsd-compat/bsd-arc4random.c] Warning fixes --- ChangeLog | 3 ++- openbsd-compat/bsd-arc4random.c | 3 ++- 2 files changed, 4 insertions(+), 2 deletions(-) (limited to 'openbsd-compat/bsd-arc4random.c') diff --git a/ChangeLog b/ChangeLog index 567222e96..6907bbd14 100644 --- a/ChangeLog +++ b/ChangeLog @@ -14,6 +14,7 @@ - (djm) [openbsd-compat/bsd-arc4random.c openbsd-compat/openbsd-compat.c] [configure.ac] Implement arc4random_buf(), import implementation of arc4random_uniform() from OpenBSD + - (djm) [openbsd-compat/bsd-arc4random.c] Warning fixes - (djm) OpenBSD CVS Sync - djm@cvs.openbsd.org 2008/04/13 00:22:17 [dh.c sshd.c] @@ -3935,4 +3936,4 @@ OpenServer 6 and add osr5bigcrypt support so when someone migrates passwords between UnixWare and OpenServer they will still work. OK dtucker@ -$Id: ChangeLog,v 1.4920 2008/05/19 05:05:07 djm Exp $ +$Id: ChangeLog,v 1.4921 2008/05/19 05:26:54 djm Exp $ diff --git a/openbsd-compat/bsd-arc4random.c b/openbsd-compat/bsd-arc4random.c index 8bf31e5d3..92e7e7b58 100644 --- a/openbsd-compat/bsd-arc4random.c +++ b/openbsd-compat/bsd-arc4random.c @@ -19,6 +19,7 @@ #include #include +#include #include #include "log.h" @@ -88,7 +89,7 @@ void arc4random_buf(void *_buf, size_t n) { size_t i; - u_int32_t r; + u_int32_t r = 0; char *buf = (char *)_buf; for (i = 0; i < n; i++) { -- cgit v1.2.3 From 58ea61ba2a747e4f0beb3afcbbdea8ada5119143 Mon Sep 17 00:00:00 2001 From: Damien Miller Date: Wed, 4 Jun 2008 10:54:00 +1000 Subject: - (djm) [openbsd-compat/bsd-arc4random.c] Fix math bug that caused bias in arc4random_uniform with upper_bound in (2^30,2*31). Note that OpenSSH did not make requests with upper bounds in this range. --- ChangeLog | 7 ++++++- openbsd-compat/bsd-arc4random.c | 2 +- 2 files changed, 7 insertions(+), 2 deletions(-) (limited to 'openbsd-compat/bsd-arc4random.c') diff --git a/ChangeLog b/ChangeLog index 713e09dbe..727767210 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,8 @@ +20080604 + - (djm) [openbsd-compat/bsd-arc4random.c] Fix math bug that caused bias + in arc4random_uniform with upper_bound in (2^30,2*31). Note that + OpenSSH did not make requests with upper bounds in this range. + 20080519 - (djm) [configure.ac mux.c sftp.c openbsd-compat/Makefile.in] [openbsd-compat/fmt_scaled.c openbsd-compat/openbsd-compat.h] @@ -4023,4 +4028,4 @@ OpenServer 6 and add osr5bigcrypt support so when someone migrates passwords between UnixWare and OpenServer they will still work. OK dtucker@ -$Id: ChangeLog,v 1.4935 2008/05/19 22:57:06 djm Exp $ +$Id: ChangeLog,v 1.4936 2008/06/04 00:54:00 djm Exp $ diff --git a/openbsd-compat/bsd-arc4random.c b/openbsd-compat/bsd-arc4random.c index 92e7e7b58..9d4c8690e 100644 --- a/openbsd-compat/bsd-arc4random.c +++ b/openbsd-compat/bsd-arc4random.c @@ -129,7 +129,7 @@ arc4random_uniform(u_int32_t upper_bound) 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; + min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound; } #endif -- cgit v1.2.3