1 /* 2 * Copyright (c) 2004, 2005, 2006 Robin J Carey. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions, and the following disclaimer, 9 * without modification, immediately at the beginning of the file. 10 * 2. The name of the author may not be used to endorse or promote products 11 * derived from this software without specific prior written permission. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR 17 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23 * SUCH DAMAGE. 24 * 25 * $DragonFly: src/sys/kern/kern_nrandom.c,v 1.7 2008/08/01 04:42:30 dillon Exp $ 26 */ 27 /* --- NOTES --- 28 * 29 * Note: The word "entropy" is often incorrectly used to describe 30 * random data. The word "entropy" originates from the science of 31 * Physics. The correct descriptive definition would be something 32 * along the lines of "seed", "unpredictable numbers" or 33 * "unpredictable data". 34 * 35 * Note: Some /dev/[u]random implementations save "seed" between 36 * boots which represents a security hazard since an adversary 37 * could acquire this data (since it is stored in a file). If 38 * the unpredictable data used in the above routines is only 39 * generated during Kernel operation, then an adversary can only 40 * acquire that data through a Kernel security compromise and/or 41 * a cryptographic algorithm failure/cryptanalysis. 42 * 43 * Note: On FreeBSD-4.11, interrupts have to be manually enabled 44 * using the rndcontrol(8) command. 45 * 46 * --- DESIGN (FreeBSD-4.11 based) --- 47 * 48 * The rnddev module automatically initializes itself the first time 49 * it is used (client calls any public rnddev_*() interface routine). 50 * Both CSPRNGs are initially seeded from the precise nano[up]time() routines. 51 * Tests show this method produces good enough results, suitable for intended 52 * use. It is necessary for both CSPRNGs to be completely seeded, initially. 53 * 54 * After initialization and during Kernel operation the only suitable 55 * unpredictable data available is: 56 * 57 * (1) Keyboard scan-codes. 58 * (2) Nanouptime acquired by a Keyboard/Read-Event. 59 * (3) Suitable interrupt source; hard-disk/ATA-device. 60 * 61 * (X) Mouse-event (xyz-data unsuitable); NOT IMPLEMENTED. 62 * 63 * This data is added to both CSPRNGs in real-time as it happens/ 64 * becomes-available. Additionally, unpredictable (?) data may be 65 * acquired from a true-random number generator if such a device is 66 * available to the system (not advisable !). 67 * Nanouptime() acquired by a Read-Event is a very important aspect of 68 * this design, since it ensures that unpredictable data is added to 69 * the CSPRNGs even if there are no other sources. 70 * The nanouptime() Kernel routine is used since time relative to 71 * boot is less adversary-known than time itself. 72 * 73 * This design has been thoroughly tested with debug logging 74 * and the output from both /dev/random and /dev/urandom has 75 * been tested with the DIEHARD test-suite; both pass. 76 * 77 * MODIFICATIONS MADE TO ORIGINAL "kern_random.c": 78 * 79 * 6th July 2005: 80 * 81 * o Changed ReadSeed() function to schedule future read-seed-events 82 * by at least one second. Previous implementation used a randomised 83 * scheduling { 0, 1, 2, 3 seconds }. 84 * o Changed SEED_NANOUP() function to use a "previous" accumulator 85 * algorithm similar to ReadSeed(). This ensures that there is no 86 * way that an adversary can tell what number is being added to the 87 * CSPRNGs, since the number added to the CSPRNGs at Event-Time is 88 * the sum of nanouptime()@Event and an unknown/secret number. 89 * o Changed rnddev_add_interrupt() function to schedule future 90 * interrupt-events by at least one second. Previous implementation 91 * had no scheduling algorithm which allowed an "interrupt storm" 92 * to occur resulting in skewed data entering into the CSPRNGs. 93 * 94 * 95 * 9th July 2005: 96 * 97 * o Some small cleanups and change all internal functions to be 98 * static/private. 99 * o Removed ReadSeed() since its functionality is already performed 100 * by another function { rnddev_add_interrupt_OR_read() } and remove 101 * the silly rndByte accumulator/feedback-thing (since multipying by 102 * rndByte could yield a value of 0). 103 * o Made IBAA/L14 public interface become static/private; 104 * Local to this file (not changed to that in the original C modules). 105 * 106 * 16th July 2005: 107 * 108 * o SEED_NANOUP() -> NANOUP_EVENT() function rename. 109 * o Make NANOUP_EVENT() handle the time-buffering directly so that all 110 * time-stamp-events use this single time-buffer (including keyboard). 111 * This removes dependancy on "time_second" Kernel variable. 112 * o Removed second-time-buffer code in rnddev_add_interrupt_OR_read (void). 113 * o Rewrote the time-buffering algorithm in NANOUP_EVENT() to use a 114 * randomised time-delay range. 115 * 116 * 12th Dec 2005: 117 * 118 * o Updated to (hopefully final) L15 algorithm. 119 * 120 * 12th June 2006: 121 * 122 * o Added missing (u_char *) cast in RnddevRead() function. 123 * o Changed copyright to 3-clause BSD license and cleaned up the layout 124 * of this file. 125 */ 126 127 #include <sys/types.h> 128 #include <sys/kernel.h> 129 #include <sys/systm.h> 130 #include <sys/poll.h> 131 #include <sys/event.h> 132 #include <sys/random.h> 133 #include <sys/systimer.h> 134 #include <sys/time.h> 135 #include <sys/proc.h> 136 #include <sys/lock.h> 137 #include <sys/sysctl.h> 138 #include <sys/spinlock.h> 139 #include <machine/clock.h> 140 141 #include <sys/thread2.h> 142 #include <sys/spinlock2.h> 143 #include <sys/mplock2.h> 144 145 /* 146 * Portability note: The u_char/unsigned char type is used where 147 * uint8_t from <stdint.h> or u_int8_t from <sys/types.h> should really 148 * be being used. On FreeBSD, it is safe to make the assumption that these 149 * different types are equivalent (on all architectures). 150 * The FreeBSD <sys/crypto/rc4> module also makes this assumption. 151 */ 152 153 /*------------------------------ IBAA ----------------------------------*/ 154 155 /*-------------------------- IBAA CSPRNG -------------------------------*/ 156 157 /* 158 * NOTE: The original source code from which this source code (IBAA) 159 * was taken has no copyright/license. The algorithm has no patent 160 * and is freely/publicly available from: 161 * 162 * http://www.burtleburtle.net/bob/rand/isaac.html 163 */ 164 165 /* 166 * ^ means XOR, & means bitwise AND, a<<b means shift a by b. 167 * barrel(a) shifts a 19 bits to the left, and bits wrap around 168 * ind(x) is (x AND 255), or (x mod 256) 169 */ 170 typedef u_int32_t u4; /* unsigned four bytes, 32 bits */ 171 172 #define ALPHA (8) 173 #define SIZE (1 << ALPHA) 174 #define MASK (SIZE - 1) 175 #define ind(x) ((x) & (SIZE - 1)) 176 #define barrel(a) (((a) << 20) ^ ((a) >> 12)) /* beta=32,shift=20 */ 177 178 static void IBAA 179 ( 180 u4 *m, /* Memory: array of SIZE ALPHA-bit terms */ 181 u4 *r, /* Results: the sequence, same size as m */ 182 u4 *aa, /* Accumulator: a single value */ 183 u4 *bb, /* the previous result */ 184 u4 *counter /* counter */ 185 ) 186 { 187 u4 a, b, x, y, i; 188 189 a = *aa; 190 b = *bb + *counter; 191 ++*counter; 192 for (i = 0; i < SIZE; ++i) { 193 x = m[i]; 194 a = barrel(a) + m[ind(i + (SIZE / 2))]; /* set a */ 195 m[i] = y = m[ind(x)] + a + b; /* set m */ 196 r[i] = b = m[ind(y >> ALPHA)] + x; /* set r */ 197 } 198 *bb = b; *aa = a; 199 } 200 201 /*-------------------------- IBAA CSPRNG -------------------------------*/ 202 203 204 static u4 IBAA_memory[SIZE]; 205 static u4 IBAA_results[SIZE]; 206 static u4 IBAA_aa; 207 static u4 IBAA_bb; 208 static u4 IBAA_counter; 209 210 static volatile int IBAA_byte_index; 211 212 213 static void IBAA_Init(void); 214 static void IBAA_Call(void); 215 static void IBAA_Seed(const u_int32_t val); 216 static u_char IBAA_Byte(void); 217 218 /* 219 * Initialize IBAA. 220 */ 221 static void 222 IBAA_Init(void) 223 { 224 size_t i; 225 226 for (i = 0; i < SIZE; ++i) { 227 IBAA_memory[i] = i; 228 } 229 IBAA_aa = IBAA_bb = 0; 230 IBAA_counter = 0; 231 IBAA_byte_index = sizeof(IBAA_results); /* force IBAA_Call() */ 232 } 233 234 /* 235 * PRIVATE: Call IBAA to produce 256 32-bit u4 results. 236 */ 237 static void 238 IBAA_Call (void) 239 { 240 IBAA(IBAA_memory, IBAA_results, &IBAA_aa, &IBAA_bb, &IBAA_counter); 241 IBAA_byte_index = 0; 242 } 243 244 /* 245 * Add a 32-bit u4 seed value into IBAAs memory. Mix the low 4 bits 246 * with 4 bits of PNG data to reduce the possibility of a seeding-based 247 * attack. 248 */ 249 static void 250 IBAA_Seed (const u_int32_t val) 251 { 252 static int memIndex; 253 u4 *iptr; 254 255 iptr = &IBAA_memory[memIndex & MASK]; 256 *iptr = ((*iptr << 3) | (*iptr >> 29)) + (val ^ (IBAA_Byte() & 15)); 257 ++memIndex; 258 } 259 260 /* 261 * Extract a byte from IBAAs 256 32-bit u4 results array. 262 * 263 * NOTE: This code is designed to prevent MP races from taking 264 * IBAA_byte_index out of bounds. 265 */ 266 static u_char 267 IBAA_Byte(void) 268 { 269 u_char result; 270 int index; 271 272 index = IBAA_byte_index; 273 if (index == sizeof(IBAA_results)) { 274 IBAA_Call(); 275 index = 0; 276 } 277 result = ((u_char *)IBAA_results)[index]; 278 IBAA_byte_index = index + 1; 279 return result; 280 } 281 282 /*------------------------------ IBAA ----------------------------------*/ 283 284 285 /*------------------------------- L15 ----------------------------------*/ 286 287 /* 288 * IMPORTANT NOTE: LByteType must be exactly 8-bits in size or this software 289 * will not function correctly. 290 */ 291 typedef unsigned char LByteType; 292 293 #define L15_STATE_SIZE 256 294 295 static LByteType L15_x, L15_y; 296 static LByteType L15_start_x; 297 static LByteType L15_state[L15_STATE_SIZE]; 298 299 /* 300 * PRIVATE FUNCS: 301 */ 302 303 static void L15_Swap(const LByteType pos1, const LByteType pos2); 304 static void L15_InitState(void); 305 static void L15_KSA(const LByteType * const key, 306 const size_t keyLen); 307 static void L15_Discard(const LByteType numCalls); 308 309 /* 310 * PUBLIC INTERFACE: 311 */ 312 static void L15(const LByteType * const key, const size_t keyLen); 313 static LByteType L15_Byte(void); 314 static void L15_Vector(const LByteType * const key, 315 const size_t keyLen); 316 317 static __inline void 318 L15_Swap(const LByteType pos1, const LByteType pos2) 319 { 320 const LByteType save1 = L15_state[pos1]; 321 322 L15_state[pos1] = L15_state[pos2]; 323 L15_state[pos2] = save1; 324 } 325 326 static void 327 L15_InitState (void) 328 { 329 size_t i; 330 for (i = 0; i < L15_STATE_SIZE; ++i) 331 L15_state[i] = i; 332 } 333 334 #define L_SCHEDULE(xx) \ 335 \ 336 for (i = 0; i < L15_STATE_SIZE; ++i) { \ 337 L15_Swap(i, (stateIndex += (L15_state[i] + (xx)))); \ 338 } 339 340 static void 341 L15_KSA (const LByteType * const key, const size_t keyLen) 342 { 343 size_t i, keyIndex; 344 LByteType stateIndex = 0; 345 346 L_SCHEDULE(keyLen); 347 for (keyIndex = 0; keyIndex < keyLen; ++keyIndex) { 348 L_SCHEDULE(key[keyIndex]); 349 } 350 } 351 352 static void 353 L15_Discard(const LByteType numCalls) 354 { 355 LByteType i; 356 for (i = 0; i < numCalls; ++i) { 357 (void)L15_Byte(); 358 } 359 } 360 361 362 /* 363 * PUBLIC INTERFACE: 364 */ 365 static void 366 L15(const LByteType * const key, const size_t keyLen) 367 { 368 L15_x = L15_start_x = 0; 369 L15_y = L15_STATE_SIZE - 1; 370 L15_InitState(); 371 L15_KSA(key, keyLen); 372 L15_Discard(L15_Byte()); 373 } 374 375 static LByteType 376 L15_Byte(void) 377 { 378 LByteType z; 379 380 L15_Swap(L15_state[L15_x], L15_y); 381 z = (L15_state [L15_x++] + L15_state[L15_y--]); 382 if (L15_x == L15_start_x) { 383 --L15_y; 384 } 385 return (L15_state[z]); 386 } 387 388 static void 389 L15_Vector (const LByteType * const key, const size_t keyLen) 390 { 391 L15_KSA(key, keyLen); 392 } 393 394 /*------------------------------- L15 ----------------------------------*/ 395 396 /************************************************************************ 397 * KERNEL INTERFACE * 398 ************************************************************************ 399 * 400 * By Robin J Carey and Matthew Dillon. 401 */ 402 403 static int rand_thread_signal = 1; 404 static void NANOUP_EVENT(void); 405 static thread_t rand_td; 406 static struct spinlock rand_spin; 407 408 static int sysctl_kern_random(SYSCTL_HANDLER_ARGS); 409 410 static int nrandevents; 411 SYSCTL_INT(_kern, OID_AUTO, nrandevents, CTLFLAG_RD, &nrandevents, 0, ""); 412 static int seedenable; 413 SYSCTL_INT(_kern, OID_AUTO, seedenable, CTLFLAG_RW, &seedenable, 0, ""); 414 SYSCTL_PROC(_kern, OID_AUTO, random, CTLFLAG_RD | CTLFLAG_ANYBODY, 0, 0, 415 sysctl_kern_random, "I", "Acquire random data"); 416 417 /* 418 * Called from early boot 419 */ 420 void 421 rand_initialize(void) 422 { 423 struct timespec now; 424 int i; 425 426 spin_init(&rand_spin); 427 428 /* Initialize IBAA. */ 429 IBAA_Init(); 430 431 /* Initialize L15. */ 432 nanouptime(&now); 433 L15((const LByteType *)&now.tv_nsec, sizeof(now.tv_nsec)); 434 for (i = 0; i < (SIZE / 2); ++i) { 435 nanotime(&now); 436 IBAA_Seed(now.tv_nsec); 437 L15_Vector((const LByteType *)&now.tv_nsec, 438 sizeof(now.tv_nsec)); 439 nanouptime(&now); 440 IBAA_Seed(now.tv_nsec); 441 L15_Vector((const LByteType *)&now.tv_nsec, 442 sizeof(now.tv_nsec)); 443 } 444 445 /* 446 * Warm up the generator to get rid of weak initial states. 447 */ 448 for (i = 0; i < 10; ++i) 449 IBAA_Call(); 450 } 451 452 /* 453 * Keyboard events 454 */ 455 void 456 add_keyboard_randomness(u_char scancode) 457 { 458 spin_lock(&rand_spin); 459 L15_Vector((const LByteType *) &scancode, sizeof (scancode)); 460 spin_unlock(&rand_spin); 461 add_interrupt_randomness(0); 462 } 463 464 /* 465 * Interrupt events. This is SMP safe and allowed to race. 466 */ 467 void 468 add_interrupt_randomness(int intr) 469 { 470 if (rand_thread_signal == 0) { 471 rand_thread_signal = 1; 472 lwkt_schedule(rand_td); 473 } 474 } 475 476 /* 477 * True random number source 478 */ 479 void 480 add_true_randomness(int val) 481 { 482 spin_lock(&rand_spin); 483 IBAA_Seed(val); 484 L15_Vector((const LByteType *) &val, sizeof (val)); 485 ++nrandevents; 486 spin_unlock(&rand_spin); 487 } 488 489 int 490 add_buffer_randomness(const char *buf, int bytes) 491 { 492 int error; 493 int i; 494 495 if (seedenable && securelevel <= 0) { 496 while (bytes >= sizeof(int)) { 497 add_true_randomness(*(const int *)buf); 498 buf += sizeof(int); 499 bytes -= sizeof(int); 500 } 501 error = 0; 502 503 /* 504 * Warm up the generator to get rid of weak initial states. 505 */ 506 for (i = 0; i < 10; ++i) 507 IBAA_Call(); 508 } else { 509 error = EPERM; 510 } 511 return (error); 512 } 513 514 /* 515 * Poll (always succeeds) 516 */ 517 int 518 random_poll(cdev_t dev, int events) 519 { 520 int revents = 0; 521 522 if (events & (POLLIN | POLLRDNORM)) 523 revents |= events & (POLLIN | POLLRDNORM); 524 if (events & (POLLOUT | POLLWRNORM)) 525 revents |= events & (POLLOUT | POLLWRNORM); 526 527 return (revents); 528 } 529 530 /* 531 * Kqueue filter (always succeeds) 532 */ 533 int 534 random_filter_read(struct knote *kn, long hint) 535 { 536 return (1); 537 } 538 539 /* 540 * Heavy weight random number generator. May return less then the 541 * requested number of bytes. 542 */ 543 u_int 544 read_random(void *buf, u_int nbytes) 545 { 546 u_int i; 547 548 spin_lock(&rand_spin); 549 for (i = 0; i < nbytes; ++i) 550 ((u_char *)buf)[i] = IBAA_Byte(); 551 spin_unlock(&rand_spin); 552 add_interrupt_randomness(0); 553 return(i); 554 } 555 556 /* 557 * Lightweight random number generator. Must return requested number of 558 * bytes. 559 */ 560 u_int 561 read_random_unlimited(void *buf, u_int nbytes) 562 { 563 u_int i; 564 565 spin_lock(&rand_spin); 566 for (i = 0; i < nbytes; ++i) 567 ((u_char *)buf)[i] = L15_Byte(); 568 spin_unlock(&rand_spin); 569 add_interrupt_randomness(0); 570 return (i); 571 } 572 573 /* 574 * Read random data via sysctl(). 575 */ 576 static 577 int 578 sysctl_kern_random(SYSCTL_HANDLER_ARGS) 579 { 580 char buf[64]; 581 size_t n; 582 size_t r; 583 int error = 0; 584 585 n = req->oldlen; 586 if (n > 1024 * 1024) 587 n = 1024 * 1024; 588 while (n > 0) { 589 if ((r = n) > sizeof(buf)) 590 r = sizeof(buf); 591 read_random_unlimited(buf, r); 592 error = SYSCTL_OUT(req, buf, r); 593 if (error) 594 break; 595 n -= r; 596 } 597 return(error); 598 } 599 600 /* 601 * Random number generator helper thread. This limits code overhead from 602 * high frequency events by delaying the clearing of rand_thread_signal. 603 * 604 * MPSAFE thread 605 */ 606 static 607 void 608 rand_thread_loop(void *dummy) 609 { 610 int count; 611 612 for (;;) { 613 NANOUP_EVENT (); 614 spin_lock(&rand_spin); 615 count = (int)(L15_Byte() * hz / (256 * 10) + hz / 10 + 1); 616 spin_unlock(&rand_spin); 617 tsleep(rand_td, 0, "rwait", count); 618 crit_enter(); 619 lwkt_deschedule_self(rand_td); 620 cpu_sfence(); 621 rand_thread_signal = 0; 622 crit_exit(); 623 lwkt_switch(); 624 } 625 } 626 627 static 628 void 629 rand_thread_init(void) 630 { 631 lwkt_create(rand_thread_loop, NULL, &rand_td, NULL, 0, 0, "random"); 632 } 633 634 SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0); 635 636 /* 637 * Time-buffered event time-stamping. This is necessary to cutoff higher 638 * event frequencies, e.g. an interrupt occuring at 25Hz. In such cases 639 * the CPU is being chewed and the timestamps are skewed (minimal variation). 640 * Use a nano-second time-delay to limit how many times an Event can occur 641 * in one second; <= 5Hz. Note that this doesn't prevent time-stamp skewing. 642 * This implementation randmoises the time-delay between events, which adds 643 * a layer of security/unpredictability with regard to read-events (a user 644 * controlled input). 645 * 646 * Note: now.tv_nsec should range [ 0 - 1000,000,000 ]. 647 * Note: "ACCUM" is a security measure (result = capped-unknown + unknown), 648 * and also produces an uncapped (>=32-bit) value. 649 */ 650 static void 651 NANOUP_EVENT(void) 652 { 653 static struct timespec ACCUM = { 0, 0 }; 654 static struct timespec NEXT = { 0, 0 }; 655 struct timespec now; 656 657 nanouptime(&now); 658 spin_lock(&rand_spin); 659 if ((now.tv_nsec > NEXT.tv_nsec) || (now.tv_sec != NEXT.tv_sec)) { 660 /* 661 * Randomised time-delay: 200e6 - 350e6 ns; 5 - 2.86 Hz. 662 */ 663 unsigned long one_mil; 664 unsigned long timeDelay; 665 666 one_mil = 1000000UL; /* 0.001 s */ 667 timeDelay = (one_mil * 200) + 668 (((unsigned long)ACCUM.tv_nsec % 151) * one_mil); 669 NEXT.tv_nsec = now.tv_nsec + timeDelay; 670 NEXT.tv_sec = now.tv_sec; 671 ACCUM.tv_nsec += now.tv_nsec; 672 673 /* 674 * The TSC, if present, generally has an even higher 675 * resolution. Integrate a portion of it into our seed. 676 */ 677 if (tsc_present) 678 ACCUM.tv_nsec ^= rdtsc() & 255; 679 680 IBAA_Seed(ACCUM.tv_nsec); 681 L15_Vector((const LByteType *)&ACCUM.tv_nsec, 682 sizeof(ACCUM.tv_nsec)); 683 ++nrandevents; 684 } 685 spin_unlock(&rand_spin); 686 } 687 688