1 /* $NetBSD: randomid.c,v 1.16 2022/05/15 20:37:50 andvar Exp $ */
2 /* $KAME: ip6_id.c,v 1.8 2003/09/06 13:41:06 itojun Exp $ */
3 /* $OpenBSD: ip_id.c,v 1.6 2002/03/15 18:19:52 millert Exp $ */
4
5 /*
6 * Copyright (C) 2003 WIDE Project.
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. Neither the name of the project nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34 /*
35 * Copyright 1998 Niels Provos <provos@citi.umich.edu>
36 * All rights reserved.
37 *
38 * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
39 * such a mathematical system to generate more random (yet non-repeating)
40 * ids to solve the resolver/named problem. But Niels designed the
41 * actual system based on the constraints.
42 *
43 * Redistribution and use in source and binary forms, with or without
44 * modification, are permitted provided that the following conditions
45 * are met:
46 * 1. Redistributions of source code must retain the above copyright
47 * notice, this list of conditions and the following disclaimer.
48 * 2. Redistributions in binary form must reproduce the above copyright
49 * notice, this list of conditions and the following disclaimer in the
50 * documentation and/or other materials provided with the distribution.
51 *
52 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
53 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
54 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
55 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
56 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
57 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
58 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
59 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
60 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
61 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
62 */
63
64 /*
65 * seed = random (bits - 1) bit
66 * n = prime, g0 = generator to n,
67 * j = random so that gcd(j,n-1) == 1
68 * g = g0^j mod n will be a generator again.
69 *
70 * X[0] = random seed.
71 * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
72 * with a = 7^(even random) mod m,
73 * b = random with gcd(b,m) == 1
74 * m = constant and a maximal period of m-1.
75 *
76 * The transaction id is determined by:
77 * id[n] = seed xor (g^X[n] mod n)
78 *
79 * Effectively the id is restricted to the lower (bits - 1) bits, thus
80 * yielding two different cycles by toggling the msb on and off.
81 * This avoids reuse issues caused by reseeding.
82 */
83
84 #include <sys/cdefs.h>
85 #if defined(LIBC_SCCS) && !defined(lint)
86 __RCSID("$NetBSD: randomid.c,v 1.16 2022/05/15 20:37:50 andvar Exp $");
87 #endif
88
89 #include "namespace.h"
90
91 #include <sys/types.h>
92 #include <sys/time.h>
93 #include <stdlib.h>
94 #include <string.h>
95 #include <errno.h>
96 #include <randomid.h>
97
98 #ifdef __weak_alias
99 __weak_alias(randomid,_randomid)
100 __weak_alias(randomid_new,_randomid_new)
101 __weak_alias(randomid_delete,_randomid_delete)
102 #endif
103
104 struct randomconf {
105 const int rc_bits; /* resulting bits */
106 const u_int32_t rc_max; /* Uniq cycle, avoid blackjack prediction */
107 const u_int32_t rc_gen; /* Starting generator */
108 const u_int32_t rc_n; /* ru_n: prime, ru_n - 1: product of pfacts[] */
109 const u_int32_t rc_agen; /* determine ru_a as ru_agen^(2*rand) */
110 const u_int32_t rc_m; /* ru_m = 2^x*3^y */
111 const u_int32_t rc_pfacts[4]; /* factors of ru_n */
112 const int rc_skip; /* skip values */
113 };
114
115 struct randomid_ctx {
116 struct randomconf *ru_conf;
117 #define ru_bits ru_conf->rc_bits
118 #define ru_max ru_conf->rc_max
119 #define ru_gen ru_conf->rc_gen
120 #define ru_n ru_conf->rc_n
121 #define ru_agen ru_conf->rc_agen
122 #define ru_m ru_conf->rc_m
123 #define ru_pfacts ru_conf->rc_pfacts
124 #define ru_skip ru_conf->rc_skip
125 long ru_out; /* Time after which will be reseeded */
126 u_int32_t ru_counter;
127 u_int32_t ru_msb;
128
129 u_int32_t ru_x;
130 u_int32_t ru_seed, ru_seed2;
131 u_int32_t ru_a, ru_b;
132 u_int32_t ru_g;
133 time_t ru_reseed;
134 };
135
136 static struct randomconf randomconf[] = {
137 {
138 32, /* resulting bits */
139 1000000000, /* Uniq cycle, avoid blackjack prediction */
140 2, /* Starting generator */
141 2147483629, /* RU_N-1 = 2^2*3^2*59652323 */
142 7, /* determine ru_a as RU_AGEN^(2*rand) */
143 1836660096, /* RU_M = 2^7*3^15 - don't change */
144 { 2, 3, 59652323, 0 }, /* factors of ru_n */
145 3, /* skip values */
146 },
147 {
148 20, /* resulting bits */
149 200000, /* Uniq cycle, avoid blackjack prediction */
150 2, /* Starting generator */
151 524269, /* RU_N-1 = 2^2*3^2*14563 */
152 7, /* determine ru_a as RU_AGEN^(2*rand) */
153 279936, /* RU_M = 2^7*3^7 - don't change */
154 { 2, 3, 14563, 0 }, /* factors of ru_n */
155 3, /* skip values */
156 },
157 {
158 16, /* resulting bits */
159 30000, /* Uniq cycle, avoid blackjack prediction */
160 2, /* Starting generator */
161 32749, /* RU_N-1 = 2^2*3*2729 */
162 7, /* determine ru_a as RU_AGEN^(2*rand) */
163 31104, /* RU_M = 2^7*3^5 - don't change */
164 { 2, 3, 2729, 0 }, /* factors of ru_n */
165 0, /* skip values */
166 },
167 {
168 .rc_bits = -1, /* termination */
169 },
170 };
171
172 static u_int32_t pmod(u_int32_t, u_int32_t, u_int32_t);
173 static void initid(struct randomid_ctx *);
174
175 struct randomid_ctx *randomid_new(int, long);
176 void randomid_delete(struct randomid_ctx *);
177 u_int32_t randomid(struct randomid_ctx *);
178
179 /*
180 * Do a fast modular exponation, returned value will be in the range
181 * of 0 - (mod-1)
182 */
183
184 static u_int32_t
pmod(u_int32_t gen,u_int32_t expo,u_int32_t mod)185 pmod(u_int32_t gen, u_int32_t expo, u_int32_t mod)
186 {
187 u_int64_t s, t, u;
188
189 s = 1;
190 t = gen;
191 u = expo;
192
193 while (u) {
194 if (u & 1)
195 s = (s * t) % mod;
196 u >>= 1;
197 t = (t * t) % mod;
198 }
199 return ((u_int32_t)s & UINT32_MAX);
200 }
201
202 /*
203 * Initializes the seed and chooses a suitable generator. Also toggles
204 * the msb flag. The msb flag is used to generate two distinct
205 * cycles of random numbers and thus avoiding reuse of ids.
206 *
207 * This function is called from id_randomid() when needed, an
208 * application does not have to worry about it.
209 */
210 static void
initid(struct randomid_ctx * p)211 initid(struct randomid_ctx *p)
212 {
213 u_int32_t j, i;
214 int noprime = 1;
215 struct timeval tv;
216
217 p->ru_x = arc4random() % p->ru_m;
218
219 /* (bits - 1) bits of random seed */
220 p->ru_seed = arc4random() & (~0U >> (32 - p->ru_bits + 1));
221 p->ru_seed2 = arc4random() & (~0U >> (32 - p->ru_bits + 1));
222
223 /* Determine the LCG we use */
224 p->ru_b = (arc4random() & (~0U >> (32 - p->ru_bits))) | 1;
225 p->ru_a = pmod(p->ru_agen,
226 (arc4random() & (~0U >> (32 - p->ru_bits))) & (~1U), p->ru_m);
227 while (p->ru_b % 3 == 0)
228 p->ru_b += 2;
229
230 j = arc4random() % p->ru_n;
231
232 /*
233 * Do a fast gcd(j, RU_N - 1), so we can find a j with
234 * gcd(j, RU_N - 1) == 1, giving a new generator for
235 * RU_GEN^j mod RU_N
236 */
237 while (noprime) {
238 for (i = 0; p->ru_pfacts[i] > 0; i++)
239 if (j % p->ru_pfacts[i] == 0)
240 break;
241
242 if (p->ru_pfacts[i] == 0)
243 noprime = 0;
244 else
245 j = (j + 1) % p->ru_n;
246 }
247
248 p->ru_g = pmod(p->ru_gen, j, p->ru_n);
249 p->ru_counter = 0;
250
251 gettimeofday(&tv, NULL);
252 p->ru_reseed = tv.tv_sec + p->ru_out;
253 p->ru_msb = p->ru_msb ? 0 : (1U << (p->ru_bits - 1));
254 }
255
256 struct randomid_ctx *
randomid_new(int bits,long timeo)257 randomid_new(int bits, long timeo)
258 {
259 struct randomconf *conf;
260 struct randomid_ctx *ctx;
261
262 if (timeo < RANDOMID_TIMEO_MIN) {
263 errno = EINVAL;
264 return (NULL);
265 }
266
267 for (conf = randomconf; conf->rc_bits > 0; conf++) {
268 if (bits == conf->rc_bits)
269 break;
270 }
271
272 /* unsupported bits */
273 if (bits != conf->rc_bits) {
274 errno = ENOTSUP;
275 return (NULL);
276 }
277
278 ctx = malloc(sizeof(*ctx));
279 if (!ctx)
280 return (NULL);
281
282 memset(ctx, 0, sizeof(*ctx));
283 ctx->ru_conf = conf;
284 ctx->ru_out = timeo;
285
286 return (ctx);
287 }
288
289 void
randomid_delete(struct randomid_ctx * ctx)290 randomid_delete(struct randomid_ctx *ctx)
291 {
292
293 memset(ctx, 0, sizeof(*ctx));
294 free(ctx);
295 }
296
297 u_int32_t
randomid(struct randomid_ctx * p)298 randomid(struct randomid_ctx *p)
299 {
300 int i, n;
301 struct timeval tv;
302
303 gettimeofday(&tv, NULL);
304 if (p->ru_counter >= p->ru_max || tv.tv_sec > p->ru_reseed)
305 initid(p);
306
307 /* Skip a random number of ids */
308 if (p->ru_skip) {
309 n = arc4random() & p->ru_skip;
310 if (p->ru_counter + n >= p->ru_max)
311 initid(p);
312 } else
313 n = 0;
314
315 for (i = 0; i <= n; i++) {
316 /* Linear Congruential Generator */
317 p->ru_x = (u_int32_t)(((u_int64_t)p->ru_a * p->ru_x + p->ru_b) % p->ru_m);
318 }
319
320 p->ru_counter += i;
321
322 return (p->ru_seed ^ pmod(p->ru_g, p->ru_seed2 + p->ru_x, p->ru_n)) |
323 p->ru_msb;
324 }
325