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