introduce a isc_random_uniform() function to return a uniformly distributed

number 0 < x <= upper_bound and use it to correct the last tiny bias in the
shuffle initialisation

feedback & ok deraadt@

3 files changed, 72 insertions, 25 deletions

diff --git a/usr.sbin/bind/lib/isc/include/isc/random.h b/usr.sbin/bind/lib/isc/include/isc/random.h
index b7304c2b5e8..8b2b1800c37 100644
--- a/usr.sbin/bind/lib/isc/include/isc/random.h
+++ b/usr.sbin/bind/lib/isc/include/isc/random.h
@@ -1,21 +1,21 @@
 /*
+ * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
  * Copyright (C) 1999-2001  Internet Software Consortium.
  *
  * 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.
  *
- * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM
- * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
- * INTERNET SOFTWARE CONSORTIUM 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.
+ * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
+ * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+ * AND FITNESS.  IN NO EVENT SHALL ISC 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.
  */
 
-/* $ISC: random.h,v 1.11 2001/01/09 21:57:23 bwelling Exp $ */
+/* $ISC: random.h,v 1.12.18.2 2005/04/29 00:17:01 marka Exp $ */
 
 #ifndef ISC_RANDOM_H
 #define ISC_RANDOM_H 1
@@ -23,9 +23,11 @@
 #include <isc/lang.h>
 #include <isc/types.h>
 
-/*
- * Implements a random state pool which will let the caller return a
- * series of possibly non-reproducable random values.  Note that the
+/*! \file
+ * \brief Implements a random state pool which will let the caller return a
+ * series of possibly non-reproducable random values.  
+ *
+ * Note that the
  * strength of these numbers is not all that high, and should not be
  * used in cryptography functions.  It is useful for jittering values
  * a bit here and there, such as timeouts, etc.
@@ -35,13 +37,13 @@ ISC_LANG_BEGINDECLS
 
 void
 isc_random_seed(isc_uint32_t seed);
-/*
+/*%<
  * Set the initial seed of the random state.
  */
 
 void
 isc_random_get(isc_uint32_t *val);
-/*
+/*%<
  * Get a random value.
  *
  * Requires:
@@ -50,11 +52,18 @@ isc_random_get(isc_uint32_t *val);
 
 isc_uint32_t
 isc_random_jitter(isc_uint32_t max, isc_uint32_t jitter);
-/*
+/*%<
  * Get a random value between (max - jitter) and (max).
  * This is useful for jittering timer values.
  */
 
+isc_uint32_t
+isc_random_uniform(isc_uint32_t upper_bound);
+/*%<
+ * Get a uniformly distributed random value < upper_bound.
+ * Avoid bias when upper_bound is not a power of two.
+ */
+
 ISC_LANG_ENDDECLS
 
 #endif /* ISC_RANDOM_H */
diff --git a/usr.sbin/bind/lib/isc/random.c b/usr.sbin/bind/lib/isc/random.c
index 442d35cd485..4f74f8b6d50 100644
--- a/usr.sbin/bind/lib/isc/random.c
+++ b/usr.sbin/bind/lib/isc/random.c
@@ -1,6 +1,7 @@
 /*
  * Copyright (C) 2004, 2005  Internet Systems Consortium, Inc. ("ISC")
  * Copyright (C) 1999-2003  Internet Software Consortium.
+ * Copyright (C) 2008 Damien Miller
  *
  * Permission to use, copy, modify, and distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
@@ -91,14 +92,54 @@ isc_random_get(isc_uint32_t *val)
 }
 
 isc_uint32_t
+isc_random_uniform(isc_uint32_t upper_bound)
+{
+	isc_uint32_t r, min;
+
+	/*
+	 * 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.
+	 */
+
+	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 doing this, 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 (;;) {
+		isc_random_get(&r);
+		if (r >= min)
+			break;
+	}
+
+	return r % upper_bound;
+}
+
+isc_uint32_t
 isc_random_jitter(isc_uint32_t max, isc_uint32_t jitter) {
 	REQUIRE(jitter < max);
 	if (jitter == 0)
 		return (max);
 	else
-#ifndef HAVE_ARC4RANDOM
-		return (max - rand() % jitter);
-#else
-		return (max - arc4random() % jitter);
-#endif
+		return max - isc_random_uniform(jitter);
 }
+
diff --git a/usr.sbin/bind/lib/isc/shuffle.c b/usr.sbin/bind/lib/isc/shuffle.c
index 8dc114d166f..5e8bb6f9529 100644
--- a/usr.sbin/bind/lib/isc/shuffle.c
+++ b/usr.sbin/bind/lib/isc/shuffle.c
@@ -15,7 +15,7 @@
  * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
-/* $OpenBSD: shuffle.c,v 1.1 2008/02/29 12:21:12 deraadt Exp $ */
+/* $OpenBSD: shuffle.c,v 1.2 2008/03/02 22:39:12 djm Exp $ */
 
 #include <config.h>
 
@@ -31,7 +31,6 @@
 void
 isc_shuffle_init(isc_shuffle_t *shuffle)
 {
-	isc_uint32_t si;
 	isc_uint16_t r;
 	int i, i2;
 
@@ -43,9 +42,7 @@ isc_shuffle_init(isc_shuffle_t *shuffle)
 
 	/* Initialize using a Durstenfeld shuffle */
 	for (i = 65536; --i; ) {
-		isc_random_get(&si);
-		/* disregard the modulo bias because it is small */
-		i2 = (si % (i + 1)) & 0xffff;
+		i2 = isc_random_uniform(i + 1);
 		r = shuffle->id_shuffle[i];
 		shuffle->id_shuffle[i] = shuffle->id_shuffle[i2];
 		shuffle->id_shuffle[i2] = r;