xref: /dragonfly/sys/kern/kern_nrandom.c (revision fe76c4fb) 
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 
597