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 } 210