ip_id.c (4b79449e2fb67cb37c4c9f46d31791893a39ddd8) ip_id.c (64dddc18727af4db4a6047ff86291d981f6e9042)
1/* $OpenBSD: ip_id.c,v 1.2 1999/08/26 13:37:01 provos Exp $ */
1
2
2/*-
3 * Copyright (c) 2008 Michael J. Silbersack.
3/*
4 * Copyright 1998 Niels Provos <provos@citi.umich.edu>
4 * All rights reserved.
5 *
5 * All rights reserved.
6 *
7 * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
8 * such a mathematical system to generate more random (yet non-repeating)
9 * ids to solve the resolver/named problem. But Niels designed the
10 * actual system based on the constraints.
11 *
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
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
10 * notice unmodified, this list of conditions, and the following
11 * disclaimer.
16 * notice, this list of conditions and the following 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.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 * 3. All advertising materials mentioning features or use of this software
21 * must display the following acknowledgement:
22 * This product includes software developed by Niels Provos.
23 * 4. The name of the author may not be used to endorse or promote products
24 * derived from this software without specific prior written permission.
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.
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
27 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
28 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
29 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
31 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
33 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
35 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 *
37 * $FreeBSD$
26 */
27
38 */
39
28#include <sys/cdefs.h>
29__FBSDID("$FreeBSD$");
30
31/*
32 * IP ID generation is a fascinating topic.
40/*
41 * seed = random 15bit
42 * n = prime, g0 = generator to n,
43 * j = random so that gcd(j,n-1) == 1
44 * g = g0^j mod n will be a generator again.
33 *
45 *
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.
46 * X[0] = random seed.
47 * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
48 * with a = 7^(even random) mod m,
49 * b = random with gcd(b,m) == 1
50 * m = 31104 and a maximal period of m-1.
38 *
51 *
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.
52 * The transaction id is determined by:
53 * id[n] = seed xor (g^X[n] mod n)
43 *
54 *
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.
55 * Effectivly the id is restricted to the lower 15 bits, thus
56 * yielding two different cycles by toggling the msb on and off.
57 * This avoids reuse issues caused by reseeding.
75 */
76
58 */
59
77#include <sys/types.h>
78#include <sys/malloc.h>
60#include "opt_random_ip_id.h"
79#include <sys/param.h>
80#include <sys/time.h>
81#include <sys/kernel.h>
61#include <sys/param.h>
62#include <sys/time.h>
63#include <sys/kernel.h>
82#include <sys/libkern.h>
83#include <sys/lock.h>
84#include <sys/mutex.h>
85#include <sys/random.h>
64#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
65
92static MALLOC_DEFINE(M_IPID, "ipid", "randomized ip id state");
66#ifdef RANDOM_IP_ID
67#define RU_OUT 180 /* Time after wich will be reseeded */
68#define RU_MAX 30000 /* Uniq cycle, avoid blackjack prediction */
69#define RU_GEN 2 /* Starting generator */
70#define RU_N 32749 /* RU_N-1 = 2*2*3*2729 */
71#define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */
72#define RU_M 31104 /* RU_M = 2^7*3^5 - don't change */
93
73
94static u_int16_t *id_array = NULL;
95static bitstr_t *id_bits = NULL;
96static int array_ptr = 0;
97static int array_size = 8192;
98static int random_id_collisions = 0;
99static int random_id_total = 0;
100static struct mtx ip_id_mtx;
74#define PFAC_N 3
75const static u_int16_t pfacts[PFAC_N] = {
76 2,
77 3,
78 2729
79};
101
80
102static void ip_initid(void);
103static int sysctl_ip_id_change(SYSCTL_HANDLER_ARGS);
81static u_int16_t ru_x;
82static u_int16_t ru_seed, ru_seed2;
83static u_int16_t ru_a, ru_b;
84static u_int16_t ru_g;
85static u_int16_t ru_counter = 0;
86static u_int16_t ru_msb = 0;
87static long ru_reseed;
88static u_int32_t tmp; /* Storage for unused random */
104
89
105MTX_SYSINIT(ip_id_mtx, &ip_id_mtx, "ip_id_mtx", MTX_DEF);
90static u_int16_t pmod __P((u_int16_t, u_int16_t, u_int16_t));
91static void ip_initid __P((void));
92u_int16_t ip_randomid __P((void));
106
93
107SYSCTL_DECL(_net_inet_ip);
108SYSCTL_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");
110SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_collisions, CTLFLAG_RD,
111 &random_id_collisions, 0, "Count of IP ID collisions");
112SYSCTL_INT(_net_inet_ip, OID_AUTO, random_id_total, CTLFLAG_RD,
113 &random_id_total, 0, "Count of IP IDs created");
94/*
95 * Do a fast modular exponation, returned value will be in the range
96 * of 0 - (mod-1)
97 */
114
98
115static int
116sysctl_ip_id_change(SYSCTL_HANDLER_ARGS)
99#ifdef __STDC__
100static u_int16_t
101pmod(u_int16_t gen, u_int16_t exp, u_int16_t mod)
102#else
103static u_int16_t
104pmod(gen, exp, mod)
105 u_int16_t gen, exp, mod;
106#endif
117{
107{
118 int error, new;
108 u_int16_t s, t, u;
119
109
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;
110 s = 1;
111 t = gen;
112 u = exp;
113
114 while (u) {
115 if (u & 1)
116 s = (s*t) % mod;
117 u >>= 1;
118 t = (t*t) % mod;
130 }
119 }
131 return (error);
120 return (s);
132}
133
121}
122
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.
123/*
124 * Initalizes the seed and chooses a suitable generator. Also toggles
125 * the msb flag. The msb flag is used to generate two distinct
126 * cycles of random numbers and thus avoiding reuse of ids.
127 *
128 * This function is called from id_randomid() when needed, an
129 * application does not have to worry about it.
140 */
130 */
141static void
131static void
142ip_initid(void)
143{
132ip_initid(void)
133{
134 u_int16_t j, i;
135 int noprime = 1;
136 struct timeval time;
144
137
145 mtx_assert(&ip_id_mtx, MA_OWNED);
138 getmicrotime(&time);
139 read_random((void *) &tmp, sizeof(tmp));
140 ru_x = (tmp & 0xFFFF) % RU_M;
146
141
147 if (id_array != NULL) {
148 free(id_array, M_IPID);
149 free(id_bits, M_IPID);
142 /* 15 bits of random seed */
143 ru_seed = (tmp >> 16) & 0x7FFF;
144 read_random((void *) &tmp, sizeof(tmp));
145 ru_seed2 = tmp & 0x7FFF;
146
147 read_random((void *) &tmp, sizeof(tmp));
148
149 /* Determine the LCG we use */
150 ru_b = (tmp & 0xfffe) | 1;
151 ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
152 while (ru_b % 3 == 0)
153 ru_b += 2;
154
155 read_random((void *) &tmp, sizeof(tmp));
156 j = tmp % RU_N;
157 tmp = tmp >> 16;
158
159 /*
160 * Do a fast gcd(j,RU_N-1), so we can find a j with
161 * gcd(j, RU_N-1) == 1, giving a new generator for
162 * RU_GEN^j mod RU_N
163 */
164
165 while (noprime) {
166 for (i=0; i<PFAC_N; i++)
167 if (j%pfacts[i] == 0)
168 break;
169
170 if (i>=PFAC_N)
171 noprime = 0;
172 else
173 j = (j+1) % RU_N;
150 }
174 }
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 }
175
176 ru_g = pmod(RU_GEN,j,RU_N);
177 ru_counter = 0;
178
179 ru_reseed = time.tv_sec + RU_OUT;
180 ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
169}
170
171u_int16_t
172ip_randomid(void)
173{
181}
182
183u_int16_t
184ip_randomid(void)
185{
174 u_int16_t new_id;
186 int i, n;
187 struct timeval time;
175
188
176 mtx_lock(&ip_id_mtx);
177 if (id_array == NULL)
189 getmicrotime(&time);
190 if (ru_counter >= RU_MAX || time.tv_sec > ru_reseed)
178 ip_initid();
179
191 ip_initid();
192
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 }
193 if (!tmp)
194 read_random((void *) &tmp, sizeof(tmp));
189
195
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);
196 /* Skip a random number of ids */
197 n = tmp & 0x3; tmp = tmp >> 2;
198 if (ru_counter + n >= RU_MAX)
199 ip_initid();
200
201 for (i = 0; i <= n; i++)
202 /* Linear Congruential Generator */
203 ru_x = (ru_a*ru_x + ru_b) % RU_M;
204
205 ru_counter += i;
206
207 return (ru_seed ^ pmod(ru_g,ru_seed2 ^ ru_x,RU_N)) | ru_msb;
209}
208}
209
210#endif /* RANDOM_IP_ID */