1 /* $NetBSD: arc4random.c,v 1.50 2025/03/11 14:30:27 riastradh Exp $ */
2
3 /*-
4 * Copyright (c) 2014 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * This code is derived from software contributed to The NetBSD Foundation
8 * by Taylor R. Campbell.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * Legacy arc4random(3) API from OpenBSD reimplemented using the
34 * ChaCha20 PRF, with per-thread state.
35 *
36 * Security model:
37 * - An attacker who sees some outputs cannot predict past or future
38 * outputs.
39 * - An attacker who sees the PRNG state cannot predict past outputs.
40 * - An attacker who sees a child's PRNG state cannot predict past or
41 * future outputs in the parent, or in other children.
42 *
43 * The arc4random(3) API may abort the process if:
44 *
45 * (a) the crypto self-test fails, or
46 * (b) sysctl(KERN_ARND) fails when reseeding the PRNG.
47 *
48 * The crypto self-test occurs only once, on the first use of any of
49 * the arc4random(3) API. KERN_ARND is unlikely to fail later unless
50 * the kernel is seriously broken.
51 */
52
53 #include <sys/cdefs.h>
54 __RCSID("$NetBSD: arc4random.c,v 1.50 2025/03/11 14:30:27 riastradh Exp $");
55
56 #include "namespace.h"
57 #include "reentrant.h"
58
59 #include <sys/bitops.h>
60 #include <sys/endian.h>
61 #include <sys/errno.h>
62 #include <sys/mman.h>
63 #include <sys/sysctl.h>
64
65 #include <assert.h>
66 #include <sha2.h>
67 #include <stdbool.h>
68 #include <stdint.h>
69 #include <stdlib.h>
70 #include <string.h>
71 #include <unistd.h>
72
73 #include "arc4random.h"
74 #include "reentrant.h"
75
76 #ifdef __weak_alias
__weak_alias(arc4random,_arc4random)77 __weak_alias(arc4random,_arc4random)
78 __weak_alias(arc4random_addrandom,_arc4random_addrandom)
79 __weak_alias(arc4random_buf,_arc4random_buf)
80 __weak_alias(arc4random_stir,_arc4random_stir)
81 __weak_alias(arc4random_uniform,_arc4random_uniform)
82 #endif
83
84 /*
85 * For standard ChaCha, use le32dec/le32enc. We don't need that for
86 * the purposes of a nondeterministic random number generator -- we
87 * don't need to be bit-for-bit compatible over any wire.
88 */
89
90 static inline uint32_t
91 crypto_le32dec(const void *p)
92 {
93 uint32_t v;
94
95 (void)memcpy(&v, p, sizeof v);
96
97 return v;
98 }
99
100 static inline void
crypto_le32enc(void * p,uint32_t v)101 crypto_le32enc(void *p, uint32_t v)
102 {
103
104 (void)memcpy(p, &v, sizeof v);
105 }
106
107 /* ChaCha core */
108
109 #define crypto_core_OUTPUTBYTES 64
110 #define crypto_core_INPUTBYTES 16
111 #define crypto_core_KEYBYTES 32
112 #define crypto_core_CONSTBYTES 16
113
114 #define crypto_core_ROUNDS 20
115
116 static uint32_t
rotate(uint32_t u,unsigned c)117 rotate(uint32_t u, unsigned c)
118 {
119
120 return (u << c) | (u >> (32 - c));
121 }
122
123 #define QUARTERROUND(a, b, c, d) do { \
124 (a) += (b); (d) ^= (a); (d) = rotate((d), 16); \
125 (c) += (d); (b) ^= (c); (b) = rotate((b), 12); \
126 (a) += (b); (d) ^= (a); (d) = rotate((d), 8); \
127 (c) += (d); (b) ^= (c); (b) = rotate((b), 7); \
128 } while (0)
129
130 static const uint8_t crypto_core_constant32[16] = "expand 32-byte k";
131
132 static void
crypto_core(uint8_t * out,const uint8_t * in,const uint8_t * k,const uint8_t * c)133 crypto_core(uint8_t *out, const uint8_t *in, const uint8_t *k,
134 const uint8_t *c)
135 {
136 uint32_t x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15;
137 uint32_t j0,j1,j2,j3,j4,j5,j6,j7,j8,j9,j10,j11,j12,j13,j14,j15;
138 int i;
139
140 j0 = x0 = crypto_le32dec(c + 0);
141 j1 = x1 = crypto_le32dec(c + 4);
142 j2 = x2 = crypto_le32dec(c + 8);
143 j3 = x3 = crypto_le32dec(c + 12);
144 j4 = x4 = crypto_le32dec(k + 0);
145 j5 = x5 = crypto_le32dec(k + 4);
146 j6 = x6 = crypto_le32dec(k + 8);
147 j7 = x7 = crypto_le32dec(k + 12);
148 j8 = x8 = crypto_le32dec(k + 16);
149 j9 = x9 = crypto_le32dec(k + 20);
150 j10 = x10 = crypto_le32dec(k + 24);
151 j11 = x11 = crypto_le32dec(k + 28);
152 j12 = x12 = crypto_le32dec(in + 0);
153 j13 = x13 = crypto_le32dec(in + 4);
154 j14 = x14 = crypto_le32dec(in + 8);
155 j15 = x15 = crypto_le32dec(in + 12);
156
157 for (i = crypto_core_ROUNDS; i > 0; i -= 2) {
158 QUARTERROUND( x0, x4, x8,x12);
159 QUARTERROUND( x1, x5, x9,x13);
160 QUARTERROUND( x2, x6,x10,x14);
161 QUARTERROUND( x3, x7,x11,x15);
162 QUARTERROUND( x0, x5,x10,x15);
163 QUARTERROUND( x1, x6,x11,x12);
164 QUARTERROUND( x2, x7, x8,x13);
165 QUARTERROUND( x3, x4, x9,x14);
166 }
167
168 crypto_le32enc(out + 0, x0 + j0);
169 crypto_le32enc(out + 4, x1 + j1);
170 crypto_le32enc(out + 8, x2 + j2);
171 crypto_le32enc(out + 12, x3 + j3);
172 crypto_le32enc(out + 16, x4 + j4);
173 crypto_le32enc(out + 20, x5 + j5);
174 crypto_le32enc(out + 24, x6 + j6);
175 crypto_le32enc(out + 28, x7 + j7);
176 crypto_le32enc(out + 32, x8 + j8);
177 crypto_le32enc(out + 36, x9 + j9);
178 crypto_le32enc(out + 40, x10 + j10);
179 crypto_le32enc(out + 44, x11 + j11);
180 crypto_le32enc(out + 48, x12 + j12);
181 crypto_le32enc(out + 52, x13 + j13);
182 crypto_le32enc(out + 56, x14 + j14);
183 crypto_le32enc(out + 60, x15 + j15);
184 }
185
186 /* ChaCha self-test */
187
188 /*
189 * Test vector for ChaCha20 from
190 * <http://tools.ietf.org/html/draft-strombergson-chacha-test-vectors-00>,
191 * test vectors for ChaCha12 and ChaCha8 and for big-endian machines
192 * generated by the same crypto_core code with crypto_core_ROUNDS and
193 * crypto_le32enc/dec varied.
194 */
195
196 static const uint8_t crypto_core_selftest_vector[64] = {
197 #if _BYTE_ORDER == _LITTLE_ENDIAN
198 # if crypto_core_ROUNDS == 8
199 0x3e,0x00,0xef,0x2f,0x89,0x5f,0x40,0xd6,
200 0x7f,0x5b,0xb8,0xe8,0x1f,0x09,0xa5,0xa1,
201 0x2c,0x84,0x0e,0xc3,0xce,0x9a,0x7f,0x3b,
202 0x18,0x1b,0xe1,0x88,0xef,0x71,0x1a,0x1e,
203 0x98,0x4c,0xe1,0x72,0xb9,0x21,0x6f,0x41,
204 0x9f,0x44,0x53,0x67,0x45,0x6d,0x56,0x19,
205 0x31,0x4a,0x42,0xa3,0xda,0x86,0xb0,0x01,
206 0x38,0x7b,0xfd,0xb8,0x0e,0x0c,0xfe,0x42,
207 # elif crypto_core_ROUNDS == 12
208 0x9b,0xf4,0x9a,0x6a,0x07,0x55,0xf9,0x53,
209 0x81,0x1f,0xce,0x12,0x5f,0x26,0x83,0xd5,
210 0x04,0x29,0xc3,0xbb,0x49,0xe0,0x74,0x14,
211 0x7e,0x00,0x89,0xa5,0x2e,0xae,0x15,0x5f,
212 0x05,0x64,0xf8,0x79,0xd2,0x7a,0xe3,0xc0,
213 0x2c,0xe8,0x28,0x34,0xac,0xfa,0x8c,0x79,
214 0x3a,0x62,0x9f,0x2c,0xa0,0xde,0x69,0x19,
215 0x61,0x0b,0xe8,0x2f,0x41,0x13,0x26,0xbe,
216 # elif crypto_core_ROUNDS == 20
217 0x76,0xb8,0xe0,0xad,0xa0,0xf1,0x3d,0x90,
218 0x40,0x5d,0x6a,0xe5,0x53,0x86,0xbd,0x28,
219 0xbd,0xd2,0x19,0xb8,0xa0,0x8d,0xed,0x1a,
220 0xa8,0x36,0xef,0xcc,0x8b,0x77,0x0d,0xc7,
221 0xda,0x41,0x59,0x7c,0x51,0x57,0x48,0x8d,
222 0x77,0x24,0xe0,0x3f,0xb8,0xd8,0x4a,0x37,
223 0x6a,0x43,0xb8,0xf4,0x15,0x18,0xa1,0x1c,
224 0xc3,0x87,0xb6,0x69,0xb2,0xee,0x65,0x86,
225 # else
226 # error crypto_core_ROUNDS must be 8, 12, or 20.
227 # endif
228 #elif _BYTE_ORDER == _BIG_ENDIAN
229 # if crypto_core_ROUNDS == 8
230 0x9a,0x13,0x07,0xe3,0x38,0x18,0x9e,0x99,
231 0x15,0x37,0x16,0x4d,0x04,0xe6,0x48,0x9a,
232 0x07,0xd6,0xe8,0x7a,0x02,0xf9,0xf5,0xc7,
233 0x3f,0xa9,0xc2,0x0a,0xe1,0xc6,0x62,0xea,
234 0x80,0xaf,0xb6,0x51,0xca,0x52,0x43,0x87,
235 0xe3,0xa6,0xa6,0x61,0x11,0xf5,0xe6,0xcf,
236 0x09,0x0f,0xdc,0x9d,0xc3,0xc3,0xbb,0x43,
237 0xd7,0xfa,0x70,0x42,0xbf,0xa5,0xee,0xa2,
238 # elif crypto_core_ROUNDS == 12
239 0xcf,0x6c,0x16,0x48,0xbf,0xf4,0xba,0x85,
240 0x32,0x69,0xd3,0x98,0xc8,0x7d,0xcd,0x3f,
241 0xdc,0x76,0x6b,0xa2,0x7b,0xcb,0x17,0x4d,
242 0x05,0xda,0xdd,0xd8,0x62,0x54,0xbf,0xe0,
243 0x65,0xed,0x0e,0xf4,0x01,0x7e,0x3c,0x05,
244 0x35,0xb2,0x7a,0x60,0xf3,0x8f,0x12,0x33,
245 0x24,0x60,0xcd,0x85,0xfe,0x4c,0xf3,0x39,
246 0xb1,0x0e,0x3e,0xe0,0xba,0xa6,0x2f,0xa9,
247 # elif crypto_core_ROUNDS == 20
248 0x83,0x8b,0xf8,0x75,0xf7,0xde,0x9d,0x8c,
249 0x33,0x14,0x72,0x28,0xd1,0xbe,0x88,0xe5,
250 0x94,0xb5,0xed,0xb8,0x56,0xb5,0x9e,0x0c,
251 0x64,0x6a,0xaf,0xd9,0xa7,0x49,0x10,0x59,
252 0xba,0x3a,0x82,0xf8,0x4a,0x70,0x9c,0x00,
253 0x82,0x2c,0xae,0xc6,0xd7,0x1c,0x2e,0xda,
254 0x2a,0xfb,0x61,0x70,0x2b,0xd1,0xbf,0x8b,
255 0x95,0xbc,0x23,0xb6,0x4b,0x60,0x02,0xec,
256 # else
257 # error crypto_core_ROUNDS must be 8, 12, or 20.
258 # endif
259 #else
260 # error Byte order must be little-endian or big-endian.
261 #endif
262 };
263
264 static int
crypto_core_selftest(void)265 crypto_core_selftest(void)
266 {
267 const uint8_t nonce[crypto_core_INPUTBYTES] = {0};
268 const uint8_t key[crypto_core_KEYBYTES] = {0};
269 uint8_t block[64];
270 unsigned i;
271
272 crypto_core(block, nonce, key, crypto_core_constant32);
273 for (i = 0; i < 64; i++) {
274 if (block[i] != crypto_core_selftest_vector[i])
275 return EIO;
276 }
277
278 return 0;
279 }
280
281 /* PRNG */
282
283 /*
284 * For a state s, rather than use ChaCha20 as a stream cipher to
285 * generate the concatenation ChaCha20_s(0) || ChaCha20_s(1) || ..., we
286 * split ChaCha20_s(0) into s' || x and yield x for the first request,
287 * split ChaCha20_s'(0) into s'' || y and yield y for the second
288 * request, &c. This provides backtracking resistance: an attacker who
289 * finds s'' can't recover s' or x.
290 */
291
292 #define crypto_prng_SEEDBYTES crypto_core_KEYBYTES
293 #define crypto_prng_MAXOUTPUTBYTES \
294 (crypto_core_OUTPUTBYTES - crypto_prng_SEEDBYTES)
295
296 __CTASSERT(sizeof(struct crypto_prng) == crypto_prng_SEEDBYTES);
297
298 static void
crypto_prng_seed(struct crypto_prng * prng,const void * seed)299 crypto_prng_seed(struct crypto_prng *prng, const void *seed)
300 {
301
302 (void)memcpy(prng->state, seed, crypto_prng_SEEDBYTES);
303 }
304
305 static void
crypto_prng_buf(struct crypto_prng * prng,void * buf,size_t n)306 crypto_prng_buf(struct crypto_prng *prng, void *buf, size_t n)
307 {
308 const uint8_t nonce[crypto_core_INPUTBYTES] = {0};
309 uint8_t output[crypto_core_OUTPUTBYTES];
310
311 _DIAGASSERT(n <= crypto_prng_MAXOUTPUTBYTES);
312 __CTASSERT(sizeof prng->state + crypto_prng_MAXOUTPUTBYTES
313 <= sizeof output);
314
315 crypto_core(output, nonce, prng->state, crypto_core_constant32);
316 (void)memcpy(prng->state, output, sizeof prng->state);
317 (void)memcpy(buf, output + sizeof prng->state, n);
318 (void)explicit_memset(output, 0, sizeof output);
319 }
320
321 static int
crypto_prng_selftest(void)322 crypto_prng_selftest(void)
323 {
324 const uint8_t expected[32] = {
325 #if _BYTE_ORDER == _LITTLE_ENDIAN
326 # if crypto_core_ROUNDS == 20
327 0x2b, /* first call */
328 0x2d,0x41,0xa5,0x9c,0x90,0xe4,0x1a,0x8e, /* second call */
329 0x7a,0x4d,0xcc,0xaa,0x1c,0x46,0x06,0x99,
330 0x83,0xb1,0xa3,0x33,0xce,0x25,0x71,0x9e,
331 0xc3,0x43,0x77,0x68,0xab,0x57,
332 0x5f, /* third call */
333 # else
334 # error crypto_core_ROUNDS other than 20 left as exercise for reader.
335 # endif
336 #elif _BYTE_ORDER == _BIG_ENDIAN
337 # if crypto_core_ROUNDS == 20
338 0xae, /* first call */
339 0x97,0x14,0x5a,0x05,0xad,0xa8,0x48,0xf1, /* second call */
340 0x3a,0x81,0x84,0xd7,0x05,0xda,0x20,0x5d,
341 0xc0,0xef,0x86,0x65,0x98,0xbd,0xb0,0x16,
342 0x1b,0xfc,0xff,0xc4,0xc2,0xfd,
343 0xa0, /* third call */
344 # else
345 # error crypto_core_ROUNDS other than 20 left as exercise for reader.
346 # endif
347 #else
348 # error Byte order must be little-endian or big-endian.
349 #endif
350 };
351 uint8_t seed[crypto_prng_SEEDBYTES];
352 struct crypto_prng prng;
353 uint8_t output[32];
354 unsigned i;
355
356 for (i = 0; i < __arraycount(seed); i++)
357 seed[i] = i;
358 crypto_prng_seed(&prng, seed);
359 crypto_prng_buf(&prng, output, 1);
360 crypto_prng_buf(&prng, output + 1, 30);
361 crypto_prng_buf(&prng, output + 31, 1);
362 if (memcmp(output, expected, 32) != 0)
363 return EIO;
364 return 0;
365 }
366
367 /* One-time stream: expand short single-use secret into long secret */
368
369 #define crypto_onetimestream_SEEDBYTES crypto_core_KEYBYTES
370
371 static void
crypto_onetimestream(const void * seed,void * buf,size_t n)372 crypto_onetimestream(const void *seed, void *buf, size_t n)
373 {
374 uint32_t nonce[crypto_core_INPUTBYTES / sizeof(uint32_t)] = {0};
375 uint8_t block[crypto_core_OUTPUTBYTES];
376 uint8_t *p8, *p32;
377 const uint8_t *nonce8 = (const uint8_t *)(void *)nonce;
378 size_t ni, nb, nf;
379
380 /*
381 * Guarantee we can generate up to n bytes. We have
382 * 2^(8*INPUTBYTES) possible inputs yielding output of
383 * OUTPUTBYTES*2^(8*INPUTBYTES) bytes. It suffices to require
384 * that sizeof n > (1/CHAR_BIT) log_2 n be less than
385 * (1/CHAR_BIT) log_2 of the total output stream length. We
386 * have
387 *
388 * log_2 (o 2^(8 i)) = log_2 o + log_2 2^(8 i)
389 * = log_2 o + 8 i.
390 */
391 #ifndef __lint__
392 __CTASSERT(CHAR_BIT * sizeof n <= (ilog2(crypto_core_OUTPUTBYTES) +
393 8 * crypto_core_INPUTBYTES));
394 #endif
395
396 p8 = buf;
397 p32 = (uint8_t *)roundup2((uintptr_t)p8, 4);
398 ni = p32 - p8;
399 if (n < ni)
400 ni = n;
401 nb = (n - ni) / sizeof block;
402 nf = (n - ni) % sizeof block;
403
404 _DIAGASSERT(((uintptr_t)p32 & 3) == 0);
405 _DIAGASSERT(ni <= n);
406 _DIAGASSERT(nb <= (n / sizeof block));
407 _DIAGASSERT(nf <= n);
408 _DIAGASSERT(n == (ni + (nb * sizeof block) + nf));
409 _DIAGASSERT(ni < 4);
410 _DIAGASSERT(nf < sizeof block);
411
412 if (ni) {
413 crypto_core(block, nonce8, seed, crypto_core_constant32);
414 crypto_le32enc(&nonce[0], 1 + crypto_le32dec(&nonce[0]));
415 (void)memcpy(p8, block, ni);
416 }
417 while (nb--) {
418 crypto_core(p32, nonce8, seed, crypto_core_constant32);
419 crypto_le32enc(&nonce[0], 1 + crypto_le32dec(&nonce[0]));
420 if (crypto_le32dec(&nonce[0]) == 0) {
421 crypto_le32enc(&nonce[1],
422 1 + crypto_le32dec(&nonce[1]));
423 }
424 p32 += crypto_core_OUTPUTBYTES;
425 }
426 if (nf) {
427 crypto_core(block, nonce8, seed, crypto_core_constant32);
428 crypto_le32enc(&nonce[0], 1 + crypto_le32dec(&nonce[0]));
429 if (crypto_le32dec(&nonce[0]) == 0) {
430 crypto_le32enc(&nonce[1],
431 1 + crypto_le32dec(&nonce[1]));
432 }
433 (void)memcpy(p32, block, nf);
434 }
435
436 if (ni | nf)
437 (void)explicit_memset(block, 0, sizeof block);
438 }
439
440 static int
crypto_onetimestream_selftest(void)441 crypto_onetimestream_selftest(void)
442 {
443 const uint8_t expected[70] = {
444 0x5a, /* guard byte */
445 #if _BYTE_ORDER == _LITTLE_ENDIAN
446 # if crypto_core_ROUNDS == 20
447 0x39,0xfd,0x2b, /* initial block */
448 0x18,0xb8,0x42,0x31,0xad,0xe6,0xa6,0xd1,
449 0x13,0x61,0x5c,0x61,0xaf,0x43,0x4e,0x27,
450 0xf8,0xb1,0xf3,0xf5,0xe1,0xad,0x5b,0x5c,
451 0xec,0xf8,0xfc,0x12,0x2a,0x35,0x75,0x5c,
452 0x72,0x08,0x08,0x6d,0xd1,0xee,0x3c,0x5d,
453 0x9d,0x81,0x58,0x24,0x64,0x0e,0x00,0x3c,
454 0x9b,0xa0,0xf6,0x5e,0xde,0x5d,0x59,0xce,
455 0x0d,0x2a,0x4a,0x7f,0x31,0x95,0x5a,0xcd,
456 0x42, /* final block */
457 # else
458 # error crypto_core_ROUNDS other than 20 left as exercise for reader.
459 # endif
460 #elif _BYTE_ORDER == _BIG_ENDIAN
461 # if crypto_core_ROUNDS == 20
462 0x20,0xf0,0x66, /* initial block */
463 0x1a,0x82,0xda,0xb6,0xba,0x90,0x42,0x19,
464 0x39,0xc2,0x4e,0x4d,0xaf,0xbc,0x67,0xcf,
465 0xe3,0xe4,0xe2,0x80,0x38,0x80,0x8e,0x53,
466 0x19,0x25,0x37,0x67,0x66,0x57,0x7c,0x78,
467 0xac,0xb3,0x8b,0x97,0x54,0x20,0xc4,0x46,
468 0xff,0x90,0x76,0x56,0xcc,0xde,0xe5,0xb9,
469 0xdf,0x82,0x8c,0x05,0x9d,0xf0,0x69,0x99,
470 0x42,0x53,0x74,0x5e,0x80,0x81,0xdb,0x9b,
471 0xb1, /* final block */
472 # else
473 # error crypto_core_ROUNDS other than 20 left as exercise for reader.
474 # endif
475 #else
476 # error Byte order must be little-endian or big-endian.
477 #endif
478 0xcc, /* guard byte */
479 };
480 uint8_t seed[crypto_prng_SEEDBYTES];
481 uint8_t output[70] __aligned(4);
482 unsigned i;
483
484 for (i = 0; i < __arraycount(seed); i++)
485 seed[i] = i;
486 output[0] = 0x5a;
487 output[69] = 0xcc;
488 crypto_onetimestream(seed, output + 1, 68);
489 if (memcmp(output, expected, 70) != 0)
490 return EIO;
491 return 0;
492 }
493
494 /*
495 * entropy_epoch()
496 *
497 * Return the current entropy epoch, from the sysctl node
498 * kern.entropy.epoch.
499 *
500 * The entropy epoch is never zero. Initially, or on error, it is
501 * (unsigned)-1. It may wrap around but it skips (unsigned)-1 and
502 * 0 when it does. Changes happen less than once per second, so
503 * wraparound will only affect systems after 136 years of uptime.
504 *
505 * XXX This should get it from a page shared read-only by kernel
506 * with userland, but until we implement such a mechanism, this
507 * sysctl -- incurring the cost of a syscall -- will have to
508 * serve.
509 */
510 static unsigned
entropy_epoch(void)511 entropy_epoch(void)
512 {
513 const int mib[] = { CTL_KERN, KERN_ENTROPY, KERN_ENTROPY_EPOCH };
514 unsigned epoch = (unsigned)-1;
515 size_t epochlen = sizeof(epoch);
516
517 if (sysctl(mib, __arraycount(mib), &epoch, &epochlen, NULL, 0) == -1)
518 return (unsigned)-1;
519 if (epochlen != sizeof(epoch))
520 return (unsigned)-1;
521
522 return epoch;
523 }
524
525 /* arc4random state: per-thread, per-process (zeroed in child on fork) */
526
527 static void
arc4random_prng_addrandom(struct arc4random_prng * prng,const void * data,size_t datalen)528 arc4random_prng_addrandom(struct arc4random_prng *prng, const void *data,
529 size_t datalen)
530 {
531 const int mib[] = { CTL_KERN, KERN_ARND };
532 SHA256_CTX ctx;
533 uint8_t buf[crypto_prng_SEEDBYTES];
534 size_t buflen = sizeof buf;
535 unsigned epoch = entropy_epoch();
536
537 __CTASSERT(sizeof buf == SHA256_DIGEST_LENGTH);
538
539 SHA256_Init(&ctx);
540
541 crypto_prng_buf(&prng->arc4_prng, buf, sizeof buf);
542 SHA256_Update(&ctx, buf, sizeof buf);
543
544 if (sysctl(mib, (u_int)__arraycount(mib), buf, &buflen, NULL, 0) == -1)
545 abort();
546 if (buflen != sizeof buf)
547 abort();
548 SHA256_Update(&ctx, buf, sizeof buf);
549
550 if (data != NULL)
551 SHA256_Update(&ctx, data, datalen);
552
553 SHA256_Final(buf, &ctx);
554 (void)explicit_memset(&ctx, 0, sizeof ctx);
555
556 /* reseed(SHA256(prng() || sysctl(KERN_ARND) || data)) */
557 crypto_prng_seed(&prng->arc4_prng, buf);
558 (void)explicit_memset(buf, 0, sizeof buf);
559 prng->arc4_epoch = epoch;
560 }
561
562 #ifdef _REENTRANT
563 static struct arc4random_prng *
arc4random_prng_create(void)564 arc4random_prng_create(void)
565 {
566 struct arc4random_prng *prng;
567 const size_t size = roundup(sizeof(*prng), sysconf(_SC_PAGESIZE));
568
569 prng = mmap(NULL, size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1,
570 0);
571 if (prng == MAP_FAILED)
572 goto fail0;
573 if (minherit(prng, size, MAP_INHERIT_ZERO) == -1)
574 goto fail1;
575
576 return prng;
577
578 fail1: (void)munmap(prng, size);
579 fail0: return NULL;
580 }
581 #endif
582
583 #ifdef _REENTRANT
584 static void
arc4random_prng_destroy(struct arc4random_prng * prng)585 arc4random_prng_destroy(struct arc4random_prng *prng)
586 {
587 const size_t size = roundup(sizeof(*prng), sysconf(_SC_PAGESIZE));
588
589 (void)explicit_memset(prng, 0, sizeof(*prng));
590 (void)munmap(prng, size);
591 }
592 #endif
593
594 /* Library state */
595
596 struct arc4random_global_state arc4random_global = {
597 #ifdef _REENTRANT
598 .lock = MUTEX_INITIALIZER,
599 #endif
600 .once = ONCE_INITIALIZER,
601 };
602
603 static void
arc4random_atfork_prepare(void)604 arc4random_atfork_prepare(void)
605 {
606
607 mutex_lock(&arc4random_global.lock);
608 (void)explicit_memset(&arc4random_global.prng, 0,
609 sizeof arc4random_global.prng);
610 }
611
612 static void
arc4random_atfork_parent(void)613 arc4random_atfork_parent(void)
614 {
615
616 mutex_unlock(&arc4random_global.lock);
617 }
618
619 static void
arc4random_atfork_child(void)620 arc4random_atfork_child(void)
621 {
622
623 mutex_unlock(&arc4random_global.lock);
624 }
625
626 #ifdef _REENTRANT
627 static void
arc4random_tsd_destructor(void * p)628 arc4random_tsd_destructor(void *p)
629 {
630 struct arc4random_prng *const prng = p;
631
632 arc4random_prng_destroy(prng);
633 }
634 #endif
635
636 static void
arc4random_initialize(void)637 arc4random_initialize(void)
638 {
639
640 /*
641 * If the crypto software is broken, abort -- something is
642 * severely wrong with this process image.
643 */
644 if (crypto_core_selftest() != 0 ||
645 crypto_prng_selftest() != 0 ||
646 crypto_onetimestream_selftest() != 0)
647 abort();
648
649 /*
650 * Set up a pthread_atfork handler to lock the global state
651 * around fork so that if forked children can't use the
652 * per-thread state, they can take the lock and use the global
653 * state without deadlock. If this fails, we will fall back to
654 * PRNG state on the stack reinitialized from the kernel
655 * entropy pool at every call.
656 */
657 if (pthread_atfork(&arc4random_atfork_prepare,
658 &arc4random_atfork_parent, &arc4random_atfork_child)
659 == 0)
660 arc4random_global.forksafe = true;
661
662 /*
663 * For multithreaded builds, try to allocate a per-thread PRNG
664 * state to avoid contention due to arc4random.
665 */
666 #ifdef _REENTRANT
667 if (thr_keycreate(&arc4random_global.thread_key,
668 &arc4random_tsd_destructor) == 0)
669 arc4random_global.per_thread = true;
670 #endif
671
672 /*
673 * Note that the arc4random library state has been initialized
674 * for the sake of automatic tests.
675 */
676 arc4random_global.initialized = true;
677 }
678
679 static struct arc4random_prng *
arc4random_prng_get(struct arc4random_prng * fallback)680 arc4random_prng_get(struct arc4random_prng *fallback)
681 {
682 struct arc4random_prng *prng = NULL;
683
684 /* Make sure the library is initialized. */
685 thr_once(&arc4random_global.once, &arc4random_initialize);
686
687 #ifdef _REENTRANT
688 /* Get or create the per-thread PRNG state. */
689 prng = __predict_true(arc4random_global.per_thread)
690 ? thr_getspecific(arc4random_global.thread_key)
691 : NULL;
692 if (__predict_false(prng == NULL) && arc4random_global.per_thread) {
693 prng = arc4random_prng_create();
694 thr_setspecific(arc4random_global.thread_key, prng);
695 }
696 #endif
697
698 /*
699 * If we can't create it, fall back to the global PRNG -- or an
700 * on-stack PRNG, in the unlikely event that pthread_atfork
701 * failed, which we have to seed from scratch each time
702 * (suboptimal, but unlikely, so not worth optimizing).
703 */
704 if (__predict_false(prng == NULL)) {
705 if (__predict_true(arc4random_global.forksafe)) {
706 mutex_lock(&arc4random_global.lock);
707 prng = &arc4random_global.prng;
708 } else {
709 prng = fallback;
710 memset(prng, 0, sizeof(*prng));
711 }
712 }
713
714 /* Guarantee the PRNG is seeded. */
715 if (__predict_false(prng->arc4_epoch != entropy_epoch()))
716 arc4random_prng_addrandom(prng, NULL, 0);
717
718 return prng;
719 }
720
721 static void
arc4random_prng_put(struct arc4random_prng * prng,struct arc4random_prng * fallback)722 arc4random_prng_put(struct arc4random_prng *prng,
723 struct arc4random_prng *fallback)
724 {
725
726 /*
727 * If we had to use a stack fallback, zero it before we return
728 * so that after we return we avoid leaving secrets on the
729 * stack that could recover the parent's future outputs in an
730 * unprivileged forked child (of course, we can't guarantee
731 * that the compiler hasn't spilled anything; this is
732 * best-effort, not a guarantee).
733 */
734 if (__predict_false(prng == fallback))
735 explicit_memset(fallback, 0, sizeof(*fallback));
736
737 /* If we had fallen back to the global PRNG, unlock it. */
738 if (__predict_false(prng == &arc4random_global.prng))
739 mutex_unlock(&arc4random_global.lock);
740 }
741
742 /* Public API */
743
744 uint32_t
arc4random(void)745 arc4random(void)
746 {
747 struct arc4random_prng *prng, fallback;
748 uint32_t v;
749
750 prng = arc4random_prng_get(&fallback);
751 crypto_prng_buf(&prng->arc4_prng, &v, sizeof v);
752 arc4random_prng_put(prng, &fallback);
753
754 return v;
755 }
756
757 void
arc4random_buf(void * buf,size_t len)758 arc4random_buf(void *buf, size_t len)
759 {
760 struct arc4random_prng *prng, fallback;
761
762 if (len <= crypto_prng_MAXOUTPUTBYTES) {
763 prng = arc4random_prng_get(&fallback);
764 crypto_prng_buf(&prng->arc4_prng, buf, len);
765 arc4random_prng_put(prng, &fallback);
766 } else {
767 uint8_t seed[crypto_onetimestream_SEEDBYTES];
768
769 prng = arc4random_prng_get(&fallback);
770 crypto_prng_buf(&prng->arc4_prng, seed, sizeof seed);
771 arc4random_prng_put(prng, &fallback);
772
773 crypto_onetimestream(seed, buf, len);
774 (void)explicit_memset(seed, 0, sizeof seed);
775 }
776 }
777
778 uint32_t
arc4random_uniform(uint32_t bound)779 arc4random_uniform(uint32_t bound)
780 {
781 struct arc4random_prng *prng, fallback;
782 uint32_t minimum, r;
783
784 /*
785 * We want a uniform random choice in [0, n), and arc4random()
786 * makes a uniform random choice in [0, 2^32). If we reduce
787 * that modulo n, values in [0, 2^32 mod n) will be represented
788 * slightly more than values in [2^32 mod n, n). Instead we
789 * choose only from [2^32 mod n, 2^32) by rejecting samples in
790 * [0, 2^32 mod n), to avoid counting the extra representative
791 * of [0, 2^32 mod n). To compute 2^32 mod n, note that
792 *
793 * 2^32 mod n = 2^32 mod n - 0
794 * = 2^32 mod n - n mod n
795 * = (2^32 - n) mod n,
796 *
797 * the last of which is what we compute in 32-bit arithmetic.
798 */
799 minimum = (-bound % bound);
800
801 prng = arc4random_prng_get(&fallback);
802 do crypto_prng_buf(&prng->arc4_prng, &r, sizeof r);
803 while (__predict_false(r < minimum));
804 arc4random_prng_put(prng, &fallback);
805
806 return (r % bound);
807 }
808
809 void
arc4random_stir(void)810 arc4random_stir(void)
811 {
812 struct arc4random_prng *prng, fallback;
813
814 prng = arc4random_prng_get(&fallback);
815 arc4random_prng_addrandom(prng, NULL, 0);
816 arc4random_prng_put(prng, &fallback);
817 }
818
819 /*
820 * Silly signature here is for hysterical raisins. Should instead be
821 * const void *data and size_t datalen.
822 */
823 void
arc4random_addrandom(u_char * data,int datalen)824 arc4random_addrandom(u_char *data, int datalen)
825 {
826 struct arc4random_prng *prng, fallback;
827
828 _DIAGASSERT(0 <= datalen);
829
830 prng = arc4random_prng_get(&fallback);
831 arc4random_prng_addrandom(prng, data, datalen);
832 arc4random_prng_put(prng, &fallback);
833 }
834
835 #ifdef _ARC4RANDOM_TEST
836
837 #include <sys/wait.h>
838
839 #include <err.h>
840 #include <stdio.h>
841
842 int
main(int argc __unused,char ** argv __unused)843 main(int argc __unused, char **argv __unused)
844 {
845 unsigned char gubbish[] = "random gubbish";
846 const uint8_t zero64[64] = {0};
847 uint8_t buf[2048];
848 unsigned i, a, n;
849
850 /* Test arc4random: should not be deterministic. */
851 if (printf("arc4random: %08"PRIx32"\n", arc4random()) < 0)
852 err(1, "printf");
853
854 /* Test stirring: should definitely not be deterministic. */
855 arc4random_stir();
856
857 /* Test small buffer. */
858 arc4random_buf(buf, 8);
859 if (printf("arc4randombuf small:") < 0)
860 err(1, "printf");
861 for (i = 0; i < 8; i++)
862 if (printf(" %02x", buf[i]) < 0)
863 err(1, "printf");
864 if (printf("\n") < 0)
865 err(1, "printf");
866
867 /* Test addrandom: should not make the rest deterministic. */
868 arc4random_addrandom(gubbish, sizeof gubbish);
869
870 /* Test large buffer. */
871 arc4random_buf(buf, sizeof buf);
872 if (printf("arc4randombuf_large:") < 0)
873 err(1, "printf");
874 for (i = 0; i < sizeof buf; i++)
875 if (printf(" %02x", buf[i]) < 0)
876 err(1, "printf");
877 if (printf("\n") < 0)
878 err(1, "printf");
879
880 /* Test misaligned small and large. */
881 for (a = 0; a < 64; a++) {
882 for (n = a; n < sizeof buf; n++) {
883 (void)memset(buf, 0, sizeof buf);
884 arc4random_buf(buf, n - a);
885 if (memcmp(buf + n - a, zero64, a) != 0)
886 errx(1, "arc4random buffer overflow 0");
887
888 (void)memset(buf, 0, sizeof buf);
889 arc4random_buf(buf + a, n - a);
890 if (memcmp(buf, zero64, a) != 0)
891 errx(1, "arc4random buffer overflow 1");
892
893 if ((2*a) <= n) {
894 (void)memset(buf, 0, sizeof buf);
895 arc4random_buf(buf + a, n - a - a);
896 if (memcmp(buf + n - a, zero64, a) != 0)
897 errx(1,
898 "arc4random buffer overflow 2");
899 }
900 }
901 }
902
903 /* Test fork-safety. */
904 {
905 pid_t pid, rpid;
906 int status;
907
908 pid = fork();
909 switch (pid) {
910 case -1:
911 err(1, "fork");
912 case 0: {
913 /*
914 * Verify the epoch has been set to zero by fork.
915 */
916 struct arc4random_prng *prng = NULL;
917 #ifdef _REENTRANT
918 prng = arc4random_global.per_thread
919 ? thr_getspecific(arc4random_global.thread_key)
920 : NULL;
921 #endif
922 if (prng == NULL)
923 prng = &arc4random_global.prng;
924 _exit(prng->arc4_epoch != 0);
925 }
926 default:
927 rpid = waitpid(pid, &status, 0);
928 if (rpid == -1)
929 err(1, "waitpid");
930 if (rpid != pid)
931 errx(1, "waitpid returned wrong pid"
932 ": %"PRIdMAX" != %"PRIdMAX,
933 (intmax_t)rpid,
934 (intmax_t)pid);
935 if (WIFEXITED(status)) {
936 if (WEXITSTATUS(status) != 0)
937 errx(1, "child exited with %d",
938 WEXITSTATUS(status));
939 } else if (WIFSIGNALED(status)) {
940 errx(1, "child terminated on signal %d",
941 WTERMSIG(status));
942 } else {
943 errx(1, "child died mysteriously: %d", status);
944 }
945 }
946 }
947
948 /* XXX Test multithreaded fork safety...? */
949
950 return 0;
951 }
952 #endif
953