add Linear Congruential Generator implementation

3 files changed, 273 insertions, 2 deletions

diff --git a/usr.sbin/bind/lib/isc/Makefile.in b/usr.sbin/bind/lib/isc/Makefile.in
index 9760d5c0321..e271abde47f 100644
--- a/usr.sbin/bind/lib/isc/Makefile.in
+++ b/usr.sbin/bind/lib/isc/Makefile.in
@@ -53,7 +53,7 @@ OBJS =		@ISC_EXTRA_OBJS@ \
 		assertions.@O@ base64.@O@ bitstring.@O@ buffer.@O@ \
 		bufferlist.@O@ commandline.@O@ error.@O@ event.@O@ \
 		heap.@O@ hex.@O@ hmacmd5.@O@ \
-		lex.@O@ lfsr.@O@ lib.@O@ log.@O@ \
+		lcg.@O@ lex.@O@ lfsr.@O@ lib.@O@ log.@O@ \
 		md5.@O@ mem.@O@ mutexblock.@O@ netaddr.@O@ ondestroy.@O@ \
 		quota.@O@ random.@O@ \
 		ratelimiter.@O@ result.@O@ rwlock.@O@ \
@@ -66,7 +66,7 @@ SRCS =		@ISC_EXTRA_SRCS@ \
 		assertions.c base64.c bitstring.c buffer.c \
 		bufferlist.c commandline.c error.c event.c \
 		heap.c hex.c hmacmd5.c \
-		lex.c lfsr.c lib.c log.c \
+		lcg.c lex.c lfsr.c lib.c log.c \
 		md5.c mem.c mutexblock.c netaddr.c ondestroy.c \
 		quota.c random.c \
 		ratelimiter.c result.c rwlock.c \
diff --git a/usr.sbin/bind/lib/isc/include/isc/lcg.h b/usr.sbin/bind/lib/isc/include/isc/lcg.h
new file mode 100644
index 00000000000..47eef55231e
--- /dev/null
+++ b/usr.sbin/bind/lib/isc/include/isc/lcg.h
@@ -0,0 +1,98 @@
+/*
+ * 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.1 2003/01/20 21:24:41 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/lcg.c b/usr.sbin/bind/lib/isc/lcg.c
new file mode 100644
index 00000000000..be6c7aede7e
--- /dev/null
+++ b/usr.sbin/bind/lib/isc/lcg.c
@@ -0,0 +1,173 @@
+/*
+ * 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.1 2003/01/20 21:24:41 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;
+}