Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 541 lines (484 sloc) 12.758 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.