1 /* $OpenBSD: ip_id.c,v 1.26 2025/01/01 13:44:22 bluhm Exp $ */
2
3 /*
4 * Copyright (c) 2008 Theo de Raadt, Ryan McBride
5 *
6 * Slightly different algorithm from the one designed by
7 * Matthew Dillon <dillon@backplane.com> for The DragonFly Project
8 *
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
12 *
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 */
21
22 /*
23 * Random ip sequence number generator. Use the system PRNG to shuffle
24 * the 65536 entry ID space. We reshuffle the ID we pick out of the array
25 * into the previous 32767 cells, providing an guarantee that an ID will not
26 * be reused for at least 32768 calls.
27 */
28 #include <sys/param.h>
29 #include <sys/systm.h>
30
31 static u_int16_t ip_shuffle[65536];
32 static int isindex = 0;
33
34 u_int16_t ip_randomid(void);
35
36 /*
37 * Return a random IP id. Shuffle the new value we get into the previous half
38 * of the ip_shuffle ring (-32767 or swap with ourself), to avoid duplicates
39 * occurring too quickly but also still be random.
40 *
41 * 0 is a special IP ID -- don't return it.
42 */
43 u_int16_t
ip_randomid(void)44 ip_randomid(void)
45 {
46 static int ipid_initialized;
47 u_int16_t si, r;
48 int i, i2;
49
50 if (!ipid_initialized) {
51 ipid_initialized = 1;
52
53 /*
54 * Initialize with a random permutation. Do so using Knuth
55 * which avoids the exchange in the Durstenfeld shuffle.
56 * (See "The Art of Computer Programming, Vol 2" 3rd ed, pg. 145).
57 *
58 * Even if our PRNG is imperfect at boot time, we have deferred
59 * doing this until the first packet being sent and now must
60 * generate an ID.
61 */
62 for (i = 0; i < nitems(ip_shuffle); ++i) {
63 i2 = arc4random_uniform(i + 1);
64 ip_shuffle[i] = ip_shuffle[i2];
65 ip_shuffle[i2] = i;
66 }
67 }
68
69 do {
70 arc4random_buf(&si, sizeof(si));
71 i = isindex & 0xFFFF;
72 i2 = (isindex - (si & 0x7FFF)) & 0xFFFF;
73 r = ip_shuffle[i];
74 ip_shuffle[i] = ip_shuffle[i2];
75 ip_shuffle[i2] = r;
76 isindex++;
77 } while (r == 0);
78
79 return (r);
80 }
81