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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
/*-
* 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.
*/
#include <sys/cdefs.h>
__FBSDID("$FreeBSD$");
/*
* 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 8192 was chosen
* because it provides a good tradeoff between randomness and non-repetition.
*
* With L=8192, the queue will use 16K of memory. The bitstring always
* uses 8K of memory. No memory is allocated until the use of random ids is
* enabled.
*/
#include <sys/types.h>
#include <sys/malloc.h>
#include <sys/param.h>
#include <sys/time.h>
#include <sys/kernel.h>
#include <sys/libkern.h>
#include <sys/lock.h>
#include <sys/mutex.h>
#include <sys/random.h>
#include <sys/systm.h>
#include <sys/sysctl.h>
#include <netinet/in.h>
#include <netinet/ip_var.h>
#include <sys/bitstring.h>
static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state");
static u_int16_t *id_array = NULL;
static bitstr_t *id_bits = NULL;
static int array_ptr = 0;
static int array_size = 8192;
static int random_id_collisions = 0;
static int random_id_total = 0;
static struct mtx ip_id_mtx;
static void ip_initid(void);
static int sysctl_ip_id_change(SYSCTL_HANDLER_ARGS);
MTX_SYSINIT(ip_id_mtx, &ip_id_mtx, "ip_id_mtx", MTX_DEF);
SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, CTLTYPE_INT|CTLFLAG_RW,
&array_size, 0, sysctl_ip_id_change, "IU", "IP ID Array size");
SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD,
&random_id_collisions, 0, "Count of IP ID collisions");
SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD,
&random_id_total, 0, "Count of IP IDs created");
static int
sysctl_ip_id_change(SYSCTL_HANDLER_ARGS)
{
int error, new;
new = array_size;
error = sysctl_handle_int(oidp, &new, 0, req);
if (error == 0 && req->newptr) {
if (new >= 512 && new <= 32768) {
mtx_lock(&ip_id_mtx);
array_size = new;
ip_initid();
mtx_unlock(&ip_id_mtx);
} else
error = EINVAL;
}
return (error);
}
/*
* ip_initid() runs with a mutex held and may execute in a network context.
* As a result, it uses M_NOWAIT. Ideally, we would always do this
* allocation from the sysctl contact and have it be an invariant that if
* this random ID allocation mode is selected, the buffers are present. This
* would also avoid potential network context failures of IP ID generation.
*/
static void
ip_initid(void)
{
mtx_assert(&ip_id_mtx, MA_OWNED);
if (id_array != NULL) {
free(id_array, M_IPID);
free(id_bits, M_IPID);
}
random_id_collisions = 0;
random_id_total = 0;
array_ptr = 0;
id_array = (u_int16_t *) malloc(array_size * sizeof(u_int16_t),
M_IPID, M_NOWAIT | M_ZERO);
id_bits = (bitstr_t *) malloc(bitstr_size(65536), M_IPID,
M_NOWAIT | M_ZERO);
if (id_array == NULL || id_bits == NULL) {
/* Neither or both. */
if (id_array != NULL) {
free(id_array, M_IPID);
id_array = NULL;
}
if (id_bits != NULL) {
free(id_bits, M_IPID);
id_bits = NULL;
}
}
}
u_int16_t
ip_randomid(void)
{
u_int16_t new_id;
mtx_lock(&ip_id_mtx);
if (id_array == NULL)
ip_initid();
/*
* Fail gracefully; return a fixed id if memory allocation failed;
* ideally we wouldn't do allocation in this context in order to
* avoid the possibility of this failure mode.
*/
if (id_array == NULL) {
mtx_unlock(&ip_id_mtx);
return (1);
}
/*
* To avoid a conflict with the zeros that the array is initially
* filled with, we never hand out an id of zero.
*/
new_id = 0;
do {
if (new_id != 0)
random_id_collisions++;
arc4rand(&new_id, sizeof(new_id), 0);
} while (bit_test(id_bits, new_id) || new_id == 0);
bit_clear(id_bits, id_array[array_ptr]);
bit_set(id_bits, new_id);
id_array[array_ptr] = new_id;
array_ptr++;
if (array_ptr == array_size)
array_ptr = 0;
random_id_total++;
mtx_unlock(&ip_id_mtx);
return (new_id);
}
|
