diff -cNr ../bind-4.9.5-P1-rel/contrib/host/host.c ./contrib/host/host.c *** ../bind-4.9.5-P1-rel/contrib/host/host.c Sat Oct 12 16:24:42 1996 --- ./contrib/host/host.c Wed Apr 9 15:27:05 1997 *************** *** 537,543 **** _res.retrans = DEF_RETRANS; /* timeout in secs between retries */ /* initialize packet id */ ! _res.id = getpid() & 0x7fff; /* save new defaults */ new_res = _res; --- 537,543 ---- _res.retrans = DEF_RETRANS; /* timeout in secs between retries */ /* initialize packet id */ ! _res.id = res_randomid(); /* save new defaults */ new_res = _res; diff -cNr ../bind-4.9.5-P1-rel/named/ns_main.c ./named/ns_main.c *** ../bind-4.9.5-P1-rel/named/ns_main.c Tue Nov 26 03:11:23 1996 --- ./named/ns_main.c Wed Apr 9 00:24:14 1997 *************** *** 1658,1668 **** } /* ! * These are here in case we ever want to get more clever, like perhaps ! * using a bitmap to keep track of outstanding queries and a random ! * allocation scheme to make it a little harder to predict them. Note ! * that the resolver will need the same protection so the cleverness ! * should be put there rather than here; this is just an interface layer. */ void --- 1658,1668 ---- } /* ! * This just an interface layer to the random number generator ! * used in the resolver. ! * A special random number generator is used to create non predictable ! * and non repeating ids over a long period. It also avoids reuse ! * by switching between two distinct number cycles. */ void *************** *** 1674,1683 **** u_int16_t nsid_next() { ! if (nsid_state == 65535) ! nsid_state = 0; ! else ! nsid_state++; return (nsid_state); } --- 1674,1680 ---- u_int16_t nsid_next() { ! nsid_state = res_randomid(); return (nsid_state); } diff -cNr ../bind-4.9.5-P1-rel/res/Makefile ./res/Makefile *** ../bind-4.9.5-P1-rel/res/Makefile Thu Aug 8 16:49:48 1996 --- ./res/Makefile Wed Apr 9 00:32:13 1997 *************** *** 77,89 **** res_comp.c res_init.c res_mkquery.c res_query.c res_send.c \ getnetbyaddr.c getnetbyname.c getnetent.c getnetnamadr.c \ gethnamaddr.c sethostent.c nsap_addr.c hostnamelen.c inet_addr.c \ ! inet_ntop.c inet_neta.c inet_pton.c inet_net_ntop.c inet_net_pton.c OBJS= base64.o herror.o res_debug.o res_data.o \ res_comp.o res_init.o res_mkquery.o res_query.o res_send.o \ getnetbyaddr.o getnetbyname.o getnetent.o getnetnamadr.o \ gethnamaddr.o sethostent.o nsap_addr.o hostnamelen.o inet_addr.o \ ! inet_ntop.o inet_neta.o inet_pton.o inet_net_ntop.o inet_net_pton.o all: libresolv.a --- 77,91 ---- res_comp.c res_init.c res_mkquery.c res_query.c res_send.c \ getnetbyaddr.c getnetbyname.c getnetent.c getnetnamadr.c \ gethnamaddr.c sethostent.c nsap_addr.c hostnamelen.c inet_addr.c \ ! inet_ntop.c inet_neta.c inet_pton.c inet_net_ntop.c inet_net_pton.c \ ! res_random.c OBJS= base64.o herror.o res_debug.o res_data.o \ res_comp.o res_init.o res_mkquery.o res_query.o res_send.o \ getnetbyaddr.o getnetbyname.o getnetent.o getnetnamadr.o \ gethnamaddr.o sethostent.o nsap_addr.o hostnamelen.o inet_addr.o \ ! inet_ntop.o inet_neta.o inet_pton.o inet_net_ntop.o inet_net_pton.o \ ! res_random.o all: libresolv.a diff -cNr ../bind-4.9.5-P1-rel/res/res_comp.c ./res/res_comp.c *** ../bind-4.9.5-P1-rel/res/res_comp.c Mon Dec 2 02:17:22 1996 --- ./res/res_comp.c Fri Apr 18 18:45:02 1997 *************** *** 98,103 **** --- 98,105 ---- dn = exp_dn; cp = comp_dn; + if (length > MAXHOSTNAMELEN-1) + length = MAXHOSTNAMELEN-1; eom = exp_dn + length; /* * fetch next label in domain name diff -cNr ../bind-4.9.5-P1-rel/res/res_init.c ./res/res_init.c *** ../bind-4.9.5-P1-rel/res/res_init.c Sat Sep 28 00:51:07 1996 --- ./res/res_init.c Wed Apr 9 00:33:30 1997 *************** *** 197,209 **** if (!(_res.options & RES_INIT)) _res.options = RES_DEFAULT; - /* - * This one used to initialize implicitly to zero, so unless the app - * has set it to something in particular, we can randomize it now. - */ - if (!_res.id) - _res.id = res_randomid(); - #ifdef USELOOPBACK _res.nsaddr.sin_addr = inet_makeaddr(IN_LOOPBACKNET, 1); #else --- 197,202 ---- *************** *** 644,655 **** return(0); /* if not using DNS configuration from NetInfo */ } #endif /* NeXT */ - - u_int - res_randomid() - { - struct timeval now; - - gettimeofday(&now, NULL); - return (0xffff & (now.tv_sec ^ now.tv_usec ^ getpid())); - } --- 637,639 ---- diff -cNr ../bind-4.9.5-P1-rel/res/res_mkquery.c ./res/res_mkquery.c *** ../bind-4.9.5-P1-rel/res/res_mkquery.c Sat Sep 28 00:37:58 1996 --- ./res/res_mkquery.c Wed Apr 9 00:31:30 1997 *************** *** 107,118 **** #endif /* * Initialize header fields. */ if ((buf == NULL) || (buflen < HFIXEDSZ)) return (-1); bzero(buf, HFIXEDSZ); hp = (HEADER *) buf; ! hp->id = htons(++_res.id); hp->opcode = op; hp->rd = (_res.options & RES_RECURSE) != 0; hp->rcode = NOERROR; --- 107,123 ---- #endif /* * Initialize header fields. + * + * A special random number generator is used to create non predictable + * and non repeating ids over a long period. It also avoids reuse + * by switching between two distinct number cycles. */ + if ((buf == NULL) || (buflen < HFIXEDSZ)) return (-1); bzero(buf, HFIXEDSZ); hp = (HEADER *) buf; ! hp->id = htons(_res.id=res_randomid()); hp->opcode = op; hp->rd = (_res.options & RES_RECURSE) != 0; hp->rcode = NOERROR; diff -cNr ../bind-4.9.5-P1-rel/res/res_random.c ./res/res_random.c *** ../bind-4.9.5-P1-rel/res/res_random.c Wed Dec 31 17:00:00 1969 --- ./res/res_random.c Tue Apr 22 02:31:25 1997 *************** *** 0 **** --- 1,262 ---- + /* $OpenBSD: res_random.c,v 1.3 1997/04/19 10:07:01 provos Exp $ */ + + /* + * Copyright 1997 Niels Provos + * All rights reserved. + * + * Theo de Raadt 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. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by Niels Provos. + * 4. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + + /* + * 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. + */ + + #include + #include + #include + #include + + #if defined(BSD) && (BSD >= 199103) + # include + # include + # include + #else + # include "../conf/portability.h" + #endif + + #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 + const static u_int16_t pfacts[PFAC_N] = { + 2, + 3, + 2729 + }; + + static u_int16_t ru_x; + static u_int16_t ru_seed; + static u_int16_t ru_a, ru_b; + static u_int16_t ru_g; + static u_int16_t ru_counter = 0; + static u_int16_t ru_msb = 0; + static long ru_reseed; + static u_int32_t tmp; /* Storage for unused random */ + static struct timeval tv; + + static u_int32_t pmod __P((u_int32_t, u_int32_t, u_int32_t)); + static void res_initid __P((void)); + + #ifndef __OpenBSD__ + /* + * No solid source of strong random in the system. Sigh. Fake it. + */ + u_long + arc4random() + { + static char state[256]; + char *savestate; + char *setstate(); + static unsigned seed; + static int count; + u_long datum; + + if (++count == 129837 || seed == 0) { + struct timeval tv; + + count = 0; + gettimeofday(&tv, NULL); + seed = getpid() ^ tv.tv_sec ^ tv.tv_usec; + initstate(seed, state, sizeof state); + } + savestate = setstate(state); + datum = random(); + setstate(savestate); + return (datum); + } + + #endif + + /* + * Do a fast modular exponation, returned value will be in the range + * of 0 - (mod-1) + */ + + static u_int32_t + pmod(gen, exp, mod) + u_int32_t gen, exp, mod; + { + u_int32_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); + } + + /* + * Initalizes 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 res_randomid() when needed, an + * application does not have to worry about it. + */ + static void + res_initid() + { + u_int16_t j, i; + int noprime = 1; + + tmp = arc4random(); + ru_x = (tmp & 0xFFFF) % RU_M; + + /* 15 bits of random seed */ + ru_seed = (tmp >> 16) & 0x7FFF; + + tmp = arc4random(); + + /* Determine the LCG we use */ + ru_b = (tmp & 0xfffe) | 1; + ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M); + while (ru_b % 3 == 0) + ru_b += 2; + + tmp = arc4random(); + j = tmp % RU_N; + tmp = tmp >> 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) { + for (i=0; i=PFAC_N) + noprime = 0; + else + j = (j+1) % RU_N; + } + + ru_g = pmod(RU_GEN,j,RU_N); + ru_counter = 0; + + gettimeofday(&tv, NULL); + ru_reseed = tv.tv_sec + RU_OUT; + ru_msb = ru_msb == 0x8000 ? 0 : 0x8000; + } + + u_int + res_randomid() + { + int i, n; + + gettimeofday(&tv, NULL); + if (ru_counter >= RU_MAX || tv.tv_sec > ru_reseed) + res_initid(); + + if (!tmp) + tmp = arc4random(); + + /* Skip a random number of ids */ + n = tmp & 0x2f; tmp = tmp >> 6; + if (ru_counter + n >= RU_MAX) + res_initid(); + + for (i=0; i<=n; i++) + /* Linear Congruential Generator */ + ru_x = (ru_a*ru_x + ru_b) % RU_M; + + ru_counter += i; + + return (ru_seed ^ pmod(ru_g,ru_x,RU_N)) | ru_msb; + } + + #if 0 + void + main(int argc, char **argv) + { + int i, n; + u_int16_t wert; + + res_initid(); + + printf("Generator: %d\n", ru_g); + printf("Seed: %d\n", ru_seed); + printf("Reseed at %ld\n", ru_reseed); + printf("Ru_X: %d\n", ru_x); + printf("Ru_A: %d\n", ru_a); + printf("Ru_B: %d\n", ru_b); + + n = atoi(argv[1]); + for (i=0;i