1 | /*␊ |
2 | * Copyright (c) 1996, David Mazieres <dm@uun.org>␊ |
3 | * Copyright (c) 2008, Damien Miller <djm@openbsd.org>␊ |
4 | *␊ |
5 | * Permission to use, copy, modify, and distribute this software for any␊ |
6 | * purpose with or without fee is hereby granted, provided that the above␊ |
7 | * copyright notice and this permission notice appear in all copies.␊ |
8 | *␊ |
9 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES␊ |
10 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF␊ |
11 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR␊ |
12 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES␊ |
13 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN␊ |
14 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF␊ |
15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.␊ |
16 | */␊ |
17 | ␊ |
18 | /*␊ |
19 | * Arc4 random number generator for OpenBSD.␊ |
20 | *␊ |
21 | * This code is derived from section 17.1 of Applied Cryptography,␊ |
22 | * second edition, which describes a stream cipher allegedly␊ |
23 | * compatible with RSA Labs "RC4" cipher (the actual description of␊ |
24 | * which is a trade secret). The same algorithm is used as a stream␊ |
25 | * cipher called "arcfour" in Tatu Ylonen's ssh package.␊ |
26 | *␊ |
27 | * Here the stream cipher has been modified always to include the time␊ |
28 | * when initializing the state. That makes it impossible to␊ |
29 | * regenerate the same random sequence twice, so this can't be used␊ |
30 | * for encryption, but will generate good random numbers.␊ |
31 | *␊ |
32 | * RC4 is a registered trademark of RSA Laboratories.␊ |
33 | */␊ |
34 | ␊ |
35 | ␊ |
36 | #include "libsaio.h"␊ |
37 | ␊ |
38 | ␊ |
39 | struct arc4_stream {␊ |
40 | ␉u_int8_t i;␊ |
41 | ␉u_int8_t j;␊ |
42 | ␉u_int8_t s[256];␊ |
43 | };␊ |
44 | ␊ |
45 | ␊ |
46 | #define KEYSIZE␉␉128␊ |
47 | ␊ |
48 | static struct arc4_stream rs = {␊ |
49 | ␉.i = 0,␊ |
50 | ␉.j = 0,␊ |
51 | ␉.s = {␊ |
52 | 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,␊ |
53 | 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,␊ |
54 | 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,␊ |
55 | 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,␊ |
56 | 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,␊ |
57 | 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95,␊ |
58 | 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,␊ |
59 | ␉␉112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,␊ |
60 | ␉␉128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,␊ |
61 | ␉␉144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,␊ |
62 | ␉␉160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,␊ |
63 | ␉␉176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,␊ |
64 | ␉␉192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,␊ |
65 | ␉␉208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,␊ |
66 | ␉␉224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,␊ |
67 | ␉␉240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255␊ |
68 | ␉}␊ |
69 | };␊ |
70 | //static int rs_initialized;␊ |
71 | static int rs_stired;␊ |
72 | static int arc4_count;␊ |
73 | ␊ |
74 | static inline u_int8_t arc4_getbyte(void);␊ |
75 | static void arc4_stir(void);␊ |
76 | __private_extern__ void _arc4_fork_child(void);␊ |
77 | ␊ |
78 | static struct {␊ |
79 | ␉struct timeval␉tv;␊ |
80 | ␉u_int8_t␉rnd[KEYSIZE];␊ |
81 | } rdat;␊ |
82 | static volatile int rs_data_available = 0;␊ |
83 | ␊ |
84 | static inline void␊ |
85 | arc4_addrandom(u_char *dat, int datlen)␊ |
86 | {␊ |
87 | ␉int n;␊ |
88 | ␉u_int8_t si;␊ |
89 | ␊ |
90 | ␉rs.i--;␊ |
91 | ␉for (n = 0; n < 256; n++) {␊ |
92 | ␉␉rs.i = (rs.i + 1);␊ |
93 | ␉␉si = rs.s[rs.i];␊ |
94 | ␉␉rs.j = (rs.j + si + dat[n % datlen]);␊ |
95 | ␉␉rs.s[rs.i] = rs.s[rs.j];␊ |
96 | ␉␉rs.s[rs.j] = si;␊ |
97 | ␉}␊ |
98 | ␉rs.j = rs.i;␊ |
99 | }␊ |
100 | ␊ |
101 | static void␊ |
102 | arc4_fetch(void)␊ |
103 | {␊ |
104 | ␉␊ |
105 | ␉(void)gettimeofday(&rdat.tv, NULL);␊ |
106 | ␉␊ |
107 | }␊ |
108 | ␊ |
109 | static void␊ |
110 | arc4_stir(void)␊ |
111 | {␊ |
112 | ␉int n;␊ |
113 | ␉/*␊ |
114 | ␉ * If we don't have data, we need some now before we can integrate␊ |
115 | ␉ * it into the static buffers␊ |
116 | ␉ */␊ |
117 | ␉if (!rs_data_available)␊ |
118 | ␉{␊ |
119 | ␉␉arc4_fetch();␊ |
120 | ␉}␊ |
121 | ␉rs_data_available = 0;␊ |
122 | ␉__sync_synchronize();␊ |
123 | ␊ |
124 | ␉arc4_addrandom((u_char *)&rdat, KEYSIZE);␊ |
125 | ␊ |
126 | ␉/*␊ |
127 | ␉ * Throw away the first N bytes of output, as suggested in the␊ |
128 | ␉ * paper "Weaknesses in the Key Scheduling Algorithm of RC4"␊ |
129 | ␉ * by Fluher, Mantin, and Shamir. N=1024 is based on␊ |
130 | ␉ * suggestions in the paper "(Not So) Random Shuffles of RC4"␊ |
131 | ␉ * by Ilya Mironov.␊ |
132 | ␉ */␊ |
133 | ␉for (n = 0; n < 1024; n++)␊ |
134 | ␉␉(void) arc4_getbyte();␊ |
135 | ␉arc4_count = 1600000;␊ |
136 | ␉rs_stired = 1;␊ |
137 | }␊ |
138 | ␊ |
139 | static inline u_int8_t␊ |
140 | arc4_getbyte(void)␊ |
141 | {␊ |
142 | ␉u_int8_t si, sj;␊ |
143 | ␊ |
144 | ␉rs.i = (rs.i + 1);␊ |
145 | ␉si = rs.s[rs.i];␊ |
146 | ␉rs.j = (rs.j + si);␊ |
147 | ␉sj = rs.s[rs.j];␊ |
148 | ␉rs.s[rs.i] = sj;␊ |
149 | ␉rs.s[rs.j] = si;␊ |
150 | ␊ |
151 | ␉return (rs.s[(si + sj) & 0xff]);␊ |
152 | }␊ |
153 | ␊ |
154 | static inline u_int32_t␊ |
155 | arc4_getword(void)␊ |
156 | {␊ |
157 | ␉u_int32_t val;␊ |
158 | ␊ |
159 | ␉val = arc4_getbyte() << 24;␊ |
160 | ␉val |= arc4_getbyte() << 16;␊ |
161 | ␉val |= arc4_getbyte() << 8;␊ |
162 | ␉val |= arc4_getbyte();␊ |
163 | ␊ |
164 | ␉return (val);␊ |
165 | }␊ |
166 | ␊ |
167 | /* 7944700: force restir in child */␊ |
168 | __private_extern__ void␊ |
169 | _arc4_fork_child(void)␊ |
170 | {␊ |
171 | ␉rs_stired = 0;␊ |
172 | ␉rs_data_available = 0;␊ |
173 | }␊ |
174 | ␊ |
175 | static inline int␊ |
176 | arc4_check_stir(void)␊ |
177 | {␊ |
178 | ␉if (!rs_stired || arc4_count <= 0) {␊ |
179 | ␉␉arc4_stir();␊ |
180 | ␉␉return 1;␊ |
181 | ␉}␊ |
182 | ␉return 0;␊ |
183 | }␊ |
184 | ␊ |
185 | void␊ |
186 | arc4random_stir(void)␊ |
187 | {␊ |
188 | ␉arc4_stir();␊ |
189 | }␊ |
190 | ␊ |
191 | void␊ |
192 | arc4random_addrandom(u_char *dat, int datlen)␊ |
193 | {␊ |
194 | ␉arc4_check_stir();␊ |
195 | ␉arc4_addrandom(dat, datlen);␊ |
196 | }␊ |
197 | ␊ |
198 | u_int32_t␊ |
199 | arc4random(void)␊ |
200 | {␊ |
201 | ␉u_int32_t rnd;␊ |
202 | ␊ |
203 | ␉int did_stir = arc4_check_stir();␊ |
204 | ␉rnd = arc4_getword();␊ |
205 | ␉arc4_count -= 4;␊ |
206 | ␊ |
207 | ␉if (did_stir)␊ |
208 | ␉{␊ |
209 | ␉␉/* stirring used up our data pool, we need to read in new data outside of the lock */␊ |
210 | ␉␉arc4_fetch();␊ |
211 | ␉␉rs_data_available = 1;␊ |
212 | ␉␉__sync_synchronize();␊ |
213 | ␉}␊ |
214 | ␊ |
215 | ␉return (rnd);␊ |
216 | }␊ |
217 | ␊ |
218 | void␊ |
219 | arc4random_buf(void *_buf, size_t n)␊ |
220 | {␊ |
221 | ␉u_char *buf = (u_char *)_buf;␊ |
222 | ␉int did_stir = 0;␊ |
223 | ␊ |
224 | ␉while (n--) {␊ |
225 | ␉␉if (arc4_check_stir())␊ |
226 | ␉␉{␊ |
227 | ␉␉␉did_stir = 1;␊ |
228 | ␉␉}␊ |
229 | ␉␉buf[n] = arc4_getbyte();␊ |
230 | ␉␉arc4_count--;␊ |
231 | ␉}␊ |
232 | ␉␊ |
233 | ␉if (did_stir)␊ |
234 | ␉{␊ |
235 | ␉␉/* stirring used up our data pool, we need to read in new data outside of the lock */␊ |
236 | ␉␉arc4_fetch();␊ |
237 | ␉␉rs_data_available = 1;␊ |
238 | ␉␉__sync_synchronize();␊ |
239 | ␉}␊ |
240 | }␊ |
241 | ␊ |
242 | /*␊ |
243 | * Calculate a uniformly distributed random number less than upper_bound␊ |
244 | * avoiding "modulo bias".␊ |
245 | *␊ |
246 | * Uniformity is achieved by generating new random numbers until the one␊ |
247 | * returned is outside the range [0, 2**32 % upper_bound). This␊ |
248 | * guarantees the selected random number will be inside␊ |
249 | * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)␊ |
250 | * after reduction modulo upper_bound.␊ |
251 | */␊ |
252 | u_int32_t␊ |
253 | arc4random_uniform(u_int32_t upper_bound)␊ |
254 | {␊ |
255 | ␉u_int32_t r, min;␊ |
256 | ␊ |
257 | ␉if (upper_bound < 2)␊ |
258 | ␉␉return (0);␊ |
259 | ␊ |
260 | #if (ULONG_MAX > 0xffffffffUL)␊ |
261 | ␉min = 0x100000000UL % upper_bound;␊ |
262 | #else␊ |
263 | ␉/* Calculate (2**32 % upper_bound) avoiding 64-bit math */␊ |
264 | ␉if (upper_bound > 0x80000000)␊ |
265 | ␉␉min = 1 + ~upper_bound;␉␉/* 2**32 - upper_bound */␊ |
266 | ␉else {␊ |
267 | ␉␉/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */␊ |
268 | ␉␉min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;␊ |
269 | ␉}␊ |
270 | #endif␊ |
271 | ␊ |
272 | ␉/*␊ |
273 | ␉ * This could theoretically loop forever but each retry has␊ |
274 | ␉ * p > 0.5 (worst case, usually far better) of selecting a␊ |
275 | ␉ * number inside the range we need, so it should rarely need␊ |
276 | ␉ * to re-roll.␊ |
277 | ␉ */␊ |
278 | ␉for (;;) {␊ |
279 | ␉␉r = arc4random();␊ |
280 | ␉␉if (r >= min)␊ |
281 | ␉␉␉break;␊ |
282 | ␉}␊ |
283 | ␊ |
284 | ␉return (r % upper_bound);␊ |
285 | }␊ |
286 | ␊ |
287 | #if 0␊ |
288 | void␊ |
289 | arc4_init(void)␊ |
290 | {␉␊ |
291 | }␊ |
292 | ␊ |
293 | /*-------- Test code for i386 --------*/␊ |
294 | #include <stdio.h>␊ |
295 | #include <machine/pctr.h>␊ |
296 | int␊ |
297 | main(int argc, char **argv)␊ |
298 | {␊ |
299 | ␉const int iter = 1000000;␊ |
300 | ␉int i;␊ |
301 | ␉pctrval v;␊ |
302 | ␊ |
303 | ␉v = rdtsc();␊ |
304 | ␉for (i = 0; i < iter; i++)␊ |
305 | ␉␉arc4random();␊ |
306 | ␉v = rdtsc() - v;␊ |
307 | ␉v /= iter;␊ |
308 | ␊ |
309 | ␉printf("%qd cycles\n", v);␊ |
310 | }␊ |
311 | #endif␊ |
312 | |