FreeBSD/Linux Kernel Cross Reference
sys/netinet/ip_id.c
1 /* $NetBSD: ip_id.c,v 1.11 2006/08/30 18:54:19 christos 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.11 2006/08/30 18:54:19 christos Exp $");
56
57 #include "opt_inet.h"
58
59 #include <sys/param.h>
60 #include <lib/libkern/libkern.h>
61
62 #include <net/if.h>
63 #include <netinet/in.h>
64 #include <netinet/ip_var.h>
65
66 #define RU_OUT 180 /* Time after wich will be reseeded */
67 #define RU_MAX 30000 /* Uniq cycle, avoid blackjack prediction */
68 #define RU_GEN 2 /* Starting generator */
69 #define RU_N 32749 /* RU_N-1 = 2*2*3*2729 */
70 #define RU_AGEN 7 /* determine ru_a as RU_AGEN^(2*rand) */
71 #define RU_M 31104 /* RU_M = 2^7*3^5 - don't change */
72
73 #define PFAC_N 3
74 static const u_int16_t pfacts[PFAC_N] = {
75 2,
76 3,
77 2729
78 };
79
80 static u_int16_t ru_x;
81 static u_int16_t ru_seed, ru_seed2;
82 static u_int16_t ru_a, ru_b;
83 static u_int16_t ru_g;
84 static u_int16_t ru_counter = 0;
85 static u_int16_t ru_msb = 0;
86 static long ru_reseed;
87 static u_int32_t tmp; /* Storage for unused random */
88
89 static u_int16_t pmod(u_int16_t, u_int16_t, u_int16_t);
90 static void ip_initid(void);
91
92 /*
93 * Do a fast modular exponation, returned value will be in the range
94 * of 0 - (mod-1)
95 */
96
97 static u_int16_t
98 pmod(u_int16_t gen, u_int16_t expo, u_int16_t mod)
99 {
100 u_int16_t s, t, u;
101
102 s = 1;
103 t = gen;
104 u = expo;
105
106 while (u) {
107 if (u & 1)
108 s = (s * t) % mod;
109 u >>= 1;
110 t = (t * t) % mod;
111 }
112 return (s);
113 }
114
115 /*
116 * Initalizes the seed and chooses a suitable generator. Also toggles
117 * the msb flag. The msb flag is used to generate two distinct
118 * cycles of random numbers and thus avoiding reuse of ids.
119 *
120 * This function is called from id_randomid() when needed, an
121 * application does not have to worry about it.
122 */
123 static void
124 ip_initid(void)
125 {
126 u_int16_t j, i;
127 int noprime = 1;
128
129 ru_x = ((tmp = arc4random()) & 0xFFFF) % RU_M;
130
131 /* 15 bits of random seed */
132 ru_seed = (tmp >> 16) & 0x7FFF;
133 ru_seed2 = arc4random() & 0x7FFF;
134
135 /* Determine the LCG we use */
136 ru_b = ((tmp = arc4random()) & 0xfffe) | 1;
137 ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
138 while (ru_b % 3 == 0)
139 ru_b += 2;
140
141 j = (tmp = arc4random()) % RU_N;
142 tmp = tmp >> 16;
143
144 /*
145 * Do a fast gcd(j,RU_N-1), so we can find a j with
146 * gcd(j, RU_N-1) == 1, giving a new generator for
147 * RU_GEN^j mod RU_N
148 */
149
150 while (noprime) {
151 for (i = 0; i < PFAC_N; i++)
152 if (j % pfacts[i] == 0)
153 break;
154
155 if (i >= PFAC_N)
156 noprime = 0;
157 else
158 j = (j + 1) % RU_N;
159 }
160
161 ru_g = pmod(RU_GEN, j, RU_N);
162 ru_counter = 0;
163
164 ru_reseed = time_second + RU_OUT;
165 ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
166 }
167
168 u_int16_t
169 ip_randomid(void)
170 {
171 int i, n;
172
173 if (ru_counter >= RU_MAX || time_second > ru_reseed)
174 ip_initid();
175
176 #if 0
177 if (!tmp)
178 tmp = arc4random();
179
180 /* Skip a random number of ids */
181 n = tmp & 0x3; tmp = tmp >> 2;
182 if (ru_counter + n >= RU_MAX)
183 ip_initid();
184 #else
185 n = 0;
186 #endif
187
188 for (i = 0; i <= n; i++)
189 /* Linear Congruential Generator */
190 ru_x = (ru_a * ru_x + ru_b) % RU_M;
191
192 ru_counter += i;
193
194 return (ru_seed ^ pmod(ru_g, ru_seed2 + ru_x, RU_N)) | ru_msb;
195 }
Cache object: f168d7d9571f491e0e1071644d3c8245
|