Mailing List Archive
Support open source code!
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
SNI-12: BIND Vulnerabilities and Solutions
- To: BUGTRAQ@example.com
- Subject: SNI-12: BIND Vulnerabilities and Solutions
- From: Oliver Friedrichs <oliver@example.com>
- Date: Tue, 22 Apr 1997 04:36:17 -0600
-----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 availible.
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 availible 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 <ivan@example.com>
Emiliano Kargieman <ek@example.com>
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 <deraadt@example.com>
Niels Provos <provos@example.com>
Todd Miller <millert@example.com>
Allen Briggs <briggs@example.com>
Further attributions:
AUSCERT <auscert@example.com>
David Sacerdote <davids@example.com>
Oliver Friedrichs <oliver@example.com>
Alfred Huger <ahuger@example.com>
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 <ivan@example.com>
Emiliano Kargieman <ek@example.com>
For more information about CORE S.A. contact: core@example.com
Or visit: http://www.secnet.com/core
Encrypted mail can also be sent to <sni@example.com> encrypted with
the following PGP key:
Type Bits/KeyID Date User ID
pub 1024/9E55000D 1997/01/13 Secure Networks Inc. <sni@example.com>
Secure Networks <security@example.com>
- -----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@example.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: res_random.c,v 1.3 1997/04/19 10:07:01 provos Exp $ */
+
+ /*
+ * Copyright 1997 Niels Provos <provos@example.com>
+ * All rights reserved.
+ *
+ * Theo de Raadt <deraadt@example.com> 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 <sys/types.h>
+ #include <netinet/in.h>
+ #include <sys/time.h>
+ #include <resolv.h>
+
+ #if defined(BSD) && (BSD >= 199103)
+ # include <unistd.h>
+ # include <stdlib.h>
+ # include <string.h>
+ #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; i++)
+ if (j%pfacts[i] == 0)
+ break;
+
+ if (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<n;i++) {
+ wert = res_randomid();
+ printf("%06d\n", wert);
+ }
+ }
+ #endif
+
--- CUT HERE ---
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3ia
Charset: noconv
iQCVAwUBM1ygQLgIhFKeVQANAQHhvwQAgm9c8ai94FzE03dZ3S8HQmpiZXDB4cGU
EqZYu32tV7a/eHT/fyw01uMXpeLIaZERQNGTJokwpZKbCUAY67ZzsOGYqp5Ja+To
YN3WMD1pXHPEC5+vq+r94chX0zobvjPrd3Rhg1PHxEcrkMjsliiYPNnTrotOMrUy
NHiFI/kbY0Q=
=vf1T
-----END PGP SIGNATURE-----
-----------------------------------------------------------------
a word from the sponsor will appear below
-----------------------------------------------------------------
The TLUG mailing list is proudly sponsored by TWICS - Japan's First
Public-Access Internet System. Now offering 20,000 yen/year flat
rate Internet access with no time charges. Full line of corporate
Internet and intranet products are available. info@example.com
Tel: 03-3351-5977 Fax: 03-3353-6096
- Next by Date: tlug: Meeting Saturday August 2
- Next by thread: tlug: Meeting Saturday August 2
- Index(es):
| Home Page | Mailing List | Linux and Japan | TLUG Members | Links |