ip_id.c revision 280971
1240122Smarcel 2240122Smarcel/*- 3240122Smarcel * Copyright (c) 2008 Michael J. Silbersack. 4240122Smarcel * All rights reserved. 5240122Smarcel * 6240122Smarcel * Redistribution and use in source and binary forms, with or without 7240122Smarcel * modification, are permitted provided that the following conditions 8240122Smarcel * are met: 9240122Smarcel * 1. Redistributions of source code must retain the above copyright 10240122Smarcel * notice unmodified, this list of conditions, and the following 11240122Smarcel * disclaimer. 12240122Smarcel * 2. Redistributions in binary form must reproduce the above copyright 13240122Smarcel * notice, this list of conditions and the following disclaimer in the 14240122Smarcel * documentation and/or other materials provided with the distribution. 15240122Smarcel * 16240122Smarcel * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17240122Smarcel * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18240122Smarcel * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19240122Smarcel * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20240122Smarcel * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21240122Smarcel * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22240122Smarcel * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23240122Smarcel * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24240122Smarcel * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25240122Smarcel * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26240122Smarcel */ 27240122Smarcel 28240122Smarcel#include <sys/cdefs.h> 29240122Smarcel__FBSDID("$FreeBSD: head/sys/netinet/ip_id.c 280971 2015-04-01 22:26:39Z glebius $"); 30240122Smarcel 31240122Smarcel/* 32240122Smarcel * IP ID generation is a fascinating topic. 33240122Smarcel * 34240122Smarcel * In order to avoid ID collisions during packet reassembly, common sense 35240122Smarcel * dictates that the period between reuse of IDs be as large as possible. 36240122Smarcel * This leads to the classic implementation of a system-wide counter, thereby 37240122Smarcel * 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/param.h> 78#include <sys/systm.h> 79#include <sys/counter.h> 80#include <sys/malloc.h> 81#include <sys/lock.h> 82#include <sys/mutex.h> 83#include <sys/random.h> 84#include <sys/smp.h> 85#include <sys/sysctl.h> 86#include <sys/bitstring.h> 87 88#include <net/vnet.h> 89 90#include <netinet/in.h> 91#include <netinet/ip.h> 92#include <netinet/ip_var.h> 93 94/* 95 * By default we generate IP ID only for non-atomic datagrams, as 96 * suggested by RFC6864. We use per-CPU counter for that, or if 97 * user wants to, we can turn on random ID generation. 98 */ 99static VNET_DEFINE(int, ip_rfc6864) = 1; 100static VNET_DEFINE(int, ip_do_randomid) = 0; 101#define V_ip_rfc6864 VNET(ip_rfc6864) 102#define V_ip_do_randomid VNET(ip_do_randomid) 103 104/* 105 * Random ID state engine. 106 */ 107static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state"); 108static VNET_DEFINE(uint16_t *, id_array); 109static VNET_DEFINE(bitstr_t *, id_bits); 110static VNET_DEFINE(int, array_ptr); 111static VNET_DEFINE(int, array_size); 112static VNET_DEFINE(int, random_id_collisions); 113static VNET_DEFINE(int, random_id_total); 114static VNET_DEFINE(struct mtx, ip_id_mtx); 115#define V_id_array VNET(id_array) 116#define V_id_bits VNET(id_bits) 117#define V_array_ptr VNET(array_ptr) 118#define V_array_size VNET(array_size) 119#define V_random_id_collisions VNET(random_id_collisions) 120#define V_random_id_total VNET(random_id_total) 121#define V_ip_id_mtx VNET(ip_id_mtx) 122 123/* 124 * Non-random ID state engine is simply a per-cpu counter. 125 */ 126static VNET_DEFINE(counter_u64_t, ip_id); 127#define V_ip_id VNET(ip_id) 128 129static int sysctl_ip_randomid(SYSCTL_HANDLER_ARGS); 130static int sysctl_ip_id_change(SYSCTL_HANDLER_ARGS); 131static void ip_initid(int); 132static uint16_t ip_randomid(void); 133static void ipid_sysinit(void); 134static void ipid_sysuninit(void); 135 136SYSCTL_DECL(_net_inet_ip); 137SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id, 138 CTLTYPE_INT | CTLFLAG_VNET | CTLFLAG_RW, 139 &VNET_NAME(ip_do_randomid), 0, sysctl_ip_randomid, "IU", 140 "Assign random ip_id values"); 141SYSCTL_INT(_net_inet_ip, OID_AUTO, rfc6864, CTLFLAG_VNET | CTLFLAG_RW, 142 &VNET_NAME(ip_rfc6864), 0, 143 "Use constant IP ID for atomic datagrams"); 144SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, 145 CTLTYPE_INT | CTLFLAG_RW | CTLFLAG_VNET, 146 &VNET_NAME(array_size), 0, sysctl_ip_id_change, "IU", "IP ID Array size"); 147SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, 148 CTLFLAG_RD | CTLFLAG_VNET, 149 &VNET_NAME(random_id_collisions), 0, "Count of IP ID collisions"); 150SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD | CTLFLAG_VNET, 151 &VNET_NAME(random_id_total), 0, "Count of IP IDs created"); 152 153static int 154sysctl_ip_randomid(SYSCTL_HANDLER_ARGS) 155{ 156 int error, new; 157 158 new = V_ip_do_randomid; 159 error = sysctl_handle_int(oidp, &new, 0, req); 160 if (error || req->newptr == NULL) 161 return (error); 162 if (new != 0 && new != 1) 163 return (EINVAL); 164 if (new == V_ip_do_randomid) 165 return (0); 166 if (new == 1 && V_ip_do_randomid == 0) 167 ip_initid(8192); 168 /* We don't free memory when turning random ID off, due to race. */ 169 V_ip_do_randomid = new; 170 return (0); 171} 172 173static int 174sysctl_ip_id_change(SYSCTL_HANDLER_ARGS) 175{ 176 int error, new; 177 178 new = V_array_size; 179 error = sysctl_handle_int(oidp, &new, 0, req); 180 if (error == 0 && req->newptr) { 181 if (new >= 512 && new <= 32768) 182 ip_initid(new); 183 else 184 error = EINVAL; 185 } 186 return (error); 187} 188 189static void 190ip_initid(int new_size) 191{ 192 uint16_t *new_array; 193 bitstr_t *new_bits; 194 195 new_array = malloc(new_size * sizeof(uint16_t), M_IPID, 196 M_WAITOK | M_ZERO); 197 new_bits = malloc(bitstr_size(65536), M_IPID, M_WAITOK | M_ZERO); 198 199 mtx_lock(&V_ip_id_mtx); 200 if (V_id_array != NULL) { 201 free(V_id_array, M_IPID); 202 free(V_id_bits, M_IPID); 203 } 204 V_id_array = new_array; 205 V_id_bits = new_bits; 206 V_array_size = new_size; 207 V_array_ptr = 0; 208 V_random_id_collisions = 0; 209 V_random_id_total = 0; 210 mtx_unlock(&V_ip_id_mtx); 211} 212 213static uint16_t 214ip_randomid(void) 215{ 216 uint16_t new_id; 217 218 mtx_lock(&V_ip_id_mtx); 219 /* 220 * To avoid a conflict with the zeros that the array is initially 221 * filled with, we never hand out an id of zero. 222 */ 223 new_id = 0; 224 do { 225 if (new_id != 0) 226 V_random_id_collisions++; 227 arc4rand(&new_id, sizeof(new_id), 0); 228 } while (bit_test(V_id_bits, new_id) || new_id == 0); 229 bit_clear(V_id_bits, V_id_array[V_array_ptr]); 230 bit_set(V_id_bits, new_id); 231 V_id_array[V_array_ptr] = new_id; 232 V_array_ptr++; 233 if (V_array_ptr == V_array_size) 234 V_array_ptr = 0; 235 V_random_id_total++; 236 mtx_unlock(&V_ip_id_mtx); 237 return (new_id); 238} 239 240void 241ip_fillid(struct ip *ip) 242{ 243 244 /* 245 * Per RFC6864 Section 4 246 * 247 * o Atomic datagrams: (DF==1) && (MF==0) && (frag_offset==0) 248 * o Non-atomic datagrams: (DF==0) || (MF==1) || (frag_offset>0) 249 */ 250 if (V_ip_rfc6864 && (ip->ip_off & htons(IP_DF)) == htons(IP_DF)) 251 ip->ip_id = 0; 252 else if (V_ip_do_randomid) 253 ip->ip_id = ip_randomid(); 254 else { 255 counter_u64_add(V_ip_id, 1); 256 ip->ip_id = htons((*(uint64_t *)zpcpu_get(V_ip_id)) & 0xffff); 257 } 258} 259 260static void 261ipid_sysinit(void) 262{ 263 264 mtx_init(&V_ip_id_mtx, "ip_id_mtx", NULL, MTX_DEF); 265 V_ip_id = counter_u64_alloc(M_WAITOK); 266 for (int i = 0; i < mp_ncpus; i++) 267 arc4rand(zpcpu_get_cpu(V_ip_id, i), sizeof(uint64_t), 0); 268} 269VNET_SYSINIT(ip_id, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, ipid_sysinit, NULL); 270 271static void 272ipid_sysuninit(void) 273{ 274 275 mtx_destroy(&V_ip_id_mtx); 276 if (V_id_array != NULL) { 277 free(V_id_array, M_IPID); 278 free(V_id_bits, M_IPID); 279 } 280 counter_u64_free(V_ip_id); 281} 282VNET_SYSUNINIT(ip_id, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, ipid_sysuninit, NULL); 283