1 /* $OpenBSD: arc4random.c,v 1.24 2013/06/11 16:59:50 deraadt Exp $ */
2
3 /*
4 * Copyright (c) 1996, David Mazieres <dm@uun.org>
5 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19
20 /*
21 * Arc4 random number generator for OpenBSD.
22 *
23 * This code is derived from section 17.1 of Applied Cryptography,
24 * second edition, which describes a stream cipher allegedly
25 * compatible with RSA Labs "RC4" cipher (the actual description of
26 * which is a trade secret). The same algorithm is used as a stream
27 * cipher called "arcfour" in Tatu Ylonen's ssh package.
28 *
29 * RC4 is a registered trademark of RSA Laboratories.
30 */
31
32 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD: stable/10/lib/libc/gen/arc4random.c 315227 2017-03-14 06:12:51Z delphij $");
34
35 #include "namespace.h"
36 #include <fcntl.h>
37 #include <limits.h>
38 #include <stdlib.h>
39 #include <unistd.h>
40 #include <sys/types.h>
41 #include <sys/param.h>
42 #include <sys/sysctl.h>
43 #include <sys/time.h>
44 #include <pthread.h>
45
46 #include "libc_private.h"
47 #include "un-namespace.h"
48
49 #ifdef __GNUC__
50 #define inline __inline
51 #else /* !__GNUC__ */
52 #define inline
53 #endif /* !__GNUC__ */
54
55 struct arc4_stream {
56 u_int8_t i;
57 u_int8_t j;
58 u_int8_t s[256];
59 };
60
61 static pthread_mutex_t arc4random_mtx = PTHREAD_MUTEX_INITIALIZER;
62
63 #define RANDOMDEV "/dev/random"
64 #define KEYSIZE 128
65 #define _ARC4_LOCK() \
66 do { \
67 if (__isthreaded) \
68 _pthread_mutex_lock(&arc4random_mtx); \
69 } while (0)
70
71 #define _ARC4_UNLOCK() \
72 do { \
73 if (__isthreaded) \
74 _pthread_mutex_unlock(&arc4random_mtx); \
75 } while (0)
76
77 static int rs_initialized;
78 static struct arc4_stream rs;
79 static pid_t arc4_stir_pid;
80 static int arc4_count;
81
82 extern int __sysctl(int *name, u_int namelen, void *oldp, size_t *oldlenp,
83 void *newp, size_t newlen);
84
85 static inline u_int8_t arc4_getbyte(void);
86 static void arc4_stir(void);
87
88 static inline void
arc4_init(void)89 arc4_init(void)
90 {
91 int n;
92
93 for (n = 0; n < 256; n++)
94 rs.s[n] = n;
95 rs.i = 0;
96 rs.j = 0;
97 }
98
99 static inline void
arc4_addrandom(u_char * dat,int datlen)100 arc4_addrandom(u_char *dat, int datlen)
101 {
102 int n;
103 u_int8_t si;
104
105 rs.i--;
106 for (n = 0; n < 256; n++) {
107 rs.i = (rs.i + 1);
108 si = rs.s[rs.i];
109 rs.j = (rs.j + si + dat[n % datlen]);
110 rs.s[rs.i] = rs.s[rs.j];
111 rs.s[rs.j] = si;
112 }
113 rs.j = rs.i;
114 }
115
116 static size_t
arc4_sysctl(u_char * buf,size_t size)117 arc4_sysctl(u_char *buf, size_t size)
118 {
119 int mib[2];
120 size_t len, done;
121
122 mib[0] = CTL_KERN;
123 mib[1] = KERN_ARND;
124 done = 0;
125
126 do {
127 len = size;
128 if (__sysctl(mib, 2, buf, &len, NULL, 0) == -1)
129 return (done);
130 done += len;
131 buf += len;
132 size -= len;
133 } while (size > 0);
134
135 return (done);
136 }
137
138 static void
arc4_stir(void)139 arc4_stir(void)
140 {
141 int done, fd, i;
142 struct {
143 struct timeval tv;
144 pid_t pid;
145 u_char rnd[KEYSIZE];
146 } rdat;
147
148 if (!rs_initialized) {
149 arc4_init();
150 rs_initialized = 1;
151 }
152 done = 0;
153 if (arc4_sysctl((u_char *)&rdat, KEYSIZE) == KEYSIZE)
154 done = 1;
155 if (!done) {
156 fd = _open(RANDOMDEV, O_RDONLY | O_CLOEXEC, 0);
157 if (fd >= 0) {
158 if (_read(fd, &rdat, KEYSIZE) == KEYSIZE)
159 done = 1;
160 (void)_close(fd);
161 }
162 }
163 if (!done) {
164 (void)gettimeofday(&rdat.tv, NULL);
165 rdat.pid = getpid();
166 /* We'll just take whatever was on the stack too... */
167 }
168
169 arc4_addrandom((u_char *)&rdat, KEYSIZE);
170
171 /*
172 * Discard early keystream, as per recommendations in:
173 * "(Not So) Random Shuffles of RC4" by Ilya Mironov.
174 */
175 for (i = 0; i < 3072; i++)
176 (void)arc4_getbyte();
177 arc4_count = 1600000;
178 }
179
180 static void
arc4_stir_if_needed(void)181 arc4_stir_if_needed(void)
182 {
183 pid_t pid = getpid();
184
185 if (arc4_count <= 0 || !rs_initialized || arc4_stir_pid != pid) {
186 arc4_stir_pid = pid;
187 arc4_stir();
188 }
189 }
190
191 static inline u_int8_t
arc4_getbyte(void)192 arc4_getbyte(void)
193 {
194 u_int8_t si, sj;
195
196 rs.i = (rs.i + 1);
197 si = rs.s[rs.i];
198 rs.j = (rs.j + si);
199 sj = rs.s[rs.j];
200 rs.s[rs.i] = sj;
201 rs.s[rs.j] = si;
202 return (rs.s[(si + sj) & 0xff]);
203 }
204
205 static inline u_int32_t
arc4_getword(void)206 arc4_getword(void)
207 {
208 u_int32_t val;
209 val = arc4_getbyte() << 24;
210 val |= arc4_getbyte() << 16;
211 val |= arc4_getbyte() << 8;
212 val |= arc4_getbyte();
213 return val;
214 }
215
216 void
arc4random_stir(void)217 arc4random_stir(void)
218 {
219 _ARC4_LOCK();
220 arc4_stir();
221 _ARC4_UNLOCK();
222 }
223
224 void
arc4random_addrandom(u_char * dat,int datlen)225 arc4random_addrandom(u_char *dat, int datlen)
226 {
227 _ARC4_LOCK();
228 if (!rs_initialized)
229 arc4_stir();
230 arc4_addrandom(dat, datlen);
231 _ARC4_UNLOCK();
232 }
233
234 u_int32_t
arc4random(void)235 arc4random(void)
236 {
237 u_int32_t val;
238 _ARC4_LOCK();
239 arc4_count -= 4;
240 arc4_stir_if_needed();
241 val = arc4_getword();
242 _ARC4_UNLOCK();
243 return val;
244 }
245
246 void
arc4random_buf(void * _buf,size_t n)247 arc4random_buf(void *_buf, size_t n)
248 {
249 u_char *buf = (u_char *)_buf;
250 _ARC4_LOCK();
251 arc4_stir_if_needed();
252 while (n--) {
253 if (--arc4_count <= 0)
254 arc4_stir();
255 buf[n] = arc4_getbyte();
256 }
257 _ARC4_UNLOCK();
258 }
259
260 /*
261 * Calculate a uniformly distributed random number less than upper_bound
262 * avoiding "modulo bias".
263 *
264 * Uniformity is achieved by generating new random numbers until the one
265 * returned is outside the range [0, 2**32 % upper_bound). This
266 * guarantees the selected random number will be inside
267 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
268 * after reduction modulo upper_bound.
269 */
270 u_int32_t
arc4random_uniform(u_int32_t upper_bound)271 arc4random_uniform(u_int32_t upper_bound)
272 {
273 u_int32_t r, min;
274
275 if (upper_bound < 2)
276 return 0;
277
278 /* 2**32 % x == (2**32 - x) % x */
279 min = -upper_bound % upper_bound;
280 /*
281 * This could theoretically loop forever but each retry has
282 * p > 0.5 (worst case, usually far better) of selecting a
283 * number inside the range we need, so it should rarely need
284 * to re-roll.
285 */
286 for (;;) {
287 r = arc4random();
288 if (r >= min)
289 break;
290 }
291
292 return r % upper_bound;
293 }
294
295 #if 0
296 /*-------- Test code for i386 --------*/
297 #include <stdio.h>
298 #include <machine/pctr.h>
299 int
300 main(int argc, char **argv)
301 {
302 const int iter = 1000000;
303 int i;
304 pctrval v;
305
306 v = rdtsc();
307 for (i = 0; i < iter; i++)
308 arc4random();
309 v = rdtsc() - v;
310 v /= iter;
311
312 printf("%qd cycles\n", v);
313 }
314 #endif
315