arc4random.c revision 254219 
1/*-
2 * THE BEER-WARE LICENSE
3 *
4 * <dan@FreeBSD.ORG> wrote this file.  As long as you retain this notice you
5 * can do whatever you want with this stuff.  If we meet some day, and you
6 * think this stuff is worth it, you can buy me a beer in return.
7 *
8 * Dan Moschuk
9 */
10#if !defined(SOLARIS2) && !defined(__osf__)
11# include <sys/cdefs.h>
12#endif
13
14#include <sys/types.h>
15#include <sys/param.h>
16#ifdef __FreeBSD__
17# include <sys/kernel.h>
18#endif
19#if !defined(__osf__)
20# include <sys/random.h>
21#endif
22#ifdef __FreeBSD__
23# include <sys/libkern.h>
24#endif
25#include <sys/lock.h>
26#ifndef __osf__
27# include <sys/mutex.h>
28#endif
29#include <sys/time.h>
30
31#if defined(SOLARIS2) && (SOLARIS2 < 9)
32# include <netinet/in_systm.h>
33#endif
34#include <sys/socket.h>
35#include <net/if.h>
36#ifdef __osf__
37# include <net/route.h>
38#endif
39#include <netinet/in.h>
40#include <netinet/ip.h>
41#include "netinet/ip_compat.h"
42#ifdef HAS_SYS_MD5_H
43# include <sys/md5.h>
44#else
45# include "md5.h"
46#endif
47
48#ifdef NEED_LOCAL_RAND
49#if !defined(__GNUC__)
50# define __inline
51#endif
52
53#define	ARC4_RESEED_BYTES 65536
54#define	ARC4_RESEED_SECONDS 300
55#define	ARC4_KEYBYTES (256 / 8)
56
57static u_int8_t arc4_i, arc4_j;
58static int arc4_numruns = 0;
59static u_int8_t arc4_sbox[256];
60static time_t arc4_t_reseed;
61static ipfmutex_t arc4_mtx;
62static MD5_CTX md5ctx;
63
64static u_int8_t arc4_randbyte(void);
65static int ipf_read_random(void *dest, int length);
66
67static __inline void
68arc4_swap(u_int8_t *a, u_int8_t *b)
69{
70	u_int8_t c;
71
72	c = *a;
73	*a = *b;
74	*b = c;
75}
76
77/*
78 * Stir our S-box.
79 */
80static void
81arc4_randomstir (void)
82{
83	u_int8_t key[256];
84	int r, n;
85	struct timeval tv_now;
86
87	/*
88	 * XXX read_random() returns unsafe numbers if the entropy
89	 * device is not loaded -- MarkM.
90	 */
91	r = ipf_read_random(key, ARC4_KEYBYTES);
92	GETKTIME(&tv_now);
93	MUTEX_ENTER(&arc4_mtx);
94	/* If r == 0 || -1, just use what was on the stack. */
95	if (r > 0) {
96		for (n = r; n < sizeof(key); n++)
97			key[n] = key[n % r];
98	}
99
100	for (n = 0; n < 256; n++) {
101		arc4_j = (arc4_j + arc4_sbox[n] + key[n]) % 256;
102		arc4_swap(&arc4_sbox[n], &arc4_sbox[arc4_j]);
103	}
104
105	/* Reset for next reseed cycle. */
106	arc4_t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
107	arc4_numruns = 0;
108
109	/*
110	 * Throw away the first N words of output, as suggested in the
111	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
112	 * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
113	 */
114	for (n = 0; n < 256*4; n++)
115		arc4_randbyte();
116	MUTEX_EXIT(&arc4_mtx);
117}
118
119/*
120 * Initialize our S-box to its beginning defaults.
121 */
122static void
123arc4_init(void)
124{
125	int n;
126
127	MD5Init(&md5ctx);
128
129	MUTEX_INIT(&arc4_mtx, "arc4_mtx");
130	arc4_i = arc4_j = 0;
131	for (n = 0; n < 256; n++)
132		arc4_sbox[n] = (u_int8_t) n;
133
134	arc4_t_reseed = 0;
135}
136
137
138/*
139 * Generate a random byte.
140 */
141static u_int8_t
142arc4_randbyte(void)
143{
144	u_int8_t arc4_t;
145
146	arc4_i = (arc4_i + 1) % 256;
147	arc4_j = (arc4_j + arc4_sbox[arc4_i]) % 256;
148
149	arc4_swap(&arc4_sbox[arc4_i], &arc4_sbox[arc4_j]);
150
151	arc4_t = (arc4_sbox[arc4_i] + arc4_sbox[arc4_j]) % 256;
152	return arc4_sbox[arc4_t];
153}
154
155/*
156 * MPSAFE
157 */
158void
159arc4rand(void *ptr, u_int len, int reseed)
160{
161	u_int8_t *p;
162	struct timeval tv;
163
164	GETKTIME(&tv);
165	if (reseed ||
166	   (arc4_numruns > ARC4_RESEED_BYTES) ||
167	   (tv.tv_sec > arc4_t_reseed))
168		arc4_randomstir();
169
170	MUTEX_ENTER(&arc4_mtx);
171	arc4_numruns += len;
172	p = ptr;
173	while (len--)
174		*p++ = arc4_randbyte();
175	MUTEX_EXIT(&arc4_mtx);
176}
177
178uint32_t
179ipf_random(void)
180{
181	uint32_t ret;
182
183	arc4rand(&ret, sizeof ret, 0);
184	return ret;
185}
186
187
188static u_char pot[ARC4_RESEED_BYTES];
189static u_char *pothead = pot, *pottail = pot;
190static int inpot = 0;
191
192/*
193 * This is not very strong, and this is understood, but the aim isn't to
194 * be cryptographically strong - it is just to make up something that is
195 * pseudo random.
196 */
197void
198ipf_rand_push(void *src, int length)
199{
200	static int arc4_inited = 0;
201	u_char *nsrc;
202	int mylen;
203
204	if (arc4_inited == 0) {
205		arc4_init();
206		arc4_inited = 1;
207	}
208
209	if (length < 64) {
210		MD5Update(&md5ctx, src, length);
211		return;
212	}
213
214	nsrc = src;
215	mylen = length;
216
217#if defined(_SYS_MD5_H) && defined(SOLARIS2)
218# define	buf	buf_un.buf8
219#endif
220	MUTEX_ENTER(&arc4_mtx);
221	while ((mylen > 64)  && (sizeof(pot) - inpot > sizeof(md5ctx.buf))) {
222		MD5Update(&md5ctx, nsrc, 64);
223		mylen -= 64;
224		nsrc += 64;
225		if (pottail + sizeof(md5ctx.buf) > pot + sizeof(pot)) {
226			int left, numbytes;
227
228			numbytes = pot + sizeof(pot) - pottail;
229			bcopy(md5ctx.buf, pottail, numbytes);
230			left = sizeof(md5ctx.buf) - numbytes;
231			pottail = pot;
232			bcopy(md5ctx.buf + sizeof(md5ctx.buf) - left,
233			      pottail, left);
234			pottail += left;
235		} else {
236			bcopy(md5ctx.buf, pottail, sizeof(md5ctx.buf));
237			pottail += sizeof(md5ctx.buf);
238		}
239		inpot += 64;
240	}
241	MUTEX_EXIT(&arc4_mtx);
242#if defined(_SYS_MD5_H) && defined(SOLARIS2)
243# undef buf
244#endif
245}
246
247
248static int
249ipf_read_random(void *dest, int length)
250{
251	if (length > inpot)
252		return 0;
253
254	MUTEX_ENTER(&arc4_mtx);
255	if (pothead + length > pot + sizeof(pot)) {
256		int left, numbytes;
257
258		left = length;
259		numbytes = pot + sizeof(pot) - pothead;
260		bcopy(pothead, dest, numbytes);
261		left -= numbytes;
262		pothead = pot;
263		bcopy(pothead, dest + length - left, left);
264		pothead += left;
265	} else {
266		bcopy(pothead, dest, length);
267		pothead += length;
268	}
269	inpot -= length;
270	if (inpot == 0)
271		pothead = pottail = pot;
272	MUTEX_EXIT(&arc4_mtx);
273
274	return length;
275}
276
277#endif /* NEED_LOCAL_RAND */
278