Line data Source code
1 : /* Portable arc4random.c based on arc4random.c from OpenBSD.
2 : * Portable version by Chris Davis, adapted for Libevent by Nick Mathewson
3 : * Copyright (c) 2010 Chris Davis, Niels Provos, and Nick Mathewson
4 : * Copyright (c) 2010-2012 Niels Provos and Nick Mathewson
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 :
48 : #ifndef ARC4RANDOM_UINT32
49 : #define ARC4RANDOM_UINT32 uint32_t
50 : #endif
51 :
52 : #ifndef ARC4RANDOM_NO_INCLUDES
53 : #include "evconfig-private.h"
54 : #ifdef _WIN32
55 : #include <wincrypt.h>
56 : #include <process.h>
57 : #else
58 : #include <fcntl.h>
59 : #include <unistd.h>
60 : #include <sys/param.h>
61 : #include <sys/time.h>
62 : #ifdef EVENT__HAVE_SYS_SYSCTL_H
63 : #include <sys/sysctl.h>
64 : #endif
65 : #endif
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 :
83 : #ifdef _WIN32
84 : #define getpid _getpid
85 : #define pid_t int
86 : #endif
87 :
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 0 : arc4_init(void)
98 : {
99 : int n;
100 :
101 0 : for (n = 0; n < 256; n++)
102 0 : rs.s[n] = n;
103 0 : rs.i = 0;
104 0 : rs.j = 0;
105 0 : }
106 :
107 : static inline void
108 0 : arc4_addrandom(const unsigned char *dat, int datlen)
109 : {
110 : int n;
111 : unsigned char si;
112 :
113 0 : rs.i--;
114 0 : for (n = 0; n < 256; n++) {
115 0 : rs.i = (rs.i + 1);
116 0 : si = rs.s[rs.i];
117 0 : rs.j = (rs.j + si + dat[n % datlen]);
118 0 : rs.s[rs.i] = rs.s[rs.j];
119 0 : rs.s[rs.j] = si;
120 : }
121 0 : rs.j = rs.i;
122 0 : }
123 :
124 : #ifndef _WIN32
125 : static ssize_t
126 0 : read_all(int fd, unsigned char *buf, size_t count)
127 : {
128 0 : size_t numread = 0;
129 : ssize_t result;
130 :
131 0 : while (numread < count) {
132 0 : result = read(fd, buf+numread, count-numread);
133 0 : if (result<0)
134 0 : return -1;
135 0 : else if (result == 0)
136 0 : break;
137 0 : numread += result;
138 : }
139 :
140 0 : return (ssize_t)numread;
141 : }
142 : #endif
143 :
144 : #ifdef _WIN32
145 : #define TRY_SEED_WIN32
146 : static int
147 : arc4_seed_win32(void)
148 : {
149 : /* This is adapted from Tor's crypto_seed_rng() */
150 : static int provider_set = 0;
151 : static HCRYPTPROV provider;
152 : unsigned char buf[ADD_ENTROPY];
153 :
154 : if (!provider_set) {
155 : if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
156 : CRYPT_VERIFYCONTEXT)) {
157 : if (GetLastError() != (DWORD)NTE_BAD_KEYSET)
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 : evutil_memclear_(buf, sizeof(buf));
166 : arc4_seeded_ok = 1;
167 : return 0;
168 : }
169 : #endif
170 :
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
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;
184 : unsigned i;
185 : int any_set;
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. */
196 : for (i=0,any_set=0; i<sizeof(buf); ++i) {
197 : any_set |= buf[i];
198 : }
199 : if (!any_set)
200 : return -1;
201 :
202 : arc4_addrandom(buf, sizeof(buf));
203 : evutil_memclear_(buf, sizeof(buf));
204 : arc4_seeded_ok = 1;
205 : return 0;
206 : }
207 : #endif
208 :
209 : #if EVENT__HAVE_DECL_CTL_KERN && EVENT__HAVE_DECL_KERN_ARND
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 : evutil_memclear_(buf, sizeof(buf));
244 : arc4_seeded_ok = 1;
245 : return 0;
246 : }
247 : #endif
248 : #endif /* defined(EVENT__HAVE_SYS_SYSCTL_H) */
249 :
250 : #ifdef __linux__
251 : #define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
252 : static int
253 0 : 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 0 : for (bytes = 0; bytes<ADD_ENTROPY; ) {
264 0 : fd = evutil_open_closeonexec_("/proc/sys/kernel/random/uuid", O_RDONLY, 0);
265 0 : if (fd < 0)
266 0 : return -1;
267 0 : n = read(fd, buf, sizeof(buf));
268 0 : close(fd);
269 0 : if (n<=0)
270 0 : return -1;
271 0 : memset(entropy, 0, sizeof(entropy));
272 0 : for (i=nybbles=0; i<n; ++i) {
273 0 : if (EVUTIL_ISXDIGIT_(buf[i])) {
274 0 : int nyb = evutil_hex_char_to_int_(buf[i]);
275 0 : if (nybbles & 1) {
276 0 : entropy[nybbles/2] |= nyb;
277 : } else {
278 0 : entropy[nybbles/2] |= nyb<<4;
279 : }
280 0 : ++nybbles;
281 : }
282 : }
283 0 : if (nybbles < 2)
284 0 : return -1;
285 0 : arc4_addrandom(entropy, nybbles/2);
286 0 : bytes += nybbles/2;
287 : }
288 0 : evutil_memclear_(entropy, sizeof(entropy));
289 0 : evutil_memclear_(buf, sizeof(buf));
290 0 : arc4_seeded_ok = 1;
291 0 : return 0;
292 : }
293 : #endif
294 :
295 : #ifndef _WIN32
296 : #define TRY_SEED_URANDOM
297 : static char *arc4random_urandom_filename = NULL;
298 :
299 0 : static int arc4_seed_urandom_helper_(const char *fname)
300 : {
301 : unsigned char buf[ADD_ENTROPY];
302 : int fd;
303 : size_t n;
304 :
305 0 : fd = evutil_open_closeonexec_(fname, O_RDONLY, 0);
306 0 : if (fd<0)
307 0 : return -1;
308 0 : n = read_all(fd, buf, sizeof(buf));
309 0 : close(fd);
310 0 : if (n != sizeof(buf))
311 0 : return -1;
312 0 : arc4_addrandom(buf, sizeof(buf));
313 0 : evutil_memclear_(buf, sizeof(buf));
314 0 : arc4_seeded_ok = 1;
315 0 : return 0;
316 : }
317 :
318 : static int
319 0 : arc4_seed_urandom(void)
320 : {
321 : /* This is adapted from Tor's crypto_seed_rng() */
322 : static const char *filenames[] = {
323 : "/dev/srandom", "/dev/urandom", "/dev/random", NULL
324 : };
325 : int i;
326 0 : if (arc4random_urandom_filename)
327 0 : return arc4_seed_urandom_helper_(arc4random_urandom_filename);
328 :
329 0 : for (i = 0; filenames[i]; ++i) {
330 0 : if (arc4_seed_urandom_helper_(filenames[i]) == 0) {
331 0 : return 0;
332 : }
333 : }
334 :
335 0 : return -1;
336 : }
337 : #endif
338 :
339 : static int
340 0 : arc4_seed(void)
341 : {
342 0 : int ok = 0;
343 : /* We try every method that might work, and don't give up even if one
344 : * does seem to work. There's no real harm in over-seeding, and if
345 : * one of these sources turns out to be broken, that would be bad. */
346 : #ifdef TRY_SEED_WIN32
347 : if (0 == arc4_seed_win32())
348 : ok = 1;
349 : #endif
350 : #ifdef TRY_SEED_URANDOM
351 0 : if (0 == arc4_seed_urandom())
352 0 : ok = 1;
353 : #endif
354 : #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
355 0 : if (arc4random_urandom_filename == NULL &&
356 0 : 0 == arc4_seed_proc_sys_kernel_random_uuid())
357 0 : ok = 1;
358 : #endif
359 : #ifdef TRY_SEED_SYSCTL_LINUX
360 : /* Apparently Linux is deprecating sysctl, and spewing warning
361 : * messages when you try to use it. */
362 : if (!ok && 0 == arc4_seed_sysctl_linux())
363 : ok = 1;
364 : #endif
365 : #ifdef TRY_SEED_SYSCTL_BSD
366 : if (0 == arc4_seed_sysctl_bsd())
367 : ok = 1;
368 : #endif
369 0 : return ok ? 0 : -1;
370 : }
371 :
372 : static int
373 0 : arc4_stir(void)
374 : {
375 : int i;
376 :
377 0 : if (!rs_initialized) {
378 0 : arc4_init();
379 0 : rs_initialized = 1;
380 : }
381 :
382 0 : arc4_seed();
383 0 : if (!arc4_seeded_ok)
384 0 : return -1;
385 :
386 : /*
387 : * Discard early keystream, as per recommendations in
388 : * "Weaknesses in the Key Scheduling Algorithm of RC4" by
389 : * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
390 : * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
391 : *
392 : * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
393 : * we drop at least 2*256 bytes, with 12*256 as a conservative
394 : * value.
395 : *
396 : * RFC4345 says to drop 6*256.
397 : *
398 : * At least some versions of this code drop 4*256, in a mistaken
399 : * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
400 : * to processor words.
401 : *
402 : * We add another sect to the cargo cult, and choose 12*256.
403 : */
404 0 : for (i = 0; i < 12*256; i++)
405 0 : (void)arc4_getbyte();
406 :
407 0 : arc4_count = BYTES_BEFORE_RESEED;
408 :
409 0 : return 0;
410 : }
411 :
412 :
413 : static void
414 0 : arc4_stir_if_needed(void)
415 : {
416 0 : pid_t pid = getpid();
417 :
418 0 : if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
419 : {
420 0 : arc4_stir_pid = pid;
421 0 : arc4_stir();
422 : }
423 0 : }
424 :
425 : static inline unsigned char
426 0 : arc4_getbyte(void)
427 : {
428 : unsigned char si, sj;
429 :
430 0 : rs.i = (rs.i + 1);
431 0 : si = rs.s[rs.i];
432 0 : rs.j = (rs.j + si);
433 0 : sj = rs.s[rs.j];
434 0 : rs.s[rs.i] = sj;
435 0 : rs.s[rs.j] = si;
436 0 : return (rs.s[(si + sj) & 0xff]);
437 : }
438 :
439 : static inline unsigned int
440 : arc4_getword(void)
441 : {
442 : unsigned int val;
443 :
444 : val = arc4_getbyte() << 24;
445 : val |= arc4_getbyte() << 16;
446 : val |= arc4_getbyte() << 8;
447 : val |= arc4_getbyte();
448 :
449 : return val;
450 : }
451 :
452 : #ifndef ARC4RANDOM_NOSTIR
453 : ARC4RANDOM_EXPORT int
454 : arc4random_stir(void)
455 : {
456 : int val;
457 : ARC4_LOCK_();
458 : val = arc4_stir();
459 : ARC4_UNLOCK_();
460 : return val;
461 : }
462 : #endif
463 :
464 : #ifndef ARC4RANDOM_NOADDRANDOM
465 : ARC4RANDOM_EXPORT void
466 0 : arc4random_addrandom(const unsigned char *dat, int datlen)
467 : {
468 : int j;
469 0 : ARC4_LOCK_();
470 0 : if (!rs_initialized)
471 0 : arc4_stir();
472 0 : for (j = 0; j < datlen; j += 256) {
473 : /* arc4_addrandom() ignores all but the first 256 bytes of
474 : * its input. We want to make sure to look at ALL the
475 : * data in 'dat', just in case the user is doing something
476 : * crazy like passing us all the files in /var/log. */
477 0 : arc4_addrandom(dat + j, datlen - j);
478 : }
479 0 : ARC4_UNLOCK_();
480 0 : }
481 : #endif
482 :
483 : #ifndef ARC4RANDOM_NORANDOM
484 : ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
485 : arc4random(void)
486 : {
487 : ARC4RANDOM_UINT32 val;
488 : ARC4_LOCK_();
489 : arc4_count -= 4;
490 : arc4_stir_if_needed();
491 : val = arc4_getword();
492 : ARC4_UNLOCK_();
493 : return val;
494 : }
495 : #endif
496 :
497 : ARC4RANDOM_EXPORT void
498 0 : arc4random_buf(void *buf_, size_t n)
499 : {
500 0 : unsigned char *buf = buf_;
501 0 : ARC4_LOCK_();
502 0 : arc4_stir_if_needed();
503 0 : while (n--) {
504 0 : if (--arc4_count <= 0)
505 0 : arc4_stir();
506 0 : buf[n] = arc4_getbyte();
507 : }
508 0 : ARC4_UNLOCK_();
509 0 : }
510 :
511 : #ifndef ARC4RANDOM_NOUNIFORM
512 : /*
513 : * Calculate a uniformly distributed random number less than upper_bound
514 : * avoiding "modulo bias".
515 : *
516 : * Uniformity is achieved by generating new random numbers until the one
517 : * returned is outside the range [0, 2**32 % upper_bound). This
518 : * guarantees the selected random number will be inside
519 : * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
520 : * after reduction modulo upper_bound.
521 : */
522 : ARC4RANDOM_EXPORT unsigned int
523 : arc4random_uniform(unsigned int upper_bound)
524 : {
525 : ARC4RANDOM_UINT32 r, min;
526 :
527 : if (upper_bound < 2)
528 : return 0;
529 :
530 : #if (UINT_MAX > 0xffffffffUL)
531 : min = 0x100000000UL % upper_bound;
532 : #else
533 : /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
534 : if (upper_bound > 0x80000000)
535 : min = 1 + ~upper_bound; /* 2**32 - upper_bound */
536 : else {
537 : /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
538 : min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
539 : }
540 : #endif
541 :
542 : /*
543 : * This could theoretically loop forever but each retry has
544 : * p > 0.5 (worst case, usually far better) of selecting a
545 : * number inside the range we need, so it should rarely need
546 : * to re-roll.
547 : */
548 : for (;;) {
549 : r = arc4random();
550 : if (r >= min)
551 : break;
552 : }
553 :
554 : return r % upper_bound;
555 : }
556 : #endif
|
