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