1 |
|
|
/* $OpenBSD: randomid.c,v 1.1 2015/10/15 19:43:30 tedu 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 |
|
|
* This code was used for generating IP IDs. It also works for DNS IDs. |
24 |
|
|
*/ |
25 |
|
|
|
26 |
|
|
/* |
27 |
|
|
* Random DNS sequence number generator. Use the system PRNG to shuffle |
28 |
|
|
* the 65536 entry ID space. We reshuffle the ID we pick out of the array |
29 |
|
|
* into the previous 32767 cells, providing an guarantee that an ID will not |
30 |
|
|
* be reused for at least 32768 calls. |
31 |
|
|
*/ |
32 |
|
|
#include <stdlib.h> |
33 |
|
|
#define nitems(arr) (sizeof(arr) / sizeof(arr[0])) |
34 |
|
|
|
35 |
|
|
static u_int16_t ip_shuffle[65536]; |
36 |
|
|
static int isindex = 0; |
37 |
|
|
|
38 |
|
|
/* |
39 |
|
|
* Return a random DNS id. Shuffle the new value we get into the previous half |
40 |
|
|
* of the ip_shuffle ring (-32767 or swap with ourself), to avoid duplicates |
41 |
|
|
* occuring too quickly but also still be random. |
42 |
|
|
* |
43 |
|
|
* 0 is a special DNS ID -- don't return it. |
44 |
|
|
*/ |
45 |
|
|
uint16_t |
46 |
|
|
randomid(void) |
47 |
|
|
{ |
48 |
|
|
static int ipid_initialized; |
49 |
|
|
u_int16_t si, r; |
50 |
|
|
int i, i2; |
51 |
|
|
|
52 |
|
|
if (!ipid_initialized) { |
53 |
|
|
ipid_initialized = 1; |
54 |
|
|
|
55 |
|
|
/* |
56 |
|
|
* Initialize with a random permutation. Do so using Knuth |
57 |
|
|
* which avoids the exchange in the Durstenfeld shuffle. |
58 |
|
|
* (See "The Art of Computer Programming, Vol 2" 3rd ed, pg. 145). |
59 |
|
|
*/ |
60 |
|
|
for (i = 0; i < nitems(ip_shuffle); ++i) { |
61 |
|
|
i2 = arc4random_uniform(i + 1); |
62 |
|
|
ip_shuffle[i] = ip_shuffle[i2]; |
63 |
|
|
ip_shuffle[i2] = i; |
64 |
|
|
} |
65 |
|
|
} |
66 |
|
|
|
67 |
|
|
do { |
68 |
|
|
arc4random_buf(&si, sizeof(si)); |
69 |
|
|
i = isindex & 0xFFFF; |
70 |
|
|
i2 = (isindex - (si & 0x7FFF)) & 0xFFFF; |
71 |
|
|
r = ip_shuffle[i]; |
72 |
|
|
ip_shuffle[i] = ip_shuffle[i2]; |
73 |
|
|
ip_shuffle[i2] = r; |
74 |
|
|
isindex++; |
75 |
|
|
} while (r == 0); |
76 |
|
|
|
77 |
|
|
return (r); |
78 |
|
|
} |