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/param.h>
41 #include <sys/sysctl.h>
45 #include "libc_private.h"
46 #include "un-namespace.h"
49 #define inline __inline
52 #endif /* !__GNUC__ */
60 static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
62 #define RANDOMDEV "/dev/random"
64 #define _ARC4_LOCK() \
67 _pthread_mutex_lock(&arc4random_mtx); \
70 #define _ARC4_UNLOCK() \
73 _pthread_mutex_unlock(&arc4random_mtx); \
76 static int rs_initialized;
77 static struct arc4_stream rs;
78 static pid_t arc4_stir_pid;
79 static int arc4_count;
81 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp,
82 void *newp, size_t newlen);
84 static inline u_int8_t arc4_getbyte(void);
85 static void arc4_stir(void);
92 for (n = 0; n < 256; n++)
99 arc4_addrandom(u_char *dat, int datlen)
105 for (n = 0; n < 256; n++) {
108 rs.j = (rs.j + si + dat[n % datlen]);
109 rs.s[rs.i] = rs.s[rs.j];
116 arc4_sysctl(u_char *buf, size_t size)
127 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)
140 u_char rdat[KEYSIZE];
143 if (!rs_initialized) {
147 if (arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) {
149 * The sysctl cannot fail. If it does fail on some FreeBSD
150 * derivative or after some future change, just abort so that
151 * the problem will be found and fixed. abort is not normally
152 * suitable for a library but makes sense here.
157 arc4_addrandom(rdat, KEYSIZE);
160 * Discard early keystream, as per recommendations in:
161 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
163 for (i = 0; i < 3072; i++)
164 (void)arc4_getbyte();
165 arc4_count = 1600000;
169 arc4_stir_if_needed(void)
171 pid_t pid = getpid();
173 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) {
179 static inline u_int8_t
190 return (rs.s[(si + sj) & 0xff]);
193 static inline u_int32_t
197 val = arc4_getbyte() << 24;
198 val |= arc4_getbyte() << 16;
199 val |= arc4_getbyte() << 8;
200 val |= arc4_getbyte();
205 arc4random_stir(void)
213 arc4random_addrandom(u_char *dat, int datlen)
218 arc4_addrandom(dat, datlen);
228 arc4_stir_if_needed();
229 val = arc4_getword();
235 arc4random_buf(void *_buf, size_t n)
237 u_char *buf = (u_char *)_buf;
239 arc4_stir_if_needed();
241 if (--arc4_count <= 0)
243 buf[n] = arc4_getbyte();
249 * Calculate a uniformly distributed random number less than upper_bound
250 * avoiding "modulo bias".
252 * Uniformity is achieved by generating new random numbers until the one
253 * returned is outside the range [0, 2**32 % upper_bound). This
254 * guarantees the selected random number will be inside
255 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
256 * after reduction modulo upper_bound.
259 arc4random_uniform(u_int32_t upper_bound)
266 /* 2**32 % x == (2**32 - x) % x */
267 min = -upper_bound % upper_bound;
269 * This could theoretically loop forever but each retry has
270 * p > 0.5 (worst case, usually far better) of selecting a
271 * number inside the range we need, so it should rarely need
280 return r % upper_bound;
284 /*-------- Test code for i386 --------*/
286 #include <machine/pctr.h>
288 main(int argc, char **argv)
290 const int iter = 1000000;
295 for (i = 0; i < iter; i++)
300 printf("%qd cycles\n", v);