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