BIND Vulnerabilities and Solutions Title: BIND Vulnerabilities and Solutions Date Issued: April 22, 1997 Last Modified: April 22, 1997 Code: SNI-12 Source: Network Associates (was SNI) -----BEGIN PGP SIGNED MESSAGE----- ###### ## ## ###### ## ### ## ## ###### ## # ## ## ## ## ### ## ###### . ## ## . ######. Secure Networks Inc. AND CORE Seguridad de la Informacion Security Advisory April 22, 1997 BIND Vulnerabilities and Solutions Problem Description ~~~~~~~~~~~~~~~~~~~ This advisory contains descriptions and solutions for two vulnerabilities present in current BIND distributions. These vulnerabilities are actively being exploited on the Internet. I. The usage of predictable IDs in queries and recursed queries allows for remote cache corruption. This allows malicious users to alter domain name server caches to change the addresses and hostnames of hosts on the internet. II. A failure to check whether hostname lengths exceed MAXHOSTNAMELEN in size. This results in potential buffer overflows in programs which expect the BIND resolver to only return a maximum hostname length of MAXHOSTNAMELEN. Problem I. The usage of predictable ID's ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Problem I. - Impact ~~~~~~~~~~~~~~~~~~~ Remote root users can poison BIND and Microsoft Windows NT name server caches by forging UDP packets. We should note that unlike other well documented attacks, in this instance it is NOT necessary for the attacker to take over a DNS server or sniff the target network. Problem I. - Technical Details ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This particular cache corruption attack requires that the target nameserver be configured to allow recursion. Recursion allows a nameserver to handle requests for zones or domains which it does not serve. When receiving a query for a zone or domain which is not served by the name server, the name server will transmit a query to a nameserver which serves the desired domain. Once a response is received from the second nameserver, the first nameserver sends the response back to the requesting party. The following attack is outlined in the paper "Addressing weaknesses in the Domain Name System Protocol" by Christopher Schuba and Eugene Spafford [6]. To the extent of our knowledge, this problem has not been previously addressed. The paper also assumes that the attacker has super-user access to a primary nameserver, here we demonstrate that this is not necessary nor are source routed packets required. Using the recursion feature, one can poison the cache on a name server with the following procedure: Problem I. - The Players ~~~~~~~~~~~~~~~~~~~~~~~~ . HOST.ATTACKER.COM is the attacking host. . DNS.ATTACKER.COM is ATTACKER.COM's nameserver, we presume that this is the only name server for ATTACKER.COM to simplify the description. . DNS.TARGET.COM is the target nameserver which runs BIND. What we will attempt to do is add an A (address) resource record on DNS.TARGET.COM that will resolve WWW.SPOOFED.COM to 127.0.0.1. We are sure that WWW.SPOOFED.COM is not cached in DNS.TARGET.COM's DNS cache. . DNS.SPOOFED.COM is the nameserver for SPOOFED.COM's domain. We have determined this before the attack begins. Once again we just presume its the only one in order to simplify this description. Problem I. - The Attack ~~~~~~~~~~~~~~~~~~~~~~~ A. First a query is sent to DNS.TARGET.COM asking for the address of UNKNOWN.ATTACKER.COM. Our query has the recursion desired bit set, meaning that if the nameserver we are querying has recursion enabled, it will query another nameserver with our query (assuming it does not have the information cached). B. DNS.TARGET.COM will first determine who serves the ATTACKER.COM domain, then it will build a query packet and send it to DNS.ATTACKER.COM. C. We sniff DNS.ATTACKER.COM's local network and retrieve the query packet sent by DNS.TARGET.COM to DNS.ATTACKER.COM. We can then determine the query ID (qid0) used by DNS.TARGET.COM. Chances are that the next queries generated by DNS.TARGET.COM will have query IDs that will fall in the range [qid0,qid0+N] where N is dependent on the amount of queries DNS.TARGET.COM is generating in the period of time on which the attack takes place. N is usually <= 10 for most cases. D. Once we have determined what the next query ID generated will be, we send a query to DNS.TARGET.COM asking for WWW.SPOOFED.COM's address. E. Then we start sending spoofed DNS replies from DNS.SPOOFED.COM, telling DNS.TARGET.COM that WWW.SPOOFED.COM is '127.0.0.1'. F. If we guessed the query ID used by DNS.TARGET.COM in its recursed query and our response is received first, our response will be taken as valid and the address will be cached. Subsequent responses will be discarded as duplicates. We can always send many (N*M) spoofed packets with different IDs in the range (qid0,qid0+N] so we will be sure that at least one of them will hit DNS.TARGET.COM and have the 'right' ID. M is a factor dependent of the amount of UDP packets we expect to lose on their way to DNS.TARGET.COM. Problem I. - The Result ~~~~~~~~~~~~~~~~~~~~~~~ If the attack succeeded, any query to DNS.TARGET.COM asking for WWW.SPOOFED.COM's address, will get 127.0.0.1 as a response. Thus, any user on TARGET.COM's domain will connect to 127.0.0.1 if they try to contact WWW.SPOOFED.COM. The usage of 127.0.0.1 in this description is of course for instructional purposes, any IP address can be used, in particular an attacker could use its own IP address (BADGUY.COM's IP) so all connections to 'host' will go to 'BADGUY'. The attacker can then 'impersonate' WWW.SPOOFED.COM. Given this attack, it is easy to visualize the effects of impersonating a high traffic FTP distribution site. This attack can also be used to intercept email traffic, and bypass address based authentication methods, including TCP wrappers and firewalls. Problem I. - Notes ~~~~~~~~~~~~~~~~~~ This attack depends on a few things to succeed: 1. The attacker has complete control of DNS.ATTACKER.COM's network, he can both spoof and sniff DNS packets there. In particular, he can sniff DNS packets sent to DNS.ATTACKER.COM. 2. Spoofed DNS responses sent from the attacker to DNS.TARGET.COM must be received before the legit response from DNS.SPOOFED.COM. This is very easy to achieve. In testing we have not yet encountered a situation where we could not get our packets to the nameserver first. 3. The name server on DNS.TARGET.COM supports recursion and caches responses. This is common practice. It should be noted that most nameservers allow recursion (unless specifically denied by configuration options). Root name servers, however, do not allow recursion. If DNS.TARGET.COM caches negative responses as well (NCACHE), a denial of service attack can be performed, in this case, spoofed responses sent by the attacker will tell DNS.TARGET.COM that WWW.SPOOFED.COM does not exist (and be authorative on this). The existence of several nameservers for the domains does not alter the basic outline of this attack. The attacker would only need to send DNS responses with source addresses of each of SPOOFED.COM's nameservers. (N*M*I responses, where I is the number of nameservers). Problem I. - Systems Affected ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - - All systems using BIND as their domain name server with recursion enabled. - - Windows NT (server) version 3.51 & 4.0 DNS server. Microsoft has been notified and has acknowledged this is a serious problem. No information on a fix is available. Problem II. Hostname length checking ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Problem II. - Impact ~~~~~~~~~~~~~~~~~~~~ BIND allows passing of hostnames larger than MAXHOSTNAMELEN in size to programs. As many programs utilize buffers of size MAXHOSTNAMELEN and copy the results from a query into these buffers, an overflow can occur. This can allow an attacker to execute arbitrary commands on a remote server in a worst case scenario. Problem II. - Systems Affected ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ All systems running BIND. Fix Information ~~~~~~~~~~~~~~~ Obtain BIND version 4.9.5-P1. BIND is available from ftp.isc.org in the directory /isc/bind/src. Patches to solve both problem I and problem II are included at the end of this advisory. Once BIND has been obtained, follow the following procedure: i. First remove the patches from this text. This can be performed by removing all text in between the "CUT HERE" lines, and saving it to a text file (i.e. /tmp/diffs.txt). ii. Perform the following operations to apply the patches: % gzip -d bind.tar.gz % mkdir bind % cd bind % tar -xvf ../bind.tar % patch < /tmp/diffs.txt iii. Rebuild BIND Attributions ~~~~~~~~~~~~ Ivan Arce Emiliano Kargieman The OpenBSD Project Who found a good solution to problem, developed a solution and performed various tests to ensure its correctness. Individuals involved in this effort were: Theo de Raadt Niels Provos Todd Miller Allen Briggs Further attributions: AUSCERT David Sacerdote Oliver Friedrichs Alfred Huger Additional Information: ~~~~~~~~~~~~~~~~~~~~~~~ [1] Vixie P. , "DNS and BIND security issues". This was originally published in the proceedings of the 5th USENIX Security Symposium and its included in the BIND distribution under the doc/misc directory. [2] Kumar A., Postel J., Neuman C., Danzig P. , Miller S. "RFC1536: Common DNS implementation errors and suggested fixes" Refer to problem 2 for a description of other weaknesses previously found in the recursion scheme. [3] Lottor, M., "RFC1033: Domain administrators operations guide" [4] Mockapetris, P., "RFC1034: Domain names - Concepts and facilities" [5] Mockapetris, P., "RFC1035: Domain Names - Implementation and specification" [6] Schuba Christopher and Spafford Eugene, "Adressing weaknesses in the Domain Name System Protocol", COAST Laboratory, Department of Computer Science, Purdue University. Comments and questions regarding this advisory can be sent to: Ivan Arce Emiliano Kargieman For more information about CORE S.A. contact: core@secnet.com Or visit: http://www.secnet.com/core Encrypted mail can also be sent to encrypted with the following PGP key: Type Bits/KeyID Date User ID pub 1024/9E55000D 1997/01/13 Secure Networks Inc. Secure Networks - -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.6.3ia mQCNAzLaFzIAAAEEAKsVzPR7Y6oFN5VPE/Rp6Sm82oE0y6Mkuof8QzERV6taihn5 uySb31UeNJ4l6Ud9alOPT/0YdeOO9on6eD1iU8qumFxzO3TLm8nTAdZehQSAQfoa rWmpwj7KpXN/3n+VyBWvhpBdKxe08SQN4ZjvV5HXy4YIrE5bTbgIhFKeVQANAAUR tCVTZWN1cmUgTmV0d29ya3MgSW5jLiA8c25pQHNlY25ldC5jb20+iQCVAwUQM1yd EB/bLKAOe7p9AQFptAQAiYpaZCpSmGgr05E698Z3t5r5BPAKUEtgvF53AvZUQLxz ZsYsVU5l5De0qKWJOQ/9LiDyWu1lvKhlTphbLy2RatWD4kO3oQL9v3TpSXm2WQhU uIzyZvj7S5ENodNnKn+gCDIvbou6OMot+7dRbWWgN2oabbru4CSlOxbG++yaTz+J AJUDBRAzTefbtOXez5VgyLkBAd0bA/43eGEgvPOFK+HHWCPpkSWCwtrtDU/dxOVz 9erHnT/CRxeojCI+50f71Qe+kvx9Q1odz2Jl/fLxhnPQdbPnpWblIbu4F8H+Syrj HTilDrl1DWa/nUNgK8sb27SMviELczP1a8gwA1eo5SUCG5TWLLTAzjWOgTxod2Ha OwseUHmqVIkAlQMFEDNOVsr/d6Iw8NVIbQEBxM0D/14XRfgSLwszgJcVbslMHm/B fF6tHoWYojzQle3opOuMYHNN8GsMZRkc1qQ8QuNA9Aj5+qDqEontGjV5IvhBu1fY FM77AhagskaFCZxwqV64Qrk328WDO89NGSd+RuovVNruDdn20TxNCEVuPTHjI0UA 8H+E6FW9jexg6RTHhPXYtCVTZWN1cmUgTmV0d29ya3MgPHNlY3VyaXR5QHNlY25l dC5jb20+iQCVAwUQMtqTKB/bLKAOe7p9AQFw5wQAgUwqJ+ZqfEy/lO1srU3nzxLA X0uHGHrMptRy/LFo8swD6G1TtWExUc3Yv/6g2/YK09b5WmplEJ+Q09maQIw+RU/s cIY+EsPauqIq4JTGh/Nm0Z4UDl2Y1x4GNtm0YqezxUPS0P0A3LHVLJ3Uo5og0G8O gPNrfbVz5ieT14OSCWCJAJUDBRAy2hd2/3eiMPDVSG0BAVNhBACfupfAcNhhnQaq aI03DOOiZSRjvql1xw4V+pPhM+IksdSK3YNUZVJJtANacgDhBT+jAPRaYbBWI3A5 ZMdcSNM8aTG0LWMLIOiOYEm6Lgd3idRBFN0Js08eyITl8mhZ33mDe4I0KQri9UiV ZcPYTbb9CWM6Hv2cMbt6S6kLnFziqIkAlQMFEDLaF0+4CIRSnlUADQEBCLoEAJwt UofDgvyZ4nCDx1KKAPkkXBRaPMWBp46xeTVcxaYiloZfwHfpk1h2mEJAxmAsvizl OtIppHl4isUxcGi/E2mLCLMvis22/IQP/9obPahPvgNaMLVtZljO1Nv3QFEkNciL FEUTNJHR1ko7ibCxkBs4cOpirFuvTMDvWnNaXAf8 =DchE - -----END PGP PUBLIC KEY BLOCK----- Copyright Notice ~~~~~~~~~~~~~~~~ The contents of this advisory are Copyright (C) 1997 Secure Networks Inc and CORE Seguridad de la Informacion S.A., and may be distributed freely provided that no fee is charged for distribution, and that proper credit is given. You can find Secure Networks papers at ftp://ftp.secnet.com/pub/papers and advisories at ftp://ftp.secnet.com/advisories You can browse our web site at http://www.secnet.com You can subscribe to our security advisory mailing list by sending mail to majordomo@secnet.com with the line "subscribe sni-advisories" Patches ~~~~~~~ --- CUT HERE --- 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: sni_12_resolverid.txt,v 1.3 2020/04/25 11:49:35 schwarze 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