arc4random.c revision 180672 
1/*
2 * Copyright (c) 1996, David Mazieres <dm@uun.org>
3 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18/*
19 * Arc4 random number generator for OpenBSD.
20 *
21 * This code is derived from section 17.1 of Applied Cryptography,
22 * second edition, which describes a stream cipher allegedly
23 * compatible with RSA Labs "RC4" cipher (the actual description of
24 * which is a trade secret).  The same algorithm is used as a stream
25 * cipher called "arcfour" in Tatu Ylonen's ssh package.
26 *
27 * Here the stream cipher has been modified always to include the time
28 * when initializing the state.  That makes it impossible to
29 * regenerate the same random sequence twice, so this can't be used
30 * for encryption, but will generate good random numbers.
31 *
32 * RC4 is a registered trademark of RSA Laboratories.
33 */
34
35#include <sys/cdefs.h>
36__FBSDID("$FreeBSD: head/lib/libc/gen/arc4random.c 180672 2008-07-21 20:04:32Z ache $");
37
38#include "namespace.h"
39#include <sys/types.h>
40#include <sys/time.h>
41#include <stdlib.h>
42#include <fcntl.h>
43#include <unistd.h>
44#include <pthread.h>
45
46#include "libc_private.h"
47#include "un-namespace.h"
48
49struct arc4_stream {
50	u_int8_t i;
51	u_int8_t j;
52	u_int8_t s[256];
53};
54
55static pthread_mutex_t	arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
56
57#define	RANDOMDEV	"/dev/urandom"
58#define	THREAD_LOCK()						\
59	do {							\
60		if (__isthreaded)				\
61			_pthread_mutex_lock(&arc4random_mtx);	\
62	} while (0)
63
64#define	THREAD_UNLOCK()						\
65	do {							\
66		if (__isthreaded)				\
67			_pthread_mutex_unlock(&arc4random_mtx);	\
68	} while (0)
69
70static struct arc4_stream rs;
71static int rs_initialized;
72static int rs_stired;
73static int arc4_count;
74
75static inline u_int8_t arc4_getbyte(void);
76static void arc4_stir(void);
77
78static inline void
79arc4_init(void)
80{
81	int     n;
82
83	for (n = 0; n < 256; n++)
84		rs.s[n] = n;
85	rs.i = 0;
86	rs.j = 0;
87}
88
89static inline void
90arc4_addrandom(u_char *dat, int datlen)
91{
92	int     n;
93	u_int8_t si;
94
95	rs.i--;
96	for (n = 0; n < 256; n++) {
97		rs.i = (rs.i + 1);
98		si = rs.s[rs.i];
99		rs.j = (rs.j + si + dat[n % datlen]);
100		rs.s[rs.i] = rs.s[rs.j];
101		rs.s[rs.j] = si;
102	}
103	rs.j = rs.i;
104}
105
106static void
107arc4_stir(void)
108{
109	int     fd, n;
110	struct {
111		struct timeval tv;
112		pid_t pid;
113		u_int8_t rnd[128 - sizeof(struct timeval) - sizeof(pid_t)];
114	}       rdat;
115
116	gettimeofday(&rdat.tv, NULL);
117	rdat.pid = getpid();
118	fd = _open(RANDOMDEV, O_RDONLY, 0);
119	if (fd >= 0) {
120		(void)_read(fd, rdat.rnd, sizeof(rdat.rnd));
121		(void)_close(fd);
122	}
123	/* fd < 0?  Ah, what the heck. We'll just take whatever was on the
124	 * stack... */
125
126	arc4_addrandom((u_char *)&rdat, sizeof(rdat));
127
128	/*
129	 * Throw away the first N bytes of output, as suggested in the
130	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
131	 * by Fluher, Mantin, and Shamir.  N=1024 is based on
132	 * suggestions in the paper "(Not So) Random Shuffles of RC4"
133	 * by Ilya Mironov.
134	 */
135	for (n = 0; n < 1024; n++)
136		(void)arc4_getbyte();
137	arc4_count = 1600000;
138}
139
140static inline u_int8_t
141arc4_getbyte(void)
142{
143	u_int8_t si, sj;
144
145	rs.i = (rs.i + 1);
146	si = rs.s[rs.i];
147	rs.j = (rs.j + si);
148	sj = rs.s[rs.j];
149	rs.s[rs.i] = sj;
150	rs.s[rs.j] = si;
151
152	return (rs.s[(si + sj) & 0xff]);
153}
154
155static inline u_int32_t
156arc4_getword(void)
157{
158	u_int32_t val;
159
160	val = arc4_getbyte() << 24;
161	val |= arc4_getbyte() << 16;
162	val |= arc4_getbyte() << 8;
163	val |= arc4_getbyte();
164
165	return (val);
166}
167
168static void
169arc4_check_init(void)
170{
171	if (!rs_initialized) {
172		arc4_init();
173		rs_initialized = 1;
174	}
175}
176
177static inline void
178arc4_check_stir(void)
179{
180	if (!rs_stired || arc4_count <= 0) {
181		arc4_stir();
182		rs_stired = 1;
183	}
184}
185
186void
187arc4random_stir(void)
188{
189	THREAD_LOCK();
190	arc4_check_init();
191	arc4_stir();
192	rs_stired = 1;
193	THREAD_UNLOCK();
194}
195
196void
197arc4random_addrandom(u_char *dat, int datlen)
198{
199	THREAD_LOCK();
200	arc4_check_init();
201	arc4_check_stir();
202	arc4_addrandom(dat, datlen);
203	THREAD_UNLOCK();
204}
205
206u_int32_t
207arc4random(void)
208{
209	u_int32_t rnd;
210
211	THREAD_LOCK();
212	arc4_check_init();
213	arc4_check_stir();
214	rnd = arc4_getword();
215	arc4_count -= 4;
216	THREAD_UNLOCK();
217
218	return (rnd);
219}
220
221void
222arc4random_buf(void *_buf, size_t n)
223{
224	u_char *buf = (u_char *)_buf;
225
226	THREAD_LOCK();
227	arc4_check_init();
228	while (n--) {
229		arc4_check_stir();
230		buf[n] = arc4_getbyte();
231		arc4_count--;
232	}
233	THREAD_UNLOCK();
234}
235
236#if 0
237/*-------- Test code for i386 --------*/
238#include <stdio.h>
239#include <machine/pctr.h>
240int
241main(int argc, char **argv)
242{
243	const int iter = 1000000;
244	int     i;
245	pctrval v;
246
247	v = rdtsc();
248	for (i = 0; i < iter; i++)
249		arc4random();
250	v = rdtsc() - v;
251	v /= iter;
252
253	printf("%qd cycles\n", v);
254}
255#endif
256