1/* 2 * Copyright (c) 2002-2013 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28 29/*- 30 * Copyright (c) 2008 Michael J. Silbersack. 31 * All rights reserved. 32 * 33 * Redistribution and use in source and binary forms, with or without 34 * modification, are permitted provided that the following conditions 35 * are met: 36 * 1. Redistributions of source code must retain the above copyright 37 * notice unmodified, this list of conditions, and the following 38 * disclaimer. 39 * 2. Redistributions in binary form must reproduce the above copyright 40 * notice, this list of conditions and the following disclaimer in the 41 * documentation and/or other materials provided with the distribution. 42 * 43 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 44 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 45 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 46 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 47 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 48 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 49 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 50 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 51 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 52 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 53 */ 54 55/* 56 * IP ID generation is a fascinating topic. 57 * 58 * In order to avoid ID collisions during packet reassembly, common sense 59 * dictates that the period between reuse of IDs be as large as possible. 60 * This leads to the classic implementation of a system-wide counter, thereby 61 * ensuring that IDs repeat only once every 2^16 packets. 62 * 63 * Subsequent security researchers have pointed out that using a global 64 * counter makes ID values predictable. This predictability allows traffic 65 * analysis, idle scanning, and even packet injection in specific cases. 66 * These results suggest that IP IDs should be as random as possible. 67 * 68 * The "searchable queues" algorithm used in this IP ID implementation was 69 * proposed by Amit Klein. It is a compromise between the above two 70 * viewpoints that has provable behavior that can be tuned to the user's 71 * requirements. 72 * 73 * The basic concept is that we supplement a standard random number generator 74 * with a queue of the last L IDs that we have handed out to ensure that all 75 * IDs have a period of at least L. 76 * 77 * To efficiently implement this idea, we keep two data structures: a 78 * circular array of IDs of size L and a bitstring of 65536 bits. 79 * 80 * To start, we ask the RNG for a new ID. A quick index into the bitstring 81 * is used to determine if this is a recently used value. The process is 82 * repeated until a value is returned that is not in the bitstring. 83 * 84 * Having found a usable ID, we remove the ID stored at the current position 85 * in the queue from the bitstring and replace it with our new ID. Our new 86 * ID is then added to the bitstring and the queue pointer is incremented. 87 * 88 * The lower limit of 512 was chosen because there doesn't seem to be much 89 * point to having a smaller value. The upper limit of 32768 was chosen for 90 * two reasons. First, every step above 32768 decreases the entropy. Taken 91 * to an extreme, 65533 would offer 1 bit of entropy. Second, the number of 92 * attempts it takes the algorithm to find an unused ID drastically 93 * increases, killing performance. The default value of 4096 was chosen 94 * because it provides a good tradeoff between randomness and non-repetition, 95 * while taking performance into account. 96 * 97 * With L=4096, the queue will use 8K of memory. The bitstring always uses 98 * 8K of memory (2^16/8). This yields to around 7% ID collisions. No memory 99 * is allocated until the use of random ids is enabled. 100 */ 101 102#include <sys/param.h> 103#include <sys/time.h> 104#include <sys/kernel.h> 105#include <sys/random.h> 106#include <sys/protosw.h> 107#include <sys/bitstring.h> 108#include <kern/locks.h> 109#include <net/if_var.h> 110#include <netinet/in.h> 111#include <netinet/in_var.h> 112#include <netinet/ip_var.h> 113#include <dev/random/randomdev.h> 114 115/* 116 * Size of L (see comments above on the lower and upper limits.) 117 */ 118#define ARRAY_SIZE (4096) 119 120static uint16_t *id_array = NULL; 121static bitstr_t *id_bits = NULL; 122static uint32_t array_ptr = 0; 123static uint32_t random_id_statistics = 0; 124static uint64_t random_id_collisions = 0; 125static uint64_t random_id_total = 0; 126 127decl_lck_mtx_data(static, ipid_lock); 128static lck_attr_t *ipid_lock_attr; 129static lck_grp_t *ipid_lock_grp; 130static lck_grp_attr_t *ipid_lock_grp_attr; 131 132SYSCTL_UINT(_net_inet_ip, OID_AUTO, random_id_statistics, 133 CTLFLAG_RW | CTLFLAG_LOCKED, &random_id_statistics, 0, 134 "Enable IP ID statistics"); 135SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_collisions, 136 CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_collisions, 137 "Count of IP ID collisions"); 138SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_total, 139 CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_total, 140 "Count of IP IDs created"); 141 142/* 143 * Called once from ip_init(). 144 */ 145void 146ip_initid(void) 147{ 148 VERIFY(id_array == NULL); 149 VERIFY(id_bits == NULL); 150 151 _CASSERT(ARRAY_SIZE >= 512 && ARRAY_SIZE <= 32768); 152 153 ipid_lock_grp_attr = lck_grp_attr_alloc_init(); 154 ipid_lock_grp = lck_grp_alloc_init("ipid", ipid_lock_grp_attr); 155 ipid_lock_attr = lck_attr_alloc_init(); 156 lck_mtx_init(&ipid_lock, ipid_lock_grp, ipid_lock_attr); 157 158 id_array = (uint16_t *)_MALLOC(ARRAY_SIZE * sizeof (uint16_t), 159 M_TEMP, M_WAITOK | M_ZERO); 160 id_bits = (bitstr_t *)_MALLOC(bitstr_size(65536), M_TEMP, 161 M_WAITOK | M_ZERO); 162 if (id_array == NULL || id_bits == NULL) { 163 /* Just in case; neither or both. */ 164 if (id_array != NULL) { 165 _FREE(id_array, M_TEMP); 166 id_array = NULL; 167 } 168 if (id_bits != NULL) { 169 _FREE(id_bits, M_TEMP); 170 id_bits = NULL; 171 } 172 } 173} 174 175uint16_t 176ip_randomid(void) 177{ 178 uint16_t new_id; 179 180 /* 181 * If net.inet.ip.random_id is disabled, revert to incrementing ip_id. 182 * Given that we don't allow the size of the array to change, accessing 183 * id_array and id_bits prior to acquiring the lock below is safe. 184 */ 185 if (id_array == NULL || ip_use_randomid == 0) 186 return (htons(ip_id++)); 187 188 /* 189 * To avoid a conflict with the zeros that the array is initially 190 * filled with, we never hand out an id of zero. bit_test() below 191 * uses single memory access, therefore no lock is needed. 192 */ 193 new_id = 0; 194 do { 195 if (random_id_statistics && new_id != 0) 196 random_id_collisions++; 197 read_random(&new_id, sizeof (new_id)); 198 } while (bit_test(id_bits, new_id) || new_id == 0); 199 200 /* 201 * These require serialization to maintain correctness. 202 */ 203 lck_mtx_lock_spin(&ipid_lock); 204 bit_clear(id_bits, id_array[array_ptr]); 205 bit_set(id_bits, new_id); 206 id_array[array_ptr] = new_id; 207 if (++array_ptr == ARRAY_SIZE) 208 array_ptr = 0; 209 lck_mtx_unlock(&ipid_lock); 210 211 if (random_id_statistics) 212 random_id_total++; 213 214 return (new_id); 215} 216