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 "atheme.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 #define fatal(msg, ...) do { \
44 slog(LG_ERROR, msg, __VA_ARGS__); exit(EXIT_FAILURE); \
45 } while (0);
46
47 #define KEYSTREAM_ONLY
48 #include "chacha_private.h"
49
50 #ifdef __GNUC__
51 #define inline __inline
52 #else /* !__GNUC__ */
53 #define inline
54 #endif /* !__GNUC__ */
55
56 /* OpenSSH isn't multithreaded */
57 #define _ARC4_LOCK()
58 #define _ARC4_UNLOCK()
59
60 #define KEYSZ 32
61 #define IVSZ 8
62 #define BLOCKSZ 64
63 #define RSBUFSZ (16*BLOCKSZ)
64 static int rs_initialized;
65 static pid_t rs_stir_pid;
66 static chacha_ctx rs; /* chacha context for random keystream */
67 static unsigned char rs_buf[RSBUFSZ]; /* keystream blocks */
68 static size_t rs_have; /* valid bytes at end of rs_buf */
69 static size_t rs_count; /* bytes till reseed */
70
71 static inline void _rs_rekey(unsigned char *dat, size_t datlen);
72
73 static inline void
_rs_init(unsigned char * buf,size_t n)74 _rs_init(unsigned char *buf, size_t n)
75 {
76 if (n < KEYSZ + IVSZ)
77 return;
78 chacha_keysetup(&rs, buf, KEYSZ * 8, 0);
79 chacha_ivsetup(&rs, buf + KEYSZ);
80 }
81
82 #ifndef WITH_OPENSSL
83 #define SSH_RANDOM_DEV "/dev/urandom"
84 /* XXX use getrandom() if supported on Linux */
85 static void
getrnd(unsigned char * s,size_t len)86 getrnd(unsigned char *s, size_t len)
87 {
88 int fd;
89 ssize_t r;
90 size_t o = 0;
91
92 if ((fd = open(SSH_RANDOM_DEV, O_RDONLY)) == -1)
93 fatal("Couldn't open %s: %s", SSH_RANDOM_DEV, strerror(errno));
94 while (o < len) {
95 r = read(fd, s + o, len - o);
96 if (r < 0) {
97 if (errno == EAGAIN || errno == EINTR ||
98 errno == EWOULDBLOCK)
99 continue;
100 fatal("read %s: %s", SSH_RANDOM_DEV, strerror(errno));
101 }
102 o += r;
103 }
104 close(fd);
105 }
106 #endif
107
108 static void
_rs_stir(void)109 _rs_stir(void)
110 {
111 unsigned char rnd[KEYSZ + IVSZ];
112
113 #ifdef WITH_OPENSSL
114 if (RAND_bytes(rnd, sizeof(rnd)) <= 0)
115 fatal("Couldn't obtain random bytes (error %ld)",
116 ERR_get_error());
117 #else
118 getrnd(rnd, sizeof(rnd));
119 #endif
120
121 if (!rs_initialized) {
122 rs_initialized = 1;
123 _rs_init(rnd, sizeof(rnd));
124 } else
125 _rs_rekey(rnd, sizeof(rnd));
126 explicit_bzero(rnd, sizeof(rnd));
127
128 /* invalidate rs_buf */
129 rs_have = 0;
130 memset(rs_buf, 0, RSBUFSZ);
131
132 rs_count = 1600000;
133 }
134
135 static inline void
_rs_stir_if_needed(size_t len)136 _rs_stir_if_needed(size_t len)
137 {
138 pid_t pid = getpid();
139
140 if (rs_count <= len || !rs_initialized || rs_stir_pid != pid) {
141 rs_stir_pid = pid;
142 _rs_stir();
143 } else
144 rs_count -= len;
145 }
146
147 static inline void
_rs_rekey(unsigned char * dat,size_t datlen)148 _rs_rekey(unsigned char *dat, size_t datlen)
149 {
150 #ifndef KEYSTREAM_ONLY
151 memset(rs_buf, 0,RSBUFSZ);
152 #endif
153 /* fill rs_buf with the keystream */
154 chacha_encrypt_bytes(&rs, rs_buf, rs_buf, RSBUFSZ);
155 /* mix in optional user provided data */
156 if (dat) {
157 size_t i, m;
158
159 m = MIN(datlen, KEYSZ + IVSZ);
160 for (i = 0; i < m; i++)
161 rs_buf[i] ^= dat[i];
162 }
163 /* immediately reinit for backtracking resistance */
164 _rs_init(rs_buf, KEYSZ + IVSZ);
165 memset(rs_buf, 0, KEYSZ + IVSZ);
166 rs_have = RSBUFSZ - KEYSZ - IVSZ;
167 }
168
169 static inline void
_rs_random_buf(void * _buf,size_t n)170 _rs_random_buf(void *_buf, size_t n)
171 {
172 unsigned char *buf = (unsigned char *)_buf;
173 size_t m;
174
175 _rs_stir_if_needed(n);
176 while (n > 0) {
177 if (rs_have > 0) {
178 m = MIN(n, rs_have);
179 memcpy(buf, rs_buf + RSBUFSZ - rs_have, m);
180 memset(rs_buf + RSBUFSZ - rs_have, 0, m);
181 buf += m;
182 n -= m;
183 rs_have -= m;
184 }
185 if (rs_have == 0)
186 _rs_rekey(NULL, 0);
187 }
188 }
189
190 static inline void
_rs_random_u32(uint32_t * val)191 _rs_random_u32(uint32_t *val)
192 {
193 _rs_stir_if_needed(sizeof(*val));
194 if (rs_have < sizeof(*val))
195 _rs_rekey(NULL, 0);
196 memcpy(val, rs_buf + RSBUFSZ - rs_have, sizeof(*val));
197 memset(rs_buf + RSBUFSZ - rs_have, 0, sizeof(*val));
198 rs_have -= sizeof(*val);
199 return;
200 }
201
202 void
arc4random_stir(void)203 arc4random_stir(void)
204 {
205 _ARC4_LOCK();
206 _rs_stir();
207 _ARC4_UNLOCK();
208 }
209
210 void
arc4random_addrandom(unsigned char * dat,int datlen)211 arc4random_addrandom(unsigned char *dat, int datlen)
212 {
213 int m;
214
215 _ARC4_LOCK();
216 if (!rs_initialized)
217 _rs_stir();
218 while (datlen > 0) {
219 m = MIN(datlen, KEYSZ + IVSZ);
220 _rs_rekey(dat, m);
221 dat += m;
222 datlen -= m;
223 }
224 _ARC4_UNLOCK();
225 }
226
227 uint32_t
arc4random(void)228 arc4random(void)
229 {
230 uint32_t val;
231
232 _ARC4_LOCK();
233 _rs_random_u32(&val);
234 _ARC4_UNLOCK();
235 return val;
236 }
237
238 /*
239 * If we are providing arc4random, then we can provide a more efficient
240 * arc4random_buf().
241 */
242 # ifndef HAVE_ARC4RANDOM_BUF
243 void
arc4random_buf(void * buf,size_t n)244 arc4random_buf(void *buf, size_t n)
245 {
246 _ARC4_LOCK();
247 _rs_random_buf(buf, n);
248 _ARC4_UNLOCK();
249 }
250 # endif /* !HAVE_ARC4RANDOM_BUF */
251 #endif /* !HAVE_ARC4RANDOM */
252
253 /* arc4random_buf() that uses platform arc4random() */
254 #if !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM)
255 void
arc4random_buf(void * _buf,size_t n)256 arc4random_buf(void *_buf, size_t n)
257 {
258 size_t i;
259 uint32_t r = 0;
260 char *buf = (char *)_buf;
261
262 for (i = 0; i < n; i++) {
263 if (i % 4 == 0)
264 r = arc4random();
265 buf[i] = r & 0xff;
266 r >>= 8;
267 }
268 explicit_bzero(&r, sizeof(r));
269 }
270 #endif /* !defined(HAVE_ARC4RANDOM_BUF) && defined(HAVE_ARC4RANDOM) */
271
272 #ifndef HAVE_ARC4RANDOM_UNIFORM
273 /*
274 * Calculate a uniformly distributed random number less than upper_bound
275 * avoiding "modulo bias".
276 *
277 * Uniformity is achieved by generating new random numbers until the one
278 * returned is outside the range [0, 2**32 % upper_bound). This
279 * guarantees the selected random number will be inside
280 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
281 * after reduction modulo upper_bound.
282 */
283 uint32_t
arc4random_uniform(uint32_t upper_bound)284 arc4random_uniform(uint32_t upper_bound)
285 {
286 uint32_t r, min;
287
288 if (upper_bound < 2)
289 return 0;
290
291 /* 2**32 % x == (2**32 - x) % x */
292 min = -upper_bound % upper_bound;
293
294 /*
295 * This could theoretically loop forever but each retry has
296 * p > 0.5 (worst case, usually far better) of selecting a
297 * number inside the range we need, so it should rarely need
298 * to re-roll.
299 */
300 for (;;) {
301 r = arc4random();
302 if (r >= min)
303 break;
304 }
305
306 return r % upper_bound;
307 }
308 #endif /* !HAVE_ARC4RANDOM_UNIFORM */
309
310 #if 0
311 /*-------- Test code for i386 --------*/
312 #include <stdio.h>
313 #include <machine/pctr.h>
314 int
315 main(int argc, char **argv)
316 {
317 const int iter = 1000000;
318 int i;
319 pctrval v;
320
321 v = rdtsc();
322 for (i = 0; i < iter; i++)
323 arc4random();
324 v = rdtsc() - v;
325 v /= iter;
326
327 printf("%qd cycles\n", v);
328 exit(0);
329 }
330 #endif
331