sys/netinet/ip_id.c

   1 /*      $NetBSD: ip_id.c,v 1.11 2006/08/30 18:54:19 christos Exp $      */
   2 /*      $OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $       */
   3
   4 /*
   5  * Copyright 1998 Niels Provos <provos@citi.umich.edu>
   6  * All rights reserved.
   7  *
   8  * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
   9  * such a mathematical system to generate more random (yet non-repeating)
  10  * ids to solve the resolver/named problem.  But Niels designed the
  11  * actual system based on the constraints.
  12  *
  13  * Redistribution and use in source and binary forms, with or without
  14  * modification, are permitted provided that the following conditions
  15  * are met:
  16  * 1. Redistributions of source code must retain the above copyright
  17  *    notice, this list of conditions and the following disclaimer.
  18  * 2. Redistributions in binary form must reproduce the above copyright
  19  *    notice, this list of conditions and the following disclaimer in the
  20  *    documentation and/or other materials provided with the distribution.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  23  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  24  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  25  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  27  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 /*
  35  * seed = random 15bit
  36  * n = prime, g0 = generator to n,
  37  * j = random so that gcd(j,n-1) == 1
  38  * g = g0^j mod n will be a generator again.
  39  *
  40  * X[0] = random seed.
  41  * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
  42  * with a = 7^(even random) mod m,
  43  *      b = random with gcd(b,m) == 1
  44  *      m = 31104 and a maximal period of m-1.
  45  *
  46  * The transaction id is determined by:
  47  * id[n] = seed xor (g^X[n] mod n)
  48  *
  49  * Effectively the id is restricted to the lower 15 bits, thus
  50  * yielding two different cycles by toggling the msb on and off.
  51  * This avoids reuse issues caused by reseeding.
  52  */
  53
  54 #include <sys/cdefs.h>
  55 __KERNEL_RCSID(0, "$NetBSD: ip_id.c,v 1.11 2006/08/30 18:54:19 christos Exp $");
  56
  57 #include "opt_inet.h"
  58
  59 #include <sys/param.h>
  60 #include <lib/libkern/libkern.h>
  61
  62 #include <net/if.h>
  63 #include <netinet/in.h>
  64 #include <netinet/in_var.h>
  65
  66 #define IPID_MAXID      65535
  67 #define IPID_NUMIDS     32768
  68
  69 static struct ipid_state {
  70         uint16_t ids_start_slot;
  71         uint16_t ids_slots[IPID_MAXID];
  72 } idstate;
  73
  74 static inline uint32_t
  75 ipid_random(void)
  76 {
  77         return arc4random();
  78 }
  79
  80 /*
  81  * Initalizes the
  82  * the msb flag. The msb flag is used to generate two distinct
  83  * cycles of random numbers and thus avoiding reuse of ids.
  84  *
  85  * This function is called from id_randomid() when needed, an
  86  * application does not have to worry about it.
  87  */
  88 void
  89 ip_initid(void)
  90 {
  91         size_t i;
  92
  93         idstate.ids_start_slot = ipid_random();
  94         for (i = 0; i < __arraycount(idstate.ids_slots); i++)
  95                 idstate.ids_slots[i] = i;
  96
  97         /*
  98          * Shuffle the array.
  99          */
 100         for (i = __arraycount(idstate.ids_slots); --i > 0;) {
 101                 size_t k = ipid_random() % (i + 1);
 102                 uint16_t t = idstate.ids_slots[i];
 103                 idstate.ids_slots[i] = idstate.ids_slots[k];
 104                 idstate.ids_slots[k] = t;
 105         }
 106 }
 107
 108 uint16_t
 109 ip_randomid(uint16_t salt)
 110 {
 111         uint32_t r, k, id;
 112
 113         /*
 114          * We need a random number
 115          */
 116         r = ipid_random();
 117
 118         /*
 119          * We do a modified Fisher-Yates shuffle but only one position at a
 120          * time. Instead of the last entry, we swap with the first entry and
 121          * then advance the start of the window by 1.  The next time that
 122          * swapped-out entry can be used is at least 32768 iterations in the
 123          * future.
 124          *
 125          * The easiest way to visual this is to imagine a card deck with 52
 126          * cards.  First thing we do is split that into two sets, each with
 127          * half of the cards; call them deck A and deck B.  Pick a card
 128          * randomly from deck A and remember it, then place it at the
 129          * bottom of deck B.  Then take the top card from deck B and add it
 130          * to deck A.  Pick another card randomly from deck A and ...
 131          */
 132         k = (r & (IPID_NUMIDS-1)) + idstate.ids_start_slot;
 133         if (k >= IPID_MAXID)
 134                 k -= IPID_MAXID;
 135
 136         id = idstate.ids_slots[k];
 137         if (k != idstate.ids_start_slot) {
 138                 idstate.ids_slots[k] = idstate.ids_slots[idstate.ids_start_slot];
 139                 idstate.ids_slots[idstate.ids_start_slot] = id;
 140         }
 141         if (++idstate.ids_start_slot == IPID_MAXID)
 142                 idstate.ids_start_slot = 0;
 143         /*
 144          * Add an optional salt to the id to further obscure it.
 145          */
 146         id += salt;
 147         if (id >= IPID_MAXID)
 148                 id -= IPID_MAXID;
 149
 150         return (uint16_t) htons(id + 1);
 151 }