X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/9bccf70c0258c7cac2dcb80011b2a964d884c552..3903760236c30e3b5ace7a4eefac3a269d68957c:/bsd/netinet/ip_id.c diff --git a/bsd/netinet/ip_id.c b/bsd/netinet/ip_id.c index 4e7e70980..4feff3e9c 100644 --- a/bsd/netinet/ip_id.c +++ b/bsd/netinet/ip_id.c @@ -1,27 +1,44 @@ -/* $OpenBSD: ip_id.c,v 1.2 1999/08/26 13:37:01 provos Exp $ */ - /* - * Copyright 1998 Niels Provos - * All rights reserved. + * Copyright (c) 2002-2013 Apple Inc. All rights reserved. + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ + * + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. + * + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. * - * Theo de Raadt came up with the idea of using - * such a mathematical system to generate more random (yet non-repeating) - * ids to solve the resolver/named problem. But Niels designed the - * actual system based on the constraints. + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, + * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ + */ + +/*- + * Copyright (c) 2008 Michael J. Silbersack. + * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. + * notice unmodified, this list of conditions, and the following + * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by Niels Provos. - * 4. The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES @@ -33,178 +50,166 @@ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * $FreeBSD: src/sys/netinet/ip_id.c,v 1.1.2.1 2001/07/19 06:37:26 kris Exp $ */ -/* - * seed = random 15bit - * n = prime, g0 = generator to n, - * j = random so that gcd(j,n-1) == 1 - * g = g0^j mod n will be a generator again. +/* + * IP ID generation is a fascinating topic. + * + * In order to avoid ID collisions during packet reassembly, common sense + * dictates that the period between reuse of IDs be as large as possible. + * This leads to the classic implementation of a system-wide counter, thereby + * ensuring that IDs repeat only once every 2^16 packets. + * + * Subsequent security researchers have pointed out that using a global + * counter makes ID values predictable. This predictability allows traffic + * analysis, idle scanning, and even packet injection in specific cases. + * These results suggest that IP IDs should be as random as possible. + * + * The "searchable queues" algorithm used in this IP ID implementation was + * proposed by Amit Klein. It is a compromise between the above two + * viewpoints that has provable behavior that can be tuned to the user's + * requirements. + * + * The basic concept is that we supplement a standard random number generator + * with a queue of the last L IDs that we have handed out to ensure that all + * IDs have a period of at least L. * - * X[0] = random seed. - * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator - * with a = 7^(even random) mod m, - * b = random with gcd(b,m) == 1 - * m = 31104 and a maximal period of m-1. + * To efficiently implement this idea, we keep two data structures: a + * circular array of IDs of size L and a bitstring of 65536 bits. * - * The transaction id is determined by: - * id[n] = seed xor (g^X[n] mod n) + * To start, we ask the RNG for a new ID. A quick index into the bitstring + * is used to determine if this is a recently used value. The process is + * repeated until a value is returned that is not in the bitstring. * - * Effectivly the id is restricted to the lower 15 bits, thus - * yielding two different cycles by toggling the msb on and off. - * This avoids reuse issues caused by reseeding. + * Having found a usable ID, we remove the ID stored at the current position + * in the queue from the bitstring and replace it with our new ID. Our new + * ID is then added to the bitstring and the queue pointer is incremented. + * + * The lower limit of 512 was chosen because there doesn't seem to be much + * point to having a smaller value. The upper limit of 32768 was chosen for + * two reasons. First, every step above 32768 decreases the entropy. Taken + * to an extreme, 65533 would offer 1 bit of entropy. Second, the number of + * attempts it takes the algorithm to find an unused ID drastically + * increases, killing performance. The default value of 4096 was chosen + * because it provides a good tradeoff between randomness and non-repetition, + * while taking performance into account. + * + * With L=4096, the queue will use 8K of memory. The bitstring always uses + * 8K of memory (2^16/8). This yields to around 7% ID collisions. No memory + * is allocated until the use of random ids is enabled. */ -#include "opt_random_ip_id.h" #include #include #include #include - -#if RANDOM_IP_ID -#define RU_OUT 180 /* Time after wich will be reseeded */ -#define RU_MAX 30000 /* Uniq cycle, avoid blackjack prediction */ -#define RU_GEN 2 /* Starting generator */ -#define RU_N 32749 /* RU_N-1 = 2*2*3*2729 */ -#define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */ -#define RU_M 31104 /* RU_M = 2^7*3^5 - don't change */ - -#define PFAC_N 3 -const static u_int16_t pfacts[PFAC_N] = { - 2, - 3, - 2729 -}; - -static u_int16_t ru_x; -static u_int16_t ru_seed, ru_seed2; -static u_int16_t ru_a, ru_b; -static u_int16_t ru_g; -static u_int16_t ru_counter = 0; -static u_int16_t ru_msb = 0; -static long ru_reseed; -static u_int32_t tmp; /* Storage for unused random */ - -static u_int16_t pmod __P((u_int16_t, u_int16_t, u_int16_t)); -static void ip_initid __P((void)); -u_int16_t ip_randomid __P((void)); +#include +#include +#include +#include +#include +#include +#include +#include /* - * Do a fast modular exponation, returned value will be in the range - * of 0 - (mod-1) + * Size of L (see comments above on the lower and upper limits.) */ +#define ARRAY_SIZE (4096) + +static uint16_t *id_array = NULL; +static bitstr_t *id_bits = NULL; +static uint32_t array_ptr = 0; +static uint32_t random_id_statistics = 0; +static uint64_t random_id_collisions = 0; +static uint64_t random_id_total = 0; + +decl_lck_mtx_data(static, ipid_lock); +static lck_attr_t *ipid_lock_attr; +static lck_grp_t *ipid_lock_grp; +static lck_grp_attr_t *ipid_lock_grp_attr; + +SYSCTL_UINT(_net_inet_ip, OID_AUTO, random_id_statistics, + CTLFLAG_RW | CTLFLAG_LOCKED, &random_id_statistics, 0, + "Enable IP ID statistics"); +SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_collisions, + CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_collisions, + "Count of IP ID collisions"); +SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_total, + CTLFLAG_RD | CTLFLAG_LOCKED, &random_id_total, + "Count of IP IDs created"); -#ifdef __STDC__ -static u_int16_t -pmod(u_int16_t gen, u_int16_t exp, u_int16_t mod) -#else -static u_int16_t -pmod(gen, exp, mod) - u_int16_t gen, exp, mod; -#endif -{ - u_int16_t s, t, u; - - s = 1; - t = gen; - u = exp; - - while (u) { - if (u & 1) - s = (s*t) % mod; - u >>= 1; - t = (t*t) % mod; - } - return (s); -} - -/* - * Initalizes the seed and chooses a suitable generator. Also toggles - * the msb flag. The msb flag is used to generate two distinct - * cycles of random numbers and thus avoiding reuse of ids. - * - * This function is called from id_randomid() when needed, an - * application does not have to worry about it. +/* + * Called once from ip_init(). */ -static void +void ip_initid(void) { - u_int16_t j, i; - int noprime = 1; - struct timeval time; - - getmicrotime(&time); - read_random((void *) &tmp, sizeof(tmp)); - ru_x = (tmp & 0xFFFF) % RU_M; - - /* 15 bits of random seed */ - ru_seed = (tmp >> 16) & 0x7FFF; - read_random((void *) &tmp, sizeof(tmp)); - ru_seed2 = tmp & 0x7FFF; - - read_random((void *) &tmp, sizeof(tmp)); - - /* Determine the LCG we use */ - ru_b = (tmp & 0xfffe) | 1; - ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M); - while (ru_b % 3 == 0) - ru_b += 2; - - read_random((void *) &tmp, sizeof(tmp)); - j = tmp % RU_N; - tmp = tmp >> 16; - - /* - * Do a fast gcd(j,RU_N-1), so we can find a j with - * gcd(j, RU_N-1) == 1, giving a new generator for - * RU_GEN^j mod RU_N - */ - - while (noprime) { - for (i=0; i=PFAC_N) - noprime = 0; - else - j = (j+1) % RU_N; + VERIFY(id_array == NULL); + VERIFY(id_bits == NULL); + + _CASSERT(ARRAY_SIZE >= 512 && ARRAY_SIZE <= 32768); + + ipid_lock_grp_attr = lck_grp_attr_alloc_init(); + ipid_lock_grp = lck_grp_alloc_init("ipid", ipid_lock_grp_attr); + ipid_lock_attr = lck_attr_alloc_init(); + lck_mtx_init(&ipid_lock, ipid_lock_grp, ipid_lock_attr); + + id_array = (uint16_t *)_MALLOC(ARRAY_SIZE * sizeof (uint16_t), + M_TEMP, M_WAITOK | M_ZERO); + id_bits = (bitstr_t *)_MALLOC(bitstr_size(65536), M_TEMP, + M_WAITOK | M_ZERO); + if (id_array == NULL || id_bits == NULL) { + /* Just in case; neither or both. */ + if (id_array != NULL) { + _FREE(id_array, M_TEMP); + id_array = NULL; + } + if (id_bits != NULL) { + _FREE(id_bits, M_TEMP); + id_bits = NULL; + } } - - ru_g = pmod(RU_GEN,j,RU_N); - ru_counter = 0; - - ru_reseed = time.tv_sec + RU_OUT; - ru_msb = ru_msb == 0x8000 ? 0 : 0x8000; } -u_int16_t +uint16_t ip_randomid(void) { - int i, n; - struct timeval time; - - getmicrotime(&time); - if (ru_counter >= RU_MAX || time.tv_sec > ru_reseed) - ip_initid(); - - if (!tmp) - read_random((void *) &tmp, sizeof(tmp)); - - /* Skip a random number of ids */ - n = tmp & 0x3; tmp = tmp >> 2; - if (ru_counter + n >= RU_MAX) - ip_initid(); - - for (i = 0; i <= n; i++) - /* Linear Congruential Generator */ - ru_x = (ru_a*ru_x + ru_b) % RU_M; + uint16_t new_id; - ru_counter += i; + /* + * If net.inet.ip.random_id is disabled, revert to incrementing ip_id. + * Given that we don't allow the size of the array to change, accessing + * id_array and id_bits prior to acquiring the lock below is safe. + */ + if (id_array == NULL || ip_use_randomid == 0) + return (htons(ip_id++)); - return (ru_seed ^ pmod(ru_g,ru_seed2 ^ ru_x,RU_N)) | ru_msb; + /* + * To avoid a conflict with the zeros that the array is initially + * filled with, we never hand out an id of zero. bit_test() below + * uses single memory access, therefore no lock is needed. + */ + new_id = 0; + do { + if (random_id_statistics && new_id != 0) + random_id_collisions++; + read_random(&new_id, sizeof (new_id)); + } while (bit_test(id_bits, new_id) || new_id == 0); + + /* + * These require serialization to maintain correctness. + */ + lck_mtx_lock_spin(&ipid_lock); + bit_clear(id_bits, id_array[array_ptr]); + bit_set(id_bits, new_id); + id_array[array_ptr] = new_id; + if (++array_ptr == ARRAY_SIZE) + array_ptr = 0; + lck_mtx_unlock(&ipid_lock); + + if (random_id_statistics) + random_id_total++; + + return (new_id); } - -#endif /* RANDOM_IP_ID */