arc4random.c revision 1.22 1 /* $NetBSD: arc4random.c,v 1.22 2014/06/07 20:55:47 roy Exp $ */
2 /* $OpenBSD: arc4random.c,v 1.6 2001/06/05 05:05:38 pvalchev Exp $ */
3
4 /*
5 * Arc4 random number generator for OpenBSD.
6 * Copyright 1996 David Mazieres <dm (at) lcs.mit.edu>.
7 *
8 * Modification and redistribution in source and binary forms is
9 * permitted provided that due credit is given to the author and the
10 * OpenBSD project by leaving this copyright notice intact.
11 */
12
13 /*
14 * This code is derived from section 17.1 of Applied Cryptography,
15 * second edition, which describes a stream cipher allegedly
16 * compatible with RSA Labs "RC4" cipher (the actual description of
17 * which is a trade secret). The same algorithm is used as a stream
18 * cipher called "arcfour" in Tatu Ylonen's ssh package.
19 *
20 * Here the stream cipher has been modified always to include the time
21 * when initializing the state. That makes it impossible to
22 * regenerate the same random sequence twice, so this can't be used
23 * for encryption, but will generate good random numbers.
24 *
25 * RC4 is a registered trademark of RSA Laboratories.
26 */
27
28 #include <sys/cdefs.h>
29 #if defined(LIBC_SCCS) && !defined(lint)
30 __RCSID("$NetBSD: arc4random.c,v 1.22 2014/06/07 20:55:47 roy Exp $");
31 #endif /* LIBC_SCCS and not lint */
32
33 #include "namespace.h"
34 #include "reentrant.h"
35 #include <fcntl.h>
36 #include <pthread.h>
37 #include <stdbool.h>
38 #include <stdlib.h>
39 #include <unistd.h>
40 #include <sys/types.h>
41 #include <sys/param.h>
42 #include <sys/time.h>
43 #include <sys/sysctl.h>
44
45 #ifdef __weak_alias
46 __weak_alias(arc4random,_arc4random)
47 __weak_alias(arc4random_addrandom,_arc4random_addrandom)
48 __weak_alias(arc4random_buf,_arc4random_buf)
49 __weak_alias(arc4random_stir,_arc4random_stir)
50 __weak_alias(arc4random_uniform,_arc4random_uniform)
51 #endif
52
53 struct arc4_stream {
54 bool inited;
55 uint8_t i;
56 uint8_t j;
57 uint8_t s[(uint8_t)~0u + 1u]; /* 256 to you and me */
58 size_t count;
59 mutex_t mtx;
60 };
61
62 #ifdef _REENTRANT
63 #define LOCK(rs) if (__isthreaded) mutex_lock(&(rs)->mtx);
64 #define UNLOCK(rs) if (__isthreaded) mutex_unlock(&(rs)->mtx);
65 #else
66 #define LOCK(rs)
67 #define UNLOCK(rs)
68 #endif
69
70 #define S(n) (n)
71 #define S4(n) S(n), S(n + 1), S(n + 2), S(n + 3)
72 #define S16(n) S4(n), S4(n + 4), S4(n + 8), S4(n + 12)
73 #define S64(n) S16(n), S16(n + 16), S16(n + 32), S16(n + 48)
74 #define S256 S64(0), S64(64), S64(128), S64(192)
75
76 static struct arc4_stream rs = { .inited = false,
77 .i = 0xff, .j = 0, .s = { S256 },
78 .count = 0, .mtx = MUTEX_INITIALIZER };
79
80 #undef S
81 #undef S4
82 #undef S16
83 #undef S64
84 #undef S256
85
86 static inline void arc4_addrandom(struct arc4_stream *, u_char *, int);
87 static __noinline void arc4_stir(struct arc4_stream *);
88 static inline uint8_t arc4_getbyte(struct arc4_stream *);
89 static inline uint32_t arc4_getword(struct arc4_stream *);
90
91 #ifdef _REENTRANT
92 static void
93 arc4_fork_prepare(void)
94 {
95
96 LOCK(&rs);
97 }
98
99 static void
100 arc4_fork_parent(void)
101 {
102
103 UNLOCK(&rs);
104 }
105 #else
106 #define arc4_fork_prepare NULL
107 #define arc4_fork_parent NULL
108 #endif
109
110 static void
111 arc4_fork_child(void)
112 {
113
114 /* Reset the counter to a force new stir after forking */
115 rs.count = 0;
116 UNLOCK(&rs);
117 }
118
119 static inline void
120 arc4_check_init(struct arc4_stream *as)
121 {
122
123 if (__predict_false(!as->inited)) {
124 as->inited = true;
125 pthread_atfork(arc4_fork_prepare,
126 arc4_fork_parent, arc4_fork_child);
127 }
128 }
129
130 static inline void
131 arc4_addrandom(struct arc4_stream *as, u_char *dat, int datlen)
132 {
133 uint8_t si;
134 size_t n;
135
136 for (n = 0; n < __arraycount(as->s); n++) {
137 as->i = (as->i + 1);
138 si = as->s[as->i];
139 as->j = (as->j + si + dat[n % datlen]);
140 as->s[as->i] = as->s[as->j];
141 as->s[as->j] = si;
142 }
143 }
144
145 static __noinline void
146 arc4_stir(struct arc4_stream *as)
147 {
148 int rdat[32];
149 int mib[] = { CTL_KERN, KERN_URND };
150 size_t len;
151 size_t i, j;
152
153 arc4_check_init(as);
154
155 /*
156 * This code once opened and read /dev/urandom on each
157 * call. That causes repeated rekeying of the kernel stream
158 * generator, which is very wasteful. Because of application
159 * behavior, caching the fd doesn't really help. So we just
160 * fill up the tank from sysctl, which is a tiny bit slower
161 * for us but much friendlier to other entropy consumers.
162 */
163
164 for (i = 0; i < __arraycount(rdat); i++) {
165 len = sizeof(rdat[i]);
166 if (sysctl(mib, 2, &rdat[i], &len, NULL, 0) == -1)
167 abort();
168 }
169
170 arc4_addrandom(as, (void *) &rdat, (int)sizeof(rdat));
171
172 /*
173 * Throw away the first N words of output, as suggested in the
174 * paper "Weaknesses in the Key Scheduling Algorithm of RC4"
175 * by Fluher, Mantin, and Shamir. (N = 256 in our case.)
176 */
177 for (j = 0; j < __arraycount(as->s) * sizeof(uint32_t); j++)
178 arc4_getbyte(as);
179
180 /* Stir again after swallowing 1600000 bytes or if the pid changes */
181 as->count = 1600000;
182 }
183
184 static inline void
185 arc4_stir_if_needed(struct arc4_stream *as, size_t len)
186 {
187
188 if (__predict_false(as->count <= len))
189 arc4_stir(as);
190 else
191 as->count -= len;
192 }
193
194 static __inline uint8_t
195 arc4_getbyte_ij(struct arc4_stream *as, uint8_t *i, uint8_t *j)
196 {
197 uint8_t si, sj;
198
199 *i = *i + 1;
200 si = as->s[*i];
201 *j = *j + si;
202 sj = as->s[*j];
203 as->s[*i] = sj;
204 as->s[*j] = si;
205 return (as->s[(si + sj) & 0xff]);
206 }
207
208 static inline uint8_t
209 arc4_getbyte(struct arc4_stream *as)
210 {
211
212 return arc4_getbyte_ij(as, &as->i, &as->j);
213 }
214
215 static inline uint32_t
216 arc4_getword(struct arc4_stream *as)
217 {
218 uint32_t val;
219
220 val = arc4_getbyte(as) << 24;
221 val |= arc4_getbyte(as) << 16;
222 val |= arc4_getbyte(as) << 8;
223 val |= arc4_getbyte(as);
224 return val;
225 }
226
227 void
228 arc4random_stir(void)
229 {
230
231 LOCK(&rs);
232 arc4_stir(&rs);
233 UNLOCK(&rs);
234 }
235
236 void
237 arc4random_addrandom(u_char *dat, int datlen)
238 {
239
240 LOCK(&rs);
241 arc4_stir_if_needed(&rs, datlen);
242 arc4_addrandom(&rs, dat, datlen);
243 UNLOCK(&rs);
244 }
245
246 uint32_t
247 arc4random(void)
248 {
249 uint32_t v;
250
251 LOCK(&rs);
252 arc4_stir_if_needed(&rs, sizeof(v));
253 v = arc4_getword(&rs);
254 UNLOCK(&rs);
255 return v;
256 }
257
258 void
259 arc4random_buf(void *buf, size_t len)
260 {
261 uint8_t *bp = buf;
262 uint8_t *ep = bp + len;
263 uint8_t i, j;
264
265 LOCK(&rs);
266 arc4_stir_if_needed(&rs, len);
267
268 /* cache i and j - compiler can't know 'buf' doesn't alias them */
269 i = rs.i;
270 j = rs.j;
271
272 while (bp < ep)
273 *bp++ = arc4_getbyte_ij(&rs, &i, &j);
274 rs.i = i;
275 rs.j = j;
276
277 UNLOCK(&rs);
278 }
279
280 /*-
281 * Written by Damien Miller.
282 * With simplifications by Jinmei Tatuya.
283 */
284
285 /*
286 * Calculate a uniformly distributed random number less than
287 * upper_bound avoiding "modulo bias".
288 *
289 * Uniformity is achieved by generating new random numbers
290 * until the one returned is outside the range
291 * [0, 2^32 % upper_bound[. This guarantees the selected
292 * random number will be inside the range
293 * [2^32 % upper_bound, 2^32[ which maps back to
294 * [0, upper_bound[ after reduction modulo upper_bound.
295 */
296 uint32_t
297 arc4random_uniform(uint32_t upper_bound)
298 {
299 uint32_t r, min;
300
301 if (upper_bound < 2)
302 return 0;
303
304 /* calculate (2^32 % upper_bound) avoiding 64-bit math */
305 /* ((2^32 - x) % x) == (2^32 % x) when x <= 2^31 */
306 min = (0xFFFFFFFFU - upper_bound + 1) % upper_bound;
307
308 LOCK(&rs);
309 arc4_stir_if_needed(&rs, sizeof(r));
310
311 /*
312 * This could theoretically loop forever but each retry has
313 * p > 0.5 (worst case, usually far better) of selecting a
314 * number inside the range we need, so it should rarely need
315 * to re-roll (at all).
316 */
317 do
318 r = arc4_getword(&rs);
319 while (r < min);
320 UNLOCK(&rs);
321
322 return r % upper_bound;
323 }
324