cprng_fast.c revision 1.2
1 /* $NetBSD: cprng_fast.c,v 1.2 2014/08/10 16:44:35 tls 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.2 2014/08/10 16:44:35 tls Exp $"); 34 35 #include <sys/types.h> 36 #include <sys/bitops.h> 37 #include <sys/param.h> 38 #include <sys/cpu.h> 39 #include <sys/intr.h> 40 #include <sys/percpu.h> 41 #include <sys/cprng.h> 42 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 extern int rnd_initial_entropy; 222 223 void 224 cprng_fast_init(void) 225 { 226 struct cpu_info *ci; 227 CPU_INFO_ITERATOR cii; 228 229 crypto_core_selftest(); 230 cprng_fast_percpu = percpu_alloc(sizeof(struct cprng_fast)); 231 for (CPU_INFO_FOREACH(cii, ci)) { 232 struct cprng_fast *cprng; 233 uint8_t seed[CPRNG_FAST_SEED_BYTES]; 234 235 percpu_traverse_enter(); 236 cprng = percpu_getptr_remote(cprng_fast_percpu, ci); 237 cprng_strong(kern_cprng, seed, sizeof(seed), FASYNC); 238 /* Can't do anything about it if not full entropy. */ 239 cprng_fast_seed(cprng, seed); 240 explicit_memset(seed, 0, sizeof(seed)); 241 percpu_traverse_exit(); 242 } 243 cprng_fast_softint = softint_establish(SOFTINT_SERIAL|SOFTINT_MPSAFE, 244 &cprng_fast_intr, NULL); 245 } 246 247 static inline int 248 cprng_fast_get(struct cprng_fast **cprngp) 249 { 250 251 *cprngp = percpu_getref(cprng_fast_percpu); 252 return splvm(); 253 } 254 255 static inline void 256 cprng_fast_put(struct cprng_fast *cprng, int s) 257 { 258 259 KASSERT((cprng == percpu_getref(cprng_fast_percpu)) && 260 (percpu_putref(cprng_fast_percpu), true)); 261 splx(s); 262 percpu_putref(cprng_fast_percpu); 263 } 264 265 static inline void 267 cprng_fast_schedule_reseed(struct cprng_fast *cprng __unused) 268 { 269 270 softint_schedule(cprng_fast_softint); 271 } 272 273 static void 274 cprng_fast_intr(void *cookie __unused) 275 { 276 struct cprng_fast *cprng; 277 uint8_t seed[CPRNG_FAST_SEED_BYTES]; 278 279 cprng_strong(kern_cprng, seed, sizeof(seed), FASYNC); 280 281 cprng = percpu_getref(cprng_fast_percpu); 282 cprng_fast_seed(cprng, seed); 283 percpu_putref(cprng_fast_percpu); 284 285 explicit_memset(seed, 0, sizeof(seed)); 286 } 287 288 /* CPRNG algorithm */ 290 291 /* 292 * The state consists of a key, the current nonce, and a 64-byte buffer 293 * of output. Since we fill the buffer only when we need output, and 294 * eat a 32-bit word at a time, one 32-bit word of the buffer would be 295 * wasted. Instead, we repurpose it to count the number of entries in 296 * the buffer remaining, counting from high to low in order to allow 297 * comparison to zero to detect when we need to refill it. 298 */ 299 #define CPRNG_FAST_BUFIDX (crypto_core_OUTPUTWORDS - 1) 300 301 static inline void 302 cprng_fast_seed(struct cprng_fast *cprng, const void *seed) 303 { 304 305 (void)memset(cprng->buffer, 0, sizeof cprng->buffer); 306 (void)memcpy(cprng->key, seed, sizeof cprng->key); 307 (void)memset(cprng->nonce, 0, sizeof cprng->nonce); 308 309 if (__predict_true(rnd_initial_entropy)) { 310 cprng->have_initial = true; 311 } else { 312 cprng->have_initial = false; 313 } 314 } 315 316 static inline uint32_t 317 cprng_fast_word(struct cprng_fast *cprng) 318 { 319 uint32_t v; 320 321 if (__predict_true(0 < cprng->buffer[CPRNG_FAST_BUFIDX])) { 322 v = cprng->buffer[--cprng->buffer[CPRNG_FAST_BUFIDX]]; 323 } else { 324 /* If we don't have enough words, refill the buffer. */ 325 crypto_core(cprng->buffer, cprng->nonce, cprng->key, 326 crypto_core_constant32); 327 if (__predict_false(++cprng->nonce[0] == 0)) { 328 cprng->nonce[1]++; 329 cprng_fast_schedule_reseed(cprng); 330 } else { 331 if (__predict_false(false == cprng->have_initial)) { 332 if (rnd_initial_entropy) { 333 cprng_fast_schedule_reseed(cprng); 334 } 335 } 336 } 337 v = cprng->buffer[CPRNG_FAST_BUFIDX]; 338 cprng->buffer[CPRNG_FAST_BUFIDX] = CPRNG_FAST_BUFIDX; 339 } 340 341 return v; 342 } 343 344 static inline void 345 cprng_fast_buf(struct cprng_fast *cprng, void *buf, unsigned n) 346 { 347 uint8_t *p = buf; 348 uint32_t v; 349 unsigned r; 350 351 while (n) { 352 r = MIN(n, 4); 353 n -= r; 354 v = cprng_fast_word(cprng); 355 while (r--) { 356 *p++ = (v & 0xff); 357 v >>= 8; 358 } 359 } 360 } 361 362 /* 364 * crypto_onetimestream: Expand a short unpredictable one-time seed 365 * into a long unpredictable output. 366 */ 367 static void 368 crypto_onetimestream(const uint32_t seed[crypto_core_KEYWORDS], void *buf, 369 size_t n) 370 { 371 uint32_t block[crypto_core_OUTPUTWORDS]; 372 uint32_t nonce[crypto_core_INPUTWORDS] = {0}; 373 uint8_t *p8; 374 uint32_t *p32; 375 size_t ni, nb, nf; 376 377 /* 378 * Guarantee we can generate up to n bytes. We have 379 * 2^(32*INPUTWORDS) possible inputs yielding output of 380 * 4*OUTPUTWORDS*2^(32*INPUTWORDS) bytes. It suffices to 381 * require that sizeof n > (1/CHAR_BIT) log_2 n be less than 382 * (1/CHAR_BIT) log_2 of the total output stream length. We 383 * have 384 * 385 * log_2 (4 o 2^(32 i)) = log_2 (4 o) + log_2 2^(32 i) 386 * = 2 + log_2 o + 32 i. 387 */ 388 __CTASSERT(CHAR_BIT*sizeof n <= 389 (2 + ilog2(crypto_core_OUTPUTWORDS) + 32*crypto_core_INPUTWORDS)); 390 391 p8 = buf; 392 p32 = (uint32_t *)roundup2((uintptr_t)p8, sizeof(uint32_t)); 393 ni = (uint8_t *)p32 - p8; 394 if (n < ni) 395 ni = n; 396 nb = (n - ni) / sizeof block; 397 nf = (n - ni) % sizeof block; 398 399 KASSERT(((uintptr_t)p32 & 3) == 0); 400 KASSERT(ni <= n); 401 KASSERT(nb <= (n / sizeof block)); 402 KASSERT(nf <= n); 403 KASSERT(n == (ni + (nb * sizeof block) + nf)); 404 KASSERT(ni < sizeof(uint32_t)); 405 KASSERT(nf < sizeof block); 406 407 if (ni) { 408 crypto_core(block, nonce, seed, crypto_core_constant32); 409 nonce[0]++; 410 (void)memcpy(p8, block, ni); 411 } 412 while (nb--) { 413 crypto_core(p32, nonce, seed, crypto_core_constant32); 414 if (++nonce[0] == 0) 415 nonce[1]++; 416 p32 += crypto_core_OUTPUTWORDS; 417 } 418 if (nf) { 419 crypto_core(block, nonce, seed, crypto_core_constant32); 420 if (++nonce[0] == 0) 421 nonce[1]++; 422 (void)memcpy(p32, block, nf); 423 } 424 425 if (ni | nf) 426 (void)explicit_memset(block, 0, sizeof block); 427 } 428 429 /* Public API */ 431 432 uint32_t 433 cprng_fast32(void) 434 { 435 struct cprng_fast *cprng; 436 uint32_t v; 437 int s; 438 439 s = cprng_fast_get(&cprng); 440 v = cprng_fast_word(cprng); 441 cprng_fast_put(cprng, s); 442 443 return v; 444 } 445 446 uint64_t 447 cprng_fast64(void) 448 { 449 struct cprng_fast *cprng; 450 uint32_t hi, lo; 451 int s; 452 453 s = cprng_fast_get(&cprng); 454 hi = cprng_fast_word(cprng); 455 lo = cprng_fast_word(cprng); 456 cprng_fast_put(cprng, s); 457 458 return ((uint64_t)hi << 32) | lo; 459 } 460 461 static void 462 cprng_fast_buf_short(void *buf, size_t len) 463 { 464 struct cprng_fast *cprng; 465 int s; 466 467 s = cprng_fast_get(&cprng); 468 cprng_fast_buf(cprng, buf, len); 469 cprng_fast_put(cprng, s); 470 } 471 472 static __noinline void 473 cprng_fast_buf_long(void *buf, size_t len) 474 { 475 uint32_t seed[crypto_core_KEYWORDS]; 476 struct cprng_fast *cprng; 477 int s; 478 479 s = cprng_fast_get(&cprng); 480 cprng_fast_buf(cprng, seed, sizeof seed); 481 cprng_fast_put(cprng, s); 482 483 crypto_onetimestream(seed, buf, len); 484 485 (void)explicit_memset(seed, 0, sizeof seed); 486 } 487 488 size_t 489 cprng_fast(void *buf, size_t len) 490 { 491 492 /* 493 * We don't want to hog the CPU, so we use the short version, 494 * to generate output without preemption, only if we can do it 495 * with at most one crypto_core. 496 */ 497 if (len <= (sizeof(uint32_t) * crypto_core_OUTPUTWORDS)) 498 cprng_fast_buf_short(buf, len); 499 else 500 cprng_fast_buf_long(buf, len); 501 502 return len; 503 } 504
Indexes created Tue Sep 30 07:10:03 GMT 2025