5103885c4c492cd7b06e1b4a6a7f6982e17f0ab0
[dragonfly.git] / 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.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 nrandevents;
409 SYSCTL_INT(_kern, OID_AUTO, nrandevents, CTLFLAG_RD, &nrandevents, 0, "");
410 static int seedenable;
411 SYSCTL_INT(_kern, OID_AUTO, seedenable, CTLFLAG_RW, &seedenable, 0, "");
412
413 /*
414  * Called from early boot
415  */
416 void
417 rand_initialize(void)
418 {
419         struct timespec now;
420         int i;
421
422         spin_init(&rand_spin);
423
424         /* Initialize IBAA. */
425         IBAA_Init();
426
427         /* Initialize L15. */
428         nanouptime(&now);
429         L15((const LByteType *)&now.tv_nsec, sizeof(now.tv_nsec));
430         for (i = 0; i < (SIZE / 2); ++i) {
431                 nanotime(&now);
432                 IBAA_Seed(now.tv_nsec);
433                 L15_Vector((const LByteType *)&now.tv_nsec,
434                            sizeof(now.tv_nsec));
435                 nanouptime(&now);
436                 IBAA_Seed(now.tv_nsec);
437                 L15_Vector((const LByteType *)&now.tv_nsec,
438                            sizeof(now.tv_nsec));
439         }
440
441         /*
442          * Warm up the generator to get rid of weak initial states.
443          */
444         for (i = 0; i < 10; ++i)
445                 IBAA_Call();
446 }
447
448 /*
449  * Keyboard events
450  */
451 void
452 add_keyboard_randomness(u_char scancode)
453 {
454         spin_lock_wr(&rand_spin);
455         L15_Vector((const LByteType *) &scancode, sizeof (scancode));
456         spin_unlock_wr(&rand_spin);
457         add_interrupt_randomness(0);
458 }
459
460 /*
461  * Interrupt events.  This is SMP safe and allowed to race.
462  */
463 void
464 add_interrupt_randomness(int intr)
465 {
466         if (rand_thread_signal == 0) {
467                 rand_thread_signal = 1;
468                 lwkt_schedule(rand_td);
469         }
470 }
471
472 /*
473  * True random number source
474  */
475 void
476 add_true_randomness(int val)
477 {
478         spin_lock_wr(&rand_spin);
479         IBAA_Seed(val);
480         L15_Vector((const LByteType *) &val, sizeof (val));
481         ++nrandevents;
482         spin_unlock_wr(&rand_spin);
483 }
484
485 int
486 add_buffer_randomness(const char *buf, int bytes)
487 {
488         int error;
489         int i;
490
491         if (seedenable && securelevel <= 0) {
492                 while (bytes >= sizeof(int)) {
493                         add_true_randomness(*(const int *)buf);
494                         buf += sizeof(int);
495                         bytes -= sizeof(int);
496                 }
497                 error = 0;
498
499                 /*
500                  * Warm up the generator to get rid of weak initial states.
501                  */
502                 for (i = 0; i < 10; ++i)
503                         IBAA_Call();
504         } else {
505                 error = EPERM;
506         }
507         return (error);
508 }
509
510 /*
511  * Poll (always succeeds)
512  */
513 int
514 random_poll(cdev_t dev, int events)
515 {
516         int revents = 0;
517
518         if (events & (POLLIN | POLLRDNORM))
519                 revents |= events & (POLLIN | POLLRDNORM);
520         if (events & (POLLOUT | POLLWRNORM))
521                 revents |= events & (POLLOUT | POLLWRNORM);
522
523         return (revents);
524 }
525
526 /*
527  * Kqueue filter (always succeeds)
528  */
529 int
530 random_filter_read(struct knote *kn, long hint)
531 {
532         return (1);
533 }
534
535 /*
536  * Heavy weight random number generator.  May return less then the
537  * requested number of bytes.
538  */
539 u_int
540 read_random(void *buf, u_int nbytes)
541 {
542         u_int i;
543
544         spin_lock_wr(&rand_spin);
545         for (i = 0; i < nbytes; ++i) 
546                 ((u_char *)buf)[i] = IBAA_Byte();
547         spin_unlock_wr(&rand_spin);
548         add_interrupt_randomness(0);
549         return(i);
550 }
551
552 /*
553  * Lightweight random number generator.  Must return requested number of
554  * bytes.
555  */
556 u_int
557 read_random_unlimited(void *buf, u_int nbytes)
558 {
559         u_int i;
560
561         spin_lock_wr(&rand_spin);
562         for (i = 0; i < nbytes; ++i)
563                 ((u_char *)buf)[i] = L15_Byte();
564         spin_unlock_wr(&rand_spin);
565         add_interrupt_randomness(0);
566         return (i);
567 }
568
569 /*
570  * Random number generator helper thread.  This limits code overhead from
571  * high frequency events by delaying the clearing of rand_thread_signal.
572  *
573  * MPSAFE thread
574  */
575 static
576 void
577 rand_thread_loop(void *dummy)
578 {
579         int count;
580
581         get_mplock();
582
583         for (;;) {
584                 NANOUP_EVENT ();
585                 spin_lock_wr(&rand_spin);
586                 count = (int)(L15_Byte() * hz / (256 * 10) + hz / 10 + 1);
587                 spin_unlock_wr(&rand_spin);
588                 tsleep(rand_td, 0, "rwait", count);
589                 crit_enter();
590                 lwkt_deschedule_self(rand_td);
591                 cpu_sfence();
592                 rand_thread_signal = 0;
593                 crit_exit();
594                 lwkt_switch();
595         }
596 }
597
598 static
599 void
600 rand_thread_init(void)
601 {
602         lwkt_create(rand_thread_loop, NULL, &rand_td, NULL, 0, 0, "random");
603 }
604
605 SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0);
606
607 /*
608  * Time-buffered event time-stamping. This is necessary to cutoff higher
609  * event frequencies, e.g. an interrupt occuring at 25Hz. In such cases
610  * the CPU is being chewed and the timestamps are skewed (minimal variation).
611  * Use a nano-second time-delay to limit how many times an Event can occur
612  * in one second; <= 5Hz. Note that this doesn't prevent time-stamp skewing.
613  * This implementation randmoises the time-delay between events, which adds
614  * a layer of security/unpredictability with regard to read-events (a user
615  * controlled input).
616  *
617  * Note: now.tv_nsec should range [ 0 - 1000,000,000 ].
618  * Note: "ACCUM" is a security measure (result = capped-unknown + unknown),
619  *       and also produces an uncapped (>=32-bit) value.
620  */
621 static void
622 NANOUP_EVENT(void)
623 {
624         static struct timespec  ACCUM = { 0, 0 };
625         static struct timespec  NEXT  = { 0, 0 };
626         struct timespec         now;
627
628         nanouptime(&now);
629         spin_lock_wr(&rand_spin);
630         if ((now.tv_nsec > NEXT.tv_nsec) || (now.tv_sec != NEXT.tv_sec)) {
631                 /* 
632                  * Randomised time-delay: 200e6 - 350e6 ns; 5 - 2.86 Hz. 
633                  */
634                 unsigned long one_mil;
635                 unsigned long timeDelay;
636
637                 one_mil = 1000000UL;    /* 0.001 s */
638                 timeDelay = (one_mil * 200) + 
639                             (((unsigned long)ACCUM.tv_nsec % 151) * one_mil);
640                 NEXT.tv_nsec = now.tv_nsec + timeDelay;
641                 NEXT.tv_sec = now.tv_sec;
642                 ACCUM.tv_nsec += now.tv_nsec;
643
644                 /*
645                  * The TSC, if present, generally has an even higher
646                  * resolution.  Integrate a portion of it into our seed.
647                  */
648                 if (tsc_present)
649                         ACCUM.tv_nsec ^= rdtsc() & 255;
650
651                 IBAA_Seed(ACCUM.tv_nsec);
652                 L15_Vector((const LByteType *)&ACCUM.tv_nsec,
653                            sizeof(ACCUM.tv_nsec));
654                 ++nrandevents;
655         }
656         spin_unlock_wr(&rand_spin);
657 }
658