summaryrefslogtreecommitdiff
path: root/sys/netinet/ip_id.c
blob: a8aef8c299b5c6e10a8e82c1bfc8587b13019c5c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/*	$OpenBSD: ip_id.c,v 1.16 2008/02/29 03:37:26 deraadt Exp $ */

/*
 * Copyright (c) 2008 Theo de Raadt, Ryan McBride
 * 
 * Slightly different algorithm from the one designed by
 * Matthew Dillon <dillon@backplane.com> for The DragonFly Project
 * 
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * Random ip sequence number generator.  Use the system PRNG to shuffle
 * the 65536 entry ID space.  We reshuffle the ID we pick out of the array
 * into the previous 32767 cells, providing an guarantee that an ID will not
 * be reused for at least 32768 calls.
 */
#include <sys/param.h>
#include <dev/rndvar.h>

static u_int16_t ip_shuffle[65536];
static int isindex = 0;

u_int16_t ip_randomid(void);

/*
 * Return a random IP id.  Shuffle the new value we get into the previous half
 * of the ip_shuffle ring (-32767 or swap with ourself), to avoid duplicates
 * occuring too quickly but also still be random.
 *
 * 0 is a special IP ID -- don't return it.
 */
u_int16_t
ip_randomid(void)
{
	static int ipid_initialized;
	u_int16_t si, r;
	int i, i2;

	if (!ipid_initialized) {
		ipid_initialized = 1;

		/*
		 * Initialize using a Durstenfeld shuffle. Even if our PRNG
		 * is imperfect at boot time, we have deferred doing this until
		 * the first packet being sent and now must generate an ID.
		 */
		for (i = 0; i < sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); ++i)
			ip_shuffle[i] = i;
		for (i = sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); --i; ) {
			/* disregard the modulo bias because it is small */
			i2 = arc4random() % (i + 1);
			r = ip_shuffle[i];
			ip_shuffle[i] = ip_shuffle[i2];
			ip_shuffle[i2] = r;
		}
	}

	do {
		arc4random_bytes(&si, sizeof(si));
		i = isindex & 0xFFFF;
		i2 = (isindex - (si & 0x7FFF)) & 0xFFFF;
		r = ip_shuffle[i];
		ip_shuffle[i] = ip_shuffle[i2];
		ip_shuffle[i2] = r;
		isindex++;
	} while (r == 0);

	return (r);
}