177574Skris 2139823Simp/*- 3176042Ssilby * Copyright (c) 2008 Michael J. Silbersack. 477574Skris * All rights reserved. 577574Skris * 677574Skris * Redistribution and use in source and binary forms, with or without 777574Skris * modification, are permitted provided that the following conditions 877574Skris * are met: 977574Skris * 1. Redistributions of source code must retain the above copyright 10176042Ssilby * notice unmodified, this list of conditions, and the following 11176042Ssilby * disclaimer. 1277574Skris * 2. Redistributions in binary form must reproduce the above copyright 1377574Skris * notice, this list of conditions and the following disclaimer in the 1477574Skris * documentation and/or other materials provided with the distribution. 1577574Skris * 1677574Skris * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1777574Skris * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1877574Skris * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1977574Skris * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2077574Skris * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2177574Skris * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2277574Skris * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2377574Skris * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2477574Skris * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2577574Skris * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2677574Skris */ 2777574Skris 28176042Ssilby#include <sys/cdefs.h> 29176042Ssilby__FBSDID("$FreeBSD$"); 30176042Ssilby 31176042Ssilby/* 32176042Ssilby * IP ID generation is a fascinating topic. 3377574Skris * 34176042Ssilby * In order to avoid ID collisions during packet reassembly, common sense 35176042Ssilby * dictates that the period between reuse of IDs be as large as possible. 36176042Ssilby * This leads to the classic implementation of a system-wide counter, thereby 37176042Ssilby * ensuring that IDs repeat only once every 2^16 packets. 3877574Skris * 39176042Ssilby * Subsequent security researchers have pointed out that using a global 40176042Ssilby * counter makes ID values predictable. This predictability allows traffic 41176042Ssilby * analysis, idle scanning, and even packet injection in specific cases. 42176042Ssilby * These results suggest that IP IDs should be as random as possible. 4377574Skris * 44176042Ssilby * The "searchable queues" algorithm used in this IP ID implementation was 45176042Ssilby * proposed by Amit Klein. It is a compromise between the above two 46176042Ssilby * viewpoints that has provable behavior that can be tuned to the user's 47176042Ssilby * requirements. 48176042Ssilby * 49176042Ssilby * The basic concept is that we supplement a standard random number generator 50176042Ssilby * with a queue of the last L IDs that we have handed out to ensure that all 51176042Ssilby * IDs have a period of at least L. 52176042Ssilby * 53176042Ssilby * To efficiently implement this idea, we keep two data structures: a 54176042Ssilby * circular array of IDs of size L and a bitstring of 65536 bits. 55176042Ssilby * 56176042Ssilby * To start, we ask the RNG for a new ID. A quick index into the bitstring 57176042Ssilby * is used to determine if this is a recently used value. The process is 58176042Ssilby * repeated until a value is returned that is not in the bitstring. 59176042Ssilby * 60176042Ssilby * Having found a usable ID, we remove the ID stored at the current position 61176042Ssilby * in the queue from the bitstring and replace it with our new ID. Our new 62176042Ssilby * ID is then added to the bitstring and the queue pointer is incremented. 63176042Ssilby * 64176042Ssilby * The lower limit of 512 was chosen because there doesn't seem to be much 65176042Ssilby * point to having a smaller value. The upper limit of 32768 was chosen for 66176042Ssilby * two reasons. First, every step above 32768 decreases the entropy. Taken 67176042Ssilby * to an extreme, 65533 would offer 1 bit of entropy. Second, the number of 68176042Ssilby * attempts it takes the algorithm to find an unused ID drastically 69176042Ssilby * increases, killing performance. The default value of 8192 was chosen 70176042Ssilby * because it provides a good tradeoff between randomness and non-repetition. 71176042Ssilby * 72176042Ssilby * With L=8192, the queue will use 16K of memory. The bitstring always 73176042Ssilby * uses 8K of memory. No memory is allocated until the use of random ids is 74176042Ssilby * enabled. 7577574Skris */ 7677574Skris 77176042Ssilby#include <sys/types.h> 78176042Ssilby#include <sys/malloc.h> 7977574Skris#include <sys/param.h> 8077574Skris#include <sys/time.h> 8177574Skris#include <sys/kernel.h> 82176042Ssilby#include <sys/libkern.h> 83176042Ssilby#include <sys/lock.h> 84176042Ssilby#include <sys/mutex.h> 8577574Skris#include <sys/random.h> 86176042Ssilby#include <sys/systm.h> 87176042Ssilby#include <sys/sysctl.h> 88176042Ssilby#include <netinet/in.h> 89176042Ssilby#include <netinet/ip_var.h> 90176042Ssilby#include <sys/bitstring.h> 9177574Skris 92176042Ssilbystatic MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state"); 9377574Skris 94176042Ssilbystatic u_int16_t *id_array = NULL; 95176042Ssilbystatic bitstr_t *id_bits = NULL; 96176042Ssilbystatic int array_ptr = 0; 97176042Ssilbystatic int array_size = 8192; 98176042Ssilbystatic int random_id_collisions = 0; 99176042Ssilbystatic int random_id_total = 0; 100250300Sandrestatic struct mtx ip_id_mtx; 10177574Skris 102176042Ssilbystatic void ip_initid(void); 103176042Ssilbystatic int sysctl_ip_id_change(SYSCTL_HANDLER_ARGS); 10477574Skris 105176042SsilbyMTX_SYSINIT(ip_id_mtx, &ip_id_mtx, "ip_id_mtx", MTX_DEF); 10677574Skris 107185571SbzSYSCTL_DECL(_net_inet_ip); 108176042SsilbySYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, CTLTYPE_INT|CTLFLAG_RW, 109176042Ssilby &array_size, 0, sysctl_ip_id_change, "IU", "IP ID Array size"); 110176042SsilbySYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD, 111176042Ssilby &random_id_collisions, 0, "Count of IP ID collisions"); 112176042SsilbySYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD, 113176042Ssilby &random_id_total, 0, "Count of IP IDs created"); 11477574Skris 115176042Ssilbystatic int 116176042Ssilbysysctl_ip_id_change(SYSCTL_HANDLER_ARGS) 11777574Skris{ 118176042Ssilby int error, new; 11977574Skris 120176042Ssilby new = array_size; 121176042Ssilby error = sysctl_handle_int(oidp, &new, 0, req); 122176042Ssilby if (error == 0 && req->newptr) { 123176042Ssilby if (new >= 512 && new <= 32768) { 124176042Ssilby mtx_lock(&ip_id_mtx); 125176042Ssilby array_size = new; 126176042Ssilby ip_initid(); 127176042Ssilby mtx_unlock(&ip_id_mtx); 128176042Ssilby } else 129176042Ssilby error = EINVAL; 13077574Skris } 131176042Ssilby return (error); 13277574Skris} 13377574Skris 134133874Srwatson/* 135176042Ssilby * ip_initid() runs with a mutex held and may execute in a network context. 136176042Ssilby * As a result, it uses M_NOWAIT. Ideally, we would always do this 137176042Ssilby * allocation from the sysctl contact and have it be an invariant that if 138176042Ssilby * this random ID allocation mode is selected, the buffers are present. This 139176042Ssilby * would also avoid potential network context failures of IP ID generation. 14077574Skris */ 141133874Srwatsonstatic void 14277574Skrisip_initid(void) 14377574Skris{ 14477574Skris 145176042Ssilby mtx_assert(&ip_id_mtx, MA_OWNED); 14677574Skris 147176042Ssilby if (id_array != NULL) { 148176042Ssilby free(id_array, M_IPID); 149176042Ssilby free(id_bits, M_IPID); 15077574Skris } 151176042Ssilby random_id_collisions = 0; 152176042Ssilby random_id_total = 0; 153176042Ssilby array_ptr = 0; 154176042Ssilby id_array = (u_int16_t *) malloc(array_size * sizeof(u_int16_t), 155176042Ssilby M_IPID, M_NOWAIT | M_ZERO); 156176042Ssilby id_bits = (bitstr_t *) malloc(bitstr_size(65536), M_IPID, 157176042Ssilby M_NOWAIT | M_ZERO); 158176042Ssilby if (id_array == NULL || id_bits == NULL) { 159176042Ssilby /* Neither or both. */ 160176042Ssilby if (id_array != NULL) { 161176042Ssilby free(id_array, M_IPID); 162176042Ssilby id_array = NULL; 163176042Ssilby } 164176042Ssilby if (id_bits != NULL) { 165176042Ssilby free(id_bits, M_IPID); 166176042Ssilby id_bits = NULL; 167176042Ssilby } 168176042Ssilby } 16977574Skris} 17077574Skris 17177574Skrisu_int16_t 17277574Skrisip_randomid(void) 17377574Skris{ 174176042Ssilby u_int16_t new_id; 17577574Skris 176176042Ssilby mtx_lock(&ip_id_mtx); 177176042Ssilby if (id_array == NULL) 17877574Skris ip_initid(); 17977574Skris 180176042Ssilby /* 181176042Ssilby * Fail gracefully; return a fixed id if memory allocation failed; 182176042Ssilby * ideally we wouldn't do allocation in this context in order to 183176042Ssilby * avoid the possibility of this failure mode. 184176042Ssilby */ 185176042Ssilby if (id_array == NULL) { 186176042Ssilby mtx_unlock(&ip_id_mtx); 187176042Ssilby return (1); 188176042Ssilby } 18977574Skris 190176042Ssilby /* 191176042Ssilby * To avoid a conflict with the zeros that the array is initially 192176042Ssilby * filled with, we never hand out an id of zero. 193176042Ssilby */ 194176042Ssilby new_id = 0; 195176042Ssilby do { 196176042Ssilby if (new_id != 0) 197176042Ssilby random_id_collisions++; 198176042Ssilby arc4rand(&new_id, sizeof(new_id), 0); 199176042Ssilby } while (bit_test(id_bits, new_id) || new_id == 0); 200176042Ssilby bit_clear(id_bits, id_array[array_ptr]); 201176042Ssilby bit_set(id_bits, new_id); 202176042Ssilby id_array[array_ptr] = new_id; 203176042Ssilby array_ptr++; 204176042Ssilby if (array_ptr == array_size) 205176042Ssilby array_ptr = 0; 206176042Ssilby random_id_total++; 207176042Ssilby mtx_unlock(&ip_id_mtx); 208176042Ssilby return (new_id); 20977574Skris} 210