1 /* OPENBSD ORIGINAL: lib/libc/crypto/arc4random.c */
2
3 /* $OpenBSD: arc4random.c,v 1.25 2013/10/01 18:34:57 markus Exp $ */
4
5 /*
6 * Copyright (c) 1996, David Mazieres <dm@uun.org>
7 * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
8 * Copyright (c) 2013, Markus Friedl <markus@openbsd.org>
9 *
10 * Permission to use, copy, modify, and distribute this software for any
11 * purpose with or without fee is hereby granted, provided that the above
12 * copyright notice and this permission notice appear in all copies.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
15 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
16 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
17 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
19 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
20 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 */
22
23 /*
24 * ChaCha based random number generator for OpenBSD.
25 */
26
27 #include "includes.h"
28
29 #include <sys/types.h>
30
31 #include <fcntl.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <unistd.h>
35
36 #ifndef HAVE_ARC4RANDOM
37
38 #ifdef WITH_OPENSSL
39 #include <openssl/rand.h>
40 #include <openssl/err.h>
41 #endif
42
43 #include "log.h"
44
45 #define KEYSTREAM_ONLY
46 #include "chacha_private.h"
47
48 #ifdef __GNUC__
49 #define inline __inline
50 #else /* !__GNUC__ */
51 #define inline
52 #endif /* !__GNUC__ */
53
54 /* OpenSSH isn't multithreaded */
55 #define _ARC4_LOCK()
56 #define _ARC4_UNLOCK()
57
58 #define KEYSZ 32
59 #define IVSZ 8
60 #define BLOCKSZ 64
61 #define RSBUFSZ (16*BLOCKSZ)
62 static int rs_initialized;
63 static pid_t rs_stir_pid;
64 static chacha_ctx rs; /* chacha context for random keystream */
65 static u_char rs_buf[RSBUFSZ]; /* keystream blocks */
66 static size_t rs_have; /* valid bytes at end of rs_buf */
67 static size_t rs_count; /* bytes till reseed */
68
69 static inline void _rs_rekey(u_char *dat, size_t datlen);
70
71 static inline void
_rs_init(u_char * buf,size_t n)72 _rs_init(u_char *buf, size_t n)
73 {
74 if (n < KEYSZ + IVSZ)
75 return;
76 chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
77 chacha_ivsetup(&rs, buf + KEYSZ);
78 }
79
80 #ifndef WITH_OPENSSL
81 #define SSH_RANDOM_DEV "/dev/urandom"
82 /* XXX use getrandom() if supported on Linux */
83 static void
getrnd(u_char * s,size_t len)84 getrnd(u_char *s, size_t len)
85 {
86 int fd;
87 ssize_t r;
88 size_t o = 0;
89
90 if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1)
91 fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno));
92 while (o < len) {
93 r = read(fd, s + o, len - o);
94 if (r < 0) {
95 if (errno == EAGAIN || errno == EINTR ||
96 errno == EWOULDBLOCK)
97 continue;
98 fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno));
99 }
100 o += r;
101 }
102 close(fd);
103 }
104 #endif
105
106 static void
_rs_stir(void)107 _rs_stir(void)
108 {
109 u_char rnd[KEYSZ + IVSZ];
110
111 #ifdef WITH_OPENSSL
112 if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
113 fatal("Couldn't obtain random bytes (error 0x%lx)",
114 (unsigned long)ERR_get_error());
115 #else
116 getrnd(rnd, sizeof(rnd));
117 #endif
118
119 if (!rs_initialized) {
120 rs_initialized = 1;
121 _rs_init(rnd, sizeof(rnd));
122 } else
123 _rs_rekey(rnd, sizeof(rnd));
124 explicit_bzero(rnd, sizeof(rnd));
125
126 /* invalidate rs_buf */
127 rs_have = 0;
128 memset(rs_buf, 0, RSBUFSZ);
129
130 rs_count = 1600000;
131 }
132
133 static inline void
_rs_stir_if_needed(size_t len)134 _rs_stir_if_needed(size_t len)
135 {
136 pid_t pid = getpid();
137
138 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
139 rs_stir_pid = pid;
140 _rs_stir();
141 } else
142 rs_count -= len;
143 }
144
145 static inline void
_rs_rekey(u_char * dat,size_t datlen)146 _rs_rekey(u_char *dat, size_t datlen)
147 {
148 #ifndef KEYSTREAM_ONLY
149 memset(rs_buf, 0,RSBUFSZ);
150 #endif
151 /* fill rs_buf with the keystream */
152 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
153 /* mix in optional user provided data */
154 if (dat) {
155 size_t i, m;
156
157 m = MIN(datlen, KEYSZ + IVSZ);
158 for (i = 0; i < m; i++)
159 rs_buf[i] ^= dat[i];
160 }
161 /* immediately reinit for backtracking resistance */
162 _rs_init(rs_buf, KEYSZ + IVSZ);
163 memset(rs_buf, 0, KEYSZ + IVSZ);
164 rs_have = RSBUFSZ - KEYSZ - IVSZ;
165 }
166
167 static inline void
_rs_random_buf(void * _buf,size_t n)168 _rs_random_buf(void *_buf, size_t n)
169 {
170 u_char *buf = (u_char *)_buf;
171 size_t m;
172
173 _rs_stir_if_needed(n);
174 while (n > 0) {
175 if (rs_have > 0) {
176 m = MIN(n, rs_have);
177 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
178 memset(rs_buf + RSBUFSZ - rs_have, 0, m);
179 buf += m;
180 n -= m;
181 rs_have -= m;
182 }
183 if (rs_have == 0)
184 _rs_rekey(NULL, 0);
185 }
186 }
187
188 static inline void
_rs_random_u32(u_int32_t * val)189 _rs_random_u32(u_int32_t *val)
190 {
191 _rs_stir_if_needed(sizeof(*val));
192 if (rs_have < sizeof(*val))
193 _rs_rekey(NULL, 0);
194 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
195 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
196 rs_have -= sizeof(*val);
197 return;
198 }
199
200 void
arc4random_stir(void)201 arc4random_stir(void)
202 {
203 _ARC4_LOCK();
204 _rs_stir();
205 _ARC4_UNLOCK();
206 }
207
208 void
arc4random_addrandom(u_char * dat,int datlen)209 arc4random_addrandom(u_char *dat, int datlen)
210 {
211 int m;
212
213 _ARC4_LOCK();
214 if (!rs_initialized)
215 _rs_stir();
216 while (datlen > 0) {
217 m = MIN(datlen, KEYSZ + IVSZ);
218 _rs_rekey(dat, m);
219 dat += m;
220 datlen -= m;
221 }
222 _ARC4_UNLOCK();
223 }
224
225 u_int32_t
arc4random(void)226 arc4random(void)
227 {
228 u_int32_t val;
229
230 _ARC4_LOCK();
231 _rs_random_u32(&val);
232 _ARC4_UNLOCK();
233 return val;
234 }
235
236 /*
237 * If we are providing arc4random, then we can provide a more efficient
238 * arc4random_buf().
239 */
240 # ifndef HAVE_ARC4RANDOM_BUF
241 void
arc4random_buf(void * buf,size_t n)242 arc4random_buf(void *buf, size_t n)
243 {
244 _ARC4_LOCK();
245 _rs_random_buf(buf, n);
246 _ARC4_UNLOCK();
247 }
248 # endif /* !HAVE_ARC4RANDOM_BUF */
249 #endif /* !HAVE_ARC4RANDOM */
250
251 /* arc4random_buf() that uses platform arc4random() */
252 #if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
253 void
arc4random_buf(void * _buf,size_t n)254 arc4random_buf(void *_buf, size_t n)
255 {
256 size_t i;
257 u_int32_t r = 0;
258 char *buf = (char *)_buf;
259
260 for (i = 0; i < n; i++) {
261 if (i % 4 == 0)
262 r = arc4random();
263 buf[i] = r & 0xff;
264 r >>= 8;
265 }
266 explicit_bzero(&r, sizeof(r));
267 }
268 #endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
269
270 #ifndef HAVE_ARC4RANDOM_UNIFORM
271 /*
272 * Calculate a uniformly distributed random number less than upper_bound
273 * avoiding "modulo bias".
274 *
275 * Uniformity is achieved by generating new random numbers until the one
276 * returned is outside the range [0, 2**32 % upper_bound). This
277 * guarantees the selected random number will be inside
278 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
279 * after reduction modulo upper_bound.
280 */
281 u_int32_t
arc4random_uniform(u_int32_t upper_bound)282 arc4random_uniform(u_int32_t upper_bound)
283 {
284 u_int32_t r, min;
285
286 if (upper_bound < 2)
287 return 0;
288
289 /* 2**32 % x == (2**32 - x) % x */
290 min = -upper_bound % upper_bound;
291
292 /*
293 * This could theoretically loop forever but each retry has
294 * p > 0.5 (worst case, usually far better) of selecting a
295 * number inside the range we need, so it should rarely need
296 * to re-roll.
297 */
298 for (;;) {
299 r = arc4random();
300 if (r >= min)
301 break;
302 }
303
304 return r % upper_bound;
305 }
306 #endif /* !HAVE_ARC4RANDOM_UNIFORM */
307
308 #if 0
309 /*-------- Test code for i386 --------*/
310 #include <stdio.h>
311 #include <machine/pctr.h>
312 int
313 main(int argc, char **argv)
314 {
315 const int iter = 1000000;
316 int i;
317 pctrval v;
318
319 v = rdtsc();
320 for (i = 0; i < iter; i++)
321 arc4random();
322 v = rdtsc() - v;
323 v /= iter;
324
325 printf("%qd cycles\n", v);
326 exit(0);
327 }
328 #endif
329