1 | /* |
2 | * Copyright (c) 2009-2013 Apple Inc. All rights reserved. |
3 | * |
4 | * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ |
5 | * |
6 | * This file contains Original Code and/or Modifications of Original Code |
7 | * as defined in and that are subject to the Apple Public Source License |
8 | * Version 2.0 (the 'License'). You may not use this file except in |
9 | * compliance with the License. The rights granted to you under the License |
10 | * may not be used to create, or enable the creation or redistribution of, |
11 | * unlawful or unlicensed copies of an Apple operating system, or to |
12 | * circumvent, violate, or enable the circumvention or violation of, any |
13 | * terms of an Apple operating system software license agreement. |
14 | * |
15 | * Please obtain a copy of the License at |
16 | * http://www.opensource.apple.com/apsl/ and read it before using this file. |
17 | * |
18 | * The Original Code and all software distributed under the License are |
19 | * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER |
20 | * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, |
21 | * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, |
22 | * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. |
23 | * Please see the License for the specific language governing rights and |
24 | * limitations under the License. |
25 | * |
26 | * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ |
27 | */ |
28 | |
29 | /*- |
30 | * Copyright (C) 2003 WIDE Project. |
31 | * All rights reserved. |
32 | * |
33 | * Redistribution and use in source and binary forms, with or without |
34 | * modification, are permitted provided that the following conditions |
35 | * are met: |
36 | * 1. Redistributions of source code must retain the above copyright |
37 | * notice, this list of conditions and the following disclaimer. |
38 | * 2. Redistributions in binary form must reproduce the above copyright |
39 | * notice, this list of conditions and the following disclaimer in the |
40 | * documentation and/or other materials provided with the distribution. |
41 | * 3. Neither the name of the project nor the names of its contributors |
42 | * may be used to endorse or promote products derived from this software |
43 | * without specific prior written permission. |
44 | * |
45 | * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND |
46 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
47 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
48 | * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE |
49 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
50 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
51 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
52 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
53 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
54 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
55 | * SUCH DAMAGE. |
56 | */ |
57 | |
58 | /*- |
59 | * Copyright 1998 Niels Provos <provos@citi.umich.edu> |
60 | * All rights reserved. |
61 | * |
62 | * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using |
63 | * such a mathematical system to generate more random (yet non-repeating) |
64 | * ids to solve the resolver/named problem. But Niels designed the |
65 | * actual system based on the constraints. |
66 | * |
67 | * Redistribution and use in source and binary forms, with or without |
68 | * modification, are permitted provided that the following conditions |
69 | * are met: |
70 | * 1. Redistributions of source code must retain the above copyright |
71 | * notice, this list of conditions and the following disclaimer. |
72 | * 2. Redistributions in binary form must reproduce the above copyright |
73 | * notice, this list of conditions and the following disclaimer in the |
74 | * documentation and/or other materials provided with the distribution. |
75 | * 3. All advertising materials mentioning features or use of this software |
76 | * must display the following acknowledgement: |
77 | * This product includes software developed by Niels Provos. |
78 | * 4. The name of the author may not be used to endorse or promote products |
79 | * derived from this software without specific prior written permission. |
80 | * |
81 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
82 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
83 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
84 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
85 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
86 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
87 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
88 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
89 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
90 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
91 | */ |
92 | |
93 | #include <sys/cdefs.h> |
94 | |
95 | /* |
96 | * seed = random (bits - 1) bit |
97 | * n = prime, g0 = generator to n, |
98 | * j = random so that gcd(j,n-1) == 1 |
99 | * g = g0^j mod n will be a generator again. |
100 | * |
101 | * X[0] = random seed. |
102 | * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator |
103 | * with a = 7^(even random) mod m, |
104 | * b = random with gcd(b,m) == 1 |
105 | * m = constant and a maximal period of m-1. |
106 | * |
107 | * The transaction id is determined by: |
108 | * id[n] = seed xor (g^X[n] mod n) |
109 | * |
110 | * Effectivly the id is restricted to the lower (bits - 1) bits, thus |
111 | * yielding two different cycles by toggling the msb on and off. |
112 | * This avoids reuse issues caused by reseeding. |
113 | */ |
114 | |
115 | #include <sys/types.h> |
116 | #include <sys/socket.h> |
117 | #include <sys/param.h> |
118 | #include <sys/time.h> |
119 | #include <sys/kernel.h> |
120 | #include <sys/random.h> |
121 | #include <sys/protosw.h> |
122 | #include <libkern/libkern.h> |
123 | #include <dev/random/randomdev.h> |
124 | |
125 | #include <net/if.h> |
126 | #include <net/route.h> |
127 | #include <netinet/in.h> |
128 | #include <netinet/ip6.h> |
129 | #include <netinet6/ip6_var.h> |
130 | |
131 | struct randomtab { |
132 | const int ru_bits; /* resulting bits */ |
133 | const long ru_out; /* Time after wich will be reseeded */ |
134 | const u_int32_t ru_max; /* Uniq cycle, avoid blackjack prediction */ |
135 | const u_int32_t ru_gen; /* Starting generator */ |
136 | const u_int32_t ru_n; /* ru_n: prime, ru_n - 1: product of pfacts[] */ |
137 | const u_int32_t ru_agen; /* determine ru_a as ru_agen^(2*rand) */ |
138 | const u_int32_t ru_m; /* ru_m = 2^x*3^y */ |
139 | const u_int32_t pfacts[4]; /* factors of ru_n */ |
140 | |
141 | u_int32_t ru_counter; |
142 | u_int32_t ru_msb; |
143 | |
144 | u_int32_t ru_x; |
145 | u_int32_t ru_seed, ru_seed2; |
146 | u_int32_t ru_a, ru_b; |
147 | u_int32_t ru_g; |
148 | long ru_reseed; |
149 | }; |
150 | |
151 | static struct randomtab randomtab_32 = { |
152 | 32, /* resulting bits */ |
153 | 180, /* Time after wich will be reseeded */ |
154 | 1000000000, /* Uniq cycle, avoid blackjack prediction */ |
155 | 2, /* Starting generator */ |
156 | 2147483629, /* RU_N-1 = 2^2*3^2*59652323 */ |
157 | 7, /* determine ru_a as RU_AGEN^(2*rand) */ |
158 | 1836660096, /* RU_M = 2^7*3^15 - don't change */ |
159 | { 2, 3, 59652323, 0 }, /* factors of ru_n */ |
160 | 0, 0, 0, 0, 0, 0, 0, 0, 0 |
161 | }; |
162 | |
163 | static struct randomtab randomtab_20 = { |
164 | 20, /* resulting bits */ |
165 | 180, /* Time after wich will be reseeded */ |
166 | 200000, /* Uniq cycle, avoid blackjack prediction */ |
167 | 2, /* Starting generator */ |
168 | 524269, /* RU_N-1 = 2^2*3^2*14563 */ |
169 | 7, /* determine ru_a as RU_AGEN^(2*rand) */ |
170 | 279936, /* RU_M = 2^7*3^7 - don't change */ |
171 | { 2, 3, 14563, 0 }, /* factors of ru_n */ |
172 | 0, 0, 0, 0, 0, 0, 0, 0, 0 |
173 | }; |
174 | |
175 | static u_int32_t pmod(u_int32_t, u_int32_t, u_int32_t); |
176 | static void initid(struct randomtab *); |
177 | static u_int32_t randomid(struct randomtab *); |
178 | |
179 | /* |
180 | * Do a fast modular exponation, returned value will be in the range |
181 | * of 0 - (mod-1) |
182 | */ |
183 | static u_int32_t |
184 | pmod(u_int32_t gen, u_int32_t expo, u_int32_t mod) |
185 | { |
186 | u_int64_t s, t, u; |
187 | |
188 | s = 1; |
189 | t = gen; |
190 | u = expo; |
191 | |
192 | while (u) { |
193 | if (u & 1) |
194 | s = (s * t) % mod; |
195 | u >>= 1; |
196 | t = (t * t) % mod; |
197 | } |
198 | return (s); |
199 | } |
200 | |
201 | /* |
202 | * Initalizes the seed and chooses a suitable generator. Also toggles |
203 | * the msb flag. The msb flag is used to generate two distinct |
204 | * cycles of random numbers and thus avoiding reuse of ids. |
205 | * |
206 | * This function is called from id_randomid() when needed, an |
207 | * application does not have to worry about it. |
208 | */ |
209 | static void |
210 | initid(struct randomtab *p) |
211 | { |
212 | time_t curtime = (time_t)net_uptime(); |
213 | u_int32_t j, i; |
214 | int noprime = 1; |
215 | |
216 | p->ru_x = RandomULong() % p->ru_m; |
217 | |
218 | /* (bits - 1) bits of random seed */ |
219 | p->ru_seed = RandomULong() & (~0U >> (32 - p->ru_bits + 1)); |
220 | p->ru_seed2 = RandomULong() & (~0U >> (32 - p->ru_bits + 1)); |
221 | |
222 | /* Determine the LCG we use */ |
223 | p->ru_b = (RandomULong() & (~0U >> (32 - p->ru_bits))) | 1; |
224 | p->ru_a = pmod(p->ru_agen, |
225 | (RandomULong() & (~0U >> (32 - p->ru_bits))) & (~1U), p->ru_m); |
226 | while (p->ru_b % 3 == 0) |
227 | p->ru_b += 2; |
228 | |
229 | j = RandomULong() % p->ru_n; |
230 | |
231 | /* |
232 | * Do a fast gcd(j, RU_N - 1), so we can find a j with |
233 | * gcd(j, RU_N - 1) == 1, giving a new generator for |
234 | * RU_GEN^j mod RU_N |
235 | */ |
236 | while (noprime) { |
237 | for (i = 0; p->pfacts[i] > 0; i++) |
238 | if (j % p->pfacts[i] == 0) |
239 | break; |
240 | |
241 | if (p->pfacts[i] == 0) |
242 | noprime = 0; |
243 | else |
244 | j = (j + 1) % p->ru_n; |
245 | } |
246 | |
247 | p->ru_g = pmod(p->ru_gen, j, p->ru_n); |
248 | p->ru_counter = 0; |
249 | |
250 | p->ru_reseed = curtime + p->ru_out; |
251 | p->ru_msb = p->ru_msb ? 0 : (1U << (p->ru_bits - 1)); |
252 | } |
253 | |
254 | static u_int32_t |
255 | randomid(struct randomtab *p) |
256 | { |
257 | time_t curtime = (time_t)net_uptime(); |
258 | int i, n; |
259 | u_int32_t tmp; |
260 | |
261 | if (p->ru_counter >= p->ru_max || curtime > p->ru_reseed) |
262 | initid(p); |
263 | |
264 | tmp = RandomULong(); |
265 | |
266 | /* Skip a random number of ids */ |
267 | n = tmp & 0x3; tmp = tmp >> 2; |
268 | if (p->ru_counter + n >= p->ru_max) |
269 | initid(p); |
270 | |
271 | for (i = 0; i <= n; i++) { |
272 | /* Linear Congruential Generator */ |
273 | p->ru_x = ((u_int64_t)p->ru_a * p->ru_x + p->ru_b) % p->ru_m; |
274 | } |
275 | |
276 | p->ru_counter += i; |
277 | |
278 | return ((p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 ^ p->ru_x, p->ru_n)) | |
279 | p->ru_msb); |
280 | } |
281 | |
282 | u_int32_t |
283 | ip6_randomid(void) |
284 | { |
285 | |
286 | return (randomid(&randomtab_32)); |
287 | } |
288 | |
289 | u_int32_t |
290 | ip6_randomflowlabel(void) |
291 | { |
292 | |
293 | return (randomid(&randomtab_20) & 0xfffff); |
294 | } |
295 | |