replacement algorithm. initialize a 64K-short buffer using Durstenfeld

shuffle. Upon allocation, swap-permute the new value to a random slot in
the 0..32K-1 th entry of the buffer as we move forward, ensuring randomness
but also satisfying the non-repeating property we need.  Inspired by Dillon's
implementation for ip id.
We believe this is easier to read though, initializes with less bias and wins
speed tests.
Thanks a lot to mcbride and djm for doing a bunch of statistical and speed
analysis, and comments from nordin
ok jakob djm mcbride

7 files changed, 143 insertions, 280 deletions

diff --git a/usr.sbin/bind/README.OpenBSD b/usr.sbin/bind/README.OpenBSD
index 2b5d8ae46a7..e5836a5a530 100644
--- a/usr.sbin/bind/README.OpenBSD
+++ b/usr.sbin/bind/README.OpenBSD
@@ -1,11 +1,11 @@
-$OpenBSD: README.OpenBSD,v 1.8 2004/09/28 17:14:01 jakob Exp $
+$OpenBSD: README.OpenBSD,v 1.9 2008/02/29 12:21:10 deraadt Exp $
 
 additional features
 
 - write pid-file before chroot
 - privilege separation for binding to privileged ports from within chroot
-- add LCG (Linear Congruential Generator) implementation to libisc
-- use LCG instead of LFSR for ID generation until LFSR is proven reliable
+- add 64K entry shuffle (somewhat like Fisher-Yates) implementation to libisc
+- use shuffle instead of LFSR for ID generation
 - strlcpy/strlcat/snprintf fixes
 
 default parameter changes
diff --git a/usr.sbin/bind/lib/dns/dispatch.c b/usr.sbin/bind/lib/dns/dispatch.c
index 5d36372bbb7..dbd50b577f8 100644
--- a/usr.sbin/bind/lib/dns/dispatch.c
+++ b/usr.sbin/bind/lib/dns/dispatch.c
@@ -26,7 +26,7 @@
 #include <unistd.h>
 
 #include <isc/entropy.h>
-#include <isc/lcg.h>
+#include <isc/shuffle.h>
 #include <isc/mem.h>
 #include <isc/mutex.h>
 #include <isc/print.h>
@@ -61,7 +61,7 @@ typedef struct dns_qid {
 	unsigned int	qid_nbuckets;	/*%< hash table size */
 	unsigned int	qid_increment;	/*%< id increment on collision */
 	isc_mutex_t	lock;
-	isc_lcg_t	qid_lcg;	/* state generator info */
+	isc_shuffle_t	qid_shuffle;	/* state generator info */
 	dns_nsid_t      nsid;
 	dns_displist_t	*qid_table;	/*%< the table itself */
 } dns_qid_t;
@@ -284,7 +284,7 @@ static dns_messageid_t
 dns_randomid(dns_qid_t *qid) {
 	isc_uint16_t id;
 
-	id = isc_lcg_generate16(&qid->qid_lcg);
+	id = isc_shuffle_generate16(&qid->qid_shuffle);
 
 	return ((dns_messageid_t)id);
 }
