[apple/xnu.git] / bsd / netinet / ip_id.c

/*
 * 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.
 *
 * 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 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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * 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.
 */

/*
 * 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.
 *
 * To efficiently implement this idea, we keep two data structures: a
 * circular array of IDs of size L and a bitstring of 65536 bits.
 *
 * 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.
 *
 * 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 <sys/param.h>
#include <sys/time.h>
#include <sys/kernel.h>
#include <sys/random.h>
#include <sys/protosw.h>
#include <sys/bitstring.h>
#include <kern/locks.h>
#include <net/if_var.h>
#include <netinet/in.h>
#include <netinet/in_var.h>
#include <netinet/ip_var.h>
#include <dev/random/randomdev.h>

/*
 * 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");

/*
 * Called once from ip_init().
 */
void
ip_initid(void)
{
	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;
		}
	}
}

uint16_t
ip_randomid(void)
{
	uint16_t new_id;

	/*
	 * 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++));

	/*
	 * 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);
}
Commit	Line	Data
9bccf70c	1	/*
39236c6e A	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.
9bccf70c	17	*
39236c6e A	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.
9bccf70c A	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
39236c6e A	37	* notice unmodified, this list of conditions, and the following
39236c6e A	38	* disclaimer.
9bccf70c A	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.
9bccf70c A	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.
9bccf70c A	53	*/
9bccf70c A	54
39236c6e A	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.
9bccf70c	76	*
39236c6e A	77	* To efficiently implement this idea, we keep two data structures: a
39236c6e A	78	* circular array of IDs of size L and a bitstring of 65536 bits.
9bccf70c	79	*
39236c6e A	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.
9bccf70c	83	*
39236c6e A	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.
9bccf70c A	100	*/
9bccf70c A	101
9bccf70c A	102	#include <sys/param.h>
	103	#include <sys/time.h>
	104	#include <sys/kernel.h>
	105	#include <sys/random.h>
39236c6e A	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>
9bccf70c	114
9bccf70c	115	/*
39236c6e	116	* Size of L (see comments above on the lower and upper limits.)
9bccf70c	117	*/
39236c6e A	118	#define ARRAY_SIZE (4096)
	119
	120	static uint16_t *id_array = NULL;
	121	static bitstr_t *id_bits = NULL;
	122	static uint32_t array_ptr = 0;
	123	static uint32_t random_id_statistics = 0;
	124	static uint64_t random_id_collisions = 0;
	125	static uint64_t random_id_total = 0;
	126
	127	decl_lck_mtx_data(static, ipid_lock);
	128	static lck_attr_t *ipid_lock_attr;
	129	static lck_grp_t *ipid_lock_grp;
	130	static lck_grp_attr_t *ipid_lock_grp_attr;
	131
	132	SYSCTL_UINT(_net_inet_ip, OID_AUTO, random_id_statistics,
	133	CTLFLAG_RW \| CTLFLAG_LOCKED, &random_id_statistics, 0,
	134	"Enable IP ID statistics");
	135	SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_collisions,
	136	CTLFLAG_RD \| CTLFLAG_LOCKED, &random_id_collisions,
	137	"Count of IP ID collisions");
	138	SYSCTL_QUAD(_net_inet_ip, OID_AUTO, random_id_total,
	139	CTLFLAG_RD \| CTLFLAG_LOCKED, &random_id_total,
	140	"Count of IP IDs created");
9bccf70c	141
39236c6e A	142	/*
39236c6e A	143	* Called once from ip_init().
9bccf70c	144	*/
39236c6e	145	void
9bccf70c A	146	ip_initid(void)
9bccf70c A	147	{
39236c6e A	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	}
9bccf70c	172	}
9bccf70c A	173	}
9bccf70c A	174
39236c6e	175	uint16_t
9bccf70c A	176	ip_randomid(void)
9bccf70c A	177	{
39236c6e	178	uint16_t new_id;
2d21ac55	179
39236c6e A	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.
2d21ac55	184	*/
39236c6e A	185	if (id_array == NULL \|\| ip_use_randomid == 0)
39236c6e A	186	return (htons(ip_id++));
2d21ac55	187
39236c6e A	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);
9bccf70c	215	}