Skip to content
Newer
Older
100644 541 lines (484 sloc) 12.5 KB
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
1 /* Portable arc4random.c based on arc4random.c from OpenBSD.
2 * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
3 * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson
e49e289 Update copyright notices to 2012
Nick Mathewson authored
4 * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
5 *
6 * Note that in Libevent, this file isn't compiled directly. Instead,
7 * it's included from evutil_rand.c
8 */
9
10 /*
11 * Copyright (c) 1996, David Mazieres <dm@uun.org>
12 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
13 *
14 * Permission to use, copy, modify, and distribute this software for any
15 * purpose with or without fee is hereby granted, provided that the above
16 * copyright notice and this permission notice appear in all copies.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
19 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
20 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
21 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
22 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
23 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
24 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
25 */
26
27 /*
28 * Arc4 random number generator for OpenBSD.
29 *
30 * This code is derived from section 17.1 of Applied Cryptography,
31 * second edition, which describes a stream cipher allegedly
32 * compatible with RSA Labs "RC4" cipher (the actual description of
33 * which is a trade secret). The same algorithm is used as a stream
34 * cipher called "arcfour" in Tatu Ylonen's ssh package.
35 *
36 * Here the stream cipher has been modified always to include the time
37 * when initializing the state. That makes it impossible to
38 * regenerate the same random sequence twice, so this can't be used
39 * for encryption, but will generate good random numbers.
40 *
41 * RC4 is a registered trademark of RSA Laboratories.
42 */
43
44 #ifndef ARC4RANDOM_EXPORT
45 #define ARC4RANDOM_EXPORT
46 #endif
47
4ec8fea Make RNG work when we have arc4random() but not arc4random_buf()
Nick Mathewson authored
48 #ifndef ARC4RANDOM_UINT32
49 #define ARC4RANDOM_UINT32 uint32_t
50 #endif
51
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
52 #ifndef ARC4RANDOM_NO_INCLUDES
ded0a09 @kev009 Add evconfig-private to remaining files
kev009 authored
53 #include "evconfig-private.h"
9f560bf Use "_WIN32", not WIN32: it's standard and we don't need to fake it
Nick Mathewson authored
54 #ifdef _WIN32
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
55 #include <wincrypt.h>
ff2a134 Fix getpid() usage on Windows
Nick Mathewson authored
56 #include <process.h>
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
57 #else
58 #include <fcntl.h>
59 #include <unistd.h>
60 #include <sys/param.h>
61 #include <sys/time.h>
68120d9 Convert event-config.h macros to avoid reserved identifiers
Nick Mathewson authored
62 #ifdef EVENT__HAVE_SYS_SYSCTL_H
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
63 #include <sys/sysctl.h>
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
64 #endif
c44de06 Numerous opensolaris compilation fixes
Nick Mathewson authored
65 #endif
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
66 #include <limits.h>
67 #include <stdlib.h>
68 #include <string.h>
69 #endif
70
71 /* Add platform entropy 32 bytes (256 bits) at a time. */
72 #define ADD_ENTROPY 32
73
74 /* Re-seed from the platform RNG after generating this many bytes. */
75 #define BYTES_BEFORE_RESEED 1600000
76
77 struct arc4_stream {
78 unsigned char i;
79 unsigned char j;
80 unsigned char s[256];
81 };
82
9f560bf Use "_WIN32", not WIN32: it's standard and we don't need to fake it
Nick Mathewson authored
83 #ifdef _WIN32
98edb89 Fix arc4random compilation on MSVC.
Nick Mathewson authored
84 #define getpid _getpid
85 #define pid_t int
86 #endif
87
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
88 static int rs_initialized;
89 static struct arc4_stream rs;
90 static pid_t arc4_stir_pid;
91 static int arc4_count;
92 static int arc4_seeded_ok;
93
94 static inline unsigned char arc4_getbyte(void);
95
96 static inline void
97 arc4_init(void)
98 {
99 int n;
100
101 for (n = 0; n < 256; n++)
102 rs.s[n] = n;
103 rs.i = 0;
104 rs.j = 0;
105 }
106
107 static inline void
108 arc4_addrandom(const unsigned char *dat, int datlen)
109 {
110 int n;
111 unsigned char si;
112
113 rs.i--;
114 for (n = 0; n < 256; n++) {
115 rs.i = (rs.i + 1);
116 si = rs.s[rs.i];
117 rs.j = (rs.j + si + dat[n % datlen]);
118 rs.s[rs.i] = rs.s[rs.j];
119 rs.s[rs.j] = si;
120 }
121 rs.j = rs.i;
122 }
123
9f560bf Use "_WIN32", not WIN32: it's standard and we don't need to fake it
Nick Mathewson authored
124 #ifndef _WIN32
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
125 static ssize_t
126 read_all(int fd, unsigned char *buf, size_t count)
127 {
128 size_t numread = 0;
129 ssize_t result;
130
131 while (numread < count) {
132 result = read(fd, buf+numread, count-numread);
133 if (result<0)
134 return -1;
135 else if (result == 0)
136 break;
137 numread += result;
138 }
139
140 return (ssize_t)numread;
141 }
142 #endif
143
9f560bf Use "_WIN32", not WIN32: it's standard and we don't need to fake it
Nick Mathewson authored
144 #ifdef _WIN32
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
145 #define TRY_SEED_WIN32
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
146 static int
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
147 arc4_seed_win32(void)
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
148 {
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
149 /* This is adapted from Tor's crypto_seed_rng() */
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
150 static int provider_set = 0;
151 static HCRYPTPROV provider;
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
152 unsigned char buf[ADD_ENTROPY];
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
153
154 if (!provider_set) {
155 if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
156 CRYPT_VERIFYCONTEXT)) {
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
157 if (GetLastError() != (DWORD)NTE_BAD_KEYSET)
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
158 return -1;
159 }
160 provider_set = 1;
161 }
162 if (!CryptGenRandom(provider, sizeof(buf), buf))
163 return -1;
164 arc4_addrandom(buf, sizeof(buf));
165 memset(buf, 0, sizeof(buf));
166 arc4_seeded_ok = 1;
167 return 0;
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
168 }
169 #endif
170
68120d9 Convert event-config.h macros to avoid reserved identifiers
Nick Mathewson authored
171 #if defined(EVENT__HAVE_SYS_SYSCTL_H) && defined(EVENT__HAVE_SYSCTL)
172 #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_RANDOM && EVENT__HAVE_DECL_RANDOM_UUID
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
173 #define TRY_SEED_SYSCTL_LINUX
174 static int
175 arc4_seed_sysctl_linux(void)
176 {
177 /* Based on code by William Ahern, this function tries to use the
178 * RANDOM_UUID sysctl to get entropy from the kernel. This can work
179 * even if /dev/urandom is inaccessible for some reason (e.g., we're
180 * running in a chroot). */
181 int mib[] = { CTL_KERN, KERN_RANDOM, RANDOM_UUID };
182 unsigned char buf[ADD_ENTROPY];
183 size_t len, n;
9c8db0f Fix all warnings in the main codebase flagged by -Wsigned-compare
Nick Mathewson authored
184 unsigned i;
185 int any_set;
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
186
187 memset(buf, 0, sizeof(buf));
188
189 for (len = 0; len < sizeof(buf); len += n) {
190 n = sizeof(buf) - len;
191
192 if (0 != sysctl(mib, 3, &buf[len], &n, NULL, 0))
193 return -1;
194 }
195 /* make sure that the buffer actually got set. */
9c8db0f Fix all warnings in the main codebase flagged by -Wsigned-compare
Nick Mathewson authored
196 for (i=0,any_set=0; i<sizeof(buf); ++i) {
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
197 any_set |= buf[i];
198 }
199 if (!any_set)
200 return -1;
201
202 arc4_addrandom(buf, sizeof(buf));
203 memset(buf, 0, sizeof(buf));
204 arc4_seeded_ok = 1;
205 return 0;
206 }
207 #endif
208
68120d9 Convert event-config.h macros to avoid reserved identifiers
Nick Mathewson authored
209 #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND
90d4225 Fix some crazy macro mistakes in arc4random.c
Nick Mathewson authored
210 #define TRY_SEED_SYSCTL_BSD
211 static int
212 arc4_seed_sysctl_bsd(void)
213 {
214 /* Based on code from William Ahern and from OpenBSD, this function
215 * tries to use the KERN_ARND syscall to get entropy from the kernel.
216 * This can work even if /dev/urandom is inaccessible for some reason
217 * (e.g., we're running in a chroot). */
218 int mib[] = { CTL_KERN, KERN_ARND };
219 unsigned char buf[ADD_ENTROPY];
220 size_t len, n;
221 int i, any_set;
222
223 memset(buf, 0, sizeof(buf));
224
225 len = sizeof(buf);
226 if (sysctl(mib, 2, buf, &len, NULL, 0) == -1) {
227 for (len = 0; len < sizeof(buf); len += sizeof(unsigned)) {
228 n = sizeof(unsigned);
229 if (n + len > sizeof(buf))
230 n = len - sizeof(buf);
231 if (sysctl(mib, 2, &buf[len], &n, NULL, 0) == -1)
232 return -1;
233 }
234 }
235 /* make sure that the buffer actually got set. */
236 for (i=any_set=0; i<sizeof(buf); ++i) {
237 any_set |= buf[i];
238 }
239 if (!any_set)
240 return -1;
241
242 arc4_addrandom(buf, sizeof(buf));
243 memset(buf, 0, sizeof(buf));
244 arc4_seeded_ok = 1;
245 return 0;
246 }
247 #endif
68120d9 Convert event-config.h macros to avoid reserved identifiers
Nick Mathewson authored
248 #endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */
90d4225 Fix some crazy macro mistakes in arc4random.c
Nick Mathewson authored
249
20fda29 Try /proc on Linux as entropy fallback; use sysctl as last resort
Nick Mathewson authored
250 #ifdef __linux__
251 #define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
252 static int
253 arc4_seed_proc_sys_kernel_random_uuid(void)
254 {
255 /* Occasionally, somebody will make /proc/sys accessible in a chroot,
256 * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid.
257 * Its format is stupid, so we need to decode it from hex.
258 */
259 int fd;
260 char buf[128];
261 unsigned char entropy[64];
262 int bytes, n, i, nybbles;
263 for (bytes = 0; bytes<ADD_ENTROPY; ) {
8ac3c4c Have all visible internal function names end with an underscore.
Nick Mathewson authored
264 fd = evutil_open_closeonexec_("/proc/sys/kernel/random/uuid", O_RDONLY, 0);
20fda29 Try /proc on Linux as entropy fallback; use sysctl as last resort
Nick Mathewson authored
265 if (fd < 0)
266 return -1;
267 n = read(fd, buf, sizeof(buf));
268 close(fd);
269 if (n<=0)
270 return -1;
271 memset(entropy, 0, sizeof(entropy));
272 for (i=nybbles=0; i<n; ++i) {
8ac3c4c Have all visible internal function names end with an underscore.
Nick Mathewson authored
273 if (EVUTIL_ISXDIGIT_(buf[i])) {
274 int nyb = evutil_hex_char_to_int_(buf[i]);
20fda29 Try /proc on Linux as entropy fallback; use sysctl as last resort
Nick Mathewson authored
275 if (nybbles & 1) {
276 entropy[nybbles/2] |= nyb;
277 } else {
278 entropy[nybbles/2] |= nyb<<4;
279 }
280 ++nybbles;
281 }
282 }
283 if (nybbles < 2)
284 return -1;
285 arc4_addrandom(entropy, nybbles/2);
286 bytes += nybbles/2;
287 }
288 memset(entropy, 0, sizeof(entropy));
289 memset(buf, 0, sizeof(buf));
290 return 0;
291 }
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
292 #endif
293
9f560bf Use "_WIN32", not WIN32: it's standard and we don't need to fake it
Nick Mathewson authored
294 #ifndef _WIN32
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
295 #define TRY_SEED_URANDOM
296 static int
297 arc4_seed_urandom(void)
298 {
299 /* This is adapted from Tor's crypto_seed_rng() */
300 static const char *filenames[] = {
301 "/dev/srandom", "/dev/urandom", "/dev/random", NULL
302 };
303 unsigned char buf[ADD_ENTROPY];
304 int fd, i;
305 size_t n;
306
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
307 for (i = 0; filenames[i]; ++i) {
8ac3c4c Have all visible internal function names end with an underscore.
Nick Mathewson authored
308 fd = evutil_open_closeonexec_(filenames[i], O_RDONLY, 0);
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
309 if (fd<0)
310 continue;
311 n = read_all(fd, buf, sizeof(buf));
312 close(fd);
313 if (n != sizeof(buf))
314 return -1;
315 arc4_addrandom(buf, sizeof(buf));
316 memset(buf, 0, sizeof(buf));
317 arc4_seeded_ok = 1;
318 return 0;
319 }
320
321 return -1;
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
322 }
323 #endif
324
325 static int
326 arc4_seed(void)
327 {
328 int ok = 0;
329 /* We try every method that might work, and don't give up even if one
330 * does seem to work. There's no real harm in over-seeding, and if
331 * one of these sources turns out to be broken, that would be bad. */
332 #ifdef TRY_SEED_WIN32
333 if (0 == arc4_seed_win32())
334 ok = 1;
335 #endif
20fda29 Try /proc on Linux as entropy fallback; use sysctl as last resort
Nick Mathewson authored
336 #ifdef TRY_SEED_URANDOM
337 if (0 == arc4_seed_urandom())
338 ok = 1;
339 #endif
90d4225 Fix some crazy macro mistakes in arc4random.c
Nick Mathewson authored
340 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
20fda29 Try /proc on Linux as entropy fallback; use sysctl as last resort
Nick Mathewson authored
341 if (0 == arc4_seed_proc_sys_kernel_random_uuid())
342 ok = 1;
343 #endif
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
344 #ifdef TRY_SEED_SYSCTL_LINUX
20fda29 Try /proc on Linux as entropy fallback; use sysctl as last resort
Nick Mathewson authored
345 /* Apparently Linux is deprecating sysctl, and spewing warning
346 * messages when you try to use it. */
347 if (!ok && 0 == arc4_seed_sysctl_linux())
71fc3eb Seed the RNG using sysctl() as well as /dev/urandom
Nick Mathewson authored
348 ok = 1;
349 #endif
350 #ifdef TRY_SEED_SYSCTL_BSD
351 if (0 == arc4_seed_sysctl_bsd())
352 ok = 1;
353 #endif
354 return ok ? 0 : -1;
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
355 }
356
f736198 Fix a type error in our (unused) arc4random_stir()
Nick Mathewson authored
357 static int
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
358 arc4_stir(void)
359 {
360 int i;
361
362 if (!rs_initialized) {
363 arc4_init();
364 rs_initialized = 1;
365 }
366
367 arc4_seed();
f736198 Fix a type error in our (unused) arc4random_stir()
Nick Mathewson authored
368 if (!arc4_seeded_ok)
369 return -1;
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
370
371 /*
372 * Discard early keystream, as per recommendations in
373 * "Weaknesses in the Key Scheduling Algorithm of RC4" by
374 * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
375 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
376 *
377 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
378 * we drop at least 2*256 bytes, with 12*256 as a conservative
379 * value.
380 *
381 * RFC4345 says to drop 6*256.
382 *
383 * At least some versions of this code drop 4*256, in a mistaken
384 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
385 * to processor words.
386 *
387 * We add another sect to the cargo cult, and choose 12*256.
388 */
389 for (i = 0; i < 12*256; i++)
390 (void)arc4_getbyte();
391 arc4_count = BYTES_BEFORE_RESEED;
f736198 Fix a type error in our (unused) arc4random_stir()
Nick Mathewson authored
392
393 return 0;
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
394 }
395
ff2a134 Fix getpid() usage on Windows
Nick Mathewson authored
396
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
397 static void
398 arc4_stir_if_needed(void)
399 {
400 pid_t pid = getpid();
401
402 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
403 {
404 arc4_stir_pid = pid;
405 arc4_stir();
406 }
407 }
408
409 static inline unsigned char
410 arc4_getbyte(void)
411 {
412 unsigned char si, sj;
413
414 rs.i = (rs.i + 1);
415 si = rs.s[rs.i];
416 rs.j = (rs.j + si);
417 sj = rs.s[rs.j];
418 rs.s[rs.i] = sj;
419 rs.s[rs.j] = si;
420 return (rs.s[(si + sj) & 0xff]);
421 }
422
423 static inline unsigned int
424 arc4_getword(void)
425 {
426 unsigned int val;
427
428 val = arc4_getbyte() << 24;
429 val |= arc4_getbyte() << 16;
430 val |= arc4_getbyte() << 8;
431 val |= arc4_getbyte();
432
433 return val;
434 }
435
436 #ifndef ARC4RANDOM_NOSTIR
437 ARC4RANDOM_EXPORT int
438 arc4random_stir(void)
439 {
440 int val;
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
441 ARC4_LOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
442 val = arc4_stir();
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
443 ARC4_UNLOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
444 return val;
445 }
446 #endif
447
448 #ifndef ARC4RANDOM_NOADDRANDOM
449 ARC4RANDOM_EXPORT void
450 arc4random_addrandom(const unsigned char *dat, int datlen)
451 {
452 int j;
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
453 ARC4_LOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
454 if (!rs_initialized)
455 arc4_stir();
456 for (j = 0; j < datlen; j += 256) {
457 /* arc4_addrandom() ignores all but the first 256 bytes of
458 * its input. We want to make sure to look at ALL the
459 * data in 'dat', just in case the user is doing something
460 * crazy like passing us all the files in /var/log. */
461 arc4_addrandom(dat + j, datlen - j);
462 }
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
463 ARC4_UNLOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
464 }
465 #endif
466
467 #ifndef ARC4RANDOM_NORANDOM
4ec8fea Make RNG work when we have arc4random() but not arc4random_buf()
Nick Mathewson authored
468 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
469 arc4random(void)
470 {
4ec8fea Make RNG work when we have arc4random() but not arc4random_buf()
Nick Mathewson authored
471 ARC4RANDOM_UINT32 val;
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
472 ARC4_LOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
473 arc4_count -= 4;
474 arc4_stir_if_needed();
475 val = arc4_getword();
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
476 ARC4_UNLOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
477 return val;
478 }
479 #endif
480
481 ARC4RANDOM_EXPORT void
946b584 Clean up lingering _identifiers.
Nick Mathewson authored
482 arc4random_buf(void *buf_, size_t n)
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
483 {
946b584 Clean up lingering _identifiers.
Nick Mathewson authored
484 unsigned char *buf = buf_;
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
485 ARC4_LOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
486 arc4_stir_if_needed();
487 while (n--) {
488 if (--arc4_count <= 0)
489 arc4_stir();
490 buf[n] = arc4_getbyte();
491 }
cb9da0b Fix all identifiers with names beginning with underscore.
Nick Mathewson authored
492 ARC4_UNLOCK_();
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
493 }
494
495 #ifndef ARC4RANDOM_NOUNIFORM
496 /*
497 * Calculate a uniformly distributed random number less than upper_bound
498 * avoiding "modulo bias".
499 *
500 * Uniformity is achieved by generating new random numbers until the one
501 * returned is outside the range [0, 2**32 % upper_bound). This
502 * guarantees the selected random number will be inside
503 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
504 * after reduction modulo upper_bound.
505 */
506 ARC4RANDOM_EXPORT unsigned int
507 arc4random_uniform(unsigned int upper_bound)
508 {
4ec8fea Make RNG work when we have arc4random() but not arc4random_buf()
Nick Mathewson authored
509 ARC4RANDOM_UINT32 r, min;
d4de062 Add an arc4random implementation for use by evdns
Nick Mathewson authored
510
511 if (upper_bound < 2)
512 return 0;
513
514 #if (UINT_MAX > 0xffffffffUL)
515 min = 0x100000000UL % upper_bound;
516 #else
517 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
518 if (upper_bound > 0x80000000)
519 min = 1 + ~upper_bound; /* 2**32 - upper_bound */
520 else {
521 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
522 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
523 }
524 #endif
525
526 /*
527 * This could theoretically loop forever but each retry has
528 * p > 0.5 (worst case, usually far better) of selecting a
529 * number inside the range we need, so it should rarely need
530 * to re-roll.
531 */
532 for (;;) {
533 r = arc4random();
534 if (r >= min)
535 break;
536 }
537
538 return r % upper_bound;
539 }
540 #endif
Something went wrong with that request. Please try again.