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;
63 #define _ARC4_LOCK() \
66 _pthread_mutex_lock(&arc4random_mtx); \
69 #define _ARC4_UNLOCK() \
72 _pthread_mutex_unlock(&arc4random_mtx); \
75 static int rs_initialized;
76 static struct arc4_stream rs;
77 static pid_t arc4_stir_pid;
78 static int arc4_count;
80 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp,
81 void *newp, size_t newlen);
83 static inline u_int8_t arc4_getbyte(void);
84 static void arc4_stir(void);
91 for (n = 0; n < 256; n++)
98 arc4_addrandom(u_char *dat, int datlen)
104 for (n = 0; n < 256; n++) {
107 rs.j = (rs.j + si + dat[n % datlen]);
108 rs.s[rs.i] = rs.s[rs.j];
115 __arc4_sysctl(u_char *buf, size_t size)
126 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)
139 u_char rdat[KEYSIZE];
142 if (!rs_initialized) {
146 if (__arc4_sysctl(rdat, KEYSIZE) != KEYSIZE) {
148 * The sysctl cannot fail. If it does fail on some FreeBSD
149 * derivative or after some future change, just abort so that
150 * the problem will be found and fixed. abort is not normally
151 * suitable for a library but makes sense here.
156 arc4_addrandom(rdat, KEYSIZE);
159 * Discard early keystream, as per recommendations in:
160 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
162 for (i = 0; i < 3072; i++)
163 (void)arc4_getbyte();
164 arc4_count = 1600000;
168 arc4_stir_if_needed(void)
170 pid_t pid = getpid();
172 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) {
178 static inline u_int8_t
189 return (rs.s[(si + sj) & 0xff]);
192 static inline u_int32_t
196 val = arc4_getbyte() << 24;
197 val |= arc4_getbyte() << 16;
198 val |= arc4_getbyte() << 8;
199 val |= arc4_getbyte();
204 arc4random_stir(void)
212 arc4random_addrandom(u_char *dat, int datlen)
217 arc4_addrandom(dat, datlen);
227 arc4_stir_if_needed();
228 val = arc4_getword();
234 arc4random_buf(void *_buf, size_t n)
236 u_char *buf = (u_char *)_buf;
238 arc4_stir_if_needed();
240 if (--arc4_count <= 0)
242 buf[n] = arc4_getbyte();
248 * Calculate a uniformly distributed random number less than upper_bound
249 * avoiding "modulo bias".
251 * Uniformity is achieved by generating new random numbers until the one
252 * returned is outside the range [0, 2**32 % upper_bound). This
253 * guarantees the selected random number will be inside
254 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
255 * after reduction modulo upper_bound.
258 arc4random_uniform(u_int32_t upper_bound)
265 /* 2**32 % x == (2**32 - x) % x */
266 min = -upper_bound % upper_bound;
268 * This could theoretically loop forever but each retry has
269 * p > 0.5 (worst case, usually far better) of selecting a
270 * number inside the range we need, so it should rarely need
279 return r % upper_bound;
283 /*-------- Test code for i386 --------*/
285 #include <machine/pctr.h>
287 main(int argc, char **argv)
289 const int iter = 1000000;
294 for (i = 0; i < iter; i++)
299 printf("%qd cycles\n", v);