summaryrefslogtreecommitdiff
path: root/usr.sbin/bind/lib
diff options
context:
space:
mode:
authorJakob Schlyter <jakob@cvs.openbsd.org>2003-01-20 21:24:42 +0000
committerJakob Schlyter <jakob@cvs.openbsd.org>2003-01-20 21:24:42 +0000
commit734b8243239d3dc0f305a649bc24f405687d21f7 (patch)
treef5cd37d3ed635dd07ac30fb4b42e27980f8acc5b /usr.sbin/bind/lib
parent8de702bfb7b51a0a01300e962789a9d445880466 (diff)
add Linear Congruential Generator implementation
Diffstat (limited to 'usr.sbin/bind/lib')
-rw-r--r--usr.sbin/bind/lib/isc/Makefile.in4
-rw-r--r--usr.sbin/bind/lib/isc/include/isc/lcg.h98
-rw-r--r--usr.sbin/bind/lib/isc/lcg.c173
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;
+}