From c0b252c353b1d81bf1e38688fbb45de4d1e54ea3 Mon Sep 17 00:00:00 2001 From: Matthew Dillon Date: Sun, 18 Jun 2006 01:34:59 +0000 Subject: [PATCH] Replace the random number generator with an IBAA generator for /dev/random and a L15 generator for /dev/urandom. Submitted-by: Robin J Carey Modified-from-original: Syntax adjusted to DragonFly kernel norms, and I integrated the original code into the DragonFly kernel random number generator API. Also added a TSC-based seed on top of nanouptime. --- sys/kern/kern_nrandom.c | 596 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 596 insertions(+) create mode 100644 sys/kern/kern_nrandom.c diff --git a/sys/kern/kern_nrandom.c b/sys/kern/kern_nrandom.c new file mode 100644 index 0000000000..2bf8c4bdf5 --- /dev/null +++ b/sys/kern/kern_nrandom.c @@ -0,0 +1,596 @@ +/* + * Copyright (c) 2004, 2005, 2006 Robin J Carey. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions, and the following disclaimer, + * without modification, immediately at the beginning of the file. + * 2. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR + * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $DragonFly: src/sys/kern/kern_nrandom.c,v 1.1 2006/06/18 01:34:59 dillon Exp $ + */ +/* --- NOTES --- + * + * Note: The word "entropy" is often incorrectly used to describe + * random data. The word "entropy" originates from the science of + * Physics. The correct descriptive definition would be something + * along the lines of "seed", "unpredictable numbers" or + * "unpredictable data". + * + * Note: Some /dev/[u]random implementations save "seed" between + * boots which represents a security hazard since an adversary + * could acquire this data (since it is stored in a file). If + * the unpredictable data used in the above routines is only + * generated during Kernel operation, then an adversary can only + * acquire that data through a Kernel security compromise and/or + * a cryptographic algorithm failure/cryptanalysis. + * + * Note: On FreeBSD-4.11, interrupts have to be manually enabled + * using the rndcontrol(8) command. + * + * --- DESIGN (FreeBSD-4.11 based) --- + * + * The rnddev module automatically initializes itself the first time + * it is used (client calls any public rnddev_*() interface routine). + * Both CSPRNGs are initially seeded from the precise nano[up]time() routines. + * Tests show this method produces good enough results, suitable for intended + * use. It is necessary for both CSPRNGs to be completely seeded, initially. + * + * After initialization and during Kernel operation the only suitable + * unpredictable data available is: + * + * (1) Keyboard scan-codes. + * (2) Nanouptime acquired by a Keyboard/Read-Event. + * (3) Suitable interrupt source; hard-disk/ATA-device. + * + * (X) Mouse-event (xyz-data unsuitable); NOT IMPLEMENTED. + * + * This data is added to both CSPRNGs in real-time as it happens/ + * becomes-available. Additionally, unpredictable (?) data may be + * acquired from a true-random number generator if such a device is + * available to the system (not advisable !). + * Nanouptime() acquired by a Read-Event is a very important aspect of + * this design, since it ensures that unpredictable data is added to + * the CSPRNGs even if there are no other sources. + * The nanouptime() Kernel routine is used since time relative to + * boot is less adversary-known than time itself. + * + * This design has been thoroughly tested with debug logging + * and the output from both /dev/random and /dev/urandom has + * been tested with the DIEHARD test-suite; both pass. + * + * MODIFICATIONS MADE TO ORIGINAL "kern_random.c": + * + * 6th July 2005: + * + * o Changed ReadSeed() function to schedule future read-seed-events + * by at least one second. Previous implementation used a randomised + * scheduling { 0, 1, 2, 3 seconds }. + * o Changed SEED_NANOUP() function to use a "previous" accumulator + * algorithm similar to ReadSeed(). This ensures that there is no + * way that an adversary can tell what number is being added to the + * CSPRNGs, since the number added to the CSPRNGs at Event-Time is + * the sum of nanouptime()@Event and an unknown/secret number. + * o Changed rnddev_add_interrupt() function to schedule future + * interrupt-events by at least one second. Previous implementation + * had no scheduling algorithm which allowed an "interrupt storm" + * to occur resulting in skewed data entering into the CSPRNGs. + * + * + * 9th July 2005: + * + * o Some small cleanups and change all internal functions to be + * static/private. + * o Removed ReadSeed() since its functionality is already performed + * by another function { rnddev_add_interrupt_OR_read() } and remove + * the silly rndByte accumulator/feedback-thing (since multipying by + * rndByte could yield a value of 0). + * o Made IBAA/L14 public interface become static/private; + * Local to this file (not changed to that in the original C modules). + * + * 16th July 2005: + * + * o SEED_NANOUP() -> NANOUP_EVENT() function rename. + * o Make NANOUP_EVENT() handle the time-buffering directly so that all + * time-stamp-events use this single time-buffer (including keyboard). + * This removes dependancy on "time_second" Kernel variable. + * o Removed second-time-buffer code in rnddev_add_interrupt_OR_read (void). + * o Rewrote the time-buffering algorithm in NANOUP_EVENT() to use a + * randomised time-delay range. + * + * 12th Dec 2005: + * + * o Updated to (hopefully final) L15 algorithm. + * + * 12th June 2006: + * + * o Added missing (u_char *) cast in RnddevRead() function. + * o Changed copyright to 3-clause BSD license and cleaned up the layout + * of this file. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +/* + * Portability note: The u_char/unsigned char type is used where + * uint8_t from or u_int8_t from should really + * be being used. On FreeBSD, it is safe to make the assumption that these + * different types are equivalent (on all architectures). + * The FreeBSD module also makes this assumption. + */ + +/*------------------------------ IBAA ----------------------------------*/ + +/*-------------------------- IBAA CSPRNG -------------------------------*/ + +/* + * NOTE: The original source code from which this source code (IBAA) + * was taken has no copyright/license. The algorithm has no patent + * and is freely/publicly available from: + * + * http://www.burtleburtle.net/bob/rand/isaac.html + */ + +/* + * ^ means XOR, & means bitwise AND, a<> 13)) /* beta=32,shift=19 */ + +static void IBAA +( + u4 *m, /* Memory: array of SIZE ALPHA-bit terms */ + u4 *r, /* Results: the sequence, same size as m */ + u4 *aa, /* Accumulator: a single value */ + u4 *bb /* the previous result */ +) +{ + u4 a, b, x, y, i; + + a = *aa; b = *bb; + for (i = 0; i < SIZE; ++i) { + x = m[i]; + a = barrel(a) + m[ind(i + (SIZE / 2))]; /* set a */ + m[i] = y = m[ind(x)] + a + b; /* set m */ + r[i] = b = m[ind(y >> ALPHA)] + x; /* set r */ + } + *bb = b; *aa = a; +} + +/*-------------------------- IBAA CSPRNG -------------------------------*/ + + +static u4 IBAA_memory[SIZE]; +static u4 IBAA_results[SIZE]; +static u4 IBAA_aa; +static u4 IBAA_bb; + +static volatile int IBAA_byte_index; + + +static void IBAA_Init(void); +static void IBAA_Call(void); +static void IBAA_Seed(const u_int32_t val); +static u_char IBAA_Byte(void); + +/* + * Initialize IBAA. + */ +static void +IBAA_Init(void) +{ + size_t i; + + for (i = 0; i < SIZE; ++i) { + IBAA_memory[i] = i; + } + IBAA_aa = IBAA_bb = 0; + IBAA_byte_index = sizeof(IBAA_results); /* force IBAA_Call() */ +} + +/* + * PRIVATE: Call IBAA to produce 256 32-bit u4 results. + */ +static void +IBAA_Call (void) +{ + IBAA(IBAA_memory, IBAA_results, &IBAA_aa, &IBAA_bb); + IBAA_byte_index = 0; +} + +/* + * Add a 32-bit u4 seed value into IBAAs memory. + */ +static void +IBAA_Seed (const u_int32_t val) +{ + static int memIndex = 0; + + IBAA_memory[memIndex % SIZE] = val; + ++memIndex; +} + +/* + * Extract a byte from IBAAs 256 32-bit u4 results array. + * + * NOTE: This code is designed to prevent MP races from taking + * IBAA_byte_index out of bounds. + */ +static u_char +IBAA_Byte(void) +{ + u_char result; + int index; + + index = IBAA_byte_index; + if (index == sizeof(IBAA_results)) { + IBAA_Call(); + index = 0; + } + result = ((u_char *)IBAA_results)[index]; + IBAA_byte_index = index + 1; + return result; +} + +/*------------------------------ IBAA ----------------------------------*/ + + +/*------------------------------- L15 ----------------------------------*/ + +/* + * IMPORTANT NOTE: LByteType must be exactly 8-bits in size or this software + * will not function correctly. + */ +typedef unsigned char LByteType; + +#define L15_STATE_SIZE 256 + +static LByteType L15_x, L15_y; +static LByteType L15_start_x; +static LByteType L15_state[L15_STATE_SIZE]; + +/* + * PRIVATE FUNCS: + */ + +static void L15_Swap(const LByteType pos1, const LByteType pos2); +static void L15_InitState(void); +static void L15_KSA(const LByteType * const key, + const size_t keyLen); +static void L15_Discard(const LByteType numCalls); + +/* + * PUBLIC INTERFACE: + */ +static void L15(const LByteType * const key, const size_t keyLen); +static LByteType L15_Byte(void); +static void L15_Vector(const LByteType * const key, + const size_t keyLen); + +static __inline void +L15_Swap(const LByteType pos1, const LByteType pos2) +{ + const LByteType save1 = L15_state[pos1]; + + L15_state[pos1] = L15_state[pos2]; + L15_state[pos2] = save1; +} + +static void +L15_InitState (void) +{ + size_t i; + for (i = 0; i < L15_STATE_SIZE; ++i) + L15_state[i] = i; +} + +#define L_SCHEDULE(xx) \ + \ +for (i = 0; i < L15_STATE_SIZE; ++i) { \ + L15_Swap(i, (stateIndex += (L15_state[i] + (xx)))); \ +} + +static void +L15_KSA (const LByteType * const key, const size_t keyLen) +{ + size_t i, keyIndex; + LByteType stateIndex = 0; + + L_SCHEDULE(keyLen); + for (keyIndex = 0; keyIndex < keyLen; ++keyIndex) { + L_SCHEDULE(key[keyIndex]); + } +} + +static void +L15_Discard(const LByteType numCalls) +{ + LByteType i; + for (i = 0; i < numCalls; ++i) { + (void)L15_Byte(); + } +} + + +/* + * PUBLIC INTERFACE: + */ +static void +L15(const LByteType * const key, const size_t keyLen) +{ + L15_x = L15_y = L15_start_x = 0; + L15_InitState(); + L15_KSA(key, keyLen); + L15_Discard(L15_Byte()); +} + +static LByteType +L15_Byte(void) +{ + LByteType z; + + L15_Swap(L15_state[L15_x], L15_y); + z = (L15_state [L15_x++] + L15_state[L15_y--]); + if (L15_x == L15_start_x) { + --L15_y; + } + return (L15_state[z]); +} + +static void +L15_Vector (const LByteType * const key, const size_t keyLen) +{ + L15_KSA(key, keyLen); +} + +/*------------------------------- L15 ----------------------------------*/ + +/************************************************************************ + * KERNEL INTERFACE * + ************************************************************************ + * + * By Robin J Carey and Matthew Dillon. + */ + +static int rand_thread_signal = 1; +static void NANOUP_EVENT(void); +static thread_t rand_td; +static struct spinlock rand_spin; + +static int nrandevents; +SYSCTL_INT(_kern, OID_AUTO, nrandevents, CTLFLAG_RD, &nrandevents, 0, ""); + + +/* + * Called from early boot + */ +void +rand_initialize(void) +{ + struct timespec now; + int i; + + spin_init(&rand_spin); + + /* Initialize IBAA. */ + IBAA_Init(); + + /* Initialize L15. */ + nanouptime(&now); + L15((const LByteType *)&now.tv_nsec, sizeof(now.tv_nsec)); + for (i = 0; i < (SIZE / 2); ++i) { + nanotime(&now); + IBAA_Seed(now.tv_nsec); + L15_Vector((const LByteType *)&now.tv_nsec, + sizeof(now.tv_nsec)); + nanouptime(&now); + IBAA_Seed(now.tv_nsec); + L15_Vector((const LByteType *)&now.tv_nsec, + sizeof(now.tv_nsec)); + } +} + +/* + * Keyboard events + */ +void +add_keyboard_randomness(u_char scancode) +{ + spin_lock_wr(&rand_spin); + L15_Vector((const LByteType *) &scancode, sizeof (scancode)); + spin_unlock_wr(&rand_spin); + add_interrupt_randomness(0); +} + +/* + * Interrupt events + */ +void +add_interrupt_randomness(int intr) +{ + if (rand_thread_signal == 0) { + rand_thread_signal = 1; + lwkt_schedule(rand_td); + } +} + +/* + * True random number source + */ +void +add_true_randomness(int val) +{ + spin_lock_wr(&rand_spin); + IBAA_Seed(val); + L15_Vector((const LByteType *) &val, sizeof (val)); + ++nrandevents; + spin_unlock_wr(&rand_spin); +} + +/* + * Poll (always succeeds) + */ +int +random_poll(dev_t dev, int events, struct thread *td) +{ + int revents = 0; + + if (events & (POLLIN | POLLRDNORM)) + revents |= events & (POLLIN | POLLRDNORM); + if (events & (POLLOUT | POLLWRNORM)) + revents |= events & (POLLOUT | POLLWRNORM); + + return (revents); +} + +/* + * Heavy weight random number generator. May return less then the + * requested number of bytes. + */ +u_int +read_random(void *buf, u_int nbytes) +{ + u_int i; + + spin_lock_wr(&rand_spin); + for (i = 0; i < nbytes; ++i) + ((u_char *)buf)[i] = IBAA_Byte(); + spin_unlock_wr(&rand_spin); + add_interrupt_randomness(0); + return(i); +} + +/* + * Lightweight random number generator. Must return requested number of + * bytes. + */ +u_int +read_random_unlimited(void *buf, u_int nbytes) +{ + u_int i; + + spin_lock_wr(&rand_spin); + for (i = 0; i < nbytes; ++i) + ((u_char *)buf)[i] = L15_Byte(); + spin_unlock_wr(&rand_spin); + add_interrupt_randomness(0); + return (i); +} + +/* + * Random number generator helper thread. This limits code overhead from + * high frequency events by delaying the clearing of rand_thread_signal. + */ +static +void +rand_thread_loop(void *dummy) +{ + int count; + + for (;;) { + NANOUP_EVENT (); + spin_lock_wr(&rand_spin); + count = (int)(L15_Byte() * hz / (256 * 10) + hz / 10); + spin_unlock_wr(&rand_spin); + tsleep(rand_td, 0, "rwait", count); + rand_thread_signal = 0; + lwkt_deschedule_self(rand_td); + lwkt_switch(); + } +} + +static +void +rand_thread_init(void) +{ + lwkt_create(rand_thread_loop, NULL, &rand_td, NULL, 0, 0, "random"); +} + +SYSINIT(rand, SI_SUB_HELPER_THREADS, SI_ORDER_ANY, rand_thread_init, 0); + +/* + * Time-buffered event time-stamping. This is necessary to cutoff higher + * event frequencies, e.g. an interrupt occuring at 25Hz. In such cases + * the CPU is being chewed and the timestamps are skewed (minimal variation). + * Use a nano-second time-delay to limit how many times an Event can occur + * in one second; <= 5Hz. Note that this doesn't prevent time-stamp skewing. + * This implementation randmoises the time-delay between events, which adds + * a layer of security/unpredictability with regard to read-events (a user + * controlled input). + * + * Note: now.tv_nsec should range [ 0 - 1000,000,000 ]. + * Note: "ACCUM" is a security measure (result = capped-unknown + unknown), + * and also produces an uncapped (>=32-bit) value. + */ +static void +NANOUP_EVENT(void) +{ + static struct timespec ACCUM = { 0, 0 }; + static struct timespec NEXT = { 0, 0 }; + struct timespec now; + + nanouptime(&now); + spin_lock_wr(&rand_spin); + if ((now.tv_nsec > NEXT.tv_nsec) || (now.tv_sec != NEXT.tv_sec)) { + /* + * Randomised time-delay: 200e6 - 350e6 ns; 5 - 2.86 Hz. + */ + unsigned long one_mil; + unsigned long timeDelay; + + one_mil = 1000000UL; /* 0.001 s */ + timeDelay = (one_mil * 200) + (((unsigned)ACCUM.tv_nsec % 151) * one_mil); + NEXT.tv_nsec = now.tv_nsec + timeDelay; + NEXT.tv_sec = now.tv_sec; + ACCUM.tv_nsec += now.tv_nsec; + + /* + * The TSC, if present, generally has an even higher + * resolution. Integrate a portion of it into our seed. + */ + if (tsc_present) + ACCUM.tv_nsec ^= rdtsc() & 255; + + IBAA_Seed(ACCUM.tv_nsec); + L15_Vector((const LByteType *)&ACCUM.tv_nsec, + sizeof(ACCUM.tv_nsec)); + ++nrandevents; + } + spin_unlock_wr(&rand_spin); +} + -- 2.41.0