sni_12_resolverid.txt

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          <ivan@secnet.com>
        Emiliano Kargieman <ek@secnet.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@openbsd.org>
        Niels Provos      <provos@openbsd.org>
        Todd Miller       <millert@openbsd.org>
        Allen Briggs      <briggs@openbsd.org>

  Further attributions:
        AUSCERT           <auscert@auscert.org.au>
        David Sacerdote   <davids@secnet.com>
        Oliver Friedrichs <oliver@secnet.com>
        Alfred Huger      <ahuger@secnet.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@secnet.com>
        Emiliano Kargieman <ek@secnet.com>

     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 <sni@secnet.com> encrypted with
     the following PGP key:

Type Bits/KeyID    Date       User ID
pub  1024/9E55000D 1997/01/13 Secure Networks Inc. <sni@secnet.com>
                              Secure Networks <security@secnet.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@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.2 2001/07/02 19:26:27 jufi Exp $ */
+
+ /*
+  * Copyright 1997 Niels Provos <provos@physnet.uni-hamburg.de>
+  * All rights reserved.
+  *
+  * 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.
+  *
+  * 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-----