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