diff options
Diffstat (limited to 'usr.sbin/bind')
| -rw-r--r-- | usr.sbin/bind/README.OpenBSD | 6 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/dns/dispatch.c | 8 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/Makefile.in | 4 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/include/isc/lcg.h | 98 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/include/isc/shuffle.h | 59 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/lcg.c | 173 | ||||
| -rw-r--r-- | usr.sbin/bind/lib/isc/shuffle.c | 75 |
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); +} |