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_PROC(_net_inet_ip, OID_AUTO, random_id_period, CTLTYPE_INT|CTLFLAG_RW, 108 &array_size, 0, sysctl_ip_id_change, "IU", "IP ID Array size"); 109 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD, 110 &random_id_collisions, 0, "Count of IP ID collisions"); 111 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD, 112 &random_id_total, 0, "Count of IP IDs created"); 113 114 static int 115 sysctl_ip_id_change(SYSCTL_HANDLER_ARGS) 116 { 117 int error, new; 118 119 new = array_size; 120 error = sysctl_handle_int(oidp, &new, 0, req); 121 if (error == 0 && req->newptr) { 122 if (new >= 512 && new <= 32768) { 123 mtx_lock(&ip_id_mtx); 124 array_size = new; 125 ip_initid(); 126 mtx_unlock(&ip_id_mtx); 127 } else 128 error = EINVAL; 129 } 130 return (error); 131 } 132 133 /* 134 * ip_initid() runs with a mutex held and may execute in a network context. 135 * As a result, it uses M_NOWAIT. Ideally, we would always do this 136 * allocation from the sysctl contact and have it be an invariant that if 137 * this random ID allocation mode is selected, the buffers are present. This 138 * would also avoid potential network context failures of IP ID generation. 139 */ 140 static void 141 ip_initid(void) 142 { 143 144 mtx_assert(&ip_id_mtx, MA_OWNED); 145 146 if (id_array != NULL) { 147 free(id_array, M_IPID); 148 free(id_bits, M_IPID); 149 } 150 random_id_collisions = 0; 151 random_id_total = 0; 152 array_ptr = 0; 153 id_array = (u_int16_t *) malloc(array_size * sizeof(u_int16_t), 154 M_IPID, M_NOWAIT | M_ZERO); 155 id_bits = (bitstr_t *) malloc(bitstr_size(65536), M_IPID, 156 M_NOWAIT | M_ZERO); 157 if (id_array == NULL || id_bits == NULL) { 158 /* Neither or both. */ 159 if (id_array != NULL) { 160 free(id_array, M_IPID); 161 id_array = NULL; 162 } 163 if (id_bits != NULL) { 164 free(id_bits, M_IPID); 165 id_bits = NULL; 166 } 167 } 168 } 169 170 u_int16_t 171 ip_randomid(void) 172 { 173 u_int16_t new_id; 174 175 mtx_lock(&ip_id_mtx); 176 if (id_array == NULL) 177 ip_initid(); 178 179 /* 180 * Fail gracefully; return a fixed id if memory allocation failed; 181 * ideally we wouldn't do allocation in this context in order to 182 * avoid the possibility of this failure mode. 183 */ 184 if (id_array == NULL) { 185 mtx_unlock(&ip_id_mtx); 186 return (1); 187 } 188 189 /* 190 * To avoid a conflict with the zeros that the array is initially 191 * filled with, we never hand out an id of zero. 192 */ 193 new_id = 0; 194 do { 195 if (new_id != 0) 196 random_id_collisions++; 197 arc4rand(&new_id, sizeof(new_id), 0); 198 } while (bit_test(id_bits, new_id) || new_id == 0); 199 bit_clear(id_bits, id_array[array_ptr]); 200 bit_set(id_bits, new_id); 201 id_array[array_ptr] = new_id; 202 array_ptr++; 203 if (array_ptr == array_size) 204 array_ptr = 0; 205 random_id_total++; 206 mtx_unlock(&ip_id_mtx); 207 return (new_id); 208 } 209