sys/kern/kern_nrandom.c

   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.1 2006/06/18 01:34:59 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/random.h>
 132 #include <sys/systimer.h>
 133 #include <sys/time.h>
 134 #include <sys/proc.h>
 135 #include <sys/lock.h>
 136 #include <sys/sysctl.h>
 137 #include <sys/spinlock.h>
 138 #include <machine/clock.h>
 139
 140 #include <sys/thread2.h>
 141 #include <sys/spinlock2.h>
 142
 143 /*
 144  * Portability note: The u_char/unsigned char type is used where
 145  * uint8_t from <stdint.h> or u_int8_t from <sys/types.h> should really
 146  * be being used. On FreeBSD, it is safe to make the assumption that these
 147  * different types are equivalent (on all architectures).
 148  * The FreeBSD <sys/crypto/rc4> module also makes this assumption.
 149  */
 150
 151 /*------------------------------ IBAA ----------------------------------*/
 152
 153 /*-------------------------- IBAA CSPRNG -------------------------------*/
 154
 155 /*
 156  * NOTE: The original source code from which this source code (IBAA)
 157  *       was taken has no copyright/license. The algorithm has no patent
 158  *       and is freely/publicly available from:
 159  *
 160  *           http://www.burtleburtle.net/bob/rand/isaac.html
 161  */
 162
 163 /*
 164  * ^ means XOR, & means bitwise AND, a<<b means shift a by b.
 165  * barrel(a) shifts a 19 bits to the left, and bits wrap around
 166  * ind(x) is (x AND 255), or (x mod 256)
 167  */
 168 typedef u_int32_t       u4;   /* unsigned four bytes, 32 bits */
 169
 170 #define ALPHA           (8)
 171 #define SIZE            (1 << ALPHA)
 172 #define ind(x)          ((x) & (SIZE - 1))
 173 #define barrel(a)       (((a) << 19) ^ ((a) >> 13))  /* beta=32,shift=19 */
 174
 175 static void IBAA
 176 (
 177         u4 *m,          /* Memory: array of SIZE ALPHA-bit terms */
 178         u4 *r,          /* Results: the sequence, same size as m */
 179         u4 *aa,         /* Accumulator: a single value */
 180         u4 *bb          /* the previous result */
 181 )
 182 {
 183         u4 a, b, x, y, i;
 184
 185         a = *aa; b = *bb;
 186         for (i = 0; i < SIZE; ++i) {
 187                 x = m[i];
 188                 a = barrel(a) + m[ind(i + (SIZE / 2))]; /* set a */
 189                 m[i] = y = m[ind(x)] + a + b;           /* set m */
 190                 r[i] = b = m[ind(y >> ALPHA)] + x;      /* set r */
 191         }
 192         *bb = b; *aa = a;
 193 }
 194
 195 /*-------------------------- IBAA CSPRNG -------------------------------*/
 196
 197
 198 static u4       IBAA_memory[SIZE];
 199 static u4       IBAA_results[SIZE];
 200 static u4       IBAA_aa;
 201 static u4       IBAA_bb;
 202
 203 static volatile int IBAA_byte_index;
 204
 205
 206 static void     IBAA_Init(void);
 207 static void     IBAA_Call(void);
 208 static void     IBAA_Seed(const u_int32_t val);
 209 static u_char   IBAA_Byte(void);
 210
 211 /*
 212  * Initialize IBAA.
 213  */
 214 static void
 215 IBAA_Init(void)
 216 {
 217         size_t  i;
 218
 219         for (i = 0; i < SIZE; ++i) {
 220                 IBAA_memory[i] = i;
 221         }
 222         IBAA_aa = IBAA_bb = 0;
 223         IBAA_byte_index = sizeof(IBAA_results); /* force IBAA_Call() */
 224 }
 225
 226 /*
 227  * PRIVATE: Call IBAA to produce 256 32-bit u4 results.
 228  */
 229 static void
 230 IBAA_Call (void)
 231 {
 232         IBAA(IBAA_memory, IBAA_results, &IBAA_aa, &IBAA_bb);
 233         IBAA_byte_index = 0;
 234 }
 235
 236 /*
 237  * Add a 32-bit u4 seed value into IBAAs memory.
 238  */
 239 static void
 240 IBAA_Seed (const u_int32_t val)
 241 {
 242         static int memIndex = 0;
 243
 244         IBAA_memory[memIndex % SIZE] = val;
 245         ++memIndex;
 246 }
 247
 248 /*
 249  * Extract a byte from IBAAs 256 32-bit u4 results array.
 250  *
 251  * NOTE: This code is designed to prevent MP races from taking
 252  * IBAA_byte_index out of bounds.
 253  */
 254 static u_char
 255 IBAA_Byte(void)
 256 {
 257         u_char result;
 258         int index;
 259
 260         index = IBAA_byte_index;
 261         if (index == sizeof(IBAA_results)) {
 262                 IBAA_Call();
 263                 index = 0;
 264         }
 265         result = ((u_char *)IBAA_results)[index];
 266         IBAA_byte_index = index + 1;
 267         return result;
 268 }
 269
 270 /*------------------------------ IBAA ----------------------------------*/
 271
 272
 273 /*------------------------------- L15 ----------------------------------*/
 274
 275 /*
 276  * IMPORTANT NOTE: LByteType must be exactly 8-bits in size or this software
 277  * will not function correctly.
 278  */
 279 typedef unsigned char   LByteType;
 280
 281 #define L15_STATE_SIZE  256
 282
 283 static LByteType        L15_x, L15_y;
 284 static LByteType        L15_start_x;
 285 static LByteType        L15_state[L15_STATE_SIZE];
 286
 287 /*
 288  * PRIVATE FUNCS:
 289  */
 290
 291 static void             L15_Swap(const LByteType pos1, const LByteType pos2);
 292 static void             L15_InitState(void);
 293 static void             L15_KSA(const LByteType * const key,
 294                                 const size_t keyLen);
 295 static void             L15_Discard(const LByteType numCalls);
 296
 297 /*
 298  * PUBLIC INTERFACE:
 299  */
 300 static void             L15(const LByteType * const key, const size_t keyLen);
 301 static LByteType        L15_Byte(void);
 302 static void             L15_Vector(const LByteType * const key,
 303                                 const size_t keyLen);
 304
 305 static __inline void
 306 L15_Swap(const LByteType pos1, const LByteType pos2)
 307 {
 308         const LByteType save1 = L15_state[pos1];
 309
 310         L15_state[pos1] = L15_state[pos2];
 311         L15_state[pos2] = save1;
 312 }
 313
 314 static void
 315 L15_InitState (void)
 316 {
 317         size_t i;
 318         for (i = 0; i < L15_STATE_SIZE; ++i)
 319                 L15_state[i] = i;
 320 }
 321
 322 #define  L_SCHEDULE(xx)                                         \
 323                                                                 \
 324 for (i = 0; i < L15_STATE_SIZE; ++i) {                          \
 325     L15_Swap(i, (stateIndex += (L15_state[i] + (xx))));         \
 326 }
 327
 328 static void
 329 L15_KSA (const LByteType * const key, const size_t keyLen)
 330 {
 331         size_t  i, keyIndex;
 332         LByteType stateIndex = 0;
 333
 334         L_SCHEDULE(keyLen);
 335         for (keyIndex = 0; keyIndex < keyLen; ++keyIndex) {
 336                 L_SCHEDULE(key[keyIndex]);
 337         }
 338 }
 339
 340 static void
 341 L15_Discard(const LByteType numCalls)
 342 {
 343         LByteType i;
 344         for (i = 0; i < numCalls; ++i) {
 345                 (void)L15_Byte();
 346         }
 347 }
 348
 349
 350 /*
 351  * PUBLIC INTERFACE:
 352  */
 353 static void
 354 L15(const LByteType * const key, const size_t keyLen)
 355 {
 356         L15_x = L15_y = L15_start_x = 0;
 357         L15_InitState();
 358         L15_KSA(key, keyLen);
 359         L15_Discard(L15_Byte());
 360 }
 361
 362 static LByteType
 363 L15_Byte(void)
 364 {
 365         LByteType z;
 366
 367         L15_Swap(L15_state[L15_x], L15_y);
 368         z = (L15_state [L15_x++] + L15_state[L15_y--]);
 369         if (L15_x == L15_start_x) {
 370                 --L15_y;
 371         }
 372         return (L15_state[z]);
 373 }
 374
 375 static void
 376 L15_Vector (const LByteType * const key, const size_t keyLen)
 377 {
 378         L15_KSA(key, keyLen);
 379 }
 380
 381 /*------------------------------- L15 ----------------------------------*/
 382
 383 /************************************************************************
 384  *                              KERNEL INTERFACE                        *
 385  ************************************************************************
 386  *
 387  * By Robin J Carey and Matthew Dillon.
 388  */
 389
 390 static int rand_thread_signal = 1;
 391 static void NANOUP_EVENT(void);
 392 static thread_t rand_td;
 393 static struct spinlock rand_spin;
 394
 395 static int nrandevents;
 396 SYSCTL_INT(_kern, OID_AUTO, nrandevents, CTLFLAG_RD, &nrandevents, 0, "");
 397
 398
 399 /*
 400  * Called from early boot
 401  */
 402 void
 403 rand_initialize(void)
 404 {
 405         struct timespec now;
 406         int i;
 407
 408         spin_init(&rand_spin);
 409
 410         /* Initialize IBAA. */
 411         IBAA_Init();
 412
 413         /* Initialize L15. */
 414         nanouptime(&now);
 415         L15((const LByteType *)&now.tv_nsec, sizeof(now.tv_nsec));
 416         for (i = 0; i < (SIZE / 2); ++i) {
 417                 nanotime(&now);
 418                 IBAA_Seed(now.tv_nsec);
 419                 L15_Vector((const LByteType *)&now.tv_nsec,
 420                            sizeof(now.tv_nsec));
 421                 nanouptime(&now);
 422                 IBAA_Seed(now.tv_nsec);
 423                 L15_Vector((const LByteType *)&now.tv_nsec,
 424                            sizeof(now.tv_nsec));
 425         }
 426 }
 427
 428 /*
 429  * Keyboard events
 430  */
 431 void
 432 add_keyboard_randomness(u_char scancode)
 433 {
 434         spin_lock_wr(&rand_spin);
 435         L15_Vector((const LByteType *) &scancode, sizeof (scancode));
 436         spin_unlock_wr(&rand_spin);
 437         add_interrupt_randomness(0);
 438 }
 439
 440 /*
 441  * Interrupt events
 442  */
 443 void
 444 add_interrupt_randomness(int intr)
 445 {
 446         if (rand_thread_signal == 0) {
 447                 rand_thread_signal = 1;
 448                 lwkt_schedule(rand_td);
 449         }
 450 }
 451
 452 /*
 453  * True random number source
 454  */
 455 void
 456 add_true_randomness(int val)
 457 {
 458         spin_lock_wr(&rand_spin);
 459         IBAA_Seed(val);
 460         L15_Vector((const LByteType *) &val, sizeof (val));
 461         ++nrandevents;
 462         spin_unlock_wr(&rand_spin);
 463 }
 464
 465 /*
 466  * Poll (always succeeds)
 467  */
 468 int
 469 random_poll(dev_t dev, int events, struct thread *td)
 470 {
 471         int revents = 0;
 472
 473         if (events & (POLLIN | POLLRDNORM))
 474                 revents |= events & (POLLIN | POLLRDNORM);
 475         if (events & (POLLOUT | POLLWRNORM))
 476                 revents |= events & (POLLOUT | POLLWRNORM);
 477
 478         return (revents);
 479 }
 480
 481 /*
 482  * Heavy weight random number generator.  May return less then the
 483  * requested number of bytes.
 484  */
 485 u_int
 486 read_random(void *buf, u_int nbytes)
 487 {
 488         u_int i;
 489
 490         spin_lock_wr(&rand_spin);
 491         for (i = 0; i < nbytes; ++i)
 492                 ((u_char *)buf)[i] = IBAA_Byte();
 493         spin_unlock_wr(&rand_spin);
 494         add_interrupt_randomness(0);
 495         return(i);
 496 }
 497
 498 /*
 499  * Lightweight random number generator.  Must return requested number of
 500  * bytes.
 501  */
 502 u_int
 503 read_random_unlimited(void *buf, u_int nbytes)
 504 {
 505         u_int i;
 506
 507         spin_lock_wr(&rand_spin);
 508         for (i = 0; i < nbytes; ++i)
 509                 ((u_char *)buf)[i] = L15_Byte();
 510         spin_unlock_wr(&rand_spin);
 511         add_interrupt_randomness(0);
 512         return (i);
 513 }
 514
 515 /*
 516  * Random number generator helper thread.  This limits code overhead from
 517  * high frequency events by delaying the clearing of rand_thread_signal.
 518  */
 519 static
 520 void
 521 rand_thread_loop(void *dummy)
 522 {
 523         int count;
 524
 525         for (;;) {
 526                 NANOUP_EVENT ();
 527                 spin_lock_wr(&rand_spin);
 528                 count = (int)(L15_Byte() * hz / (256 * 10) + hz / 10);
 529                 spin_unlock_wr(&rand_spin);
 530                 tsleep(rand_td, 0, "rwait", count);
 531                 rand_thread_signal = 0;
 532                 lwkt_deschedule_self(rand_td);
 533                 lwkt_switch();
 534         }
 535 }
 536
 537 static
 538 void
 539 rand_thread_init(void)
 540 {
 541         lwkt_create(rand_thread_loop, NULL, &rand_td, NULL, 0, 0, "random");
 542 }
 543
 544 SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0);
 545
 546 /*
 547  * Time-buffered event time-stamping. This is necessary to cutoff higher
 548  * event frequencies, e.g. an interrupt occuring at 25Hz. In such cases
 549  * the CPU is being chewed and the timestamps are skewed (minimal variation).
 550  * Use a nano-second time-delay to limit how many times an Event can occur
 551  * in one second; <= 5Hz. Note that this doesn't prevent time-stamp skewing.
 552  * This implementation randmoises the time-delay between events, which adds
 553  * a layer of security/unpredictability with regard to read-events (a user
 554  * controlled input).
 555  *
 556  * Note: now.tv_nsec should range [ 0 - 1000,000,000 ].
 557  * Note: "ACCUM" is a security measure (result = capped-unknown + unknown),
 558  *       and also produces an uncapped (>=32-bit) value.
 559  */
 560 static void
 561 NANOUP_EVENT(void)
 562 {
 563         static struct timespec  ACCUM = { 0, 0 };
 564         static struct timespec  NEXT  = { 0, 0 };
 565         struct timespec         now;
 566
 567         nanouptime(&now);
 568         spin_lock_wr(&rand_spin);
 569         if ((now.tv_nsec > NEXT.tv_nsec) || (now.tv_sec != NEXT.tv_sec)) {
 570                 /*
 571                  * Randomised time-delay: 200e6 - 350e6 ns; 5 - 2.86 Hz.
 572                  */
 573                 unsigned long one_mil;
 574                 unsigned long timeDelay;
 575
 576                 one_mil = 1000000UL;    /* 0.001 s */
 577                 timeDelay = (one_mil * 200) + (((unsigned)ACCUM.tv_nsec % 151) * one_mil);
 578                 NEXT.tv_nsec = now.tv_nsec + timeDelay;
 579                 NEXT.tv_sec = now.tv_sec;
 580                 ACCUM.tv_nsec += now.tv_nsec;
 581
 582                 /*
 583                  * The TSC, if present, generally has an even higher
 584                  * resolution.  Integrate a portion of it into our seed.
 585                  */
 586                 if (tsc_present)
 587                         ACCUM.tv_nsec ^= rdtsc() & 255;
 588
 589                 IBAA_Seed(ACCUM.tv_nsec);
 590                 L15_Vector((const LByteType *)&ACCUM.tv_nsec,
 591                            sizeof(ACCUM.tv_nsec));
 592                 ++nrandevents;
 593         }
 594         spin_unlock_wr(&rand_spin);
 595 }
 596