1 /*-
2 * THE BEER-WARE LICENSE
3 *
4 * <dan@FreeBSD.ORG> wrote this file. As long as you retain this notice you
5 * can do whatever you want with this stuff. If we meet some day, and you
6 * think this stuff is worth it, you can buy me a beer in return.
7 *
8 * Dan Moschuk
9 *
10 * $FreeBSD: src/sys/libkern/arc4random.c,v 1.3.2.2 2001/09/17 07:06:50 silby Exp $
11 */
12
13 #include <sys/types.h>
14 #include <sys/systm.h>
15 #include <sys/random.h>
16 #include <sys/libkern.h>
17 #include <sys/time.h>
18
19 #include <vm/vm_extern.h>
20
21 #define ARC4_MAXRUNS 16384
22 #define ARC4_RESEED_SECONDS 300
23 #define ARC4_KEYBYTES 32 /* 256 bit key */
24
25 struct arc4_data {
26 uint8_t arc4_i;
27 uint8_t arc4_j;
28 int arc4_numruns;
29 time_t arc4_nextreseed;
30 uint8_t arc4_sbox[256];
31 };
32
33 static struct arc4_data *arc4_data_pcpu[MAXCPU];
34
35 static uint8_t arc4_randbyte(struct arc4_data *);
36
37 static __inline void
arc4_swap(uint8_t * a,uint8_t * b)38 arc4_swap(uint8_t *a, uint8_t *b)
39 {
40 uint8_t c;
41
42 c = *a;
43 *a = *b;
44 *b = c;
45 }
46
47 /*
48 * Stir our S-box.
49 */
50 static void
arc4_randomstir(struct arc4_data * d)51 arc4_randomstir(struct arc4_data *d)
52 {
53 uint8_t key[256];
54 int r, n;
55
56 /*
57 * XXX read_random() returns unsafe numbers if the entropy
58 * device is not loaded -- MarkM.
59 */
60 r = read_random(key, ARC4_KEYBYTES, 1);
61 /* If r == 0 || -1, just use what was on the stack. */
62 if (r > 0) {
63 for (n = r; n < sizeof(key); n++)
64 key[n] = key[n % r];
65 }
66
67 for (n = 0; n < 256; n++) {
68 d->arc4_j = (d->arc4_j + d->arc4_sbox[n] + key[n]) % 256;
69 arc4_swap(&d->arc4_sbox[n], &d->arc4_sbox[d->arc4_j]);
70 }
71
72 /*
73 * Discard early keystream, as per recommendations in:
74 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
75 */
76 for (n = 0; n < 768 * 4; n++)
77 arc4_randbyte(d);
78
79 /* Reset for next reseed cycle. */
80 d->arc4_nextreseed = time_uptime + ARC4_RESEED_SECONDS;
81 d->arc4_numruns = 0;
82 }
83
84 /*
85 * Generate a random byte.
86 */
87 static uint8_t
arc4_randbyte(struct arc4_data * d)88 arc4_randbyte(struct arc4_data *d)
89 {
90 uint8_t arc4_t;
91
92 d->arc4_i = (d->arc4_i + 1) % 256;
93 d->arc4_j = (d->arc4_j + d->arc4_sbox[d->arc4_i]) % 256;
94
95 arc4_swap(&d->arc4_sbox[d->arc4_i], &d->arc4_sbox[d->arc4_j]);
96
97 arc4_t = (d->arc4_sbox[d->arc4_i] + d->arc4_sbox[d->arc4_j]) % 256;
98 return d->arc4_sbox[arc4_t];
99 }
100
101 uint32_t
karc4random(void)102 karc4random(void)
103 {
104 struct arc4_data *d = arc4_data_pcpu[mycpuid];
105 uint32_t ret;
106
107 if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
108 time_uptime > d->arc4_nextreseed)
109 arc4_randomstir(d);
110
111 ret = arc4_randbyte(d);
112 ret |= arc4_randbyte(d) << 8;
113 ret |= arc4_randbyte(d) << 16;
114 ret |= arc4_randbyte(d) << 24;
115
116 return ret;
117 }
118
119 uint64_t
karc4random64(void)120 karc4random64(void)
121 {
122 struct arc4_data *d = arc4_data_pcpu[mycpuid];
123 uint64_t ret;
124
125 if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
126 time_uptime > d->arc4_nextreseed)
127 arc4_randomstir(d);
128
129 ret = arc4_randbyte(d);
130 ret |= arc4_randbyte(d) << 8;
131 ret |= arc4_randbyte(d) << 16;
132 ret |= arc4_randbyte(d) << 24;
133 ret |= (uint64_t)arc4_randbyte(d) << 32;
134 ret |= (uint64_t)arc4_randbyte(d) << 40;
135 ret |= (uint64_t)arc4_randbyte(d) << 48;
136 ret |= (uint64_t)arc4_randbyte(d) << 56;
137
138 return ret;
139 }
140
141 void
karc4random_buf(void * ptr,size_t len)142 karc4random_buf(void *ptr, size_t len)
143 {
144 struct arc4_data *d = arc4_data_pcpu[mycpuid];
145 uint8_t *p = ptr;
146
147 #if 0
148 /* No one call this function in ISR/ithread. */
149 crit_enter();
150 #endif
151
152 if (++(d->arc4_numruns) > ARC4_MAXRUNS ||
153 time_uptime > d->arc4_nextreseed)
154 arc4_randomstir(d);
155
156 while (len--)
157 *p++ = arc4_randbyte(d);
158
159 #if 0
160 crit_exit();
161 #endif
162 }
163
164 /*
165 * Initialize our S-box to its beginning defaults.
166 */
167 void
arc4_init_pcpu(int cpuid)168 arc4_init_pcpu(int cpuid)
169 {
170 struct arc4_data *d;
171 int n;
172
173 KASSERT(arc4_data_pcpu[cpuid] == NULL,
174 ("arc4 was initialized on cpu%d", cpuid));
175
176 d = (void *)kmem_alloc3(kernel_map, sizeof(*d), VM_SUBSYS_GD,
177 KM_CPU(cpuid));
178 memset(d, 0, sizeof(*d));
179
180 for (n = 0; n < 256; n++)
181 d->arc4_sbox[n] = (uint8_t)n;
182
183 arc4_randomstir(d);
184
185 /*
186 * Discard early keystream, as per recommendations in:
187 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
188 */
189 for (n = 0; n < 768 * 4; n++)
190 arc4_randbyte(d);
191
192 arc4_data_pcpu[cpuid] = d;
193 }
194