xref: /freebsd/sys/libkern/arc4random.c (revision 1fb62fb074788ca4713551be09d6569966a3abee)
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 
11 #include <sys/cdefs.h>
12 __FBSDID("$FreeBSD$");
13 
14 #include <sys/types.h>
15 #include <sys/param.h>
16 #include <sys/kernel.h>
17 #include <sys/random.h>
18 #include <sys/libkern.h>
19 #include <sys/lock.h>
20 #include <sys/mutex.h>
21 #include <sys/time.h>
22 #include <sys/smp.h>
23 #include <sys/malloc.h>
24 
25 #define	ARC4_RESEED_BYTES 65536
26 #define	ARC4_RESEED_SECONDS 300
27 #define	ARC4_KEYBYTES 256
28 
29 int arc4rand_iniseed_state = ARC4_ENTR_NONE;
30 
31 MALLOC_DEFINE(M_ARC4RANDOM, "arc4random", "arc4random structures");
32 
33 struct arc4_s {
34 	struct mtx mtx;
35 	u_int8_t i, j;
36 	int numruns;
37 	u_int8_t sbox[256];
38 	time_t t_reseed;
39 
40 } __aligned(CACHE_LINE_SIZE);
41 
42 static struct arc4_s *arc4inst = NULL;
43 
44 #define ARC4_FOREACH(_arc4) \
45 	for (_arc4 = &arc4inst[0]; _arc4 <= &arc4inst[mp_maxid]; _arc4++)
46 
47 static u_int8_t arc4_randbyte(struct arc4_s *arc4);
48 
49 static __inline void
50 arc4_swap(u_int8_t *a, u_int8_t *b)
51 {
52 	u_int8_t c;
53 
54 	c = *a;
55 	*a = *b;
56 	*b = c;
57 }
58 
59 /*
60  * Stir our S-box.
61  */
62 static void
63 arc4_randomstir(struct arc4_s* arc4)
64 {
65 	u_int8_t key[ARC4_KEYBYTES];
66 	int n;
67 	struct timeval tv_now;
68 
69 	/*
70 	 * XXX: FIX!! This isn't brilliant. Need more confidence.
71 	 * This returns zero entropy before random(4) is seeded.
72 	 */
73 	(void)read_random(key, ARC4_KEYBYTES);
74 	getmicrouptime(&tv_now);
75 	mtx_lock(&arc4->mtx);
76 	for (n = 0; n < 256; n++) {
77 		arc4->j = (arc4->j + arc4->sbox[n] + key[n]) % 256;
78 		arc4_swap(&arc4->sbox[n], &arc4->sbox[arc4->j]);
79 	}
80 	arc4->i = arc4->j = 0;
81 	/* Reset for next reseed cycle. */
82 	arc4->t_reseed = tv_now.tv_sec + ARC4_RESEED_SECONDS;
83 	arc4->numruns = 0;
84 	/*
85 	 * Throw away the first N words of output, as suggested in the
86 	 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
87 	 * by Fluher, Mantin, and Shamir.  (N = 256 in our case.)
88 	 *
89 	 * http://dl.acm.org/citation.cfm?id=646557.694759
90 	 */
91 	for (n = 0; n < 256*4; n++)
92 		arc4_randbyte(arc4);
93 
94 	mtx_unlock(&arc4->mtx);
95 }
96 
97 /*
98  * Initialize our S-box to its beginning defaults.
99  */
100 static void
101 arc4_init(void)
102 {
103 	struct arc4_s *arc4;
104 	int n;
105 
106 	arc4inst = malloc((mp_maxid + 1) * sizeof(struct arc4_s),
107 			M_ARC4RANDOM, M_NOWAIT | M_ZERO);
108 	KASSERT(arc4inst != NULL, ("arc4_init: memory allocation error"));
109 
110 	ARC4_FOREACH(arc4) {
111 		mtx_init(&arc4->mtx, "arc4_mtx", NULL, MTX_DEF);
112 
113 		arc4->i = arc4->j = 0;
114 		for (n = 0; n < 256; n++)
115 			arc4->sbox[n] = (u_int8_t) n;
116 
117 		arc4->t_reseed = -1;
118 		arc4->numruns = 0;
119 	}
120 }
121 SYSINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_init, NULL);
122 
123 
124 static void
125 arc4_uninit(void)
126 {
127 	struct arc4_s *arc4;
128 
129 	ARC4_FOREACH(arc4) {
130 		mtx_destroy(&arc4->mtx);
131 	}
132 
133 	free(arc4inst, M_ARC4RANDOM);
134 }
135 
136 SYSUNINIT(arc4, SI_SUB_LOCK, SI_ORDER_ANY, arc4_uninit, NULL);
137 
138 
139 /*
140  * Generate a random byte.
141  */
142 static u_int8_t
143 arc4_randbyte(struct arc4_s *arc4)
144 {
145 	u_int8_t arc4_t;
146 
147 	arc4->i = (arc4->i + 1) % 256;
148 	arc4->j = (arc4->j + arc4->sbox[arc4->i]) % 256;
149 
150 	arc4_swap(&arc4->sbox[arc4->i], &arc4->sbox[arc4->j]);
151 
152 	arc4_t = (arc4->sbox[arc4->i] + arc4->sbox[arc4->j]) % 256;
153 	return arc4->sbox[arc4_t];
154 }
155 
156 /*
157  * MPSAFE
158  */
159 void
160 arc4rand(void *ptr, u_int len, int reseed)
161 {
162 	u_char *p;
163 	struct timeval tv;
164 	struct arc4_s *arc4;
165 
166 	if (reseed || atomic_cmpset_int(&arc4rand_iniseed_state,
167 			ARC4_ENTR_HAVE, ARC4_ENTR_SEED)) {
168 		ARC4_FOREACH(arc4)
169 			arc4_randomstir(arc4);
170 	}
171 
172 	arc4 = &arc4inst[curcpu];
173 	getmicrouptime(&tv);
174 	if ((arc4->numruns > ARC4_RESEED_BYTES) ||
175 		(tv.tv_sec > arc4->t_reseed))
176 		arc4_randomstir(arc4);
177 
178 	mtx_lock(&arc4->mtx);
179 	arc4->numruns += len;
180 	p = ptr;
181 	while (len--)
182 		*p++ = arc4_randbyte(arc4);
183 	mtx_unlock(&arc4->mtx);
184 }
185 
186 uint32_t
187 arc4random(void)
188 {
189 	uint32_t ret;
190 
191 	arc4rand(&ret, sizeof ret, 0);
192 	return ret;
193 }
194