sys/netinet/ip_id.c

   1
   2 /*-
   3  * Copyright (c) 2008 Michael J. Silbersack.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice unmodified, this list of conditions, and the following
  11  *    disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30
  31 /*
  32  * IP ID generation is a fascinating topic.
  33  *
  34  * In order to avoid ID collisions during packet reassembly, common sense
  35  * dictates that the period between reuse of IDs be as large as possible.
  36  * This leads to the classic implementation of a system-wide counter, thereby
  37  * ensuring that IDs repeat only once every 2^16 packets.
  38  *
  39  * Subsequent security researchers have pointed out that using a global
  40  * counter makes ID values predictable.  This predictability allows traffic
  41  * analysis, idle scanning, and even packet injection in specific cases.
  42  * These results suggest that IP IDs should be as random as possible.
  43  *
  44  * The "searchable queues" algorithm used in this IP ID implementation was
  45  * proposed by Amit Klein.  It is a compromise between the above two
  46  * viewpoints that has provable behavior that can be tuned to the user's
  47  * requirements.
  48  *
  49  * The basic concept is that we supplement a standard random number generator
  50  * with a queue of the last L IDs that we have handed out to ensure that all
  51  * IDs have a period of at least L.
  52  *
  53  * To efficiently implement this idea, we keep two data structures: a
  54  * circular array of IDs of size L and a bitstring of 65536 bits.
  55  *
  56  * To start, we ask the RNG for a new ID.  A quick index into the bitstring
  57  * is used to determine if this is a recently used value.  The process is
  58  * repeated until a value is returned that is not in the bitstring.
  59  *
  60  * Having found a usable ID, we remove the ID stored at the current position
  61  * in the queue from the bitstring and replace it with our new ID.  Our new
  62  * ID is then added to the bitstring and the queue pointer is incremented.
  63  *
  64  * The lower limit of 512 was chosen because there doesn't seem to be much
  65  * point to having a smaller value.  The upper limit of 32768 was chosen for
  66  * two reasons.  First, every step above 32768 decreases the entropy.  Taken
  67  * to an extreme, 65533 would offer 1 bit of entropy.  Second, the number of
  68  * attempts it takes the algorithm to find an unused ID drastically
  69  * increases, killing performance.  The default value of 8192 was chosen
  70  * because it provides a good tradeoff between randomness and non-repetition.
  71  *
  72  * With L=8192, the queue will use 16K of memory.  The bitstring always
  73  * uses 8K of memory.  No memory is allocated until the use of random ids is
  74  * enabled.
  75  */
  76
  77 #include <sys/types.h>
  78 #include <sys/malloc.h>
  79 #include <sys/param.h>
  80 #include <sys/time.h>
  81 #include <sys/kernel.h>
  82 #include <sys/libkern.h>
  83 #include <sys/lock.h>
  84 #include <sys/mutex.h>
  85 #include <sys/random.h>
  86 #include <sys/systm.h>
  87 #include <sys/sysctl.h>
  88 #include <netinet/in.h>
  89 #include <netinet/ip_var.h>
  90 #include <sys/bitstring.h>
  91
  92 static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state");
  93
  94 static u_int16_t        *id_array = NULL;
  95 static bitstr_t         *id_bits = NULL;
  96 static int               array_ptr = 0;
  97 static int               array_size = 8192;
  98 static int               random_id_collisions = 0;
  99 static int               random_id_total = 0;
 100 static struct mtx        ip_id_mtx;
 101
 102 static void     ip_initid(void);
 103 static int      sysctl_ip_id_change(SYSCTL_HANDLER_ARGS);
 104
 105 MTX_SYSINIT(ip_id_mtx, &ip_id_mtx, "ip_id_mtx", MTX_DEF);
 106
 107 SYSCTL_DECL(_net_inet_ip);
 108 SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, CTLTYPE_INT|CTLFLAG_RW,
 109     &array_size, 0, sysctl_ip_id_change, "IU", "IP ID Array size");
 110 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD,
 111     &random_id_collisions, 0, "Count of IP ID collisions");
 112 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD,
 113     &random_id_total, 0, "Count of IP IDs created");
 114
 115 static int
 116 sysctl_ip_id_change(SYSCTL_HANDLER_ARGS)
 117 {
 118         int error, new;
 119
 120         new = array_size;
 121         error = sysctl_handle_int(oidp, &new, 0, req);
 122         if (error == 0 && req->newptr) {
 123                 if (new >= 512 && new <= 32768) {
 124                         mtx_lock(&ip_id_mtx);
 125                         array_size = new;
 126                         ip_initid();
 127                         mtx_unlock(&ip_id_mtx);
 128                 } else
 129                         error = EINVAL;
 130         }
 131         return (error);
 132 }
 133
 134 /*
 135  * ip_initid() runs with a mutex held and may execute in a network context.
 136  * As a result, it uses M_NOWAIT.  Ideally, we would always do this
 137  * allocation from the sysctl contact and have it be an invariant that if
 138  * this random ID allocation mode is selected, the buffers are present.  This
 139  * would also avoid potential network context failures of IP ID generation.
 140  */
 141 static void
 142 ip_initid(void)
 143 {
 144
 145         mtx_assert(&ip_id_mtx, MA_OWNED);
 146
 147         if (id_array != NULL) {
 148                 free(id_array, M_IPID);
 149                 free(id_bits, M_IPID);
 150         }
 151         random_id_collisions = 0;
 152         random_id_total = 0;
 153         array_ptr = 0;
 154         id_array = (u_int16_t *) malloc(array_size * sizeof(u_int16_t),
 155             M_IPID, M_NOWAIT | M_ZERO);
 156         id_bits = (bitstr_t *) malloc(bitstr_size(65536), M_IPID,
 157             M_NOWAIT | M_ZERO);
 158         if (id_array == NULL || id_bits == NULL) {
 159                 /* Neither or both. */
 160                 if (id_array != NULL) {
 161                         free(id_array, M_IPID);
 162                         id_array = NULL;
 163                 }
 164                 if (id_bits != NULL) {
 165                         free(id_bits, M_IPID);
 166                         id_bits = NULL;
 167                 }
 168         }
 169 }
 170
 171 u_int16_t
 172 ip_randomid(void)
 173 {
 174         u_int16_t new_id;
 175
 176         mtx_lock(&ip_id_mtx);
 177         if (id_array == NULL)
 178                 ip_initid();
 179
 180         /*
 181          * Fail gracefully; return a fixed id if memory allocation failed;
 182          * ideally we wouldn't do allocation in this context in order to
 183          * avoid the possibility of this failure mode.
 184          */
 185         if (id_array == NULL) {
 186                 mtx_unlock(&ip_id_mtx);
 187                 return (1);
 188         }
 189
 190         /*
 191          * To avoid a conflict with the zeros that the array is initially
 192          * filled with, we never hand out an id of zero.
 193          */
 194         new_id = 0;
 195         do {
 196                 if (new_id != 0)
 197                         random_id_collisions++;
 198                 arc4rand(&new_id, sizeof(new_id), 0);
 199         } while (bit_test(id_bits, new_id) || new_id == 0);
 200         bit_clear(id_bits, id_array[array_ptr]);
 201         bit_set(id_bits, new_id);
 202         id_array[array_ptr] = new_id;
 203         array_ptr++;
 204         if (array_ptr == array_size)
 205                 array_ptr = 0;
 206         random_id_total++;
 207         mtx_unlock(&ip_id_mtx);
 208         return (new_id);
 209 }