FYI...

  • To: apops at teckla dot apnic dot net
  • Subject: FYI...
  • From: David R Conrad <davidc at apnic dot net>
  • Date: Wed, 23 Apr 1997 10:47:28 +0900
  • Sender: owner-apops@apnic.net
    • 
      ------- Forwarded Message
      
      Date:    Tue, 22 Apr 1997 04:34:00 -0600
      From:    Oliver Friedrichs <oliver at secnet dot com>
      To:      sni-advisories at silence dot secnet dot com
      Subject: SNI-12: BIND Vulnerabilities and Solutions
      
      
      - -----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 at secnet dot com>
      	Emiliano Kargieman <ek at secnet dot 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 at openbsd dot org>
              Niels Provos      <provos at openbsd dot org>
              Todd Miller       <millert at openbsd dot org>
              Allen Briggs      <briggs at openbsd dot org>
      
        Further attributions:
              AUSCERT           <auscert at auscert dot org dot au>
      	David Sacerdote   <davids at secnet dot com>
              Oliver Friedrichs <oliver at secnet dot com>
              Alfred Huger      <ahuger at secnet dot 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 at secnet dot com>
      	Emiliano Kargieman <ek at secnet dot com>
      
           For more information about CORE S.A. contact: core at secnet dot com
      
           Or visit: http://www.secnet.com/core
      
           Encrypted mail can also be sent to <sni at secnet dot com> encrypted with
           the following PGP key:
      
      Type Bits/KeyID    Date       User ID
      pub  1024/9E55000D 1997/01/13 Secure Networks Inc. <sni at secnet dot com>
                                    Secure Networks <security at secnet dot 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 at secnet dot 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 at physnet dot uni-hamburg dot de>
      +  * All rights reserved.
      +  *
      +  * Theo de Raadt <deraadt at openbsd dot 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 predicti
      on */
      + #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-----
      
      
      
      
      ------- End of Forwarded Message
      
      _________________________________________________________________________
      To unsubscribe: send "unsubscribe" to apops-request at apnic dot net
      ------------------------------------------------------------------------