1 /* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */
4 * Copyright (c) 1996, David Mazieres <dm@uun.org>
5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * Arc4 random number generator for OpenBSD.
23 * This code is derived from section 17.1 of Applied Cryptography,
24 * second edition, which describes a stream cipher allegedly
25 * compatible with RSA Labs "RC4" cipher (the actual description of
26 * which is a trade secret). The same algorithm is used as a stream
27 * cipher called "arcfour" in Tatu Ylonen's ssh package.
29 * RC4 is a registered trademark of RSA Laboratories.
32 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD$");
35 #include "namespace.h"
40 #include <sys/types.h>
41 #include <sys/param.h>
42 #include <sys/sysctl.h>
46 #include "libc_private.h"
47 #include "un-namespace.h"
50 #define inline __inline
53 #endif /* !__GNUC__ */
61 static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
63 #define RANDOMDEV "/dev/random"
65 #define _ARC4_LOCK() \
68 _pthread_mutex_lock(&arc4random_mtx); \
71 #define _ARC4_UNLOCK() \
74 _pthread_mutex_unlock(&arc4random_mtx); \
77 static int rs_initialized;
78 static struct arc4_stream rs;
79 static pid_t arc4_stir_pid;
80 static int arc4_count;
82 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp,
83 void *newp, size_t newlen);
85 static inline u_int8_t arc4_getbyte(void);
86 static void arc4_stir(void);
93 for (n = 0; n < 256; n++)
100 arc4_addrandom(u_char *dat, int datlen)
106 for (n = 0; n < 256; n++) {
109 rs.j = (rs.j + si + dat[n % datlen]);
110 rs.s[rs.i] = rs.s[rs.j];
117 arc4_sysctl(u_char *buf, size_t size)
128 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)
148 if (!rs_initialized) {
153 if (arc4_sysctl((u_char *)&rdat, KEYSIZE) == KEYSIZE)
156 fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0);
158 if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
164 (void)gettimeofday(&rdat.tv, NULL);
166 /* We'll just take whatever was on the stack too... */
169 arc4_addrandom((u_char *)&rdat, KEYSIZE);
172 * Discard early keystream, as per recommendations in:
173 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
175 for (i = 0; i < 1024; i++)
176 (void)arc4_getbyte();
177 arc4_count = 1600000;
181 arc4_stir_if_needed(void)
183 pid_t pid = getpid();
185 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) {
191 static inline u_int8_t
202 return (rs.s[(si + sj) & 0xff]);
205 static inline u_int32_t
209 val = arc4_getbyte() << 24;
210 val |= arc4_getbyte() << 16;
211 val |= arc4_getbyte() << 8;
212 val |= arc4_getbyte();
217 arc4random_stir(void)
225 arc4random_addrandom(u_char *dat, int datlen)
230 arc4_addrandom(dat, datlen);
240 arc4_stir_if_needed();
241 val = arc4_getword();
247 arc4random_buf(void *_buf, size_t n)
249 u_char *buf = (u_char *)_buf;
251 arc4_stir_if_needed();
253 if (--arc4_count <= 0)
255 buf[n] = arc4_getbyte();
261 * Calculate a uniformly distributed random number less than upper_bound
262 * avoiding "modulo bias".
264 * Uniformity is achieved by generating new random numbers until the one
265 * returned is outside the range [0, 2**32 % upper_bound). This
266 * guarantees the selected random number will be inside
267 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
268 * after reduction modulo upper_bound.
271 arc4random_uniform(u_int32_t upper_bound)
278 /* 2**32 % x == (2**32 - x) % x */
279 min = -upper_bound % upper_bound;
281 * This could theoretically loop forever but each retry has
282 * p > 0.5 (worst case, usually far better) of selecting a
283 * number inside the range we need, so it should rarely need
292 return r % upper_bound;
296 /*-------- Test code for i386 --------*/
298 #include <machine/pctr.h>
300 main(int argc, char **argv)
302 const int iter = 1000000;
307 for (i = 0; i < iter; i++)
312 printf("%qd cycles\n", v);