cprng_fast.c revision 1.7
1 /* $NetBSD: cprng_fast.c,v 1.7 2014/08/11 13:01:58 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 #include <sys/cdefs.h> 33 __KERNEL_RCSID(0, "$NetBSD: cprng_fast.c,v 1.7 2014/08/11 13:01:58 riastradh Exp $"); 34 35 #include <sys/types.h> 36 #include <sys/param.h> 37 #include <sys/bitops.h> 38 #include <sys/cprng.h> 39 #include <sys/cpu.h> 40 #include <sys/intr.h> 41 #include <sys/percpu.h> 42 #include <sys/rnd.h> 43 44 /* ChaCha core */ 46 47 #define crypto_core_OUTPUTWORDS 16 48 #define crypto_core_INPUTWORDS 4 49 #define crypto_core_KEYWORDS 8 50 #define crypto_core_CONSTWORDS 4 51 52 #define crypto_core_ROUNDS 8 53 54 static uint32_t 55 rotate(uint32_t u, unsigned c) 56 { 57 58 return (u << c) | (u >> (32 - c)); 59 } 60 61 #define QUARTERROUND(a, b, c, d) do { \ 62 (a) += (b); (d) ^= (a); (d) = rotate((d), 16); \ 63 (c) += (d); (b) ^= (c); (b) = rotate((b), 12); \ 64 (a) += (b); (d) ^= (a); (d) = rotate((d), 8); \ 65 (c) += (d); (b) ^= (c); (b) = rotate((b), 7); \ 66 } while (0) 67 68 static void 69 crypto_core(uint32_t *out, const uint32_t *in, const uint32_t *k, 70 const uint32_t *c) 71 { 72 uint32_t x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15; 73 int i; 74 75 x0 = c[0]; 76 x1 = c[1]; 77 x2 = c[2]; 78 x3 = c[3]; 79 x4 = k[0]; 80 x5 = k[1]; 81 x6 = k[2]; 82 x7 = k[3]; 83 x8 = k[4]; 84 x9 = k[5]; 85 x10 = k[6]; 86 x11 = k[7]; 87 x12 = in[0]; 88 x13 = in[1]; 89 x14 = in[2]; 90 x15 = in[3]; 91 92 for (i = crypto_core_ROUNDS; i > 0; i -= 2) { 93 QUARTERROUND( x0, x4, x8,x12); 94 QUARTERROUND( x1, x5, x9,x13); 95 QUARTERROUND( x2, x6,x10,x14); 96 QUARTERROUND( x3, x7,x11,x15); 97 QUARTERROUND( x0, x5,x10,x15); 98 QUARTERROUND( x1, x6,x11,x12); 99 QUARTERROUND( x2, x7, x8,x13); 100 QUARTERROUND( x3, x4, x9,x14); 101 } 102 103 out[0] = x0 + c[0]; 104 out[1] = x1 + c[1]; 105 out[2] = x2 + c[2]; 106 out[3] = x3 + c[3]; 107 out[4] = x4 + k[0]; 108 out[5] = x5 + k[1]; 109 out[6] = x6 + k[2]; 110 out[7] = x7 + k[3]; 111 out[8] = x8 + k[4]; 112 out[9] = x9 + k[5]; 113 out[10] = x10 + k[6]; 114 out[11] = x11 + k[7]; 115 out[12] = x12 + in[0]; 116 out[13] = x13 + in[1]; 117 out[14] = x14 + in[2]; 118 out[15] = x15 + in[3]; 119 } 120 121 /* `expand 32-byte k' */ 123 static const uint32_t crypto_core_constant32[4] = { 124 0x61707865U, 0x3320646eU, 0x79622d32U, 0x6b206574U, 125 }; 126 127 /* 128 * Test vector for ChaCha20 from 129 * <http://tools.ietf.org/html/draft-strombergson-chacha-test-vectors-00>, 130 * test vectors for ChaCha12 and ChaCha8 generated by the same 131 * crypto_core code with crypto_core_ROUNDS varied. 132 */ 133 134 #define check(E) do \ 135 { \ 136 if (!(E)) \ 137 panic("crypto self-test failed: %s", #E); \ 138 } while (0) 139 140 static void 141 crypto_core_selftest(void) 142 { 143 const uint32_t zero32[8] = {0}; 144 const uint8_t sigma[] = "expand 32-byte k"; 145 uint32_t block[16]; 146 unsigned i; 147 148 #if crypto_core_ROUNDS == 8 149 static const uint8_t out[64] = { 150 0x3e,0x00,0xef,0x2f,0x89,0x5f,0x40,0xd6, 151 0x7f,0x5b,0xb8,0xe8,0x1f,0x09,0xa5,0xa1, 152 0x2c,0x84,0x0e,0xc3,0xce,0x9a,0x7f,0x3b, 153 0x18,0x1b,0xe1,0x88,0xef,0x71,0x1a,0x1e, 154 0x98,0x4c,0xe1,0x72,0xb9,0x21,0x6f,0x41, 155 0x9f,0x44,0x53,0x67,0x45,0x6d,0x56,0x19, 156 0x31,0x4a,0x42,0xa3,0xda,0x86,0xb0,0x01, 157 0x38,0x7b,0xfd,0xb8,0x0e,0x0c,0xfe,0x42, 158 }; 159 #elif crypto_core_ROUNDS == 12 160 static const uint8_t out[64] = { 161 0x9b,0xf4,0x9a,0x6a,0x07,0x55,0xf9,0x53, 162 0x81,0x1f,0xce,0x12,0x5f,0x26,0x83,0xd5, 163 0x04,0x29,0xc3,0xbb,0x49,0xe0,0x74,0x14, 164 0x7e,0x00,0x89,0xa5,0x2e,0xae,0x15,0x5f, 165 0x05,0x64,0xf8,0x79,0xd2,0x7a,0xe3,0xc0, 166 0x2c,0xe8,0x28,0x34,0xac,0xfa,0x8c,0x79, 167 0x3a,0x62,0x9f,0x2c,0xa0,0xde,0x69,0x19, 168 0x61,0x0b,0xe8,0x2f,0x41,0x13,0x26,0xbe, 169 }; 170 #elif crypto_core_ROUNDS == 20 171 static const uint8_t out[64] = { 172 0x76,0xb8,0xe0,0xad,0xa0,0xf1,0x3d,0x90, 173 0x40,0x5d,0x6a,0xe5,0x53,0x86,0xbd,0x28, 174 0xbd,0xd2,0x19,0xb8,0xa0,0x8d,0xed,0x1a, 175 0xa8,0x36,0xef,0xcc,0x8b,0x77,0x0d,0xc7, 176 0xda,0x41,0x59,0x7c,0x51,0x57,0x48,0x8d, 177 0x77,0x24,0xe0,0x3f,0xb8,0xd8,0x4a,0x37, 178 0x6a,0x43,0xb8,0xf4,0x15,0x18,0xa1,0x1c, 179 0xc3,0x87,0xb6,0x69,0xb2,0xee,0x65,0x86, 180 }; 181 #else 182 #error crypto_core_ROUNDS must be 8, 12, or 20. 183 #endif 184 185 check(crypto_core_constant32[0] == le32dec(&sigma[0])); 186 check(crypto_core_constant32[1] == le32dec(&sigma[4])); 187 check(crypto_core_constant32[2] == le32dec(&sigma[8])); 188 check(crypto_core_constant32[3] == le32dec(&sigma[12])); 189 190 crypto_core(block, zero32, zero32, crypto_core_constant32); 191 for (i = 0; i < 16; i++) 192 check(block[i] == le32dec(&out[i*4])); 193 } 194 195 #undef check 196 197 #define CPRNG_FAST_SEED_BYTES (crypto_core_KEYWORDS * sizeof(uint32_t)) 199 200 struct cprng_fast { 201 uint32_t buffer[crypto_core_OUTPUTWORDS]; 202 uint32_t key[crypto_core_KEYWORDS]; 203 uint32_t nonce[crypto_core_INPUTWORDS]; 204 bool have_initial; 205 }; 206 207 __CTASSERT(sizeof ((struct cprng_fast *)0)->key == CPRNG_FAST_SEED_BYTES); 208 209 static void cprng_fast_schedule_reseed(struct cprng_fast *); 210 static void cprng_fast_intr(void *); 211 212 static void cprng_fast_seed(struct cprng_fast *, const void *); 213 static void cprng_fast_buf(struct cprng_fast *, void *, unsigned); 214 215 static void cprng_fast_buf_short(void *, size_t); 216 static void cprng_fast_buf_long(void *, size_t); 217 218 static percpu_t *cprng_fast_percpu __read_mostly; 219 static void *cprng_fast_softint __read_mostly; 220 221 void 222 cprng_fast_init(void) 223 { 224 struct cpu_info *ci; 225 CPU_INFO_ITERATOR cii; 226 227 crypto_core_selftest(); 228 cprng_fast_percpu = percpu_alloc(sizeof(struct cprng_fast)); 229 for (CPU_INFO_FOREACH(cii, ci)) { 230 struct cprng_fast *cprng; 231 uint8_t seed[CPRNG_FAST_SEED_BYTES]; 232 233 percpu_traverse_enter(); 234 cprng = percpu_getptr_remote(cprng_fast_percpu, ci); 235 cprng_strong(kern_cprng, seed, sizeof(seed), FASYNC); 236 /* Can't do anything about it if not full entropy. */ 237 cprng_fast_seed(cprng, seed); 238 explicit_memset(seed, 0, sizeof(seed)); 239 percpu_traverse_exit(); 240 } 241 cprng_fast_softint = softint_establish(SOFTINT_SERIAL|SOFTINT_MPSAFE, 242 &cprng_fast_intr, NULL); 243 } 244 245 static inline int 246 cprng_fast_get(struct cprng_fast **cprngp) 247 { 248 249 *cprngp = percpu_getref(cprng_fast_percpu); 250 return splvm(); 251 } 252 253 static inline void 254 cprng_fast_put(struct cprng_fast *cprng, int s) 255 { 256 257 KASSERT((cprng == percpu_getref(cprng_fast_percpu)) && 258 (percpu_putref(cprng_fast_percpu), true)); 259 splx(s); 260 percpu_putref(cprng_fast_percpu); 261 } 262 263 static inline void 265 cprng_fast_schedule_reseed(struct cprng_fast *cprng __unused) 266 { 267 268 softint_schedule(cprng_fast_softint); 269 } 270 271 static void 272 cprng_fast_intr(void *cookie __unused) 273 { 274 struct cprng_fast *cprng; 275 uint8_t seed[CPRNG_FAST_SEED_BYTES]; 276 int s; 277 278 cprng_strong(kern_cprng, seed, sizeof(seed), FASYNC); 279 280 cprng = percpu_getref(cprng_fast_percpu); 281 s = splvm(); 282 cprng_fast_seed(cprng, seed); 283 splx(s); 284 percpu_putref(cprng_fast_percpu); 285 286 explicit_memset(seed, 0, sizeof(seed)); 287 } 288 289 /* CPRNG algorithm */ 291 292 /* 293 * The state consists of a key, the current nonce, and a 64-byte buffer 294 * of output. Since we fill the buffer only when we need output, and 295 * eat a 32-bit word at a time, one 32-bit word of the buffer would be 296 * wasted. Instead, we repurpose it to count the number of entries in 297 * the buffer remaining, counting from high to low in order to allow 298 * comparison to zero to detect when we need to refill it. 299 */ 300 #define CPRNG_FAST_BUFIDX (crypto_core_OUTPUTWORDS - 1) 301 302 static void 303 cprng_fast_seed(struct cprng_fast *cprng, const void *seed) 304 { 305 306 (void)memset(cprng->buffer, 0, sizeof cprng->buffer); 307 (void)memcpy(cprng->key, seed, sizeof cprng->key); 308 (void)memset(cprng->nonce, 0, sizeof cprng->nonce); 309 310 if (__predict_true(rnd_initial_entropy)) { 311 cprng->have_initial = true; 312 } else { 313 cprng->have_initial = false; 314 } 315 } 316 317 static inline uint32_t 318 cprng_fast_word(struct cprng_fast *cprng) 319 { 320 uint32_t v; 321 322 if (__predict_true(0 < cprng->buffer[CPRNG_FAST_BUFIDX])) { 323 v = cprng->buffer[--cprng->buffer[CPRNG_FAST_BUFIDX]]; 324 } else { 325 /* If we don't have enough words, refill the buffer. */ 326 crypto_core(cprng->buffer, cprng->nonce, cprng->key, 327 crypto_core_constant32); 328 if (__predict_false(++cprng->nonce[0] == 0)) { 329 cprng->nonce[1]++; 330 cprng_fast_schedule_reseed(cprng); 331 } else { 332 if (__predict_false(false == cprng->have_initial)) { 333 if (rnd_initial_entropy) { 334 cprng_fast_schedule_reseed(cprng); 335 } 336 } 337 } 338 v = cprng->buffer[CPRNG_FAST_BUFIDX]; 339 cprng->buffer[CPRNG_FAST_BUFIDX] = CPRNG_FAST_BUFIDX; 340 } 341 342 return v; 343 } 344 345 static inline void 346 cprng_fast_buf(struct cprng_fast *cprng, void *buf, unsigned n) 347 { 348 uint8_t *p = buf; 349 uint32_t v; 350 unsigned r; 351 352 while (n) { 353 r = MIN(n, 4); 354 n -= r; 355 v = cprng_fast_word(cprng); 356 while (r--) { 357 *p++ = (v & 0xff); 358 v >>= 8; 359 } 360 } 361 } 362 363 /* 365 * crypto_onetimestream: Expand a short unpredictable one-time seed 366 * into a long unpredictable output. 367 */ 368 static void 369 crypto_onetimestream(const uint32_t seed[crypto_core_KEYWORDS], void *buf, 370 size_t n) 371 { 372 uint32_t block[crypto_core_OUTPUTWORDS]; 373 uint32_t nonce[crypto_core_INPUTWORDS] = {0}; 374 uint8_t *p8; 375 uint32_t *p32; 376 size_t ni, nb, nf; 377 378 /* 379 * Guarantee we can generate up to n bytes. We have 380 * 2^(32*INPUTWORDS) possible inputs yielding output of 381 * 4*OUTPUTWORDS*2^(32*INPUTWORDS) bytes. It suffices to 382 * require that sizeof n > (1/CHAR_BIT) log_2 n be less than 383 * (1/CHAR_BIT) log_2 of the total output stream length. We 384 * have 385 * 386 * log_2 (4 o 2^(32 i)) = log_2 (4 o) + log_2 2^(32 i) 387 * = 2 + log_2 o + 32 i. 388 */ 389 __CTASSERT(CHAR_BIT*sizeof n <= 390 (2 + ilog2(crypto_core_OUTPUTWORDS) + 32*crypto_core_INPUTWORDS)); 391 392 p8 = buf; 393 p32 = (uint32_t *)roundup2((uintptr_t)p8, sizeof(uint32_t)); 394 ni = (uint8_t *)p32 - p8; 395 if (n < ni) 396 ni = n; 397 nb = (n - ni) / sizeof block; 398 nf = (n - ni) % sizeof block; 399 400 KASSERT(((uintptr_t)p32 & 3) == 0); 401 KASSERT(ni <= n); 402 KASSERT(nb <= (n / sizeof block)); 403 KASSERT(nf <= n); 404 KASSERT(n == (ni + (nb * sizeof block) + nf)); 405 KASSERT(ni < sizeof(uint32_t)); 406 KASSERT(nf < sizeof block); 407 408 if (ni) { 409 crypto_core(block, nonce, seed, crypto_core_constant32); 410 nonce[0]++; 411 (void)memcpy(p8, block, ni); 412 } 413 while (nb--) { 414 crypto_core(p32, nonce, seed, crypto_core_constant32); 415 if (++nonce[0] == 0) 416 nonce[1]++; 417 p32 += crypto_core_OUTPUTWORDS; 418 } 419 if (nf) { 420 crypto_core(block, nonce, seed, crypto_core_constant32); 421 if (++nonce[0] == 0) 422 nonce[1]++; 423 (void)memcpy(p32, block, nf); 424 } 425 426 if (ni | nf) 427 (void)explicit_memset(block, 0, sizeof block); 428 } 429 430 /* Public API */ 432 433 uint32_t 434 cprng_fast32(void) 435 { 436 struct cprng_fast *cprng; 437 uint32_t v; 438 int s; 439 440 s = cprng_fast_get(&cprng); 441 v = cprng_fast_word(cprng); 442 cprng_fast_put(cprng, s); 443 444 return v; 445 } 446 447 uint64_t 448 cprng_fast64(void) 449 { 450 struct cprng_fast *cprng; 451 uint32_t hi, lo; 452 int s; 453 454 s = cprng_fast_get(&cprng); 455 hi = cprng_fast_word(cprng); 456 lo = cprng_fast_word(cprng); 457 cprng_fast_put(cprng, s); 458 459 return ((uint64_t)hi << 32) | lo; 460 } 461 462 static void 463 cprng_fast_buf_short(void *buf, size_t len) 464 { 465 struct cprng_fast *cprng; 466 int s; 467 468 s = cprng_fast_get(&cprng); 469 cprng_fast_buf(cprng, buf, len); 470 cprng_fast_put(cprng, s); 471 } 472 473 static __noinline void 474 cprng_fast_buf_long(void *buf, size_t len) 475 { 476 uint32_t seed[crypto_core_KEYWORDS]; 477 struct cprng_fast *cprng; 478 int s; 479 480 s = cprng_fast_get(&cprng); 481 cprng_fast_buf(cprng, seed, sizeof seed); 482 cprng_fast_put(cprng, s); 483 484 crypto_onetimestream(seed, buf, len); 485 486 (void)explicit_memset(seed, 0, sizeof seed); 487 } 488 489 size_t 490 cprng_fast(void *buf, size_t len) 491 { 492 493 /* 494 * We don't want to hog the CPU, so we use the short version, 495 * to generate output without preemption, only if we can do it 496 * with at most one crypto_core. 497 */ 498 if (len <= (sizeof(uint32_t) * crypto_core_OUTPUTWORDS)) 499 cprng_fast_buf_short(buf, len); 500 else 501 cprng_fast_buf_long(buf, len); 502 503 return len; 504 } 505
Indexes created Tue Sep 30 11:09:46 GMT 2025