kernel - All lwkt thread now start out mpsafe part 1/2
[dragonfly.git] / sys / kern / kern_nrandom.c
CommitLineData
c0b252c3
MD
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 *
1ee4c2e3 25 * $DragonFly: src/sys/kern/kern_nrandom.c,v 1.7 2008/08/01 04:42:30 dillon Exp $
c0b252c3
MD
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>
6dcd6ba9 131#include <sys/event.h>
c0b252c3
MD
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>
c9e9fb21 143#include <sys/mplock2.h>
c0b252c3
MD
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 */
170typedef u_int32_t u4; /* unsigned four bytes, 32 bits */
171
172#define ALPHA (8)
173#define SIZE (1 << ALPHA)
c26b3d4d 174#define MASK (SIZE - 1)
c0b252c3 175#define ind(x) ((x) & (SIZE - 1))
31f10bcb 176#define barrel(a) (((a) << 20) ^ ((a) >> 12)) /* beta=32,shift=20 */
c0b252c3
MD
177
178static 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 */
31f10bcb
MD
183 u4 *bb, /* the previous result */
184 u4 *counter /* counter */
c0b252c3
MD
185)
186{
187 u4 a, b, x, y, i;
188
31f10bcb
MD
189 a = *aa;
190 b = *bb + *counter;
191 ++*counter;
c0b252c3
MD
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
204static u4 IBAA_memory[SIZE];
205static u4 IBAA_results[SIZE];
206static u4 IBAA_aa;
207static u4 IBAA_bb;
31f10bcb 208static u4 IBAA_counter;
c0b252c3
MD
209
210static volatile int IBAA_byte_index;
211
212
213static void IBAA_Init(void);
214static void IBAA_Call(void);
215static void IBAA_Seed(const u_int32_t val);
216static u_char IBAA_Byte(void);
217
218/*
219 * Initialize IBAA.
220 */
221static void
222IBAA_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;
31f10bcb 230 IBAA_counter = 0;
c0b252c3
MD
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 */
237static void
238IBAA_Call (void)
239{
31f10bcb 240 IBAA(IBAA_memory, IBAA_results, &IBAA_aa, &IBAA_bb, &IBAA_counter);
c0b252c3
MD
241 IBAA_byte_index = 0;
242}
243
244/*
c26b3d4d
MD
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.
c0b252c3
MD
248 */
249static void
250IBAA_Seed (const u_int32_t val)
251{
c26b3d4d
MD
252 static int memIndex;
253 u4 *iptr;
c0b252c3 254
c26b3d4d
MD
255 iptr = &IBAA_memory[memIndex & MASK];
256 *iptr = ((*iptr << 3) | (*iptr >> 29)) + (val ^ (IBAA_Byte() & 15));
c0b252c3
MD
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 */
266static u_char
267IBAA_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 */
291typedef unsigned char LByteType;
292
293#define L15_STATE_SIZE 256
294
295static LByteType L15_x, L15_y;
296static LByteType L15_start_x;
297static LByteType L15_state[L15_STATE_SIZE];
298
299/*
300 * PRIVATE FUNCS:
301 */
302
303static void L15_Swap(const LByteType pos1, const LByteType pos2);
304static void L15_InitState(void);
305static void L15_KSA(const LByteType * const key,
306 const size_t keyLen);
307static void L15_Discard(const LByteType numCalls);
308
309/*
310 * PUBLIC INTERFACE:
311 */
312static void L15(const LByteType * const key, const size_t keyLen);
313static LByteType L15_Byte(void);
314static void L15_Vector(const LByteType * const key,
315 const size_t keyLen);
316
317static __inline void
318L15_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
326static void
327L15_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 \
336for (i = 0; i < L15_STATE_SIZE; ++i) { \
337 L15_Swap(i, (stateIndex += (L15_state[i] + (xx)))); \
338}
339
340static void
341L15_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
352static void
353L15_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 */
365static void
366L15(const LByteType * const key, const size_t keyLen)
367{
01b40dc2
MD
368 L15_x = L15_start_x = 0;
369 L15_y = L15_STATE_SIZE - 1;
c0b252c3
MD
370 L15_InitState();
371 L15_KSA(key, keyLen);
372 L15_Discard(L15_Byte());
373}
374
375static LByteType
376L15_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
388static void
389L15_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
403static int rand_thread_signal = 1;
404static void NANOUP_EVENT(void);
405static thread_t rand_td;
406static struct spinlock rand_spin;
407
408static int nrandevents;
409SYSCTL_INT(_kern, OID_AUTO, nrandevents, CTLFLAG_RD, &nrandevents, 0, "");
c26b3d4d
MD
410static int seedenable;
411SYSCTL_INT(_kern, OID_AUTO, seedenable, CTLFLAG_RW, &seedenable, 0, "");
c0b252c3
MD
412
413/*
414 * Called from early boot
415 */
416void
417rand_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 }
01b40dc2
MD
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();
c0b252c3
MD
446}
447
448/*
449 * Keyboard events
450 */
451void
452add_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/*
53d9cb72 461 * Interrupt events. This is SMP safe and allowed to race.
c0b252c3
MD
462 */
463void
464add_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 */
475void
476add_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
c26b3d4d
MD
485int
486add_buffer_randomness(const char *buf, int bytes)
487{
488 int error;
01b40dc2 489 int i;
c26b3d4d
MD
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;
01b40dc2
MD
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();
c26b3d4d
MD
504 } else {
505 error = EPERM;
506 }
507 return (error);
508}
509
c0b252c3
MD
510/*
511 * Poll (always succeeds)
512 */
513int
b13267a5 514random_poll(cdev_t dev, int events)
c0b252c3
MD
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/*
6dcd6ba9
SG
527 * Kqueue filter (always succeeds)
528 */
529int
530random_filter_read(struct knote *kn, long hint)
531{
532 return (1);
533}
534
535/*
c0b252c3
MD
536 * Heavy weight random number generator. May return less then the
537 * requested number of bytes.
538 */
539u_int
540read_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 */
556u_int
557read_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.
c9e9fb21
MD
572 *
573 * MPSAFE thread
c0b252c3
MD
574 */
575static
576void
577rand_thread_loop(void *dummy)
578{
579 int count;
580
c9e9fb21
MD
581 get_mplock();
582
c0b252c3
MD
583 for (;;) {
584 NANOUP_EVENT ();
585 spin_lock_wr(&rand_spin);
c9e9fb21 586 count = (int)(L15_Byte() * hz / (256 * 10) + hz / 10 + 1);
c0b252c3
MD
587 spin_unlock_wr(&rand_spin);
588 tsleep(rand_td, 0, "rwait", count);
53d9cb72 589 crit_enter();
c0b252c3 590 lwkt_deschedule_self(rand_td);
53d9cb72
MD
591 cpu_sfence();
592 rand_thread_signal = 0;
593 crit_exit();
c0b252c3
MD
594 lwkt_switch();
595 }
596}
597
598static
599void
600rand_thread_init(void)
601{
c9e9fb21
MD
602 lwkt_create(rand_thread_loop, NULL, &rand_td, NULL,
603 TDF_MPSAFE, 0, "random");
c0b252c3
MD
604}
605
606SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0);
607
608/*
609 * Time-buffered event time-stamping. This is necessary to cutoff higher
610 * event frequencies, e.g. an interrupt occuring at 25Hz. In such cases
611 * the CPU is being chewed and the timestamps are skewed (minimal variation).
612 * Use a nano-second time-delay to limit how many times an Event can occur
613 * in one second; <= 5Hz. Note that this doesn't prevent time-stamp skewing.
614 * This implementation randmoises the time-delay between events, which adds
615 * a layer of security/unpredictability with regard to read-events (a user
616 * controlled input).
617 *
618 * Note: now.tv_nsec should range [ 0 - 1000,000,000 ].
619 * Note: "ACCUM" is a security measure (result = capped-unknown + unknown),
620 * and also produces an uncapped (>=32-bit) value.
621 */
622static void
623NANOUP_EVENT(void)
624{
625 static struct timespec ACCUM = { 0, 0 };
626 static struct timespec NEXT = { 0, 0 };
627 struct timespec now;
628
629 nanouptime(&now);
630 spin_lock_wr(&rand_spin);
631 if ((now.tv_nsec > NEXT.tv_nsec) || (now.tv_sec != NEXT.tv_sec)) {
632 /*
633 * Randomised time-delay: 200e6 - 350e6 ns; 5 - 2.86 Hz.
634 */
635 unsigned long one_mil;
636 unsigned long timeDelay;
637
638 one_mil = 1000000UL; /* 0.001 s */
1ee4c2e3
MD
639 timeDelay = (one_mil * 200) +
640 (((unsigned long)ACCUM.tv_nsec % 151) * one_mil);
c0b252c3
MD
641 NEXT.tv_nsec = now.tv_nsec + timeDelay;
642 NEXT.tv_sec = now.tv_sec;
643 ACCUM.tv_nsec += now.tv_nsec;
644
645 /*
646 * The TSC, if present, generally has an even higher
647 * resolution. Integrate a portion of it into our seed.
648 */
649 if (tsc_present)
650 ACCUM.tv_nsec ^= rdtsc() & 255;
651
652 IBAA_Seed(ACCUM.tv_nsec);
653 L15_Vector((const LByteType *)&ACCUM.tv_nsec,
654 sizeof(ACCUM.tv_nsec));
655 ++nrandevents;
656 }
657 spin_unlock_wr(&rand_spin);
658}
659