1 /* $OpenBSD: arc4random.c,v 1.22 2010/12/22 08:23:42 otto 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>
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 static inline u_int8_t arc4_getbyte(void);
82 static void arc4_stir(void);
89 for (n = 0; n < 256; n++)
96 arc4_addrandom(u_char *dat, int datlen)
102 for (n = 0; n < 256; n++) {
105 rs.j = (rs.j + si + dat[n % datlen]);
106 rs.s[rs.i] = rs.s[rs.j];
122 if (!rs_initialized) {
126 fd = _open(RANDOMDEV, O_RDONLY, 0);
129 if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
134 (void)gettimeofday(&rdat.tv, NULL);
136 /* We'll just take whatever was on the stack too... */
139 arc4_addrandom((u_char *)&rdat, KEYSIZE);
142 * Discard early keystream, as per recommendations in:
143 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
145 for (i = 0; i < 1024; i++)
146 (void)arc4_getbyte();
147 arc4_count = 1600000;
151 arc4_stir_if_needed(void)
153 pid_t pid = getpid();
155 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid)
162 static inline u_int8_t
173 return (rs.s[(si + sj) & 0xff]);
176 static inline u_int32_t
180 val = arc4_getbyte() << 24;
181 val |= arc4_getbyte() << 16;
182 val |= arc4_getbyte() << 8;
183 val |= arc4_getbyte();
188 arc4random_stir(void)
196 arc4random_addrandom(u_char *dat, int datlen)
201 arc4_addrandom(dat, datlen);
211 arc4_stir_if_needed();
212 val = arc4_getword();
218 arc4random_buf(void *_buf, size_t n)
220 u_char *buf = (u_char *)_buf;
222 arc4_stir_if_needed();
224 if (--arc4_count <= 0)
226 buf[n] = arc4_getbyte();
232 * Calculate a uniformly distributed random number less than upper_bound
233 * avoiding "modulo bias".
235 * Uniformity is achieved by generating new random numbers until the one
236 * returned is outside the range [0, 2**32 % upper_bound). This
237 * guarantees the selected random number will be inside
238 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
239 * after reduction modulo upper_bound.
242 arc4random_uniform(u_int32_t upper_bound)
249 #if (ULONG_MAX > 0xffffffffUL)
250 min = 0x100000000UL % upper_bound;
252 /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
253 if (upper_bound > 0x80000000)
254 min = 1 + ~upper_bound; /* 2**32 - upper_bound */
256 /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
257 min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
262 * This could theoretically loop forever but each retry has
263 * p > 0.5 (worst case, usually far better) of selecting a
264 * number inside the range we need, so it should rarely need
273 return r % upper_bound;
277 /*-------- Test code for i386 --------*/
279 #include <machine/pctr.h>
281 main(int argc, char **argv)
283 const int iter = 1000000;
288 for (i = 0; i < iter; i++)
293 printf("%qd cycles\n", v);