arc4random.c revision 181261
126628Sache/*
2180672Sache * Copyright (c) 1996, David Mazieres <dm@uun.org>
3180672Sache * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
426628Sache *
5180672Sache * Permission to use, copy, modify, and distribute this software for any
6180672Sache * purpose with or without fee is hereby granted, provided that the above
7180672Sache * copyright notice and this permission notice appear in all copies.
8180672Sache *
9180672Sache * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10180672Sache * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11180672Sache * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12180672Sache * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13180672Sache * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14180672Sache * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15180672Sache * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
1626628Sache */
1726628Sache
1826628Sache/*
19180672Sache * Arc4 random number generator for OpenBSD.
20180672Sache *
2126628Sache * This code is derived from section 17.1 of Applied Cryptography,
2226628Sache * second edition, which describes a stream cipher allegedly
2326628Sache * compatible with RSA Labs "RC4" cipher (the actual description of
2426628Sache * which is a trade secret).  The same algorithm is used as a stream
2526628Sache * cipher called "arcfour" in Tatu Ylonen's ssh package.
2626628Sache *
2726628Sache * Here the stream cipher has been modified always to include the time
2826628Sache * when initializing the state.  That makes it impossible to
2926628Sache * regenerate the same random sequence twice, so this can't be used
3026628Sache * for encryption, but will generate good random numbers.
3126628Sache *
3226628Sache * RC4 is a registered trademark of RSA Laboratories.
3326628Sache */
3426628Sache
3592986Sobrien#include <sys/cdefs.h>
3692986Sobrien__FBSDID("$FreeBSD: head/lib/libc/gen/arc4random.c 181261 2008-08-03 20:15:22Z ache $");
3792986Sobrien
3871579Sdeischen#include "namespace.h"
3992986Sobrien#include <sys/types.h>
4092986Sobrien#include <sys/time.h>
4126628Sache#include <stdlib.h>
4226628Sache#include <fcntl.h>
4326628Sache#include <unistd.h>
44127373Sgreen#include <pthread.h>
45127373Sgreen
46127373Sgreen#include "libc_private.h"
4771579Sdeischen#include "un-namespace.h"
4826628Sache
4926628Sachestruct arc4_stream {
5026628Sache	u_int8_t i;
5126628Sache	u_int8_t j;
5226628Sache	u_int8_t s[256];
5326628Sache};
5426628Sache
55127373Sgreenstatic pthread_mutex_t	arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
56127373Sgreen
57180804Sache#define	RANDOMDEV	"/dev/urandom"
58181261Sache#define KEYSIZE		128
59127373Sgreen#define	THREAD_LOCK()						\
60127373Sgreen	do {							\
61127373Sgreen		if (__isthreaded)				\
62127373Sgreen			_pthread_mutex_lock(&arc4random_mtx);	\
63127373Sgreen	} while (0)
64127373Sgreen
65127373Sgreen#define	THREAD_UNLOCK()						\
66127373Sgreen	do {							\
67127373Sgreen		if (__isthreaded)				\
68127373Sgreen			_pthread_mutex_unlock(&arc4random_mtx);	\
69127373Sgreen	} while (0)
70127373Sgreen
71127373Sgreenstatic struct arc4_stream rs;
7226628Sachestatic int rs_initialized;
73127373Sgreenstatic int rs_stired;
74162995Sachestatic int arc4_count;
7526628Sache
76180672Sachestatic inline u_int8_t arc4_getbyte(void);
77180672Sachestatic void arc4_stir(void);
78124741Sdas
7926628Sachestatic inline void
80180672Sachearc4_init(void)
8126628Sache{
8226628Sache	int     n;
8326628Sache
8426628Sache	for (n = 0; n < 256; n++)
85180672Sache		rs.s[n] = n;
86180672Sache	rs.i = 0;
87180672Sache	rs.j = 0;
8826628Sache}
8926628Sache
9026628Sachestatic inline void
91180672Sachearc4_addrandom(u_char *dat, int datlen)
9226628Sache{
9326628Sache	int     n;
9426628Sache	u_int8_t si;
9526628Sache
96180672Sache	rs.i--;
9726628Sache	for (n = 0; n < 256; n++) {
98180672Sache		rs.i = (rs.i + 1);
99180672Sache		si = rs.s[rs.i];
100180672Sache		rs.j = (rs.j + si + dat[n % datlen]);
101180672Sache		rs.s[rs.i] = rs.s[rs.j];
102180672Sache		rs.s[rs.j] = si;
10326628Sache	}
104180672Sache	rs.j = rs.i;
10526628Sache}
10626628Sache
10726628Sachestatic void
108180672Sachearc4_stir(void)
10926628Sache{
110181261Sache	int done, fd, n;
11126628Sache	struct {
112181261Sache		struct timeval	tv;
113181261Sache		pid_t 		pid;
114181261Sache		u_int8_t 	rnd[KEYSIZE];
115181261Sache	} rdat;
11626628Sache
117127373Sgreen	fd = _open(RANDOMDEV, O_RDONLY, 0);
118181261Sache	done = 0;
11926628Sache	if (fd >= 0) {
120181261Sache		if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
121181261Sache			done = 1;
122181261Sache		(void)_close(fd);
123127373Sgreen	}
124181261Sache	if (!done) {
125181261Sache		(void)gettimeofday(&rdat.tv, NULL);
126181261Sache		rdat.pid = getpid();
127181261Sache		/* We'll just take whatever was on the stack too... */
128181261Sache	}
12926628Sache
130181261Sache	arc4_addrandom((u_char *)&rdat, KEYSIZE);
131124741Sdas
132124741Sdas	/*
133124741Sdas	 * Throw away the first N bytes of output, as suggested in the
134124741Sdas	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
135180804Sache	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
136124741Sdas	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
137124741Sdas	 * by Ilya Mironov.
138124741Sdas	 */
139180804Sache	for (n = 0; n < 1024; n++)
140180804Sache		(void) arc4_getbyte();
141180655Sache	arc4_count = 1600000;
14226628Sache}
14326628Sache
14426628Sachestatic inline u_int8_t
145180672Sachearc4_getbyte(void)
14626628Sache{
14726628Sache	u_int8_t si, sj;
14826628Sache
149180672Sache	rs.i = (rs.i + 1);
150180672Sache	si = rs.s[rs.i];
151180672Sache	rs.j = (rs.j + si);
152180672Sache	sj = rs.s[rs.j];
153180672Sache	rs.s[rs.i] = sj;
154180672Sache	rs.s[rs.j] = si;
155126180Sgreen
156180672Sache	return (rs.s[(si + sj) & 0xff]);
15726628Sache}
15826628Sache
15926628Sachestatic inline u_int32_t
160180672Sachearc4_getword(void)
16126628Sache{
16226628Sache	u_int32_t val;
163126180Sgreen
164180672Sache	val = arc4_getbyte() << 24;
165180672Sache	val |= arc4_getbyte() << 16;
166180672Sache	val |= arc4_getbyte() << 8;
167180672Sache	val |= arc4_getbyte();
168126180Sgreen
169126180Sgreen	return (val);
17026628Sache}
17126628Sache
172127373Sgreenstatic void
173127373Sgreenarc4_check_init(void)
17426628Sache{
17526628Sache	if (!rs_initialized) {
176180672Sache		arc4_init();
177180804Sache		rs_initialized = 1;
17826628Sache	}
179127373Sgreen}
180127373Sgreen
181180657Sachestatic inline void
182127373Sgreenarc4_check_stir(void)
183127373Sgreen{
184180656Sache	if (!rs_stired || arc4_count <= 0) {
185180672Sache		arc4_stir();
186127373Sgreen		rs_stired = 1;
187127373Sgreen	}
188127373Sgreen}
189127373Sgreen
190127373Sgreenvoid
191169981Sdelphijarc4random_stir(void)
192127373Sgreen{
193127373Sgreen	THREAD_LOCK();
194127373Sgreen	arc4_check_init();
195180672Sache	arc4_stir();
196127373Sgreen	THREAD_UNLOCK();
19726628Sache}
19826628Sache
19926628Sachevoid
200169981Sdelphijarc4random_addrandom(u_char *dat, int datlen)
20126628Sache{
202127373Sgreen	THREAD_LOCK();
203127373Sgreen	arc4_check_init();
204127373Sgreen	arc4_check_stir();
205180672Sache	arc4_addrandom(dat, datlen);
206127373Sgreen	THREAD_UNLOCK();
20726628Sache}
20826628Sache
20926628Sacheu_int32_t
210169981Sdelphijarc4random(void)
21126628Sache{
212127373Sgreen	u_int32_t rnd;
213126180Sgreen
214127373Sgreen	THREAD_LOCK();
215127373Sgreen	arc4_check_init();
216127373Sgreen	arc4_check_stir();
217180672Sache	rnd = arc4_getword();
218180656Sache	arc4_count -= 4;
219127373Sgreen	THREAD_UNLOCK();
220127373Sgreen
221127373Sgreen	return (rnd);
22226628Sache}
22326628Sache
224180657Sachevoid
225180657Sachearc4random_buf(void *_buf, size_t n)
226180657Sache{
227180657Sache	u_char *buf = (u_char *)_buf;
228180657Sache
229180657Sache	THREAD_LOCK();
230180657Sache	arc4_check_init();
231180657Sache	while (n--) {
232180657Sache		arc4_check_stir();
233180672Sache		buf[n] = arc4_getbyte();
234180657Sache		arc4_count--;
235180657Sache	}
236180657Sache	THREAD_UNLOCK();
237180657Sache}
238180657Sache
239180688Sache/*
240180688Sache * Calculate a uniformly distributed random number less than upper_bound
241180688Sache * avoiding "modulo bias".
242180688Sache *
243180688Sache * Uniformity is achieved by generating new random numbers until the one
244180688Sache * returned is outside the range [0, 2**32 % upper_bound).  This
245180688Sache * guarantees the selected random number will be inside
246180688Sache * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
247180688Sache * after reduction modulo upper_bound.
248180688Sache */
249180688Sacheu_int32_t
250180688Sachearc4random_uniform(u_int32_t upper_bound)
251180688Sache{
252180688Sache	u_int32_t r, min;
253180688Sache
254180688Sache	if (upper_bound < 2)
255180690Sache		return (0);
256180688Sache
257180688Sache#if (ULONG_MAX > 0xffffffffUL)
258180688Sache	min = 0x100000000UL % upper_bound;
259180688Sache#else
260180688Sache	/* Calculate (2**32 % upper_bound) avoiding 64-bit math */
261180688Sache	if (upper_bound > 0x80000000)
262180688Sache		min = 1 + ~upper_bound;		/* 2**32 - upper_bound */
263180688Sache	else {
264180688Sache		/* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
265180688Sache		min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
266180688Sache	}
267180688Sache#endif
268180688Sache
269180688Sache	/*
270180688Sache	 * This could theoretically loop forever but each retry has
271180688Sache	 * p > 0.5 (worst case, usually far better) of selecting a
272180688Sache	 * number inside the range we need, so it should rarely need
273180688Sache	 * to re-roll.
274180688Sache	 */
275180688Sache	for (;;) {
276180688Sache		r = arc4random();
277180688Sache		if (r >= min)
278180688Sache			break;
279180688Sache	}
280180688Sache
281180688Sache	return (r % upper_bound);
282180688Sache}
283180688Sache
28426628Sache#if 0
28526628Sache/*-------- Test code for i386 --------*/
28626628Sache#include <stdio.h>
28726628Sache#include <machine/pctr.h>
28826628Sacheint
28926628Sachemain(int argc, char **argv)
29026628Sache{
29126628Sache	const int iter = 1000000;
29226628Sache	int     i;
29326628Sache	pctrval v;
29426628Sache
29526628Sache	v = rdtsc();
29626628Sache	for (i = 0; i < iter; i++)
29726628Sache		arc4random();
29826628Sache	v = rdtsc() - v;
29926628Sache	v /= iter;
30026628Sache
30126628Sache	printf("%qd cycles\n", v);
30226628Sache}
30326628Sache#endif
304