X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=drivers%2Fchar%2Frandom.c;h=0fcbfa3a77dfc6c9f9f65c95d0f47785ebc1dd8c;hb=6a77f38946aaee1cd85eeec6cf4229b204c15071;hp=295e3f718b5c4dc3e1b8a02c13c8c19ea4164fe5;hpb=87fc8d1bb10cd459024a742c6a10961fefcef18f;p=linux-2.6.git diff --git a/drivers/char/random.c b/drivers/char/random.c index 295e3f718..0fcbfa3a7 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -2,7 +2,7 @@ * random.c -- A strong random number generator * * Version 1.89, last modified 19-Sep-99 - * + * * 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,17 @@ * 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. @@ -299,8 +292,8 @@ 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^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1 -- 115 */ { 2048, 1638, 1231, 819, 411, 1 }, @@ -353,12 +346,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 @@ -390,7 +383,7 @@ static struct poolinfo { * Linux 2.2 compatibility */ #ifndef DECLARE_WAITQUEUE -#define DECLARE_WAITQUEUE(WAIT, PTR) struct wait_queue WAIT = { PTR, NULL } +#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 @@ -416,7 +409,7 @@ static void sysctl_init_random(struct entropy_store *random_state); * * Utility functions, with some ASM defined functions for speed * purposes - * + * *****************************************************************/ /* @@ -428,7 +421,6 @@ static void sysctl_init_random(struct entropy_store *random_state); 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) @@ -442,9 +434,9 @@ static inline __u32 rotate_left(int i, __u32 word) /* * More asm magic.... - * + * * For entropy estimation, we need to do an integral base 2 - * logarithm. + * logarithm. * * Note the "12bits" suffix - this is used for numbers between * 0 and 4095 only. This allows a few shortcuts. @@ -453,7 +445,7 @@ static inline __u32 rotate_left(int i, __u32 word) static inline __u32 int_ln_12bits(__u32 word) { __u32 nbits = 0; - + while (word >>= 1) nbits++; return nbits; @@ -478,7 +470,15 @@ static inline __u32 int_ln_12bits(__u32 word) #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,\ + random_state->entropy_count,\ + sec_random_state->entropy_count,\ + urandom_state->entropy_count,\ + ## arg); } while (0) #else #define DEBUG_ENT(fmt, arg...) do {} while (0) #endif @@ -487,20 +487,20 @@ 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 { /* mostly-read data: */ struct poolinfo poolinfo; - __u32 *pool; - const char *name; + __u32 *pool; + const char *name; /* 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; }; /* @@ -512,9 +512,9 @@ struct entropy_store { static int create_entropy_store(int size, const char *name, struct entropy_store **ret_bucket) { - struct entropy_store *r; - struct poolinfo *p; - int poolwords; + struct entropy_store *r; + struct poolinfo *p; + int poolwords; poolwords = (size + 3) / 4; /* Convert bytes->words */ /* The pool size must be a multiple of 16 32-bit words */ @@ -540,7 +540,7 @@ static int create_entropy_store(int size, const char *name, return -ENOMEM; } memset(r->pool, 0, POOLBYTES); - r->lock = SPIN_LOCK_UNLOCKED; + spin_lock_init(&r->lock); r->name = name; *ret_bucket = r; return 0; @@ -554,29 +554,22 @@ static void clear_entropy_store(struct entropy_store *r) 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; @@ -626,9 +619,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 */ @@ -647,8 +653,8 @@ static void credit_entropy_store(struct entropy_store *r, int nbits) } 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); @@ -668,10 +674,10 @@ struct sample { }; 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_head, batch_tail; +static DEFINE_SPINLOCK(batch_lock); -static int batch_max; +static int batch_max; static void batch_entropy_process(void *private_); static DECLARE_WORK(batch_work, batch_entropy_process, NULL); @@ -698,7 +704,7 @@ static int __init batch_entropy_init(int size, struct entropy_store *r) * 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) +static void batch_entropy_store(u32 a, u32 b, int num) { int new; unsigned long flags; @@ -712,25 +718,18 @@ void batch_entropy_store(u32 a, u32 b, int num) 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: - */ + if (((batch_head - batch_tail) & (batch_max - 1)) >= (batch_max / 2)) schedule_delayed_work(&batch_work, 1); - } - new = (batch_head+1) & (batch_max-1); - if (new == batch_tail) { + new = (batch_head + 1) & (batch_max - 1); + if (new == batch_tail) DEBUG_ENT("batch entropy buffer full\n"); - } else { + 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 @@ -750,7 +749,7 @@ static void batch_entropy_process(void *private_) spin_lock_irq(&batch_lock); memcpy(batch_entropy_copy, batch_entropy_pool, - batch_max*sizeof(struct sample)); + batch_max * sizeof(struct sample)); head = batch_head; tail = batch_tail; @@ -761,13 +760,13 @@ static void batch_entropy_process(void *private_) p = r; while (head != tail) { if (r->entropy_count >= max_entropy) { - r = (r == sec_random_state) ? random_state : - sec_random_state; + 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); + tail = (tail + 1) & (batch_max - 1); } if (p->entropy_count >= random_read_wakeup_thresh) wake_up_interruptible(&random_read_wait); @@ -781,13 +780,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 input_timer_state; static struct timer_rand_state extract_timer_state; static struct timer_rand_state *irq_timer_state[NR_IRQS]; @@ -803,33 +801,23 @@ 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; + cycles_t data; + long delta, delta2, delta3, time; + int entropy = 0; 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 (random_state->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; - } - /* * 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. */ + time = jiffies; + if (!state->dont_count_entropy) { delta = time - state->last_time; state->last_time = time; @@ -861,46 +849,55 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num) entropy = int_ln_12bits(delta); } - batch_entropy_store(num, time, entropy); + + /* + * Use get_cycles() if implemented, otherwise fall back to + * jiffies. + */ + data = get_cycles(); + if (data) + num ^= (u32)((data >> 31) >> 1); + else + data = time; + + batch_entropy_store(num, data, entropy); out: preempt_enable(); } -void add_keyboard_randomness(unsigned char scancode) +extern 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)); + DEBUG_ENT("disk event %d:%d\n", disk->major, disk->first_minor); + + add_timer_randomness(disk->random, + 0x100 + MKDEV(disk->major, disk->first_minor)); } EXPORT_SYMBOL(add_disk_randomness); @@ -915,7 +912,7 @@ EXPORT_SYMBOL(add_disk_randomness); * 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 @@ -930,7 +927,7 @@ EXPORT_SYMBOL(add_disk_randomness); * 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. @@ -952,9 +949,9 @@ EXPORT_SYMBOL(add_disk_randomness); /* The SHA f()-functions. */ -#define f1(x,y,z) ( z ^ (x & (y^z)) ) /* Rounds 0-19: x ? y : z */ +#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 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 */ @@ -964,199 +961,198 @@ EXPORT_SYMBOL(add_disk_randomness); #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 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 ) ) - + (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; + __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. */ + /* + * 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; + /* + * 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; } - 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; - } + 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 ] ); - } + 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 ] ); + 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; + /* 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 @@ -1167,18 +1163,18 @@ static void SHATransform(__u32 digest[85], __u32 const data[16]) #undef f2 #undef f3 #undef f4 -#undef K1 +#undef K1 #undef K2 -#undef K3 -#undef K4 +#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 @@ -1194,7 +1190,7 @@ static void SHATransform(__u32 digest[85], __u32 const data[16]) /* 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 ) + (w += f(x, y, z) + data, w = w << s | w >> (32 - s), w += x ) /* * The core of the MD5 algorithm, this alters an existing MD5 hash to @@ -1320,15 +1316,13 @@ static inline void xfer_secondary_pool(struct entropy_store *r, int bytes = max_t(int, random_read_wakeup_thresh / 8, min_t(int, nbytes, TMP_BUF_SIZE)); - 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); + add_entropy_words(r, tmp, (bytes + 3) / 4); credit_entropy_store(r, bytes*8); } } @@ -1350,11 +1344,10 @@ 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 tmp[TMP_BUF_SIZE], data[16]; __u32 x; unsigned long cpuflags; - /* Redundant, but just in case... */ if (r->entropy_count > r->poolinfo.POOLBITS) r->entropy_count = r->poolinfo.POOLBITS; @@ -1365,9 +1358,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, /* Hold lock while accounting */ spin_lock_irqsave(&r->lock, cpuflags); - 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) @@ -1381,7 +1372,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, if (r->entropy_count < random_write_wakeup_thresh) wake_up_interruptible(&random_write_wait); - DEBUG_ENT("Debiting %d entropy credits from %s%s\n", + DEBUG_ENT("debiting %d entropy credits from %s%s\n", nbytes * 8, r->name, flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)"); @@ -1399,15 +1390,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, 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 */ @@ -1430,7 +1413,15 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, HASH_TRANSFORM(tmp, r->pool+i); add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1); } - + + /* + * To avoid duplicates, we atomically extract a + * portion of the pool while mixing, and hash one + * final time. + */ + __add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1, data); + HASH_TRANSFORM(tmp, data); + /* * In case the hash function has some recognizable * output pattern, we fold it in half. @@ -1442,7 +1433,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, 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) { @@ -1453,6 +1444,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void * buf, } } else memcpy(buf, (__u8 const *)tmp, i); + nbytes -= i; buf += i; ret += i; @@ -1460,7 +1452,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; } @@ -1503,10 +1495,10 @@ EXPORT_SYMBOL(get_random_bytes); */ static void init_std_data(struct entropy_store *r) { - struct timeval tv; - __u32 words[2]; - char *p; - int i; + struct timeval tv; + __u32 words[2]; + char *p; + int i; do_gettimeofday(&tv); words[0] = tv.tv_sec; @@ -1550,8 +1542,7 @@ static int __init rand_initialize(void) #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(&input_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; return 0; @@ -1563,7 +1554,7 @@ 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 +1568,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. @@ -1597,8 +1588,8 @@ 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 +1598,14 @@ 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); - 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) { @@ -1633,10 +1618,6 @@ random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) break; } - DEBUG_ENT("%04d %04d : sleeping?\n", - random_state->entropy_count, - sec_random_state->entropy_count); - set_current_state(TASK_INTERRUPTIBLE); add_wait_queue(&random_read_wait, &wait); @@ -1646,10 +1627,6 @@ random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) 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); - continue; } @@ -1669,7 +1646,7 @@ random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos) */ if (count) file_accessed(file); - + return (count ? count : retval); } @@ -1707,11 +1684,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)); @@ -1729,8 +1706,9 @@ random_write(struct file * file, const char __user * buffer, 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,7 +1720,7 @@ 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; @@ -1801,22 +1779,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 +1822,24 @@ 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 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; + unsigned char buf[64], tmp_uuid[16], *uuid; uuid = table->data; if (!uuid) { @@ -1954,8 +1865,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 +1891,15 @@ static int uuid_strategy(ctl_table *table, int __user *name, int nlen, return 1; } +static int sysctl_poolsize = DEFAULT_POOL_SIZE; 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, @@ -2054,6 +1965,7 @@ static void sysctl_init_random(struct entropy_store *random_state) * ********************************************************************/ +#ifdef CONFIG_INET /* * TCP initial sequence number picking. This uses the random number * generator to pick an initial secret value. This value is hashed @@ -2079,7 +1991,7 @@ 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 @@ -2089,7 +2001,7 @@ static void sysctl_init_random(struct entropy_store *random_state) */ static __u32 halfMD4Transform (__u32 const buf[4], __u32 const in[8]) { - __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); @@ -2129,7 +2041,7 @@ static __u32 halfMD4Transform (__u32 const buf[4], __u32 const in[8]) 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 +2085,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 +2099,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 +2117,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 +2160,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,25 +2178,24 @@ 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; } @@ -2294,15 +2205,15 @@ EXPORT_SYMBOL(secure_tcpv6_sequence_number); __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; @@ -2321,7 +2232,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); @@ -2354,6 +2265,24 @@ __u32 secure_ip_id(__u32 daddr) return halfMD4Transform(hash, keyptr->secret); } +/* Generate secure starting point for ephemeral TCP port search */ +u32 secure_tcp_port_ephemeral(__u32 saddr, __u32 daddr, __u16 dport) +{ + struct keydata *keyptr = get_keyptr(); + u32 hash[4]; + + /* + * Pick a unique starting offset for each ephemeral port search + * (saddr, daddr, dport) and 48bits of random data. + */ + hash[0] = saddr; + hash[1] = daddr; + hash[2] = dport ^ keyptr->secret[10]; + hash[3] = keyptr->secret[11]; + + return halfMD4Transform(hash, keyptr->secret); +} + #ifdef CONFIG_SYN_COOKIES /* * Secure SYN cookie computation. This is the algorithm worked out by @@ -2366,14 +2295,14 @@ __u32 secure_ip_id(__u32 daddr) #define COOKIEBITS 24 /* Upper bits store count */ #define COOKIEMASK (((__u32)1 << COOKIEBITS) - 1) -static int syncookie_init; -static __u32 syncookie_secret[2][16-3+HASH_BUFFER_SIZE]; +static int syncookie_init; +static __u32 syncookie_secret[2][16-3+HASH_BUFFER_SIZE]; __u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport, __u16 dport, __u32 sseq, __u32 count, __u32 data) { - __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; - __u32 seq; + __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; + __u32 seq; /* * Pick two random secrets the first time we need a cookie. @@ -2394,19 +2323,19 @@ __u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport, * MSS into the second hash value. */ - memcpy(tmp+3, syncookie_secret[0], sizeof(syncookie_secret[0])); + 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])); + 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); + HASH_TRANSFORM(tmp + 16, tmp); /* Add in the second hash and the data */ return seq + ((tmp[17] + data) & COOKIEMASK); @@ -2424,18 +2353,18 @@ __u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport, __u32 check_tcp_syn_cookie(__u32 cookie, __u32 saddr, __u32 daddr, __u16 sport, __u16 dport, __u32 sseq, __u32 count, __u32 maxdiff) { - __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; - __u32 diff; + __u32 tmp[16 + HASH_BUFFER_SIZE + HASH_EXTRA_SIZE]; + __u32 diff; if (syncookie_init == 0) - return (__u32)-1; /* Well, duh! */ + return (__u32)-1; /* Well, duh! */ /* Strip away the layers from the cookie */ - memcpy(tmp+3, syncookie_secret[0], sizeof(syncookie_secret[0])); + 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); + HASH_TRANSFORM(tmp + 16, tmp); cookie -= tmp[17] + sseq; /* Cookie is now reduced to (count * 2^24) ^ (hash % 2^24) */ @@ -2448,8 +2377,9 @@ __u32 check_tcp_syn_cookie(__u32 cookie, __u32 saddr, __u32 daddr, __u16 sport, tmp[1] = daddr; tmp[2] = (sport << 16) + dport; tmp[3] = count - diff; /* minute counter */ - HASH_TRANSFORM(tmp+16, tmp); + HASH_TRANSFORM(tmp + 16, tmp); return (cookie - tmp[17]) & COOKIEMASK; /* Leaving the data behind */ } #endif +#endif /* CONFIG_INET */