FreeBSD/Linux Kernel Cross Reference
sys/netinet/ip_id.c
1
2 /*-
3 * Copyright (c) 2008 Michael J. Silbersack.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice unmodified, this list of conditions, and the following
11 * disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include <sys/cdefs.h>
29 __FBSDID("$FreeBSD: src/sys/netinet/ip_id.c,v 1.12 2008/12/02 21:37:28 bz Exp $");
30
31 /*
32 * IP ID generation is a fascinating topic.
33 *
34 * In order to avoid ID collisions during packet reassembly, common sense
35 * dictates that the period between reuse of IDs be as large as possible.
36 * This leads to the classic implementation of a system-wide counter, thereby
37 * ensuring that IDs repeat only once every 2^16 packets.
38 *
39 * Subsequent security researchers have pointed out that using a global
40 * counter makes ID values predictable. This predictability allows traffic
41 * analysis, idle scanning, and even packet injection in specific cases.
42 * These results suggest that IP IDs should be as random as possible.
43 *
44 * The "searchable queues" algorithm used in this IP ID implementation was
45 * proposed by Amit Klein. It is a compromise between the above two
46 * viewpoints that has provable behavior that can be tuned to the user's
47 * requirements.
48 *
49 * The basic concept is that we supplement a standard random number generator
50 * with a queue of the last L IDs that we have handed out to ensure that all
51 * IDs have a period of at least L.
52 *
53 * To efficiently implement this idea, we keep two data structures: a
54 * circular array of IDs of size L and a bitstring of 65536 bits.
55 *
56 * To start, we ask the RNG for a new ID. A quick index into the bitstring
57 * is used to determine if this is a recently used value. The process is
58 * repeated until a value is returned that is not in the bitstring.
59 *
60 * Having found a usable ID, we remove the ID stored at the current position
61 * in the queue from the bitstring and replace it with our new ID. Our new
62 * ID is then added to the bitstring and the queue pointer is incremented.
63 *
64 * The lower limit of 512 was chosen because there doesn't seem to be much
65 * point to having a smaller value. The upper limit of 32768 was chosen for
66 * two reasons. First, every step above 32768 decreases the entropy. Taken
67 * to an extreme, 65533 would offer 1 bit of entropy. Second, the number of
68 * attempts it takes the algorithm to find an unused ID drastically
69 * increases, killing performance. The default value of 8192 was chosen
70 * because it provides a good tradeoff between randomness and non-repetition.
71 *
72 * With L=8192, the queue will use 16K of memory. The bitstring always
73 * uses 8K of memory. No memory is allocated until the use of random ids is
74 * enabled.
75 */
76
77 #include <sys/types.h>
78 #include <sys/malloc.h>
79 #include <sys/param.h>
80 #include <sys/time.h>
81 #include <sys/kernel.h>
82 #include <sys/libkern.h>
83 #include <sys/lock.h>
84 #include <sys/mutex.h>
85 #include <sys/random.h>
86 #include <sys/systm.h>
87 #include <sys/sysctl.h>
88 #include <netinet/in.h>
89 #include <netinet/ip_var.h>
90 #include <sys/bitstring.h>
91
92 static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state");
93
94 static u_int16_t *id_array = NULL;
95 static bitstr_t *id_bits = NULL;
96 static int array_ptr = 0;
97 static int array_size = 8192;
98 static int random_id_collisions = 0;
99 static int random_id_total = 0;
100 static struct mtx ip_id_mtx;
101
102 static void ip_initid(void);
103 static int sysctl_ip_id_change(SYSCTL_HANDLER_ARGS);
104
105 MTX_SYSINIT(ip_id_mtx, &ip_id_mtx, "ip_id_mtx", MTX_DEF);
106
107 SYSCTL_DECL(_net_inet_ip);
108 SYSCTL_PROC(_net_inet_ip, OID_AUTO, random_id_period, CTLTYPE_INT|CTLFLAG_RW,
109 &array_size, 0, sysctl_ip_id_change, "IU", "IP ID Array size");
110 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD,
111 &random_id_collisions, 0, "Count of IP ID collisions");
112 SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD,
113 &random_id_total, 0, "Count of IP IDs created");
114
115 static int
116 sysctl_ip_id_change(SYSCTL_HANDLER_ARGS)
117 {
118 int error, new;
119
120 new = array_size;
121 error = sysctl_handle_int(oidp, &new, 0, req);
122 if (error == 0 && req->newptr) {
123 if (new >= 512 && new <= 32768) {
124 mtx_lock(&ip_id_mtx);
125 array_size = new;
126 ip_initid();
127 mtx_unlock(&ip_id_mtx);
128 } else
129 error = EINVAL;
130 }
131 return (error);
132 }
133
134 /*
135 * ip_initid() runs with a mutex held and may execute in a network context.
136 * As a result, it uses M_NOWAIT. Ideally, we would always do this
137 * allocation from the sysctl contact and have it be an invariant that if
138 * this random ID allocation mode is selected, the buffers are present. This
139 * would also avoid potential network context failures of IP ID generation.
140 */
141 static void
142 ip_initid(void)
143 {
144
145 mtx_assert(&ip_id_mtx, MA_OWNED);
146
147 if (id_array != NULL) {
148 free(id_array, M_IPID);
149 free(id_bits, M_IPID);
150 }
151 random_id_collisions = 0;
152 random_id_total = 0;
153 array_ptr = 0;
154 id_array = (u_int16_t *) malloc(array_size * sizeof(u_int16_t),
155 M_IPID, M_NOWAIT | M_ZERO);
156 id_bits = (bitstr_t *) malloc(bitstr_size(65536), M_IPID,
157 M_NOWAIT | M_ZERO);
158 if (id_array == NULL || id_bits == NULL) {
159 /* Neither or both. */
160 if (id_array != NULL) {
161 free(id_array, M_IPID);
162 id_array = NULL;
163 }
164 if (id_bits != NULL) {
165 free(id_bits, M_IPID);
166 id_bits = NULL;
167 }
168 }
169 }
170
171 u_int16_t
172 ip_randomid(void)
173 {
174 u_int16_t new_id;
175
176 mtx_lock(&ip_id_mtx);
177 if (id_array == NULL)
178 ip_initid();
179
180 /*
181 * Fail gracefully; return a fixed id if memory allocation failed;
182 * ideally we wouldn't do allocation in this context in order to
183 * avoid the possibility of this failure mode.
184 */
185 if (id_array == NULL) {
186 mtx_unlock(&ip_id_mtx);
187 return (1);
188 }
189
190 /*
191 * To avoid a conflict with the zeros that the array is initially
192 * filled with, we never hand out an id of zero.
193 */
194 new_id = 0;
195 do {
196 if (new_id != 0)
197 random_id_collisions++;
198 arc4rand(&new_id, sizeof(new_id), 0);
199 } while (bit_test(id_bits, new_id) || new_id == 0);
200 bit_clear(id_bits, id_array[array_ptr]);
201 bit_set(id_bits, new_id);
202 id_array[array_ptr] = new_id;
203 array_ptr++;
204 if (array_ptr == array_size)
205 array_ptr = 0;
206 random_id_total++;
207 mtx_unlock(&ip_id_mtx);
208 return (new_id);
209 }
210
|