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
6 * Note that in Libevent, this file isn't compiled directly. Instead,
7 * it's included from evutil_rand.c
11 * Copyright (c) 1996, David Mazieres <dm@uun.org>
12 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
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.
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.
28 * Arc4 random number generator for OpenBSD.
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.
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.
41 * RC4 is a registered trademark of RSA Laboratories.
44 #ifndef ARC4RANDOM_EXPORT
45 #define ARC4RANDOM_EXPORT
48 #ifndef ARC4RANDOM_UINT32
49 #define ARC4RANDOM_UINT32 uint32_t
52 #ifndef ARC4RANDOM_NO_INCLUDES
59 #include <sys/param.h>
61 #ifdef _EVENT_HAVE_SYS_SYSCTL_H
62 #include <sys/sysctl.h>
70 /* Add platform entropy 32 bytes (256 bits) at a time. */
71 #define ADD_ENTROPY 32
73 /* Re-seed from the platform RNG after generating this many bytes. */
74 #define BYTES_BEFORE_RESEED 1600000
83 #define getpid _getpid
87 static int rs_initialized
;
88 static struct arc4_stream rs
;
89 static pid_t arc4_stir_pid
;
90 static int arc4_count
;
91 static int arc4_seeded_ok
;
93 static inline unsigned char arc4_getbyte(void);
96 arc4random_memzero(void * const pnt
, const size_t size
)
98 volatile unsigned char *pnt_
= (volatile unsigned char *) pnt
;
99 size_t i
= (size_t) 0U;
111 for (n
= 0; n
< 256; n
++)
118 arc4_addrandom(const unsigned char *dat
, int datlen
)
124 for (n
= 0; n
< 256; n
++) {
127 rs
.j
= (rs
.j
+ si
+ dat
[n
% datlen
]);
128 rs
.s
[rs
.i
] = rs
.s
[rs
.j
];
136 read_all(int fd
, unsigned char *buf
, size_t count
)
141 while (numread
< count
) {
142 result
= read(fd
, buf
+numread
, count
-numread
);
145 else if (result
== 0)
150 return (ssize_t
)numread
;
155 #define TRY_SEED_WIN32
157 arc4_seed_win32(void)
159 /* This is adapted from Tor's crypto_seed_rng() */
160 static int provider_set
= 0;
161 static HCRYPTPROV provider
;
162 unsigned char buf
[ADD_ENTROPY
];
165 if (!CryptAcquireContext(&provider
, NULL
, NULL
, PROV_RSA_FULL
,
166 CRYPT_VERIFYCONTEXT
)) {
167 if (GetLastError() != (DWORD
)NTE_BAD_KEYSET
)
172 if (!CryptGenRandom(provider
, sizeof(buf
), buf
))
174 arc4_addrandom(buf
, sizeof(buf
));
175 arc4random_memzero(buf
, sizeof(buf
));
181 #if defined(_EVENT_HAVE_SYS_SYSCTL_H) && defined(_EVENT_HAVE_SYSCTL)
182 #if _EVENT_HAVE_DECL_CTL_KERN && _EVENT_HAVE_DECL_KERN_RANDOM && _EVENT_HAVE_DECL_RANDOM_UUID
183 #define TRY_SEED_SYSCTL_LINUX
185 arc4_seed_sysctl_linux(void)
187 /* Based on code by William Ahern, this function tries to use the
188 * RANDOM_UUID sysctl to get entropy from the kernel. This can work
189 * even if /dev/urandom is inaccessible for some reason (e.g., we're
190 * running in a chroot). */
191 int mib
[] = { CTL_KERN
, KERN_RANDOM
, RANDOM_UUID
};
192 unsigned char buf
[ADD_ENTROPY
];
197 memset(buf
, 0, sizeof(buf
));
199 for (len
= 0; len
< sizeof(buf
); len
+= n
) {
200 n
= sizeof(buf
) - len
;
202 if (0 != sysctl(mib
, 3, &buf
[len
], &n
, NULL
, 0))
205 /* make sure that the buffer actually got set. */
206 for (i
=0,any_set
=0; i
<sizeof(buf
); ++i
) {
212 arc4_addrandom(buf
, sizeof(buf
));
213 arc4random_memzero(buf
, sizeof(buf
));
219 #if _EVENT_HAVE_DECL_CTL_KERN && _EVENT_HAVE_DECL_KERN_ARND
220 #define TRY_SEED_SYSCTL_BSD
222 arc4_seed_sysctl_bsd(void)
224 /* Based on code from William Ahern and from OpenBSD, this function
225 * tries to use the KERN_ARND syscall to get entropy from the kernel.
226 * This can work even if /dev/urandom is inaccessible for some reason
227 * (e.g., we're running in a chroot). */
228 int mib
[] = { CTL_KERN
, KERN_ARND
};
229 unsigned char buf
[ADD_ENTROPY
];
233 memset(buf
, 0, sizeof(buf
));
236 if (sysctl(mib
, 2, buf
, &len
, NULL
, 0) == -1) {
237 for (len
= 0; len
< sizeof(buf
); len
+= sizeof(unsigned)) {
238 n
= sizeof(unsigned);
239 if (n
+ len
> sizeof(buf
))
240 n
= len
- sizeof(buf
);
241 if (sysctl(mib
, 2, &buf
[len
], &n
, NULL
, 0) == -1)
245 /* make sure that the buffer actually got set. */
246 for (i
=any_set
=0; i
<sizeof(buf
); ++i
) {
252 arc4_addrandom(buf
, sizeof(buf
));
253 arc4random_memzero(buf
, sizeof(buf
));
258 #endif /* defined(_EVENT_HAVE_SYS_SYSCTL_H) */
261 #define TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
263 arc4_seed_proc_sys_kernel_random_uuid(void)
265 /* Occasionally, somebody will make /proc/sys accessible in a chroot,
266 * but not /dev/urandom. Let's try /proc/sys/kernel/random/uuid.
267 * Its format is stupid, so we need to decode it from hex.
271 unsigned char entropy
[64];
272 int bytes
, n
, i
, nybbles
;
273 for (bytes
= 0; bytes
<ADD_ENTROPY
; ) {
275 fd
= evutil_open_closeonexec("/proc/sys/kernel/random/uuid", O_RDONLY
, 0);
278 n
= read(fd
, buf
, sizeof(buf
));
281 memset(entropy
, 0, sizeof(entropy
));
282 for (i
=nybbles
=0; i
<n
; ++i
) {
283 if (EVUTIL_ISXDIGIT(buf
[i
])) {
284 int nyb
= evutil_hex_char_to_int(buf
[i
]);
286 entropy
[nybbles
/2] |= nyb
;
288 entropy
[nybbles
/2] |= nyb
<<4;
295 arc4_addrandom(entropy
, nybbles
/2);
298 arc4random_memzero(entropy
, sizeof(entropy
));
299 arc4random_memzero(buf
, sizeof(buf
));
305 #define TRY_SEED_URANDOM
307 arc4_seed_urandom(void)
309 /* This is adapted from Tor's crypto_seed_rng() */
310 static const char *filenames
[] = {
311 "/dev/srandom", "/dev/urandom", "/dev/random", NULL
313 unsigned char buf
[ADD_ENTROPY
];
318 for (i
= 0; filenames
[i
]; ++i
) {
320 fd
= evutil_open_closeonexec(filenames
[i
], O_RDONLY
, 0);
323 n
= read_all(fd
, buf
, sizeof(buf
));
324 if (n
!= sizeof(buf
))
326 arc4_addrandom(buf
, sizeof(buf
));
327 arc4random_memzero(buf
, sizeof(buf
));
340 /* We try every method that might work, and don't give up even if one
341 * does seem to work. There's no real harm in over-seeding, and if
342 * one of these sources turns out to be broken, that would be bad. */
343 #ifdef TRY_SEED_WIN32
344 if (0 == arc4_seed_win32())
347 #ifdef TRY_SEED_URANDOM
348 if (0 == arc4_seed_urandom())
351 #ifdef TRY_SEED_PROC_SYS_KERNEL_RANDOM_UUID
352 if (0 == arc4_seed_proc_sys_kernel_random_uuid())
355 #ifdef TRY_SEED_SYSCTL_LINUX
356 /* Apparently Linux is deprecating sysctl, and spewing warning
357 * messages when you try to use it. */
358 if (!ok
&& 0 == arc4_seed_sysctl_linux())
361 #ifdef TRY_SEED_SYSCTL_BSD
362 if (0 == arc4_seed_sysctl_bsd())
373 if (!rs_initialized
) {
383 * Discard early keystream, as per recommendations in
384 * "Weaknesses in the Key Scheduling Algorithm of RC4" by
385 * Scott Fluhrer, Itsik Mantin, and Adi Shamir.
386 * http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps
388 * Ilya Mironov's "(Not So) Random Shuffles of RC4" suggests that
389 * we drop at least 2*256 bytes, with 12*256 as a conservative
392 * RFC4345 says to drop 6*256.
394 * At least some versions of this code drop 4*256, in a mistaken
395 * belief that "words" in the Fluhrer/Mantin/Shamir paper refers
396 * to processor words.
398 * We add another sect to the cargo cult, and choose 12*256.
400 for (i
= 0; i
< 12*256; i
++)
401 (void)arc4_getbyte();
402 arc4_count
= BYTES_BEFORE_RESEED
;
409 arc4_stir_if_needed(void)
411 pid_t pid
= getpid();
413 if (arc4_count
<= 0 || !rs_initialized
|| arc4_stir_pid
!= pid
)
420 static inline unsigned char
423 unsigned char si
, sj
;
431 return (rs
.s
[(si
+ sj
) & 0xff]);
434 static inline unsigned int
439 val
= arc4_getbyte() << 24;
440 val
|= arc4_getbyte() << 16;
441 val
|= arc4_getbyte() << 8;
442 val
|= arc4_getbyte();
447 #ifndef ARC4RANDOM_NOSTIR
448 ARC4RANDOM_EXPORT
int
449 arc4random_stir(void)
459 #ifndef ARC4RANDOM_NOADDRANDOM
460 ARC4RANDOM_EXPORT
void
461 arc4random_addrandom(const unsigned char *dat
, int datlen
)
467 for (j
= 0; j
< datlen
; j
+= 256) {
468 /* arc4_addrandom() ignores all but the first 256 bytes of
469 * its input. We want to make sure to look at ALL the
470 * data in 'dat', just in case the user is doing something
471 * crazy like passing us all the files in /var/log. */
472 arc4_addrandom(dat
+ j
, datlen
- j
);
478 #ifndef ARC4RANDOM_NORANDOM
479 ARC4RANDOM_EXPORT ARC4RANDOM_UINT32
482 ARC4RANDOM_UINT32 val
;
485 arc4_stir_if_needed();
486 val
= arc4_getword();
492 ARC4RANDOM_EXPORT
void
493 arc4random_buf(void *_buf
, size_t n
)
495 unsigned char *buf
= _buf
;
497 arc4_stir_if_needed();
499 if (--arc4_count
<= 0)
501 buf
[n
] = arc4_getbyte();
506 #ifndef ARC4RANDOM_NOUNIFORM
508 * Calculate a uniformly distributed random number less than upper_bound
509 * avoiding "modulo bias".
511 * Uniformity is achieved by generating new random numbers until the one
512 * returned is outside the range [0, 2**32 % upper_bound). This
513 * guarantees the selected random number will be inside
514 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
515 * after reduction modulo upper_bound.
517 ARC4RANDOM_EXPORT
unsigned int
518 arc4random_uniform(unsigned int upper_bound
)
520 ARC4RANDOM_UINT32 r
, min
;
525 #if (UINT_MAX > 0xffffffffUL)
526 min
= 0x100000000UL
% upper_bound
;
528 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
529 if (upper_bound
> 0x80000000)
530 min
= 1 + ~upper_bound
; /* 2**32 - upper_bound */
532 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
533 min
= ((0xffffffff - (upper_bound
* 2)) + 1) % upper_bound
;
538 * This could theoretically loop forever but each retry has
539 * p > 0.5 (worst case, usually far better) of selecting a
540 * number inside the range we need, so it should rarely need
549 return r
% upper_bound
;