X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=drivers%2Fchar%2Frandom.c;h=074bf22f313a4498ac9f4f096a2b4b4550a84159;hb=43bc926fffd92024b46cafaf7350d669ba9ca884;hp=295e3f718b5c4dc3e1b8a02c13c8c19ea4164fe5;hpb=c7b5ebbddf7bcd3651947760f423e3783bbe6573;p=linux-2.6.git diff --git a/drivers/char/random.c b/drivers/char/random.c index 295e3f718..074bf22f3 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -1,8 +1,8 @@ /* * random.c -- A strong random number generator * - * Version 1.89, last modified 19-Sep-99 - * + * Copyright Matt Mackall , 2003, 2004, 2005 + * * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All * rights reserved. * @@ -18,13 +18,13 @@ * 3. The name of the author may not be used to endorse or promote * products derived from this software without specific prior * written permission. - * + * * ALTERNATIVELY, this product may be distributed under the terms of * the GNU General Public License, in which case the provisions of the GPL are * required INSTEAD OF the above restrictions. (This clause is * necessary due to a potential bad interaction between the GPL and * the restrictions contained in a BSD-style copyright.) - * + * * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF @@ -40,8 +40,8 @@ */ /* - * (now, with legal B.S. out of the way.....) - * + * (now, with legal B.S. out of the way.....) + * * This routine gathers environmental noise from device drivers, etc., * and returns good random numbers, suitable for cryptographic use. * Besides the obvious cryptographic uses, these numbers are also good @@ -51,7 +51,7 @@ * * Theory of operation * =================== - * + * * Computers are very predictable devices. Hence it is extremely hard * to produce truly random numbers on a computer --- as opposed to * pseudo-random numbers, which can easily generated by using a @@ -62,7 +62,7 @@ * must be hard for outside attackers to observe, and use that to * generate random numbers. In a Unix environment, this is best done * from inside the kernel. - * + * * Sources of randomness from the environment include inter-keyboard * timings, inter-interrupt timings from some interrupts, and other * events which are both (a) non-deterministic and (b) hard for an @@ -74,7 +74,7 @@ * As random bytes are mixed into the entropy pool, the routines keep * an *estimate* of how many bits of randomness have been stored into * the random number generator's internal state. - * + * * When random bytes are desired, they are obtained by taking the SHA * hash of the contents of the "entropy pool". The SHA hash avoids * exposing the internal state of the entropy pool. It is believed to @@ -86,7 +86,7 @@ * reason, the routine decreases its internal estimate of how many * bits of "true randomness" are contained in the entropy pool as it * outputs random numbers. - * + * * If this estimate goes to zero, the routine can still generate * random numbers; however, an attacker may (at least in theory) be * able to infer the future output of the generator from prior @@ -94,10 +94,10 @@ * not believed to be feasible, but there is a remote possibility. * Nonetheless, these numbers should be useful for the vast majority * of purposes. - * + * * Exported interfaces ---- output * =============================== - * + * * There are three exported interfaces; the first is one designed to * be used from within the kernel: * @@ -105,14 +105,14 @@ * * This interface will return the requested number of random bytes, * and place it in the requested buffer. - * + * * The two other interfaces are two character devices /dev/random and * /dev/urandom. /dev/random is suitable for use when very high * quality randomness is desired (for example, for key generation or * one-time pads), as it will only return a maximum of the number of * bits of randomness (as estimated by the random number generator) * contained in the entropy pool. - * + * * The /dev/urandom device does not have this limit, and will return * as many bytes as are requested. As more and more random bytes are * requested without giving time for the entropy pool to recharge, @@ -121,19 +121,16 @@ * * Exported interfaces ---- input * ============================== - * + * * The current exported interfaces for gathering environmental noise * from the devices are: - * - * void add_keyboard_randomness(unsigned char scancode); - * void add_mouse_randomness(__u32 mouse_data); + * + * void add_input_randomness(unsigned int type, unsigned int code, + * unsigned int value); * void add_interrupt_randomness(int irq); - * - * add_keyboard_randomness() uses the inter-keypress timing, as well as the - * scancode as random inputs into the "entropy pool". - * - * add_mouse_randomness() uses the mouse interrupt timing, as well as - * the reported position of the mouse from the hardware. + * + * add_input_randomness() uses the input layer interrupt timing, as well as + * the event type information from the hardware. * * add_interrupt_randomness() uses the inter-interrupt timing as random * inputs to the entropy pool. Note that not all interrupts are good @@ -142,14 +139,14 @@ * regular, and hence predictable to an attacker. Disk interrupts are * a better measure, since the timing of the disk interrupts are more * unpredictable. - * + * * All of these routines try to estimate how many bits of randomness a * particular randomness source. They do this by keeping track of the * first and second order deltas of the event timings. * * Ensuring unpredictability at system startup * ============================================ - * + * * When any operating system starts up, it will go through a sequence * of actions that are fairly predictable by an adversary, especially * if the start-up does not involve interaction with a human operator. @@ -158,7 +155,7 @@ * counteract this effect, it helps to carry information in the * entropy pool across shut-downs and start-ups. To do this, put the * following lines an appropriate script which is run during the boot - * sequence: + * sequence: * * echo "Initializing random number generator..." * random_seed=/var/run/random-seed @@ -170,9 +167,7 @@ * touch $random_seed * fi * chmod 600 $random_seed - * poolfile=/proc/sys/kernel/random/poolsize - * [ -r $poolfile ] && bytes=`cat $poolfile` || bytes=512 - * dd if=/dev/urandom of=$random_seed count=1 bs=$bytes + * dd if=/dev/urandom of=$random_seed count=1 bs=512 * * and the following lines in an appropriate script which is run as * the system is shutdown: @@ -183,15 +178,13 @@ * random_seed=/var/run/random-seed * touch $random_seed * chmod 600 $random_seed - * poolfile=/proc/sys/kernel/random/poolsize - * [ -r $poolfile ] && bytes=`cat $poolfile` || bytes=512 - * dd if=/dev/urandom of=$random_seed count=1 bs=$bytes + * dd if=/dev/urandom of=$random_seed count=1 bs=512 * * For example, on most modern systems using the System V init * scripts, such code fragments would be found in * /etc/rc.d/init.d/random. On older Linux systems, the correct script * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0. - * + * * Effectively, these commands cause the contents of the entropy pool * to be saved at shut-down time and reloaded into the entropy pool at * start-up. (The 'dd' in the addition to the bootup script is to @@ -211,7 +204,7 @@ * * mknod /dev/random c 1 8 * mknod /dev/urandom c 1 9 - * + * * Acknowledgements: * ================= * @@ -221,17 +214,10 @@ * number generator, which speed up the mixing function of the entropy * pool, taken from PGPfone. Dale Worley has also contributed many * useful ideas and suggestions to improve this driver. - * + * * Any flaws in the design are solely my responsibility, and should * not be attributed to the Phil, Colin, or any of authors of PGP. - * - * The code for SHA transform was taken from Peter Gutmann's - * implementation, which has been placed in the public domain. - * The code for MD5 transform was taken from Colin Plumb's - * implementation, which has been placed in the public domain. - * The MD5 cryptographic checksum was devised by Ronald Rivest, and is - * documented in RFC 1321, "The MD5 Message Digest Algorithm". - * + * * Further background information on this topic may be obtained from * RFC 1750, "Randomness Recommendations for Security", by Donald * Eastlake, Steve Crocker, and Jeff Schiller. @@ -249,11 +235,11 @@ #include #include #include -#include #include #include #include #include +#include #include #include @@ -263,10 +249,9 @@ /* * Configuration information */ -#define DEFAULT_POOL_SIZE 512 -#define SECONDARY_POOL_SIZE 128 -#define BATCH_ENTROPY_SIZE 256 -#define USE_SHA +#define INPUT_POOL_WORDS 128 +#define OUTPUT_POOL_WORDS 32 +#define SEC_XFER_SIZE 512 /* * The minimum number of bits of entropy before we wake up a read on @@ -286,7 +271,7 @@ static int random_write_wakeup_thresh = 128; * samples to avoid wasting CPU time and reduce lock contention. */ -static int trickle_thresh = DEFAULT_POOL_SIZE * 7; +static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28; static DEFINE_PER_CPU(int, trickle_count) = 0; @@ -299,45 +284,40 @@ static DEFINE_PER_CPU(int, trickle_count) = 0; * get the twisting happening as fast as possible. */ static struct poolinfo { - int poolwords; - int tap1, tap2, tap3, tap4, tap5; + int poolwords; + int tap1, tap2, tap3, tap4, tap5; } poolinfo_table[] = { + /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ + { 128, 103, 76, 51, 25, 1 }, + /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ + { 32, 26, 20, 14, 7, 1 }, +#if 0 /* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ { 2048, 1638, 1231, 819, 411, 1 }, /* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */ { 1024, 817, 615, 412, 204, 1 }, -#if 0 /* Alternate polynomial */ + /* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */ { 1024, 819, 616, 410, 207, 2 }, -#endif /* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */ { 512, 411, 308, 208, 104, 1 }, -#if 0 /* Alternates */ + /* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */ { 512, 409, 307, 206, 102, 2 }, /* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */ { 512, 409, 309, 205, 103, 2 }, -#endif /* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */ { 256, 205, 155, 101, 52, 1 }, - /* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */ - { 128, 103, 76, 51, 25, 1 }, -#if 0 /* Alternate polynomial */ /* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */ { 128, 103, 78, 51, 27, 2 }, -#endif /* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */ { 64, 52, 39, 26, 14, 1 }, - - /* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */ - { 32, 26, 20, 14, 7, 1 }, - - { 0, 0, 0, 0, 0, 0 }, +#endif }; #define POOLBITS poolwords*32 @@ -353,12 +333,12 @@ static struct poolinfo { * II. ACM Transactions on Mdeling and Computer Simulation 4:254-266) * * Thanks to Colin Plumb for suggesting this. - * + * * We have not analyzed the resultant polynomial to prove it primitive; * in fact it almost certainly isn't. Nonetheless, the irreducible factors * of a random large-degree polynomial over GF(2) are more than large enough * that periodicity is not a concern. - * + * * The input hash is much less sensitive than the output hash. All * that we want of it is that it be a good non-cryptographic hash; * i.e. it not produce collisions when fed "random" data of the sort @@ -386,99 +366,22 @@ static struct poolinfo { * hash; hash collisions will occur no more often than chance. */ -/* - * Linux 2.2 compatibility - */ -#ifndef DECLARE_WAITQUEUE -#define DECLARE_WAITQUEUE(WAIT, PTR) struct wait_queue WAIT = { PTR, NULL } -#endif -#ifndef DECLARE_WAIT_QUEUE_HEAD -#define DECLARE_WAIT_QUEUE_HEAD(WAIT) struct wait_queue *WAIT -#endif - /* * Static global variables */ -static struct entropy_store *random_state; /* The default global store */ -static struct entropy_store *sec_random_state; /* secondary store */ -static struct entropy_store *urandom_state; /* For urandom */ static DECLARE_WAIT_QUEUE_HEAD(random_read_wait); static DECLARE_WAIT_QUEUE_HEAD(random_write_wait); -/* - * Forward procedure declarations - */ -#ifdef CONFIG_SYSCTL -static void sysctl_init_random(struct entropy_store *random_state); -#endif - -/***************************************************************** - * - * Utility functions, with some ASM defined functions for speed - * purposes - * - *****************************************************************/ - -/* - * Unfortunately, while the GCC optimizer for the i386 understands how - * to optimize a static rotate left of x bits, it doesn't know how to - * deal with a variable rotate of x bits. So we use a bit of asm magic. - */ -#if (!defined (__i386__)) -static inline __u32 rotate_left(int i, __u32 word) -{ - return (word << i) | (word >> (32 - i)); - -} -#else -static inline __u32 rotate_left(int i, __u32 word) -{ - __asm__("roll %%cl,%0" - :"=r" (word) - :"0" (word),"c" (i)); - return word; -} -#endif - -/* - * More asm magic.... - * - * For entropy estimation, we need to do an integral base 2 - * logarithm. - * - * Note the "12bits" suffix - this is used for numbers between - * 0 and 4095 only. This allows a few shortcuts. - */ -#if 0 /* Slow but clear version */ -static inline __u32 int_ln_12bits(__u32 word) -{ - __u32 nbits = 0; - - while (word >>= 1) - nbits++; - return nbits; -} -#else /* Faster (more clever) version, courtesy Colin Plumb */ -static inline __u32 int_ln_12bits(__u32 word) -{ - /* Smear msbit right to make an n-bit mask */ - word |= word >> 8; - word |= word >> 4; - word |= word >> 2; - word |= word >> 1; - /* Remove one bit to make this a logarithm */ - word >>= 1; - /* Count the bits set in the word */ - word -= (word >> 1) & 0x555; - word = (word & 0x333) + ((word >> 2) & 0x333); - word += (word >> 4); - word += (word >> 8); - return word & 15; -} -#endif - #if 0 -#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg) +static int debug = 0; +module_param(debug, bool, 0644); +#define DEBUG_ENT(fmt, arg...) do { if (debug) \ + printk(KERN_DEBUG "random %04d %04d %04d: " \ + fmt,\ + input_pool.entropy_count,\ + blocking_pool.entropy_count,\ + nonblocking_pool.entropy_count,\ + ## arg); } while (0) #else #define DEBUG_ENT(fmt, arg...) do {} while (0) #endif @@ -487,109 +390,82 @@ static inline __u32 int_ln_12bits(__u32 word) * * OS independent entropy store. Here are the functions which handle * storing entropy in an entropy pool. - * + * **********************************************************************/ +struct entropy_store; struct entropy_store { /* mostly-read data: */ - struct poolinfo poolinfo; - __u32 *pool; - const char *name; + struct poolinfo *poolinfo; + __u32 *pool; + const char *name; + int limit; + struct entropy_store *pull; /* read-write data: */ spinlock_t lock ____cacheline_aligned_in_smp; - unsigned add_ptr; - int entropy_count; - int input_rotate; + unsigned add_ptr; + int entropy_count; + int input_rotate; }; -/* - * Initialize the entropy store. The input argument is the size of - * the random pool. - * - * Returns an negative error if there is a problem. - */ -static int create_entropy_store(int size, const char *name, - struct entropy_store **ret_bucket) -{ - struct entropy_store *r; - struct poolinfo *p; - int poolwords; +static __u32 input_pool_data[INPUT_POOL_WORDS]; +static __u32 blocking_pool_data[OUTPUT_POOL_WORDS]; +static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS]; - poolwords = (size + 3) / 4; /* Convert bytes->words */ - /* The pool size must be a multiple of 16 32-bit words */ - poolwords = ((poolwords + 15) / 16) * 16; - - for (p = poolinfo_table; p->poolwords; p++) { - if (poolwords == p->poolwords) - break; - } - if (p->poolwords == 0) - return -EINVAL; - - r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL); - if (!r) - return -ENOMEM; +static struct entropy_store input_pool = { + .poolinfo = &poolinfo_table[0], + .name = "input", + .limit = 1, + .lock = SPIN_LOCK_UNLOCKED, + .pool = input_pool_data +}; - memset (r, 0, sizeof(struct entropy_store)); - r->poolinfo = *p; +static struct entropy_store blocking_pool = { + .poolinfo = &poolinfo_table[1], + .name = "blocking", + .limit = 1, + .pull = &input_pool, + .lock = SPIN_LOCK_UNLOCKED, + .pool = blocking_pool_data +}; - r->pool = kmalloc(POOLBYTES, GFP_KERNEL); - if (!r->pool) { - kfree(r); - return -ENOMEM; - } - memset(r->pool, 0, POOLBYTES); - r->lock = SPIN_LOCK_UNLOCKED; - r->name = name; - *ret_bucket = r; - return 0; -} +static struct entropy_store nonblocking_pool = { + .poolinfo = &poolinfo_table[1], + .name = "nonblocking", + .pull = &input_pool, + .lock = SPIN_LOCK_UNLOCKED, + .pool = nonblocking_pool_data +}; -/* Clear the entropy pool and associated counters. */ -static void clear_entropy_store(struct entropy_store *r) -{ - r->add_ptr = 0; - r->entropy_count = 0; - r->input_rotate = 0; - memset(r->pool, 0, r->poolinfo.POOLBYTES); -} -#ifdef CONFIG_SYSCTL -static void free_entropy_store(struct entropy_store *r) -{ - if (r->pool) - kfree(r->pool); - kfree(r); -} -#endif /* * This function adds a byte into the entropy "pool". It does not * update the entropy estimate. The caller should call * credit_entropy_store if this is appropriate. - * + * * The pool is stirred with a primitive polynomial of the appropriate * degree, and then twisted. We twist by three bits at a time because * it's cheap to do so and helps slightly in the expected case where * the entropy is concentrated in the low-order bits. */ -static void add_entropy_words(struct entropy_store *r, const __u32 *in, - int nwords) +static void __add_entropy_words(struct entropy_store *r, const __u32 *in, + int nwords, __u32 out[16]) { static __u32 const twist_table[8] = { - 0, 0x3b6e20c8, 0x76dc4190, 0x4db26158, + 0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158, 0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 }; unsigned long i, add_ptr, tap1, tap2, tap3, tap4, tap5; int new_rotate, input_rotate; - int wordmask = r->poolinfo.poolwords - 1; + int wordmask = r->poolinfo->poolwords - 1; __u32 w, next_w; unsigned long flags; /* Taps are constant, so we can load them without holding r->lock. */ - tap1 = r->poolinfo.tap1; - tap2 = r->poolinfo.tap2; - tap3 = r->poolinfo.tap3; - tap4 = r->poolinfo.tap4; - tap5 = r->poolinfo.tap5; + tap1 = r->poolinfo->tap1; + tap2 = r->poolinfo->tap2; + tap3 = r->poolinfo->tap3; + tap4 = r->poolinfo->tap4; + tap5 = r->poolinfo->tap5; next_w = *in++; spin_lock_irqsave(&r->lock, flags); @@ -598,7 +474,7 @@ static void add_entropy_words(struct entropy_store *r, const __u32 *in, add_ptr = r->add_ptr; while (nwords--) { - w = rotate_left(input_rotate, next_w); + w = rol32(next_w, input_rotate); if (nwords > 0) next_w = *in++; i = add_ptr = (add_ptr - 1) & wordmask; @@ -626,9 +502,22 @@ static void add_entropy_words(struct entropy_store *r, const __u32 *in, r->input_rotate = input_rotate; r->add_ptr = add_ptr; + if (out) { + for (i = 0; i < 16; i++) { + out[i] = r->pool[add_ptr]; + add_ptr = (add_ptr - 1) & wordmask; + } + } + spin_unlock_irqrestore(&r->lock, flags); } +static inline void add_entropy_words(struct entropy_store *r, const __u32 *in, + int nwords) +{ + __add_entropy_words(r, in, nwords, NULL); +} + /* * Credit (or debit) the entropy store with n bits of entropy */ @@ -642,137 +531,18 @@ static void credit_entropy_store(struct entropy_store *r, int nbits) DEBUG_ENT("negative entropy/overflow (%d+%d)\n", r->entropy_count, nbits); r->entropy_count = 0; - } else if (r->entropy_count + nbits > r->poolinfo.POOLBITS) { - r->entropy_count = r->poolinfo.POOLBITS; + } else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) { + r->entropy_count = r->poolinfo->POOLBITS; } else { r->entropy_count += nbits; if (nbits) - DEBUG_ENT("Added %d entropy credits to %s, now %d\n", - nbits, r->name, r->entropy_count); + DEBUG_ENT("added %d entropy credits to %s\n", + nbits, r->name); } spin_unlock_irqrestore(&r->lock, flags); } -/********************************************************************** - * - * Entropy batch input management - * - * We batch entropy to be added to avoid increasing interrupt latency - * - **********************************************************************/ - -struct sample { - __u32 data[2]; - int credit; -}; - -static struct sample *batch_entropy_pool, *batch_entropy_copy; -static int batch_head, batch_tail; -static spinlock_t batch_lock = SPIN_LOCK_UNLOCKED; - -static int batch_max; -static void batch_entropy_process(void *private_); -static DECLARE_WORK(batch_work, batch_entropy_process, NULL); - -/* note: the size must be a power of 2 */ -static int __init batch_entropy_init(int size, struct entropy_store *r) -{ - batch_entropy_pool = kmalloc(size*sizeof(struct sample), GFP_KERNEL); - if (!batch_entropy_pool) - return -1; - batch_entropy_copy = kmalloc(size*sizeof(struct sample), GFP_KERNEL); - if (!batch_entropy_copy) { - kfree(batch_entropy_pool); - return -1; - } - batch_head = batch_tail = 0; - batch_work.data = r; - batch_max = size; - return 0; -} - -/* - * Changes to the entropy data is put into a queue rather than being added to - * the entropy counts directly. This is presumably to avoid doing heavy - * hashing calculations during an interrupt in add_timer_randomness(). - * Instead, the entropy is only added to the pool by keventd. - */ -void batch_entropy_store(u32 a, u32 b, int num) -{ - int new; - unsigned long flags; - - if (!batch_max) - return; - - spin_lock_irqsave(&batch_lock, flags); - - batch_entropy_pool[batch_head].data[0] = a; - batch_entropy_pool[batch_head].data[1] = b; - batch_entropy_pool[batch_head].credit = num; - - if (((batch_head - batch_tail) & (batch_max-1)) >= (batch_max / 2)) { - /* - * Schedule it for the next timer tick: - */ - schedule_delayed_work(&batch_work, 1); - } - - new = (batch_head+1) & (batch_max-1); - if (new == batch_tail) { - DEBUG_ENT("batch entropy buffer full\n"); - } else { - batch_head = new; - } - - spin_unlock_irqrestore(&batch_lock, flags); -} - -EXPORT_SYMBOL(batch_entropy_store); - -/* - * Flush out the accumulated entropy operations, adding entropy to the passed - * store (normally random_state). If that store has enough entropy, alternate - * between randomizing the data of the primary and secondary stores. - */ -static void batch_entropy_process(void *private_) -{ - struct entropy_store *r = (struct entropy_store *) private_, *p; - int max_entropy = r->poolinfo.POOLBITS; - unsigned head, tail; - - /* Mixing into the pool is expensive, so copy over the batch - * data and release the batch lock. The pool is at least half - * full, so don't worry too much about copying only the used - * part. - */ - spin_lock_irq(&batch_lock); - - memcpy(batch_entropy_copy, batch_entropy_pool, - batch_max*sizeof(struct sample)); - - head = batch_head; - tail = batch_tail; - batch_tail = batch_head; - - spin_unlock_irq(&batch_lock); - - p = r; - while (head != tail) { - if (r->entropy_count >= max_entropy) { - r = (r == sec_random_state) ? random_state : - sec_random_state; - max_entropy = r->poolinfo.POOLBITS; - } - add_entropy_words(r, batch_entropy_copy[tail].data, 2); - credit_entropy_store(r, batch_entropy_copy[tail].credit); - tail = (tail+1) & (batch_max-1); - } - if (p->entropy_count >= random_read_wakeup_thresh) - wake_up_interruptible(&random_read_wait); -} - /********************************************************************* * * Entropy input management @@ -781,14 +551,12 @@ static void batch_entropy_process(void *private_) /* There is one of these per entropy source */ struct timer_rand_state { - cycles_t last_time; - long last_delta,last_delta2; - unsigned dont_count_entropy:1; + cycles_t last_time; + long last_delta,last_delta2; + unsigned dont_count_entropy:1; }; -static struct timer_rand_state keyboard_timer_state; -static struct timer_rand_state mouse_timer_state; -static struct timer_rand_state extract_timer_state; +static struct timer_rand_state input_timer_state; static struct timer_rand_state *irq_timer_state[NR_IRQS]; /* @@ -803,36 +571,33 @@ static struct timer_rand_state *irq_timer_state[NR_IRQS]; */ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) { - cycles_t time; - long delta, delta2, delta3; - int entropy = 0; + struct { + cycles_t cycles; + long jiffies; + unsigned num; + } sample; + long delta, delta2, delta3; preempt_disable(); /* if over the trickle threshold, use only 1 in 4096 samples */ - if ( random_state->entropy_count > trickle_thresh && - (__get_cpu_var(trickle_count)++ & 0xfff)) + if (input_pool.entropy_count > trickle_thresh && + (__get_cpu_var(trickle_count)++ & 0xfff)) goto out; - /* - * Use get_cycles() if implemented, otherwise fall back to - * jiffies. - */ - time = get_cycles(); - if (time != 0) { - if (sizeof(time) > 4) - num ^= (u32)(time >> 32); - } else { - time = jiffies; - } + sample.jiffies = jiffies; + sample.cycles = get_cycles(); + sample.num = num; + add_entropy_words(&input_pool, (u32 *)&sample, sizeof(sample)/4); /* * Calculate number of bits of randomness we probably added. * We take into account the first, second and third-order deltas * in order to make our estimate. */ + if (!state->dont_count_entropy) { - delta = time - state->last_time; - state->last_time = time; + delta = sample.jiffies - state->last_time; + state->last_time = sample.jiffies; delta2 = delta - state->last_delta; state->last_delta = delta; @@ -856,441 +621,55 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) * Round down by 1 bit on general principles, * and limit entropy entimate to 12 bits. */ - delta >>= 1; - delta &= (1 << 12) - 1; - - entropy = int_ln_12bits(delta); + credit_entropy_store(&input_pool, + min_t(int, fls(delta>>1), 11)); } - batch_entropy_store(num, time, entropy); + + if(input_pool.entropy_count >= random_read_wakeup_thresh) + wake_up_interruptible(&random_read_wait); + out: preempt_enable(); } -void add_keyboard_randomness(unsigned char scancode) +void add_input_randomness(unsigned int type, unsigned int code, + unsigned int value) { - static unsigned char last_scancode; - /* ignore autorepeat (multiple key down w/o key up) */ - if (scancode != last_scancode) { - last_scancode = scancode; - add_timer_randomness(&keyboard_timer_state, scancode); - } -} + static unsigned char last_value; -EXPORT_SYMBOL(add_keyboard_randomness); + /* ignore autorepeat and the like */ + if (value == last_value) + return; -void add_mouse_randomness(__u32 mouse_data) -{ - add_timer_randomness(&mouse_timer_state, mouse_data); + DEBUG_ENT("input event\n"); + last_value = value; + add_timer_randomness(&input_timer_state, + (type << 4) ^ code ^ (code >> 4) ^ value); } -EXPORT_SYMBOL(add_mouse_randomness); - void add_interrupt_randomness(int irq) { if (irq >= NR_IRQS || irq_timer_state[irq] == 0) return; - add_timer_randomness(irq_timer_state[irq], 0x100+irq); + DEBUG_ENT("irq event %d\n", irq); + add_timer_randomness(irq_timer_state[irq], 0x100 + irq); } -EXPORT_SYMBOL(add_interrupt_randomness); - void add_disk_randomness(struct gendisk *disk) { if (!disk || !disk->random) return; /* first major is 1, so we get >= 0x200 here */ - add_timer_randomness(disk->random, 0x100+MKDEV(disk->major, disk->first_minor)); -} - -EXPORT_SYMBOL(add_disk_randomness); - -/****************************************************************** - * - * Hash function definition - * - *******************************************************************/ - -/* - * This chunk of code defines a function - * void HASH_TRANSFORM(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE], - * __u32 const data[16]) - * - * The function hashes the input data to produce a digest in the first - * HASH_BUFFER_SIZE words of the digest[] array, and uses HASH_EXTRA_SIZE - * more words for internal purposes. (This buffer is exported so the - * caller can wipe it once rather than this code doing it each call, - * and tacking it onto the end of the digest[] array is the quick and - * dirty way of doing it.) - * - * It so happens that MD5 and SHA share most of the initial vector - * used to initialize the digest[] array before the first call: - * 1) 0x67452301 - * 2) 0xefcdab89 - * 3) 0x98badcfe - * 4) 0x10325476 - * 5) 0xc3d2e1f0 (SHA only) - * - * For /dev/random purposes, the length of the data being hashed is - * fixed in length, so appending a bit count in the usual way is not - * cryptographically necessary. - */ - -#ifdef USE_SHA - -#define HASH_BUFFER_SIZE 5 -#define HASH_EXTRA_SIZE 80 -#define HASH_TRANSFORM SHATransform + DEBUG_ENT("disk event %d:%d\n", disk->major, disk->first_minor); -/* Various size/speed tradeoffs are available. Choose 0..3. */ -#define SHA_CODE_SIZE 0 - -/* - * SHA transform algorithm, taken from code written by Peter Gutmann, - * and placed in the public domain. - */ - -/* The SHA f()-functions. */ - -#define f1(x,y,z) ( z ^ (x & (y^z)) ) /* Rounds 0-19: x ? y : z */ -#define f2(x,y,z) (x ^ y ^ z) /* Rounds 20-39: XOR */ -#define f3(x,y,z) ( (x & y) + (z & (x ^ y)) ) /* Rounds 40-59: majority */ -#define f4(x,y,z) (x ^ y ^ z) /* Rounds 60-79: XOR */ - -/* The SHA Mysterious Constants */ - -#define K1 0x5A827999L /* Rounds 0-19: sqrt(2) * 2^30 */ -#define K2 0x6ED9EBA1L /* Rounds 20-39: sqrt(3) * 2^30 */ -#define K3 0x8F1BBCDCL /* Rounds 40-59: sqrt(5) * 2^30 */ -#define K4 0xCA62C1D6L /* Rounds 60-79: sqrt(10) * 2^30 */ - -#define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) ) - -#define subRound(a, b, c, d, e, f, k, data) \ - ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) ) - - -static void SHATransform(__u32 digest[85], __u32 const data[16]) -{ - __u32 A, B, C, D, E; /* Local vars */ - __u32 TEMP; - int i; -#define W (digest + HASH_BUFFER_SIZE) /* Expanded data array */ - - /* - * Do the preliminary expansion of 16 to 80 words. Doing it - * out-of-line line this is faster than doing it in-line on - * register-starved machines like the x86, and not really any - * slower on real processors. - */ - memcpy(W, data, 16*sizeof(__u32)); - for (i = 0; i < 64; i++) { - TEMP = W[i] ^ W[i+2] ^ W[i+8] ^ W[i+13]; - W[i+16] = ROTL(1, TEMP); - } - - /* Set up first buffer and local data buffer */ - A = digest[ 0 ]; - B = digest[ 1 ]; - C = digest[ 2 ]; - D = digest[ 3 ]; - E = digest[ 4 ]; - - /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */ -#if SHA_CODE_SIZE == 0 - /* - * Approximately 50% of the speed of the largest version, but - * takes up 1/16 the space. Saves about 6k on an i386 kernel. - */ - for (i = 0; i < 80; i++) { - if (i < 40) { - if (i < 20) - TEMP = f1(B, C, D) + K1; - else - TEMP = f2(B, C, D) + K2; - } else { - if (i < 60) - TEMP = f3(B, C, D) + K3; - else - TEMP = f4(B, C, D) + K4; - } - TEMP += ROTL(5, A) + E + W[i]; - E = D; D = C; C = ROTL(30, B); B = A; A = TEMP; - } -#elif SHA_CODE_SIZE == 1 - for (i = 0; i < 20; i++) { - TEMP = f1(B, C, D) + K1 + ROTL(5, A) + E + W[i]; - E = D; D = C; C = ROTL(30, B); B = A; A = TEMP; - } - for (; i < 40; i++) { - TEMP = f2(B, C, D) + K2 + ROTL(5, A) + E + W[i]; - E = D; D = C; C = ROTL(30, B); B = A; A = TEMP; - } - for (; i < 60; i++) { - TEMP = f3(B, C, D) + K3 + ROTL(5, A) + E + W[i]; - E = D; D = C; C = ROTL(30, B); B = A; A = TEMP; - } - for (; i < 80; i++) { - TEMP = f4(B, C, D) + K4 + ROTL(5, A) + E + W[i]; - E = D; D = C; C = ROTL(30, B); B = A; A = TEMP; - } -#elif SHA_CODE_SIZE == 2 - for (i = 0; i < 20; i += 5) { - subRound( A, B, C, D, E, f1, K1, W[ i ] ); - subRound( E, A, B, C, D, f1, K1, W[ i+1 ] ); - subRound( D, E, A, B, C, f1, K1, W[ i+2 ] ); - subRound( C, D, E, A, B, f1, K1, W[ i+3 ] ); - subRound( B, C, D, E, A, f1, K1, W[ i+4 ] ); - } - for (; i < 40; i += 5) { - subRound( A, B, C, D, E, f2, K2, W[ i ] ); - subRound( E, A, B, C, D, f2, K2, W[ i+1 ] ); - subRound( D, E, A, B, C, f2, K2, W[ i+2 ] ); - subRound( C, D, E, A, B, f2, K2, W[ i+3 ] ); - subRound( B, C, D, E, A, f2, K2, W[ i+4 ] ); - } - for (; i < 60; i += 5) { - subRound( A, B, C, D, E, f3, K3, W[ i ] ); - subRound( E, A, B, C, D, f3, K3, W[ i+1 ] ); - subRound( D, E, A, B, C, f3, K3, W[ i+2 ] ); - subRound( C, D, E, A, B, f3, K3, W[ i+3 ] ); - subRound( B, C, D, E, A, f3, K3, W[ i+4 ] ); - } - for (; i < 80; i += 5) { - subRound( A, B, C, D, E, f4, K4, W[ i ] ); - subRound( E, A, B, C, D, f4, K4, W[ i+1 ] ); - subRound( D, E, A, B, C, f4, K4, W[ i+2 ] ); - subRound( C, D, E, A, B, f4, K4, W[ i+3 ] ); - subRound( B, C, D, E, A, f4, K4, W[ i+4 ] ); - } -#elif SHA_CODE_SIZE == 3 /* Really large version */ - subRound( A, B, C, D, E, f1, K1, W[ 0 ] ); - subRound( E, A, B, C, D, f1, K1, W[ 1 ] ); - subRound( D, E, A, B, C, f1, K1, W[ 2 ] ); - subRound( C, D, E, A, B, f1, K1, W[ 3 ] ); - subRound( B, C, D, E, A, f1, K1, W[ 4 ] ); - subRound( A, B, C, D, E, f1, K1, W[ 5 ] ); - subRound( E, A, B, C, D, f1, K1, W[ 6 ] ); - subRound( D, E, A, B, C, f1, K1, W[ 7 ] ); - subRound( C, D, E, A, B, f1, K1, W[ 8 ] ); - subRound( B, C, D, E, A, f1, K1, W[ 9 ] ); - subRound( A, B, C, D, E, f1, K1, W[ 10 ] ); - subRound( E, A, B, C, D, f1, K1, W[ 11 ] ); - subRound( D, E, A, B, C, f1, K1, W[ 12 ] ); - subRound( C, D, E, A, B, f1, K1, W[ 13 ] ); - subRound( B, C, D, E, A, f1, K1, W[ 14 ] ); - subRound( A, B, C, D, E, f1, K1, W[ 15 ] ); - subRound( E, A, B, C, D, f1, K1, W[ 16 ] ); - subRound( D, E, A, B, C, f1, K1, W[ 17 ] ); - subRound( C, D, E, A, B, f1, K1, W[ 18 ] ); - subRound( B, C, D, E, A, f1, K1, W[ 19 ] ); - - subRound( A, B, C, D, E, f2, K2, W[ 20 ] ); - subRound( E, A, B, C, D, f2, K2, W[ 21 ] ); - subRound( D, E, A, B, C, f2, K2, W[ 22 ] ); - subRound( C, D, E, A, B, f2, K2, W[ 23 ] ); - subRound( B, C, D, E, A, f2, K2, W[ 24 ] ); - subRound( A, B, C, D, E, f2, K2, W[ 25 ] ); - subRound( E, A, B, C, D, f2, K2, W[ 26 ] ); - subRound( D, E, A, B, C, f2, K2, W[ 27 ] ); - subRound( C, D, E, A, B, f2, K2, W[ 28 ] ); - subRound( B, C, D, E, A, f2, K2, W[ 29 ] ); - subRound( A, B, C, D, E, f2, K2, W[ 30 ] ); - subRound( E, A, B, C, D, f2, K2, W[ 31 ] ); - subRound( D, E, A, B, C, f2, K2, W[ 32 ] ); - subRound( C, D, E, A, B, f2, K2, W[ 33 ] ); - subRound( B, C, D, E, A, f2, K2, W[ 34 ] ); - subRound( A, B, C, D, E, f2, K2, W[ 35 ] ); - subRound( E, A, B, C, D, f2, K2, W[ 36 ] ); - subRound( D, E, A, B, C, f2, K2, W[ 37 ] ); - subRound( C, D, E, A, B, f2, K2, W[ 38 ] ); - subRound( B, C, D, E, A, f2, K2, W[ 39 ] ); - - subRound( A, B, C, D, E, f3, K3, W[ 40 ] ); - subRound( E, A, B, C, D, f3, K3, W[ 41 ] ); - subRound( D, E, A, B, C, f3, K3, W[ 42 ] ); - subRound( C, D, E, A, B, f3, K3, W[ 43 ] ); - subRound( B, C, D, E, A, f3, K3, W[ 44 ] ); - subRound( A, B, C, D, E, f3, K3, W[ 45 ] ); - subRound( E, A, B, C, D, f3, K3, W[ 46 ] ); - subRound( D, E, A, B, C, f3, K3, W[ 47 ] ); - subRound( C, D, E, A, B, f3, K3, W[ 48 ] ); - subRound( B, C, D, E, A, f3, K3, W[ 49 ] ); - subRound( A, B, C, D, E, f3, K3, W[ 50 ] ); - subRound( E, A, B, C, D, f3, K3, W[ 51 ] ); - subRound( D, E, A, B, C, f3, K3, W[ 52 ] ); - subRound( C, D, E, A, B, f3, K3, W[ 53 ] ); - subRound( B, C, D, E, A, f3, K3, W[ 54 ] ); - subRound( A, B, C, D, E, f3, K3, W[ 55 ] ); - subRound( E, A, B, C, D, f3, K3, W[ 56 ] ); - subRound( D, E, A, B, C, f3, K3, W[ 57 ] ); - subRound( C, D, E, A, B, f3, K3, W[ 58 ] ); - subRound( B, C, D, E, A, f3, K3, W[ 59 ] ); - - subRound( A, B, C, D, E, f4, K4, W[ 60 ] ); - subRound( E, A, B, C, D, f4, K4, W[ 61 ] ); - subRound( D, E, A, B, C, f4, K4, W[ 62 ] ); - subRound( C, D, E, A, B, f4, K4, W[ 63 ] ); - subRound( B, C, D, E, A, f4, K4, W[ 64 ] ); - subRound( A, B, C, D, E, f4, K4, W[ 65 ] ); - subRound( E, A, B, C, D, f4, K4, W[ 66 ] ); - subRound( D, E, A, B, C, f4, K4, W[ 67 ] ); - subRound( C, D, E, A, B, f4, K4, W[ 68 ] ); - subRound( B, C, D, E, A, f4, K4, W[ 69 ] ); - subRound( A, B, C, D, E, f4, K4, W[ 70 ] ); - subRound( E, A, B, C, D, f4, K4, W[ 71 ] ); - subRound( D, E, A, B, C, f4, K4, W[ 72 ] ); - subRound( C, D, E, A, B, f4, K4, W[ 73 ] ); - subRound( B, C, D, E, A, f4, K4, W[ 74 ] ); - subRound( A, B, C, D, E, f4, K4, W[ 75 ] ); - subRound( E, A, B, C, D, f4, K4, W[ 76 ] ); - subRound( D, E, A, B, C, f4, K4, W[ 77 ] ); - subRound( C, D, E, A, B, f4, K4, W[ 78 ] ); - subRound( B, C, D, E, A, f4, K4, W[ 79 ] ); -#else -#error Illegal SHA_CODE_SIZE -#endif - - /* Build message digest */ - digest[ 0 ] += A; - digest[ 1 ] += B; - digest[ 2 ] += C; - digest[ 3 ] += D; - digest[ 4 ] += E; - - /* W is wiped by the caller */ -#undef W -} - -#undef ROTL -#undef f1 -#undef f2 -#undef f3 -#undef f4 -#undef K1 -#undef K2 -#undef K3 -#undef K4 -#undef subRound - -#else /* !USE_SHA - Use MD5 */ - -#define HASH_BUFFER_SIZE 4 -#define HASH_EXTRA_SIZE 0 -#define HASH_TRANSFORM MD5Transform - -/* - * MD5 transform algorithm, taken from code written by Colin Plumb, - * and put into the public domain - */ - -/* The four core functions - F1 is optimized somewhat */ - -/* #define F1(x, y, z) (x & y | ~x & z) */ -#define F1(x, y, z) (z ^ (x & (y ^ z))) -#define F2(x, y, z) F1(z, x, y) -#define F3(x, y, z) (x ^ y ^ z) -#define F4(x, y, z) (y ^ (x | ~z)) - -/* This is the central step in the MD5 algorithm. */ -#define MD5STEP(f, w, x, y, z, data, s) \ - ( w += f(x, y, z) + data, w = w<>(32-s), w += x ) - -/* - * The core of the MD5 algorithm, this alters an existing MD5 hash to - * reflect the addition of 16 longwords of new data. MD5Update blocks - * the data and converts bytes into longwords for this routine. - */ -static void MD5Transform(__u32 buf[HASH_BUFFER_SIZE], __u32 const in[16]) -{ - __u32 a, b, c, d; - - a = buf[0]; - b = buf[1]; - c = buf[2]; - d = buf[3]; - - MD5STEP(F1, a, b, c, d, in[ 0]+0xd76aa478, 7); - MD5STEP(F1, d, a, b, c, in[ 1]+0xe8c7b756, 12); - MD5STEP(F1, c, d, a, b, in[ 2]+0x242070db, 17); - MD5STEP(F1, b, c, d, a, in[ 3]+0xc1bdceee, 22); - MD5STEP(F1, a, b, c, d, in[ 4]+0xf57c0faf, 7); - MD5STEP(F1, d, a, b, c, in[ 5]+0x4787c62a, 12); - MD5STEP(F1, c, d, a, b, in[ 6]+0xa8304613, 17); - MD5STEP(F1, b, c, d, a, in[ 7]+0xfd469501, 22); - MD5STEP(F1, a, b, c, d, in[ 8]+0x698098d8, 7); - MD5STEP(F1, d, a, b, c, in[ 9]+0x8b44f7af, 12); - MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17); - MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22); - MD5STEP(F1, a, b, c, d, in[12]+0x6b901122, 7); - MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12); - MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17); - MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22); - - MD5STEP(F2, a, b, c, d, in[ 1]+0xf61e2562, 5); - MD5STEP(F2, d, a, b, c, in[ 6]+0xc040b340, 9); - MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14); - MD5STEP(F2, b, c, d, a, in[ 0]+0xe9b6c7aa, 20); - MD5STEP(F2, a, b, c, d, in[ 5]+0xd62f105d, 5); - MD5STEP(F2, d, a, b, c, in[10]+0x02441453, 9); - MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14); - MD5STEP(F2, b, c, d, a, in[ 4]+0xe7d3fbc8, 20); - MD5STEP(F2, a, b, c, d, in[ 9]+0x21e1cde6, 5); - MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6, 9); - MD5STEP(F2, c, d, a, b, in[ 3]+0xf4d50d87, 14); - MD5STEP(F2, b, c, d, a, in[ 8]+0x455a14ed, 20); - MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905, 5); - MD5STEP(F2, d, a, b, c, in[ 2]+0xfcefa3f8, 9); - MD5STEP(F2, c, d, a, b, in[ 7]+0x676f02d9, 14); - MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20); - - MD5STEP(F3, a, b, c, d, in[ 5]+0xfffa3942, 4); - MD5STEP(F3, d, a, b, c, in[ 8]+0x8771f681, 11); - MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16); - MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23); - MD5STEP(F3, a, b, c, d, in[ 1]+0xa4beea44, 4); - MD5STEP(F3, d, a, b, c, in[ 4]+0x4bdecfa9, 11); - MD5STEP(F3, c, d, a, b, in[ 7]+0xf6bb4b60, 16); - MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23); - MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6, 4); - MD5STEP(F3, d, a, b, c, in[ 0]+0xeaa127fa, 11); - MD5STEP(F3, c, d, a, b, in[ 3]+0xd4ef3085, 16); - MD5STEP(F3, b, c, d, a, in[ 6]+0x04881d05, 23); - MD5STEP(F3, a, b, c, d, in[ 9]+0xd9d4d039, 4); - MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11); - MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16); - MD5STEP(F3, b, c, d, a, in[ 2]+0xc4ac5665, 23); - - MD5STEP(F4, a, b, c, d, in[ 0]+0xf4292244, 6); - MD5STEP(F4, d, a, b, c, in[ 7]+0x432aff97, 10); - MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15); - MD5STEP(F4, b, c, d, a, in[ 5]+0xfc93a039, 21); - MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3, 6); - MD5STEP(F4, d, a, b, c, in[ 3]+0x8f0ccc92, 10); - MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15); - MD5STEP(F4, b, c, d, a, in[ 1]+0x85845dd1, 21); - MD5STEP(F4, a, b, c, d, in[ 8]+0x6fa87e4f, 6); - MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10); - MD5STEP(F4, c, d, a, b, in[ 6]+0xa3014314, 15); - MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21); - MD5STEP(F4, a, b, c, d, in[ 4]+0xf7537e82, 6); - MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10); - MD5STEP(F4, c, d, a, b, in[ 2]+0x2ad7d2bb, 15); - MD5STEP(F4, b, c, d, a, in[ 9]+0xeb86d391, 21); - - buf[0] += a; - buf[1] += b; - buf[2] += c; - buf[3] += d; + add_timer_randomness(disk->random, + 0x100 + MKDEV(disk->major, disk->first_minor)); } -#undef F1 -#undef F2 -#undef F3 -#undef F4 -#undef MD5STEP +EXPORT_SYMBOL(add_disk_randomness); -#endif /* !USE_SHA */ +#define EXTRACT_SIZE 10 /********************************************************************* * @@ -1298,161 +677,174 @@ static void MD5Transform(__u32 buf[HASH_BUFFER_SIZE], __u32 const in[16]) * *********************************************************************/ -#define EXTRACT_ENTROPY_USER 1 -#define EXTRACT_ENTROPY_SECONDARY 2 -#define EXTRACT_ENTROPY_LIMIT 4 -#define TMP_BUF_SIZE (HASH_BUFFER_SIZE + HASH_EXTRA_SIZE) -#define SEC_XFER_SIZE (TMP_BUF_SIZE*4) - static ssize_t extract_entropy(struct entropy_store *r, void * buf, - size_t nbytes, int flags); + size_t nbytes, int min, int rsvd); /* * This utility inline function is responsible for transfering entropy * from the primary pool to the secondary extraction pool. We make * sure we pull enough for a 'catastrophic reseed'. */ -static inline void xfer_secondary_pool(struct entropy_store *r, - size_t nbytes, __u32 *tmp) +static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes) { - if (r->entropy_count < nbytes * 8 && - r->entropy_count < r->poolinfo.POOLBITS) { + __u32 tmp[OUTPUT_POOL_WORDS]; + + if (r->pull && r->entropy_count < nbytes * 8 && + r->entropy_count < r->poolinfo->POOLBITS) { int bytes = max_t(int, random_read_wakeup_thresh / 8, - min_t(int, nbytes, TMP_BUF_SIZE)); + min_t(int, nbytes, sizeof(tmp))); + int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4; - DEBUG_ENT("%04d %04d : going to reseed %s with %d bits " + DEBUG_ENT("going to reseed %s with %d bits " "(%d of %d requested)\n", - random_state->entropy_count, - sec_random_state->entropy_count, r->name, bytes * 8, nbytes * 8, r->entropy_count); - bytes=extract_entropy(random_state, tmp, bytes, - EXTRACT_ENTROPY_LIMIT); - add_entropy_words(r, tmp, bytes); + bytes=extract_entropy(r->pull, tmp, bytes, + random_read_wakeup_thresh / 8, rsvd); + add_entropy_words(r, tmp, (bytes + 3) / 4); credit_entropy_store(r, bytes*8); } } /* - * This function extracts randomness from the "entropy pool", and - * returns it in a buffer. This function computes how many remaining - * bits of entropy are left in the pool, but it does not restrict the - * number of bytes that are actually obtained. If the EXTRACT_ENTROPY_USER - * flag is given, then the buf pointer is assumed to be in user space. + * These functions extracts randomness from the "entropy pool", and + * returns it in a buffer. * - * If the EXTRACT_ENTROPY_SECONDARY flag is given, then we are actually - * extracting entropy from the secondary pool, and can refill from the - * primary pool if needed. + * The min parameter specifies the minimum amount we can pull before + * failing to avoid races that defeat catastrophic reseeding while the + * reserved parameter indicates how much entropy we must leave in the + * pool after each pull to avoid starving other readers. * * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words. */ -static ssize_t extract_entropy(struct entropy_store *r, void * buf, - size_t nbytes, int flags) -{ - ssize_t ret, i; - __u32 tmp[TMP_BUF_SIZE]; - __u32 x; - unsigned long cpuflags; - - /* Redundant, but just in case... */ - if (r->entropy_count > r->poolinfo.POOLBITS) - r->entropy_count = r->poolinfo.POOLBITS; +static size_t account(struct entropy_store *r, size_t nbytes, int min, + int reserved) +{ + unsigned long flags; - if (flags & EXTRACT_ENTROPY_SECONDARY) - xfer_secondary_pool(r, nbytes, tmp); + BUG_ON(r->entropy_count > r->poolinfo->POOLBITS); /* Hold lock while accounting */ - spin_lock_irqsave(&r->lock, cpuflags); + spin_lock_irqsave(&r->lock, flags); - DEBUG_ENT("%04d %04d : trying to extract %d bits from %s\n", - random_state->entropy_count, - sec_random_state->entropy_count, + DEBUG_ENT("trying to extract %d bits from %s\n", nbytes * 8, r->name); - if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8) - nbytes = r->entropy_count / 8; + /* Can we pull enough? */ + if (r->entropy_count / 8 < min + reserved) { + nbytes = 0; + } else { + /* If limited, never pull more than available */ + if (r->limit && nbytes + reserved >= r->entropy_count / 8) + nbytes = r->entropy_count/8 - reserved; - if (r->entropy_count / 8 >= nbytes) - r->entropy_count -= nbytes*8; - else - r->entropy_count = 0; + if(r->entropy_count / 8 >= nbytes + reserved) + r->entropy_count -= nbytes*8; + else + r->entropy_count = reserved; + + if (r->entropy_count < random_write_wakeup_thresh) + wake_up_interruptible(&random_write_wait); + } + + DEBUG_ENT("debiting %d entropy credits from %s%s\n", + nbytes * 8, r->name, r->limit ? "" : " (unlimited)"); + + spin_unlock_irqrestore(&r->lock, flags); - if (r->entropy_count < random_write_wakeup_thresh) - wake_up_interruptible(&random_write_wait); + return nbytes; +} + +static void extract_buf(struct entropy_store *r, __u8 *out) +{ + int i, x; + __u32 data[16], buf[5 + SHA_WORKSPACE_WORDS]; - DEBUG_ENT("Debiting %d entropy credits from %s%s\n", - nbytes * 8, r->name, - flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)"); + sha_init(buf); + /* + * As we hash the pool, we mix intermediate values of + * the hash back into the pool. This eliminates + * backtracking attacks (where the attacker knows + * the state of the pool plus the current outputs, and + * attempts to find previous ouputs), unless the hash + * function can be inverted. + */ + for (i = 0, x = 0; i < r->poolinfo->poolwords; i += 16, x+=2) { + sha_transform(buf, (__u8 *)r->pool+i, buf + 5); + add_entropy_words(r, &buf[x % 5], 1); + } - spin_unlock_irqrestore(&r->lock, cpuflags); + /* + * To avoid duplicates, we atomically extract a + * portion of the pool while mixing, and hash one + * final time. + */ + __add_entropy_words(r, &buf[x % 5], 1, data); + sha_transform(buf, (__u8 *)data, buf + 5); + + /* + * In case the hash function has some recognizable + * output pattern, we fold it in half. + */ + + buf[0] ^= buf[3]; + buf[1] ^= buf[4]; + buf[0] ^= rol32(buf[3], 16); + memcpy(out, buf, EXTRACT_SIZE); + memset(buf, 0, sizeof(buf)); +} + +static ssize_t extract_entropy(struct entropy_store *r, void * buf, + size_t nbytes, int min, int reserved) +{ + ssize_t ret = 0, i; + __u8 tmp[EXTRACT_SIZE]; + + xfer_secondary_pool(r, nbytes); + nbytes = account(r, nbytes, min, reserved); - ret = 0; while (nbytes) { - /* - * Check if we need to break out or reschedule.... - */ - if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) { + extract_buf(r, tmp); + i = min_t(int, nbytes, EXTRACT_SIZE); + memcpy(buf, tmp, i); + nbytes -= i; + buf += i; + ret += i; + } + + /* Wipe data just returned from memory */ + memset(tmp, 0, sizeof(tmp)); + + return ret; +} + +static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf, + size_t nbytes) +{ + ssize_t ret = 0, i; + __u8 tmp[EXTRACT_SIZE]; + + xfer_secondary_pool(r, nbytes); + nbytes = account(r, nbytes, 0, 0); + + while (nbytes) { + if (need_resched()) { if (signal_pending(current)) { if (ret == 0) ret = -ERESTARTSYS; break; } - - DEBUG_ENT("%04d %04d : extract feeling sleepy (%d bytes left)\n", - random_state->entropy_count, - sec_random_state->entropy_count, nbytes); - schedule(); - - DEBUG_ENT("%04d %04d : extract woke up\n", - random_state->entropy_count, - sec_random_state->entropy_count); } - /* Hash the pool to get the output */ - tmp[0] = 0x67452301; - tmp[1] = 0xefcdab89; - tmp[2] = 0x98badcfe; - tmp[3] = 0x10325476; -#ifdef USE_SHA - tmp[4] = 0xc3d2e1f0; -#endif - /* - * As we hash the pool, we mix intermediate values of - * the hash back into the pool. This eliminates - * backtracking attacks (where the attacker knows - * the state of the pool plus the current outputs, and - * attempts to find previous ouputs), unless the hash - * function can be inverted. - */ - for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) { - HASH_TRANSFORM(tmp, r->pool+i); - add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1); + extract_buf(r, tmp); + i = min_t(int, nbytes, EXTRACT_SIZE); + if (copy_to_user(buf, tmp, i)) { + ret = -EFAULT; + break; } - - /* - * In case the hash function has some recognizable - * output pattern, we fold it in half. - */ - for (i = 0; i < HASH_BUFFER_SIZE/2; i++) - tmp[i] ^= tmp[i + (HASH_BUFFER_SIZE+1)/2]; -#if HASH_BUFFER_SIZE & 1 /* There's a middle word to deal with */ - x = tmp[HASH_BUFFER_SIZE/2]; - x ^= (x >> 16); /* Fold it in half */ - ((__u16 *)tmp)[HASH_BUFFER_SIZE-1] = (__u16)x; -#endif - - /* Copy data to destination buffer */ - i = min(nbytes, HASH_BUFFER_SIZE*sizeof(__u32)/2); - if (flags & EXTRACT_ENTROPY_USER) { - i -= copy_to_user(buf, (__u8 const *)tmp, i); - if (!i) { - ret = -EFAULT; - break; - } - } else - memcpy(buf, (__u8 const *)tmp, i); + nbytes -= i; buf += i; ret += i; @@ -1460,7 +852,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, /* Wipe data just returned from memory */ memset(tmp, 0, sizeof(tmp)); - + return ret; } @@ -1471,99 +863,48 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, */ void get_random_bytes(void *buf, int nbytes) { - struct entropy_store *r = urandom_state; - int flags = EXTRACT_ENTROPY_SECONDARY; - - if (!r) - r = sec_random_state; - if (!r) { - r = random_state; - flags = 0; - } - if (!r) { - printk(KERN_NOTICE "get_random_bytes called before " - "random driver initialization\n"); - return; - } - extract_entropy(r, (char *) buf, nbytes, flags); + extract_entropy(&nonblocking_pool, buf, nbytes, 0, 0); } EXPORT_SYMBOL(get_random_bytes); -/********************************************************************* - * - * Functions to interface with Linux - * - *********************************************************************/ - /* - * Initialize the random pool with standard stuff. + * init_std_data - initialize pool with system data * - * NOTE: This is an OS-dependent function. + * @r: pool to initialize + * + * This function clears the pool's entropy count and mixes some system + * data into the pool to prepare it for use. The pool is not cleared + * as that can only decrease the entropy in the pool. */ static void init_std_data(struct entropy_store *r) { - struct timeval tv; - __u32 words[2]; - char *p; - int i; + struct timeval tv; + unsigned long flags; - do_gettimeofday(&tv); - words[0] = tv.tv_sec; - words[1] = tv.tv_usec; - add_entropy_words(r, words, 2); + spin_lock_irqsave(&r->lock, flags); + r->entropy_count = 0; + spin_unlock_irqrestore(&r->lock, flags); - /* - * This doesn't lock system.utsname. However, we are generating - * entropy so a race with a name set here is fine. - */ - p = (char *) &system_utsname; - for (i = sizeof(system_utsname) / sizeof(words); i; i--) { - memcpy(words, p, sizeof(words)); - add_entropy_words(r, words, sizeof(words)/4); - p += sizeof(words); - } + do_gettimeofday(&tv); + add_entropy_words(r, (__u32 *)&tv, sizeof(tv)/4); + add_entropy_words(r, (__u32 *)&system_utsname, + sizeof(system_utsname)/4); } static int __init rand_initialize(void) { - int i; - - if (create_entropy_store(DEFAULT_POOL_SIZE, "primary", &random_state)) - goto err; - if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state)) - goto err; - if (create_entropy_store(SECONDARY_POOL_SIZE, "secondary", - &sec_random_state)) - goto err; - if (create_entropy_store(SECONDARY_POOL_SIZE, "urandom", - &urandom_state)) - goto err; - clear_entropy_store(random_state); - clear_entropy_store(sec_random_state); - clear_entropy_store(urandom_state); - init_std_data(random_state); - init_std_data(sec_random_state); - init_std_data(urandom_state); -#ifdef CONFIG_SYSCTL - sysctl_init_random(random_state); -#endif - for (i = 0; i < NR_IRQS; i++) - irq_timer_state[i] = NULL; - memset(&keyboard_timer_state, 0, sizeof(struct timer_rand_state)); - memset(&mouse_timer_state, 0, sizeof(struct timer_rand_state)); - memset(&extract_timer_state, 0, sizeof(struct timer_rand_state)); - extract_timer_state.dont_count_entropy = 1; + init_std_data(&input_pool); + init_std_data(&blocking_pool); + init_std_data(&nonblocking_pool); return 0; -err: - return -1; } module_init(rand_initialize); void rand_initialize_irq(int irq) { struct timer_rand_state *state; - + if (irq >= NR_IRQS || irq_timer_state[irq]) return; @@ -1577,11 +918,11 @@ void rand_initialize_irq(int irq) irq_timer_state[irq] = state; } } - + void rand_initialize_disk(struct gendisk *disk) { struct timer_rand_state *state; - + /* * If kmalloc returns null, we just won't use that entropy * source. @@ -1596,9 +937,8 @@ void rand_initialize_disk(struct gendisk *disk) static ssize_t random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) { - DECLARE_WAITQUEUE(wait, current); - ssize_t n, retval = 0, count = 0; - + ssize_t n, retval = 0, count = 0; + if (nbytes == 0) return 0; @@ -1607,20 +947,11 @@ random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) if (n > SEC_XFER_SIZE) n = SEC_XFER_SIZE; - DEBUG_ENT("%04d %04d : reading %d bits, p: %d s: %d\n", - random_state->entropy_count, - sec_random_state->entropy_count, - n*8, random_state->entropy_count, - sec_random_state->entropy_count); + DEBUG_ENT("reading %d bits\n", n*8); - n = extract_entropy(sec_random_state, buf, n, - EXTRACT_ENTROPY_USER | - EXTRACT_ENTROPY_LIMIT | - EXTRACT_ENTROPY_SECONDARY); + n = extract_entropy_user(&blocking_pool, buf, n); - DEBUG_ENT("%04d %04d : read got %d bits (%d still needed)\n", - random_state->entropy_count, - sec_random_state->entropy_count, + DEBUG_ENT("read got %d bits (%d still needed)\n", n*8, (nbytes-n)*8); if (n == 0) { @@ -1628,27 +959,19 @@ random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) retval = -EAGAIN; break; } - if (signal_pending(current)) { - retval = -ERESTARTSYS; - break; - } - DEBUG_ENT("%04d %04d : sleeping?\n", - random_state->entropy_count, - sec_random_state->entropy_count); + DEBUG_ENT("sleeping?\n"); - set_current_state(TASK_INTERRUPTIBLE); - add_wait_queue(&random_read_wait, &wait); + wait_event_interruptible(random_read_wait, + input_pool.entropy_count >= + random_read_wakeup_thresh); - if (sec_random_state->entropy_count / 8 == 0) - schedule(); + DEBUG_ENT("awake\n"); - set_current_state(TASK_RUNNING); - remove_wait_queue(&random_read_wait, &wait); - - DEBUG_ENT("%04d %04d : waking up\n", - random_state->entropy_count, - sec_random_state->entropy_count); + if (signal_pending(current)) { + retval = -ERESTARTSYS; + break; + } continue; } @@ -1669,7 +992,7 @@ random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) */ if (count) file_accessed(file); - + return (count ? count : retval); } @@ -1677,15 +1000,7 @@ static ssize_t urandom_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) { - int flags = EXTRACT_ENTROPY_USER; - unsigned long cpuflags; - - spin_lock_irqsave(&random_state->lock, cpuflags); - if (random_state->entropy_count > random_state->poolinfo.POOLBITS) - flags |= EXTRACT_ENTROPY_SECONDARY; - spin_unlock_irqrestore(&random_state->lock, cpuflags); - - return extract_entropy(urandom_state, buf, nbytes, flags); + return extract_entropy_user(&nonblocking_pool, buf, nbytes); } static unsigned int @@ -1696,9 +1011,9 @@ random_poll(struct file *file, poll_table * wait) poll_wait(file, &random_read_wait, wait); poll_wait(file, &random_write_wait, wait); mask = 0; - if (random_state->entropy_count >= random_read_wakeup_thresh) + if (input_pool.entropy_count >= random_read_wakeup_thresh) mask |= POLLIN | POLLRDNORM; - if (random_state->entropy_count < random_write_wakeup_thresh) + if (input_pool.entropy_count < random_write_wakeup_thresh) mask |= POLLOUT | POLLWRNORM; return mask; } @@ -1707,11 +1022,11 @@ static ssize_t random_write(struct file * file, const char __user * buffer, size_t count, loff_t *ppos) { - int ret = 0; - size_t bytes; - __u32 buf[16]; - const char __user *p = buffer; - size_t c = count; + int ret = 0; + size_t bytes; + __u32 buf[16]; + const char __user *p = buffer; + size_t c = count; while (c > 0) { bytes = min(c, sizeof(buf)); @@ -1724,13 +1039,14 @@ random_write(struct file * file, const char __user * buffer, c -= bytes; p += bytes; - add_entropy_words(random_state, buf, (bytes + 3) / 4); + add_entropy_words(&input_pool, buf, (bytes + 3) / 4); } if (p == buffer) { return (ssize_t)ret; } else { - file->f_dentry->d_inode->i_mtime = CURRENT_TIME; - mark_inode_dirty(file->f_dentry->d_inode); + struct inode *inode = file->f_dentry->d_inode; + inode->i_mtime = current_fs_time(inode->i_sb); + mark_inode_dirty(inode); return (ssize_t)(p - buffer); } } @@ -1742,10 +1058,10 @@ random_ioctl(struct inode * inode, struct file * file, int size, ent_count; int __user *p = (int __user *)arg; int retval; - + switch (cmd) { case RNDGETENTCNT: - ent_count = random_state->entropy_count; + ent_count = input_pool.entropy_count; if (put_user(ent_count, p)) return -EFAULT; return 0; @@ -1754,12 +1070,12 @@ random_ioctl(struct inode * inode, struct file * file, return -EPERM; if (get_user(ent_count, p)) return -EFAULT; - credit_entropy_store(random_state, ent_count); + credit_entropy_store(&input_pool, ent_count); /* * Wake up waiting processes if we have enough * entropy. */ - if (random_state->entropy_count >= random_read_wakeup_thresh) + if (input_pool.entropy_count >= random_read_wakeup_thresh) wake_up_interruptible(&random_read_wait); return 0; case RNDADDENTROPY: @@ -1775,25 +1091,22 @@ random_ioctl(struct inode * inode, struct file * file, size, &file->f_pos); if (retval < 0) return retval; - credit_entropy_store(random_state, ent_count); + credit_entropy_store(&input_pool, ent_count); /* * Wake up waiting processes if we have enough * entropy. */ - if (random_state->entropy_count >= random_read_wakeup_thresh) + if (input_pool.entropy_count >= random_read_wakeup_thresh) wake_up_interruptible(&random_read_wait); return 0; case RNDZAPENTCNT: - if (!capable(CAP_SYS_ADMIN)) - return -EPERM; - random_state->entropy_count = 0; - return 0; case RNDCLEARPOOL: - /* Clear the entropy pool and associated counters. */ + /* Clear the entropy pool counters. */ if (!capable(CAP_SYS_ADMIN)) return -EPERM; - clear_entropy_store(random_state); - init_std_data(random_state); + init_std_data(&input_pool); + init_std_data(&blocking_pool); + init_std_data(&nonblocking_pool); return 0; default: return -EINVAL; @@ -1801,22 +1114,22 @@ random_ioctl(struct inode * inode, struct file * file, } struct file_operations random_fops = { - .read = random_read, - .write = random_write, - .poll = random_poll, - .ioctl = random_ioctl, + .read = random_read, + .write = random_write, + .poll = random_poll, + .ioctl = random_ioctl, }; struct file_operations urandom_fops = { - .read = urandom_read, - .write = random_write, - .ioctl = random_ioctl, + .read = urandom_read, + .write = random_write, + .ioctl = random_ioctl, }; /*************************************************************** * Random UUID interface - * - * Used here for a Boot ID, but can be useful for other kernel + * + * Used here for a Boot ID, but can be useful for other kernel * drivers. ***************************************************************/ @@ -1844,91 +1157,25 @@ EXPORT_SYMBOL(generate_random_uuid); #include -static int sysctl_poolsize; -static int min_read_thresh, max_read_thresh; -static int min_write_thresh, max_write_thresh; +static int min_read_thresh = 8, min_write_thresh; +static int max_read_thresh = INPUT_POOL_WORDS * 32; +static int max_write_thresh = INPUT_POOL_WORDS * 32; static char sysctl_bootid[16]; -/* - * This function handles a request from the user to change the pool size - * of the primary entropy store. - */ -static int change_poolsize(int poolsize) -{ - struct entropy_store *new_store, *old_store; - int ret; - - if ((ret = create_entropy_store(poolsize, random_state->name, - &new_store))) - return ret; - - add_entropy_words(new_store, random_state->pool, - random_state->poolinfo.poolwords); - credit_entropy_store(new_store, random_state->entropy_count); - - sysctl_init_random(new_store); - old_store = random_state; - random_state = batch_work.data = new_store; - free_entropy_store(old_store); - return 0; -} - -static int proc_do_poolsize(ctl_table *table, int write, struct file *filp, - void __user *buffer, size_t *lenp, loff_t *ppos) -{ - int ret; - - sysctl_poolsize = random_state->poolinfo.POOLBYTES; - - ret = proc_dointvec(table, write, filp, buffer, lenp, ppos); - if (ret || !write || - (sysctl_poolsize == random_state->poolinfo.POOLBYTES)) - return ret; - - return change_poolsize(sysctl_poolsize); -} - -static int poolsize_strategy(ctl_table *table, int __user *name, int nlen, - void __user *oldval, size_t __user *oldlenp, - void __user *newval, size_t newlen, void **context) -{ - int len; - - sysctl_poolsize = random_state->poolinfo.POOLBYTES; - - /* - * We only handle the write case, since the read case gets - * handled by the default handler (and we don't care if the - * write case happens twice; it's harmless). - */ - if (newval && newlen) { - len = newlen; - if (len > table->maxlen) - len = table->maxlen; - if (copy_from_user(table->data, newval, len)) - return -EFAULT; - } - - if (sysctl_poolsize != random_state->poolinfo.POOLBYTES) - return change_poolsize(sysctl_poolsize); - - return 0; -} - /* * These functions is used to return both the bootid UUID, and random * UUID. The difference is in whether table->data is NULL; if it is, * then a new UUID is generated and returned to the user. - * + * * If the user accesses this via the proc interface, it will be returned - * as an ASCII string in the standard UUID format. If accesses via the + * as an ASCII string in the standard UUID format. If accesses via the * sysctl system call, it is returned as 16 bytes of binary data. */ static int proc_do_uuid(ctl_table *table, int write, struct file *filp, void __user *buffer, size_t *lenp, loff_t *ppos) { - ctl_table fake_table; - unsigned char buf[64], tmp_uuid[16], *uuid; + ctl_table fake_table = {0}; + unsigned char buf[64], tmp_uuid[16], *uuid; uuid = table->data; if (!uuid) { @@ -1954,8 +1201,8 @@ static int uuid_strategy(ctl_table *table, int __user *name, int nlen, void __user *oldval, size_t __user *oldlenp, void __user *newval, size_t newlen, void **context) { - unsigned char tmp_uuid[16], *uuid; - unsigned int len; + unsigned char tmp_uuid[16], *uuid; + unsigned int len; if (!oldval || !oldlenp) return 1; @@ -1980,15 +1227,15 @@ static int uuid_strategy(ctl_table *table, int __user *name, int nlen, return 1; } +static int sysctl_poolsize = INPUT_POOL_WORDS * 32; ctl_table random_table[] = { { - .ctl_name = RANDOM_POOLSIZE, + .ctl_name = RANDOM_POOLSIZE, .procname = "poolsize", .data = &sysctl_poolsize, .maxlen = sizeof(int), - .mode = 0644, - .proc_handler = &proc_do_poolsize, - .strategy = &poolsize_strategy, + .mode = 0444, + .proc_handler = &proc_dointvec, }, { .ctl_name = RANDOM_ENTROPY_COUNT, @@ -1996,6 +1243,7 @@ ctl_table random_table[] = { .maxlen = sizeof(int), .mode = 0444, .proc_handler = &proc_dointvec, + .data = &input_pool.entropy_count, }, { .ctl_name = RANDOM_READ_THRESH, @@ -2038,14 +1286,6 @@ ctl_table random_table[] = { }, { .ctl_name = 0 } }; - -static void sysctl_init_random(struct entropy_store *random_state) -{ - min_read_thresh = 8; - min_write_thresh = 0; - max_read_thresh = max_write_thresh = random_state->poolinfo.POOLBITS; - random_table[1].data = &random_state->entropy_count; -} #endif /* CONFIG_SYSCTL */ /******************************************************************** @@ -2079,57 +1319,16 @@ static void sysctl_init_random(struct entropy_store *random_state) * Rotation is separate from addition to prevent recomputation */ #define ROUND(f, a, b, c, d, x, s) \ - (a += f(b, c, d) + x, a = (a << s) | (a >> (32-s))) + (a += f(b, c, d) + x, a = (a << s) | (a >> (32 - s))) #define K1 0 #define K2 013240474631UL #define K3 015666365641UL -/* - * Basic cut-down MD4 transform. Returns only 32 bits of result. - */ -static __u32 halfMD4Transform (__u32 const buf[4], __u32 const in[8]) -{ - __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; - - /* Round 1 */ - ROUND(F, a, b, c, d, in[0] + K1, 3); - ROUND(F, d, a, b, c, in[1] + K1, 7); - ROUND(F, c, d, a, b, in[2] + K1, 11); - ROUND(F, b, c, d, a, in[3] + K1, 19); - ROUND(F, a, b, c, d, in[4] + K1, 3); - ROUND(F, d, a, b, c, in[5] + K1, 7); - ROUND(F, c, d, a, b, in[6] + K1, 11); - ROUND(F, b, c, d, a, in[7] + K1, 19); - - /* Round 2 */ - ROUND(G, a, b, c, d, in[1] + K2, 3); - ROUND(G, d, a, b, c, in[3] + K2, 5); - ROUND(G, c, d, a, b, in[5] + K2, 9); - ROUND(G, b, c, d, a, in[7] + K2, 13); - ROUND(G, a, b, c, d, in[0] + K2, 3); - ROUND(G, d, a, b, c, in[2] + K2, 5); - ROUND(G, c, d, a, b, in[4] + K2, 9); - ROUND(G, b, c, d, a, in[6] + K2, 13); - - /* Round 3 */ - ROUND(H, a, b, c, d, in[3] + K3, 3); - ROUND(H, d, a, b, c, in[7] + K3, 9); - ROUND(H, c, d, a, b, in[2] + K3, 11); - ROUND(H, b, c, d, a, in[6] + K3, 15); - ROUND(H, a, b, c, d, in[1] + K3, 3); - ROUND(H, d, a, b, c, in[5] + K3, 9); - ROUND(H, c, d, a, b, in[0] + K3, 11); - ROUND(H, b, c, d, a, in[4] + K3, 15); - - return buf[1] + b; /* "most hashed" word */ - /* Alternative: return sum of all words? */ -} - #if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE) static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12]) { - __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; + __u32 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; /* Round 1 */ ROUND(F, a, b, c, d, in[ 0] + K1, 3); @@ -2173,7 +1372,7 @@ static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12]) ROUND(H, c, d, a, b, in[ 4] + K3, 11); ROUND(H, b, c, d, a, in[ 8] + K3, 15); - return buf[1] + b; /* "most hashed" word */ + return buf[1] + b; /* "most hashed" word */ /* Alternative: return sum of all words? */ } #endif @@ -2187,7 +1386,7 @@ static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12]) #undef K3 /* This should not be decreased so low that ISNs wrap too fast. */ -#define REKEY_INTERVAL (300*HZ) +#define REKEY_INTERVAL (300 * HZ) /* * Bit layout of the tcp sequence numbers (before adding current time): * bit 24-31: increased after every key exchange @@ -2205,16 +1404,16 @@ static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12]) * * SMP cleanup and lock avoidance with poor man's RCU. * Manfred Spraul - * + * */ -#define COUNT_BITS 8 -#define COUNT_MASK ( (1<secret, sizeof(keyptr->secret)); - keyptr->count = (ip_cnt&COUNT_MASK)<count = (ip_cnt & COUNT_MASK) << HASH_BITS; smp_wmb(); ip_cnt++; schedule_delayed_work(&rekey_work, REKEY_INTERVAL); @@ -2248,7 +1447,7 @@ static void rekey_seq_generator(void *private_) static inline struct keydata *get_keyptr(void) { - struct keydata *keyptr = &ip_keydata[ip_cnt&1]; + struct keydata *keyptr = &ip_keydata[ip_cnt & 1]; smp_rmb(); @@ -2266,43 +1465,67 @@ late_initcall(seqgen_init); __u32 secure_tcpv6_sequence_number(__u32 *saddr, __u32 *daddr, __u16 sport, __u16 dport) { - struct timeval tv; - __u32 seq; - __u32 hash[12]; + struct timeval tv; + __u32 seq; + __u32 hash[12]; struct keydata *keyptr = get_keyptr(); /* The procedure is the same as for IPv4, but addresses are longer. * Thus we must use twothirdsMD4Transform. */ - memcpy(hash, saddr, 16); hash[4]=(sport << 16) + dport; - memcpy(&hash[5],keyptr->secret,sizeof(__u32)*7); + memcpy(&hash[5],keyptr->secret,sizeof(__u32) * 7); seq = twothirdsMD4Transform(daddr, hash) & HASH_MASK; seq += keyptr->count; do_gettimeofday(&tv); - seq += tv.tv_usec + tv.tv_sec*1000000; + seq += tv.tv_usec + tv.tv_sec * 1000000; return seq; } EXPORT_SYMBOL(secure_tcpv6_sequence_number); #endif +/* The code below is shamelessly stolen from secure_tcp_sequence_number(). + * All blames to Andrey V. Savochkin . + */ +__u32 secure_ip_id(__u32 daddr) +{ + struct keydata *keyptr; + __u32 hash[4]; + + keyptr = get_keyptr(); + + /* + * Pick a unique starting offset for each IP destination. + * The dest ip address is placed in the starting vector, + * which is then hashed with random data. + */ + hash[0] = daddr; + hash[1] = keyptr->secret[9]; + hash[2] = keyptr->secret[10]; + hash[3] = keyptr->secret[11]; + + return half_md4_transform(hash, keyptr->secret); +} + +#ifdef CONFIG_INET + __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr, __u16 sport, __u16 dport) { - struct timeval tv; - __u32 seq; - __u32 hash[4]; + struct timeval tv; + __u32 seq; + __u32 hash[4]; struct keydata *keyptr = get_keyptr(); /* * Pick a unique starting offset for each TCP connection endpoints * (saddr, daddr, sport, dport). - * Note that the words are placed into the starting vector, which is + * Note that the words are placed into the starting vector, which is * then mixed with a partial MD4 over random data. */ hash[0]=saddr; @@ -2310,7 +1533,7 @@ __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr, hash[2]=(sport << 16) + dport; hash[3]=keyptr->secret[11]; - seq = halfMD4Transform(hash, keyptr->secret) & HASH_MASK; + seq = half_md4_transform(hash, keyptr->secret) & HASH_MASK; seq += keyptr->count; /* * As close as possible to RFC 793, which @@ -2321,7 +1544,7 @@ __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr, * (Networks are faster now - should this be increased?) */ do_gettimeofday(&tv); - seq += tv.tv_usec + tv.tv_sec*1000000; + seq += tv.tv_usec + tv.tv_sec * 1000000; #if 0 printk("init_seq(%lx, %lx, %d, %d) = %d\n", saddr, daddr, sport, dport, seq); @@ -2331,125 +1554,112 @@ __u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr, EXPORT_SYMBOL(secure_tcp_sequence_number); -/* The code below is shamelessly stolen from secure_tcp_sequence_number(). - * All blames to Andrey V. Savochkin . - */ -__u32 secure_ip_id(__u32 daddr) +/* Generate secure starting point for ephemeral IPV4 transport port search */ +u32 secure_ipv4_port_ephemeral(__u32 saddr, __u32 daddr, __u16 dport) { - struct keydata *keyptr; - __u32 hash[4]; - - keyptr = get_keyptr(); + struct keydata *keyptr = get_keyptr(); + u32 hash[4]; /* - * Pick a unique starting offset for each IP destination. - * The dest ip address is placed in the starting vector, - * which is then hashed with random data. + * Pick a unique starting offset for each ephemeral port search + * (saddr, daddr, dport) and 48bits of random data. */ - hash[0] = daddr; - hash[1] = keyptr->secret[9]; - hash[2] = keyptr->secret[10]; + hash[0] = saddr; + hash[1] = daddr; + hash[2] = dport ^ keyptr->secret[10]; hash[3] = keyptr->secret[11]; - return halfMD4Transform(hash, keyptr->secret); + return half_md4_transform(hash, keyptr->secret); } -#ifdef CONFIG_SYN_COOKIES -/* - * Secure SYN cookie computation. This is the algorithm worked out by - * Dan Bernstein and Eric Schenk. - * - * For linux I implement the 1 minute counter by looking at the jiffies clock. - * The count is passed in as a parameter, so this code doesn't much care. - */ +#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE) +u32 secure_ipv6_port_ephemeral(const __u32 *saddr, const __u32 *daddr, __u16 dport) +{ + struct keydata *keyptr = get_keyptr(); + u32 hash[12]; -#define COOKIEBITS 24 /* Upper bits store count */ -#define COOKIEMASK (((__u32)1 << COOKIEBITS) - 1) + memcpy(hash, saddr, 16); + hash[4] = dport; + memcpy(&hash[5],keyptr->secret,sizeof(__u32) * 7); -static int syncookie_init; -static __u32 syncookie_secret[2][16-3+HASH_BUFFER_SIZE]; + return twothirdsMD4Transform(daddr, hash); +} +#endif -__u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport, - __u16 dport, __u32 sseq, __u32 count, __u32 data) +#if defined(CONFIG_IP_DCCP) || defined(CONFIG_IP_DCCP_MODULE) +/* Similar to secure_tcp_sequence_number but generate a 48 bit value + * bit's 32-47 increase every key exchange + * 0-31 hash(source, dest) + */ +u64 secure_dccp_sequence_number(__u32 saddr, __u32 daddr, + __u16 sport, __u16 dport) { - __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; - __u32 seq; + struct timeval tv; + u64 seq; + __u32 hash[4]; + struct keydata *keyptr = get_keyptr(); - /* - * Pick two random secrets the first time we need a cookie. - */ - if (syncookie_init == 0) { - get_random_bytes(syncookie_secret, sizeof(syncookie_secret)); - syncookie_init = 1; - } + hash[0] = saddr; + hash[1] = daddr; + hash[2] = (sport << 16) + dport; + hash[3] = keyptr->secret[11]; + + seq = half_md4_transform(hash, keyptr->secret); + seq |= ((u64)keyptr->count) << (32 - HASH_BITS); + + do_gettimeofday(&tv); + seq += tv.tv_usec + tv.tv_sec * 1000000; + seq &= (1ull << 48) - 1; +#if 0 + printk("dccp init_seq(%lx, %lx, %d, %d) = %d\n", + saddr, daddr, sport, dport, seq); +#endif + return seq; +} + +EXPORT_SYMBOL(secure_dccp_sequence_number); +#endif + +#endif /* CONFIG_INET */ + + +/* + * Get a random word for internal kernel use only. Similar to urandom but + * with the goal of minimal entropy pool depletion. As a result, the random + * value is not cryptographically secure but for several uses the cost of + * depleting entropy is too high + */ +unsigned int get_random_int(void) +{ + unsigned int val = 0; +#ifdef CONFIG_X86_HAS_TSC + rdtscl(val); +#endif /* - * Compute the secure sequence number. - * The output should be: - * HASH(sec1,saddr,sport,daddr,dport,sec1) + sseq + (count * 2^24) - * + (HASH(sec2,saddr,sport,daddr,dport,count,sec2) % 2^24). - * Where sseq is their sequence number and count increases every - * minute by 1. - * As an extra hack, we add a small "data" value that encodes the - * MSS into the second hash value. + * Use IP's RNG. It suits our purpose perfectly: it re-keys itself + * every second, from the entropy pool (and thus creates a limited + * drain on it), and uses halfMD4Transform within the second. We + * also mix it with jiffies and the PID: */ - - memcpy(tmp+3, syncookie_secret[0], sizeof(syncookie_secret[0])); - tmp[0]=saddr; - tmp[1]=daddr; - tmp[2]=(sport << 16) + dport; - HASH_TRANSFORM(tmp+16, tmp); - seq = tmp[17] + sseq + (count << COOKIEBITS); - - memcpy(tmp+3, syncookie_secret[1], sizeof(syncookie_secret[1])); - tmp[0]=saddr; - tmp[1]=daddr; - tmp[2]=(sport << 16) + dport; - tmp[3] = count; /* minute counter */ - HASH_TRANSFORM(tmp+16, tmp); - - /* Add in the second hash and the data */ - return seq + ((tmp[17] + data) & COOKIEMASK); + return secure_ip_id(current->pid + jiffies + (int)val); } /* - * This retrieves the small "data" value from the syncookie. - * If the syncookie is bad, the data returned will be out of - * range. This must be checked by the caller. + * randomize_range() returns a start address such that + * + * [...... .....] + * start end * - * The count value used to generate the cookie must be within - * "maxdiff" if the current (passed-in) "count". The return value - * is (__u32)-1 if this test fails. + * a with size "len" starting at the return value is inside in the + * area defined by [start, end], but is otherwise randomized. */ -__u32 check_tcp_syn_cookie(__u32 cookie, __u32 saddr, __u32 daddr, __u16 sport, - __u16 dport, __u32 sseq, __u32 count, __u32 maxdiff) +unsigned long +randomize_range(unsigned long start, unsigned long end, unsigned long len) { - __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; - __u32 diff; - - if (syncookie_init == 0) - return (__u32)-1; /* Well, duh! */ - - /* Strip away the layers from the cookie */ - memcpy(tmp+3, syncookie_secret[0], sizeof(syncookie_secret[0])); - tmp[0]=saddr; - tmp[1]=daddr; - tmp[2]=(sport << 16) + dport; - HASH_TRANSFORM(tmp+16, tmp); - cookie -= tmp[17] + sseq; - /* Cookie is now reduced to (count * 2^24) ^ (hash % 2^24) */ - - diff = (count - (cookie >> COOKIEBITS)) & ((__u32)-1 >> COOKIEBITS); - if (diff >= maxdiff) - return (__u32)-1; - - memcpy(tmp+3, syncookie_secret[1], sizeof(syncookie_secret[1])); - tmp[0] = saddr; - tmp[1] = daddr; - tmp[2] = (sport << 16) + dport; - tmp[3] = count - diff; /* minute counter */ - HASH_TRANSFORM(tmp+16, tmp); - - return (cookie - tmp[17]) & COOKIEMASK; /* Leaving the data behind */ + unsigned long range = end - len - start; + + if (end <= start + len) + return 0; + return PAGE_ALIGN(get_random_int() % range + start); } -#endif