@@ -1444,7 +1444,7 @@ qid_allocate(dns_dispatchmgr_t *mgr, unsigned int buckets,
 	qid->qid_increment = increment;
 	qid->magic = QID_MAGIC;
 
-	isc_lcg_init(&qid->qid_lcg);
+	isc_shuffle_init(&qid->qid_shuffle);
 
 	*qidp = qid;
 	return (ISC_R_SUCCESS);
diff --git a/usr.sbin/bind/lib/isc/Makefile.in b/usr.sbin/bind/lib/isc/Makefile.in
index 88478f6e177..3b93c655561 100644
--- a/usr.sbin/bind/lib/isc/Makefile.in
+++ b/usr.sbin/bind/lib/isc/Makefile.in
@@ -54,7 +54,7 @@ WIN32OBJS = 	win32/condition.@O@ win32/dir.@O@ win32/file.@O@ \
 OBJS =		@ISC_EXTRA_OBJS@ \
 		assertions.@O@ base64.@O@ bitstring.@O@ buffer.@O@ \
 		bufferlist.@O@ commandline.@O@ error.@O@ event.@O@ \
-		lcg.@O@ \
+		shuffle.@O@ \
 		hash.@O@ heap.@O@ hex.@O@ hmacmd5.@O@ hmacsha.@O@\
 		lex.@O@ lfsr.@O@ lib.@O@ log.@O@ md5.@O@ \
 		mem.@O@ mutexblock.@O@ netaddr.@O@ netscope.@O@ ondestroy.@O@ \
@@ -68,7 +68,7 @@ OBJS =		@ISC_EXTRA_OBJS@ \
 SRCS =		@ISC_EXTRA_SRCS@ \
 		assertions.c base64.c bitstring.c buffer.c \
 		bufferlist.c commandline.c error.c event.c \
-		lcg.c \
+		shuffle.c \
 		heap.c hex.c hmacmd5.c hmacsha.c \
 		lex.c lfsr.c lib.c log.c \
 		md5.c mem.c mutexblock.c netaddr.c netscope.c ondestroy.c \
diff --git a/usr.sbin/bind/lib/isc/include/isc/lcg.h b/usr.sbin/bind/lib/isc/include/isc/lcg.h
deleted file mode 100644
index 6c50c36c2aa..00000000000
--- a/usr.sbin/bind/lib/isc/include/isc/lcg.h
+++ /dev/null
@@ -1,98 +0,0 @@
-/*
- * Portions Copyright (C) 2002  Internet Software Consortium.
- * Portions Copyright (C) 1997  Niels Provos.
- *
- * 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.
- */
-
-/* $OpenBSD: lcg.h,v 1.2 2004/09/28 17:14:07 jakob Exp $ */
-
-/*
- * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
- * such a mathematical system to generate more random (yet non-repeating)
- * ids to solve the resolver/named problem.  But Niels designed the
- * actual system based on the constraints.
- */
-
-/*
- * seed = random 15bit
- * n = prime, g0 = generator to n,
- * j = random so that gcd(j,n-1) == 1
- * g = g0^j mod n will be a generator again.
- *
- * X[0] = random seed.
- * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
- * with a = 7^(even random) mod m, 
- *      b = random with gcd(b,m) == 1
- *      m = 31104 and a maximal period of m-1.
- *
- * The transaction id is determined by:
- * id[n] = seed xor (g^X[n] mod n)
- *
- * Effectivly the id is restricted to the lower 15 bits, thus
- * yielding two different cycles by toggling the msb on and off.
- * This avoids reuse issues caused by reseeding.
- *
- * The 16 bit space is very small and brute force attempts are
- * entirly feasible, we skip a random number of transaction ids
- * so that an attacker will not get sequential ids.
- */
-
-
-#ifndef ISC_LCG_H
-#define ISC_LCG_H 1
-
-#include <isc/lang.h>
-#include <isc/types.h>
-
-typedef struct isc_lcg isc_lcg_t;
-
-struct isc_lcg {
-	isc_uint16_t ru_x;
-	isc_uint16_t ru_seed, ru_seed2;
-	isc_uint16_t ru_a, ru_b;
-	isc_uint16_t ru_g;
-	isc_uint16_t ru_counter;
-	isc_uint16_t ru_msb;
-	isc_uint32_t ru_reseed;
-	isc_uint32_t random;
-};
-
-ISC_LANG_BEGINDECLS
-
-void
-isc_lcg_init(isc_lcg_t *lcg);
-/*
- * Initialize a Linear Congruential Generator
- *
- * Requires:
- *
- *	lcg != NULL
- */
-
-isc_uint16_t
-isc_lcg_generate16(isc_lcg_t *lcg);
-/*
- * Get a random number from a Linear Congruential Generator
- *
- * Requires:
- *
- *	lcg be valid.
- *
- *	data != NULL.
- */
-
-ISC_LANG_ENDDECLS
-
-#endif /* ISC_LCG_H */
diff --git a/usr.sbin/bind/lib/isc/include/isc/shuffle.h b/usr.sbin/bind/lib/isc/include/isc/shuffle.h
new file mode 100644
index 00000000000..e75a28249a2
--- /dev/null
+++ b/usr.sbin/bind/lib/isc/include/isc/shuffle.h
@@ -0,0 +1,59 @@
+/*
+ * Portions Copyright (C) 2002  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.
+ */
+
+/* $OpenBSD: shuffle.h,v 1.1 2008/02/29 12:21:12 deraadt Exp $ */
+
+#ifndef ISC_SHUFFLE_H
+#define ISC_SHUFFLE_H 1
+
+#include <isc/lang.h>
+#include <isc/types.h>
+
+typedef struct isc_shuffle isc_shuffle_t;
+
+struct isc_shuffle {
+	isc_uint16_t id_shuffle[65536];
+	int isindex;
+};
+
+ISC_LANG_BEGINDECLS
+
+void
+isc_shuffle_init(isc_shuffle_t *shuffle);
+/*
+ * Initialize a Shuffle generator
+ *
+ * Requires:
+ *
+ *	shuffle != NULL
+ */
+
+isc_uint16_t
+isc_shuffle_generate16(isc_shuffle_t *shuffle);
+/*
+ * Get a random number from a Shuffle generator
+ *
+ * Requires:
+ *
+ *	shuffle be valid.
+ *
+ *	data != NULL.
+ */
+
+ISC_LANG_ENDDECLS
+
+#endif /* ISC_SHUFFLE_H */
diff --git a/usr.sbin/bind/lib/isc/lcg.c b/usr.sbin/bind/lib/isc/lcg.c
deleted file mode 100644
index dfbce53a3fc..00000000000
--- a/usr.sbin/bind/lib/isc/lcg.c
+++ /dev/null
@@ -1,173 +0,0 @@
-/*
- * Portions Copyright (C) 2002  Internet Software Consortium.
- * Portions Copyright (C) 1997  Niels Provos.
- *
- * 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.
- */
-
-/* $OpenBSD: lcg.c,v 1.2 2004/09/28 17:14:07 jakob Exp $ */
-
-#include <config.h>
-
-#include <stdlib.h>
-
-#include <isc/lcg.h>
-#include <isc/random.h>
-#include <isc/time.h>
-#include <isc/util.h>
-
-#define VALID_LCG(x)	(x != NULL)
-
-#define RU_OUT  180             /* Time after wich will be reseeded */
-#define RU_MAX	30000		/* Uniq cycle, avoid blackjack prediction */
-#define RU_GEN	2		/* Starting generator */
-#define RU_N	32749		/* RU_N-1 = 2*2*3*2729 */
-#define RU_AGEN	7               /* determine ru_a as RU_AGEN^(2*rand) */
-#define RU_M	31104           /* RU_M = 2^7*3^5 - don't change */
-
-#define PFAC_N 3
-static const isc_uint16_t pfacts[PFAC_N] = {
-	2, 
-	3,
-	2729
-};
-
-/*
- * Do a fast modular exponation, returned value will be in the range
- * of 0 - (mod-1)
- */
-static isc_uint16_t
-pmod(isc_uint16_t gen, isc_uint16_t exp, isc_uint16_t mod)
-{
-	isc_uint16_t s, t, u;
-
-	s = 1;
-	t = gen;
-	u = exp;
-
-	while (u) {
-		if (u & 1)
-			s = (s*t) % mod;
-		u >>= 1;
-		t = (t*t) % mod;
-	}
-	return (s);
-}
-
-/* 
- * Initializes the seed and chooses a suitable generator. Also toggles 
- * the msb flag. The msb flag is used to generate two distinct
- * cycles of random numbers and thus avoiding reuse of ids.
- *
- * This function is called from isc_lcg_generate() when needed, an
- * application does not have to worry about it.
- */
-static void 
-reseed(isc_lcg_t *lcg)
-{
-	isc_time_t isctime;
-	isc_boolean_t noprime = ISC_TRUE;
-	isc_uint16_t j, i;
-
-	isc_random_get(&lcg->random);
-	lcg->ru_x = (lcg->random & 0xFFFF) % RU_M;
-
-	/* 15 bits of random seed */
-	lcg->ru_seed = (lcg->random >> 16) & 0x7FFF;
-	isc_random_get(&lcg->random);
-	lcg->ru_seed2 = lcg->random & 0x7FFF;
-
-	isc_random_get(&lcg->random);
-
-	/* Determine the LCG we use */
-	lcg->ru_b = (lcg->random & 0xfffe) | 1;
-	lcg->ru_a = pmod(RU_AGEN, (lcg->random >> 16) & 0xfffe, RU_M);
-	while (lcg->ru_b % 3 == 0)
-		lcg->ru_b += 2;
-	
-	isc_random_get(&lcg->random);
-	j = lcg->random % RU_N;
-	lcg->random = lcg->random >> 16;
-
-	/* 
-	 * Do a fast gcd(j,RU_N-1), so we can find a j with
-	 * gcd(j, RU_N-1) == 1, giving a new generator for
-	 * RU_GEN^j mod RU_N
-	 */
-	while (noprime == ISC_TRUE) {
-		for (i=0; i<PFAC_N; i++)
-			if (j % pfacts[i] == 0)
-				break;
-
-		if (i >= PFAC_N)
-			noprime = ISC_FALSE;
-		else 
-			j = (j+1) % RU_N;
-	}
-
-	lcg->ru_g = pmod(RU_GEN, j, RU_N);
-	lcg->ru_counter = 0;
-
-	isc_time_now(&isctime);
-	lcg->ru_reseed = isc_time_seconds(&isctime) + RU_OUT;
-	lcg->ru_msb = lcg->ru_msb == 0x8000 ? 0 : 0x8000; 
-}
-
-void
-isc_lcg_init(isc_lcg_t *lcg)
-{
-	REQUIRE(VALID_LCG(lcg));
-
-	lcg->ru_x = 0;
-	lcg->ru_seed = 0;
-	lcg->ru_seed2 = 0;
-	lcg->ru_a = 0;
-	lcg->ru_b = 0;
-	lcg->ru_g = 0;
-	lcg->ru_counter = 0;
-	lcg->ru_msb = 0;
-	lcg->ru_reseed = 0;
-	lcg->random = 0;
-}
-
-isc_uint16_t
-isc_lcg_generate16(isc_lcg_t *lcg)
-{
-	isc_time_t isctime;
-        int i, n;
-
-	REQUIRE(VALID_LCG(lcg));
-
-	isc_time_now(&isctime);
-	if (lcg->ru_counter >= RU_MAX ||
-	    isc_time_seconds(&isctime) > lcg->ru_reseed)
-		reseed(lcg);
-
-	if (! lcg->random)
-		isc_random_get(&lcg->random);
-
-	/* Skip a random number of ids */
-	n = lcg->random & 0x7; lcg->random = lcg->random >> 3;
-	if (lcg->ru_counter + n >= RU_MAX)
-                reseed(lcg);
-
-	for (i=0; i<=n; i++)
-	        /* Linear Congruential Generator */
-	        lcg->ru_x = (lcg->ru_a*lcg->ru_x + lcg->ru_b) % RU_M;
-
-	lcg->ru_counter += i;
-
-	return (lcg->ru_seed ^
-	    pmod(lcg->ru_g, lcg->ru_seed2 ^ lcg->ru_x, RU_N)) | lcg->ru_msb;
-}
diff --git a/usr.sbin/bind/lib/isc/shuffle.c b/usr.sbin/bind/lib/isc/shuffle.c
new file mode 100644
index 00000000000..8dc114d166f
--- /dev/null
+++ b/usr.sbin/bind/lib/isc/shuffle.c
@@ -0,0 +1,75 @@
+/*
+ * Portions Copyright (C) 2008 Theo de Raadt
+ *
+ * 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.
+ */
+
+/* $OpenBSD: shuffle.c,v 1.1 2008/02/29 12:21:12 deraadt Exp $ */
+
+#include <config.h>
+
+#include <stdlib.h>
+
+#include <isc/shuffle.h>
+#include <isc/random.h>
+#include <isc/time.h>
+#include <isc/util.h>
+
+#define VALID_SHUFFLE(x)	(x != NULL)
+
+void
+isc_shuffle_init(isc_shuffle_t *shuffle)
+{
+	isc_uint32_t si;
+	isc_uint16_t r;
+	int i, i2;
+
+	REQUIRE(VALID_SHUFFLE(shuffle));
+
+	shuffle->isindex = 0;
+	for (i = 0; i < 65536; ++i)
+		shuffle->id_shuffle[i] = i;
+
+	/* 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;
+		r = shuffle->id_shuffle[i];
+		shuffle->id_shuffle[i] = shuffle->id_shuffle[i2];
+		shuffle->id_shuffle[i2] = r;
+	}
+}
+
+isc_uint16_t
+isc_shuffle_generate16(isc_shuffle_t *shuffle)
+{
+	isc_uint32_t si;
+	isc_uint16_t r;
+	int i, i2;
+
+	REQUIRE(VALID_SHUFFLE(shuffle));
+
+	do {
+		isc_random_get(&si);
+		i = shuffle->isindex & 0xFFFF;
+		i2 = (shuffle->isindex - (si & 0x7FFF)) & 0xFFFF;
+		r = shuffle->id_shuffle[i];
+		shuffle->id_shuffle[i] = shuffle->id_shuffle[i2];
+		shuffle->id_shuffle[i2] = r;
+		shuffle->isindex++;
+	} while (r == 0);
+
+	return (r);
+}