bsd/netinet/ip_id.c

   1 /*
   2  * Copyright (c) 2002-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 /*-
  30  * Copyright (c) 2008 Michael J. Silbersack.
  31  * All rights reserved.
  32  *
  33  * Redistribution and use in source and binary forms, with or without
  34  * modification, are permitted provided that the following conditions
  35  * are met:
  36  * 1. Redistributions of source code must retain the above copyright
  37  *    notice unmodified, this list of conditions, and the following
  38  *    disclaimer.
  39  * 2. Redistributions in binary form must reproduce the above copyright
  40  *    notice, this list of conditions and the following disclaimer in the
  41  *    documentation and/or other materials provided with the distribution.
  42  *
  43  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  44  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  45  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  46  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  47  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  48  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  49  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  50  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  51  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  52  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  53  */
  54
  55 /*
  56  * IP ID generation is a fascinating topic.
  57  *
  58  * In order to avoid ID collisions during packet reassembly, common sense
  59  * dictates that the period between reuse of IDs be as large as possible.
  60  * This leads to the classic implementation of a system-wide counter, thereby
  61  * ensuring that IDs repeat only once every 2^16 packets.
  62  *
  63  * Subsequent security researchers have pointed out that using a global
  64  * counter makes ID values predictable.  This predictability allows traffic
  65  * analysis, idle scanning, and even packet injection in specific cases.
  66  * These results suggest that IP IDs should be as random as possible.
  67  *
  68  * The "searchable queues" algorithm used in this IP ID implementation was
  69  * proposed by Amit Klein.  It is a compromise between the above two
  70  * viewpoints that has provable behavior that can be tuned to the user's
  71  * requirements.
  72  *
  73  * The basic concept is that we supplement a standard random number generator
  74  * with a queue of the last L IDs that we have handed out to ensure that all
  75  * IDs have a period of at least L.
  76  *
  77  * To efficiently implement this idea, we keep two data structures: a
  78  * circular array of IDs of size L and a bitstring of 65536 bits.
  79  *
  80  * To start, we ask the RNG for a new ID.  A quick index into the bitstring
  81  * is used to determine if this is a recently used value.  The process is
  82  * repeated until a value is returned that is not in the bitstring.
  83  *
  84  * Having found a usable ID, we remove the ID stored at the current position
  85  * in the queue from the bitstring and replace it with our new ID.  Our new
  86  * ID is then added to the bitstring and the queue pointer is incremented.
  87  *
  88  * The lower limit of 512 was chosen because there doesn't seem to be much
  89  * point to having a smaller value.  The upper limit of 32768 was chosen for
  90  * two reasons.  First, every step above 32768 decreases the entropy.  Taken
  91  * to an extreme, 65533 would offer 1 bit of entropy.  Second, the number of
  92  * attempts it takes the algorithm to find an unused ID drastically
  93  * increases, killing performance.  The default value of 4096 was chosen
  94  * because it provides a good tradeoff between randomness and non-repetition,
  95  * while taking performance into account.
  96  *
  97  * With L=4096, the queue will use 8K of memory.  The bitstring always uses
  98  * 8K of memory (2^16/8).  This yields to around 7% ID collisions.  No memory
  99  * is allocated until the use of random ids is enabled.
 100  */
 101
 102 #include <sys/param.h>
 103 #include <sys/time.h>
 104 #include <sys/kernel.h>
 105 #include <sys/random.h>
 106 #include <sys/protosw.h>
 107 #include <sys/bitstring.h>
 108 #include <kern/locks.h>
 109 #include <net/if_var.h>
 110 #include <netinet/in.h>
 111 #include <netinet/in_var.h>
 112 #include <netinet/ip_var.h>
 113 #include <dev/random/randomdev.h>
 114
 115 /*
 116  * Size of L (see comments above on the lower and upper limits.)
 117  */
 118 #define ARRAY_SIZE      (4096)
 119
 120 static uint16_t *id_array = NULL;
 121 static bitstr_t *id_bits = NULL;
 122 static uint32_t array_ptr = 0;
 123 static uint32_t random_id_statistics = 0;
 124 static uint64_t random_id_collisions = 0;
 125 static uint64_t random_id_total = 0;
 126
 127 decl_lck_mtx_data(static, ipid_lock);
 128 static lck_attr_t *ipid_lock_attr;
 129 static lck_grp_t *ipid_lock_grp;
 130 static lck_grp_attr_t *ipid_lock_grp_attr;
 131
 132 SYSCTL_UINT(_net_inet_ip, OID_AUTO, random_id_statistics,
 133         CTLFLAG_RW | CTLFLAG_LOCKED, &random_id_statistics, 0,
 134         "Enable IP ID statistics");
 135 SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_collisions,
 136         CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_collisions,
 137         "Count of IP ID collisions");
 138 SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_total,
 139         CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_total,
 140         "Count of IP IDs created");
 141
 142 /*
 143  * Called once from ip_init().
 144  */
 145 void
 146 ip_initid(void)
 147 {
 148         VERIFY(id_array == NULL);
 149         VERIFY(id_bits == NULL);
 150
 151         _CASSERT(ARRAY_SIZE >= 512 && ARRAY_SIZE <= 32768);
 152
 153         ipid_lock_grp_attr  = lck_grp_attr_alloc_init();
 154         ipid_lock_grp = lck_grp_alloc_init("ipid", ipid_lock_grp_attr);
 155         ipid_lock_attr = lck_attr_alloc_init();
 156         lck_mtx_init(&ipid_lock, ipid_lock_grp, ipid_lock_attr);
 157
 158         id_array = (uint16_t *)_MALLOC(ARRAY_SIZE * sizeof (uint16_t),
 159             M_TEMP, M_WAITOK | M_ZERO);
 160         id_bits = (bitstr_t *)_MALLOC(bitstr_size(65536), M_TEMP,
 161             M_WAITOK | M_ZERO);
 162         if (id_array == NULL || id_bits == NULL) {
 163                 /* Just in case; neither or both. */
 164                 if (id_array != NULL) {
 165                         _FREE(id_array, M_TEMP);
 166                         id_array = NULL;
 167                 }
 168                 if (id_bits != NULL) {
 169                         _FREE(id_bits, M_TEMP);
 170                         id_bits = NULL;
 171                 }
 172         }
 173 }
 174
 175 uint16_t
 176 ip_randomid(void)
 177 {
 178         uint16_t new_id;
 179
 180         /*
 181          * If net.inet.ip.random_id is disabled, revert to incrementing ip_id.
 182          * Given that we don't allow the size of the array to change, accessing
 183          * id_array and id_bits prior to acquiring the lock below is safe.
 184          */
 185         if (id_array == NULL || ip_use_randomid == 0)
 186                 return (htons(ip_id++));
 187
 188         /*
 189          * To avoid a conflict with the zeros that the array is initially
 190          * filled with, we never hand out an id of zero.  bit_test() below
 191          * uses single memory access, therefore no lock is needed.
 192          */
 193         new_id = 0;
 194         do {
 195                 if (random_id_statistics && new_id != 0)
 196                         random_id_collisions++;
 197                 read_random(&new_id, sizeof (new_id));
 198         } while (bit_test(id_bits, new_id) || new_id == 0);
 199
 200         /*
 201          * These require serialization to maintain correctness.
 202          */
 203         lck_mtx_lock_spin(&ipid_lock);
 204         bit_clear(id_bits, id_array[array_ptr]);
 205         bit_set(id_bits, new_id);
 206         id_array[array_ptr] = new_id;
 207         if (++array_ptr == ARRAY_SIZE)
 208                 array_ptr = 0;
 209         lck_mtx_unlock(&ipid_lock);
 210
 211         if (random_id_statistics)
 212                 random_id_total++;
 213
 214         return (new_id);
 215 }