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 <sys/bitstring.h> 89 90 #include <net/vnet.h> 91 92 #include <netinet/in.h> 93 #include <netinet/ip_var.h> 94 95 static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state"); 96 97 static VNET_DEFINE(uint16_t *, id_array); 98 static VNET_DEFINE(bitstr_t *, id_bits); 99 static VNET_DEFINE(int, array_ptr); 100 static VNET_DEFINE(int, array_size); 101 static VNET_DEFINE(int, random_id_collisions); 102 static VNET_DEFINE(int, random_id_total); 103 static VNET_DEFINE(struct mtx, ip_id_mtx); 104 #define V_id_array VNET(id_array) 105 #define V_id_bits VNET(id_bits) 106 #define V_array_ptr VNET(array_ptr) 107 #define V_array_size VNET(array_size) 108 #define V_random_id_collisions VNET(random_id_collisions) 109 #define V_random_id_total VNET(random_id_total) 110 #define V_ip_id_mtx VNET(ip_id_mtx) 111 112 static void ip_initid(int); 113 static int sysctl_ip_id_change(SYSCTL_HANDLER_ARGS); 114 static void ipid_sysinit(void); 115 static void ipid_sysuninit(void); 116 117 SYSCTL_DECL(_net_inet_ip); 118 SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, 119 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_VNET, 120 &VNET_NAME(array_size), 0, sysctl_ip_id_change, "IU", "IP ID Array size"); 121 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, 122 CTLFLAG_RD | CTLFLAG_VNET, 123 &VNET_NAME(random_id_collisions), 0, "Count of IP ID collisions"); 124 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD | CTLFLAG_VNET, 125 &VNET_NAME(random_id_total), 0, "Count of IP IDs created"); 126 127 static int 128 sysctl_ip_id_change(SYSCTL_HANDLER_ARGS) 129 { 130 int error, new; 131 132 new = V_array_size; 133 error = sysctl_handle_int(oidp, &new, 0, req); 134 if (error == 0 && req->newptr) { 135 if (new >= 512 && new <= 32768) 136 ip_initid(new); 137 else 138 error = EINVAL; 139 } 140 return (error); 141 } 142 143 static void 144 ip_initid(int new_size) 145 { 146 uint16_t *new_array; 147 bitstr_t *new_bits; 148 149 new_array = malloc(new_size * sizeof(uint16_t), M_IPID, 150 M_WAITOK | M_ZERO); 151 new_bits = malloc(bitstr_size(65536), M_IPID, M_WAITOK | M_ZERO); 152 153 mtx_lock(&V_ip_id_mtx); 154 if (V_id_array != NULL) { 155 free(V_id_array, M_IPID); 156 free(V_id_bits, M_IPID); 157 } 158 V_id_array = new_array; 159 V_id_bits = new_bits; 160 V_array_size = new_size; 161 V_array_ptr = 0; 162 V_random_id_collisions = 0; 163 V_random_id_total = 0; 164 mtx_unlock(&V_ip_id_mtx); 165 } 166 167 uint16_t 168 ip_randomid(void) 169 { 170 uint16_t new_id; 171 172 mtx_lock(&V_ip_id_mtx); 173 /* 174 * To avoid a conflict with the zeros that the array is initially 175 * filled with, we never hand out an id of zero. 176 */ 177 new_id = 0; 178 do { 179 if (new_id != 0) 180 V_random_id_collisions++; 181 arc4rand(&new_id, sizeof(new_id), 0); 182 } while (bit_test(V_id_bits, new_id) || new_id == 0); 183 bit_clear(V_id_bits, V_id_array[V_array_ptr]); 184 bit_set(V_id_bits, new_id); 185 V_id_array[V_array_ptr] = new_id; 186 V_array_ptr++; 187 if (V_array_ptr == V_array_size) 188 V_array_ptr = 0; 189 V_random_id_total++; 190 mtx_unlock(&V_ip_id_mtx); 191 return (new_id); 192 } 193 194 static void 195 ipid_sysinit(void) 196 { 197 198 mtx_init(&V_ip_id_mtx, "ip_id_mtx", NULL, MTX_DEF); 199 ip_initid(8192); 200 } 201 VNET_SYSINIT(ip_id, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, ipid_sysinit, NULL); 202 203 static void 204 ipid_sysuninit(void) 205 { 206 207 mtx_destroy(&V_ip_id_mtx); 208 free(V_id_array, M_IPID); 209 free(V_id_bits, M_IPID); 210 } 211 VNET_SYSUNINIT(ip_id, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, ipid_sysuninit, NULL); 212