/*
` * random.c -- A strong random number generator
` *
` * Version 1.00, last modified 26-May-96
` *
` * Copyright Theodore Ts'o, 1994, 1995, 1996. All rights reserved.
` *
` * Redistribution and use in source and binary forms, with or without
` * modification, are permitted provided that the following conditions
` * are met:
` * 1. Redistributions of source code must retain the above copyright
` * notice, and the entire permission notice in its entirety,
` * including the disclaimer of warranties.
` * 2. Redistributions in binary form must reproduce the above copyright
` * notice, this list of conditions and the following disclaimer in the
` * documentation and/or other materials provided with the distribution.
` * 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 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 ARE
` * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
` * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
` * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
` * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
` * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
` * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
` * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
` * OF THE POSSIBILITY OF SUCH DAMAGE.
` */
`
`/*
` * (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
` * for seeding TCP sequence numbers, and other places where it is
` * desirable to have numbers which are not only random, but hard to
` * predict by an attacker.
` *
` * 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
` * algorithm. Unfortunately, it is very easy for attackers to guess
` * the sequence of pseudo-random number generators, and for some
` * applications this is not acceptable. So instead, we must try to
` * gather "environmental noise" from the computer's environment, which
` * 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
`
`1
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 1
`
`

`
` * timings, inter-interrupt timings from some interrupts, and other
` * events which are both (a) non-deterministic and (b) hard for an
` * outside observer to measure. Randomness from these sources are
` * added to an "entropy pool", which is mixed using a CRC-like function.
` * This is not cryptographically strong, but it is adequate assuming
` * the randomness is not chosen maliciously, and it is fast enough that
` * the overhead of doing it on every interrupt is very reasonable.
` * 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 MD5
` * hash of the contents of the "entropy pool". The MD5 hash avoids
` * exposing the internal state of the entropy pool. It is believed to
` * be computationally infeasible to derive any useful information
` * about the input of MD5 from its output. Even if it is possible to
` * analyze MD5 in some clever way, as long as the amount of data
` * returned from the generator is less than the inherent entropy in
` * the pool, the output data is totally unpredictable. For this
` * 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
` * outputs. This requires successful cryptanalysis of MD5, which is
` * 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:
` *
` *
` *
` * 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,
` * this will result in random numbers that are merely cryptographically
` * strong. For many applications, however, this is acceptable.
` *
` * 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_interrupt_randomness(int irq);
`
`void get_random_bytes(void *buf, int nbytes);
`
`2
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 2
`
`

`
`void add_blkdev_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_interrupt_randomness() uses the inter-interrupt timing as random
` * inputs to the entropy pool. Note that not all interrupts are good
` * sources of randomness! For example, the timer interrupts is not a
` * good choice, because the periodicity of the interrupts is to
` * regular, and hence predictable to an attacker. Disk interrupts are
` * a better measure, since the timing of the disk interrupts are more
` * unpredictable.
` *
` * add_blkdev_randomness() times the finishing time of block requests.
` *
` * 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.
` * This reduces the actual number of bits of unpredictability in the
` * entropy pool below the value in entropy_count. In order to
` * 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:
` *
` *
` *
` *
` *
` *
` *
` *
` *
` * and the following lines in an appropriate script which is run as
` * the system is shutdown:
` *
` *
` *
` *
` *
` *
` * For example, on many Linux systems, the appropriate scripts are
` * usually /etc/rc.d/rc.local and /etc/rc.d/rc.0, respectively.
` *
` * 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
` * make sure that /etc/random-seed is different for every start-up,
` * even if the system crashes without executing rc.0.) Even with
` * complete knowledge of the start-up activities, predicting the state
` * of the entropy pool requires knowledge of the previous history of
` * the system.
` *
` * Configuring the /dev/random driver under Linux
`
`echo "Initializing random number generator..."
`# Carry a random seed from start-up to start-up
`# Load and then save 512 bytes, which is the size of the entropy pool
`if [ -f /etc/random-seed ]; then
`cat /etc/random-seed >/dev/urandom
`
`fi
`dd if=/dev/urandom of=/etc/random-seed count=1
`
`# Carry a random seed from shut-down to start-up
`# Save 512 bytes, which is the size of the entropy pool
`echo "Saving random seed..."
`dd if=/dev/urandom of=/etc/random-seed count=1
`
`3
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 3
`
`

`
`mknod /dev/random c 1 8
`mknod /dev/urandom c 1 9
`
` * ==============================================
` *
` * The /dev/random driver under Linux uses minor numbers 8 and 9 of
` * the /dev/mem major number (#1). So if your system does not have
` * /dev/random and /dev/urandom created already, they can be created
` * by using the commands:
` *
` *
` *
` *
` * Acknowledgements:
` * =================
` *
` * Ideas for constructing this random number generator were derived
` * from the Pretty Good Privacy's random number generator, and from
` * private discussions with Phil Karn. Colin Plumb provided a faster
` * random number generator, which speed up the mixing function of the
` * entropy pool, taken from PGP 3.0 (under development). It has since
` * been modified by myself to provide better mixing in the case where
` * the input values to add_entropy_word() are mostly small numbers.
` * 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 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.
` */
`
`#include <linux/config.h> /* CONFIG_RST_COOKIES and CONFIG_SYN_COOKIES */
`#include <linux/utsname.h>
`#include <linux/kernel.h>
`#include <linux/major.h>
`#include <linux/string.h>
`#include <linux/fcntl.h>
`#include <linux/malloc.h>
`#include <linux/random.h>
`
`#include <asm/segment.h>
`#include <asm/irq.h>
`#include <asm/io.h>
`
`/*
` * Configuration information
` */
`#undef RANDOM_BENCHMARK
`#undef BENCHMARK_NOINT
`
`/*
` * The pool is stirred with a primitive polynomial of degree 128
` * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
` * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
` */
`#define POOLWORDS 128 /* Power of 2 - note that this is 32-bit words */
`#define POOLBITS (POOLWORDS*32)
`#if POOLWORDS == 128
`#define TAP1 99 /* The polynomial taps */
`
`4
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 4
`
`

`
`#define TAP2 59
`#define TAP3 31
`#define TAP4 9
`#define TAP5 7
`#elif POOLWORDS == 64
`#define TAP1 62 /* The polynomial taps */
`#define TAP2 38
`#define TAP3 10
`#define TAP4 6
`#define TAP5 1
`#else
`#error No primitive polynomial available for chosen POOLWORDS
`#endif
`
`/*
` * The minimum number of bits to release a "wait on input". Should
` * probably always be 8, since a /dev/random read can return a single
` * byte.
` */
`#define WAIT_INPUT_BITS 8
`/*
` * The limit number of bits under which to release a "wait on
` * output". Should probably always be the same as WAIT_INPUT_BITS, so
` * that an output wait releases when and only when a wait on input
` * would block.
` */
`#define WAIT_OUTPUT_BITS WAIT_INPUT_BITS
`
`/* There is actually only one of these, globally. */
`struct random_bucket {
`unsigned add_ptr;
`unsigned entropy_count;
`int input_rotate;
`__u32 *pool;
`
`};
`
`#ifdef RANDOM_BENCHMARK
`/* For benchmarking only */
`struct random_benchmark {
`unsigned long long start_time;
`int
`times;
`unsigned long
`min;
`unsigned long
`max;
`unsigned long
`accum;
`const char
`*descr;
`int
`unit;
`unsigned long
`flags;
`
`};
`
`#define BENCHMARK_INTERVAL 500
`
`/* # of samples */
`
`/* accumulator for average */
`
`static void initialize_benchmark(struct random_benchmark *bench,
` const char *descr, int unit);
`static void begin_benchmark(struct random_benchmark *bench);
`static void end_benchmark(struct random_benchmark *bench);
`
`struct random_benchmark timer_benchmark;
`#endif
`
`/* There is one of these per entropy source */
`struct timer_rand_state {
`unsigned long last_time;
`int
`last_delta,last_delta2;
`int
`dont_count_entropy:1;
`
`5
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 5
`
`

`
`};
`
`static struct random_bucket random_state;
`static __u32 random_pool[POOLWORDS];
`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 *irq_timer_state[NR_IRQS];
`static struct timer_rand_state *blkdev_timer_state[MAX_BLKDEV];
`static struct wait_queue *random_wait;
`
`static int random_read(struct inode * inode, struct file * file,
` char * buf, int nbytes);
`static int random_read_unlimited(struct inode * inode, struct file * file,
` char * buf, int nbytes);
`static int random_select(struct inode *inode, struct file *file,
` int sel_type, select_table * wait);
`static int random_write(struct inode * inode, struct file * file,
`const char * buffer, int count);
`static int random_ioctl(struct inode * inode, struct file * file,
`unsigned int cmd, unsigned long arg);
`
`static inline void fast_add_entropy_word(struct random_bucket *r,
` const __u32 input);
`
`static void add_entropy_word(struct random_bucket *r,
` const __u32 input);
`
`#ifndef MIN
`#define MIN(a,b) (((a) < (b)) ? (a) : (b))
`#endif
`
`/*
` * 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__))
`extern inline __u32 rotate_left(int i, __u32 word)
`{
`
`return (word << i) | (word >> (32 - i));
`
`}#
`
`else
`extern 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. By default, use an open-coded C version, although we do
` * have a version which takes advantage of the Intel's x86's "bsr"
` * instruction.
` */
`#if (!defined (__i386__))
`static inline __u32 int_ln(__u32 word)
`{
`
`6
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 6
`
`

`
`__u32 nbits = 0;
`
`while (1) {
`word >>= 1;
`if (!word)
`break;
`nbits++;
`
`}r
`
`eturn nbits;
`
`}#
`
`else
`static inline __u32 int_ln(__u32 word)
`{
`
`__asm__("bsrl %1,%0\n\t"
`"jnz 1f\n\t"
`"movl $0,%0\n"
`"1:"
`:"=r" (word)
`:"r" (word));
`return word;
`
`}#
`
`endif
`
`/*
` * Initialize the random pool with standard stuff.
` *
` * NOTE: This is an OS-dependent function.
` */
`static void init_std_data(struct random_bucket *r)
`{
`
`__u32 word, *p;
`int i;
`struct timeval
`
`tv;
`
`do_gettimeofday(&tv);
`add_entropy_word(r, tv.tv_sec);
`add_entropy_word(r, tv.tv_usec);
`
`for (p = (__u32 *) &system_utsname,
` i = sizeof(system_utsname) / sizeof(__u32);
` i ; i--, p++) {
`memcpy(&word, p, sizeof(__u32));
`add_entropy_word(r, word);
`
`}
`
`} /
`
`* Clear the entropy pool and associated counters. */
`static void rand_clear_pool(void)
`{
`
`random_state.add_ptr = 0;
`random_state.entropy_count = 0;
`random_state.pool = random_pool;
`random_state.input_rotate = 0;
`memset(random_pool, 0, sizeof(random_pool));
`init_std_data(&random_state);
`
`} v
`
`{
`
`oid rand_initialize(void)
`
`int i;
`
`rand_clear_pool();
`
`7
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 7
`
`

`
`for (i = 0; i < NR_IRQS; i++)
`irq_timer_state[i] = NULL;
`for (i = 0; i < MAX_BLKDEV; i++)
`blkdev_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));
`#ifdef RANDOM_BENCHMARK
`initialize_benchmark(&timer_benchmark, "timer", 0);
`
`#endif
`
`extract_timer_state.dont_count_entropy = 1;
`random_wait = NULL;
`
`} v
`
`{
`
`} v
`
`{
`
`oid rand_initialize_irq(int irq)
`
`struct timer_rand_state *state;
`
`if (irq >= NR_IRQS || irq_timer_state[irq])
`return;
`
`/*
` * If kmalloc returns null, we just won't use that entropy
` * source.
` */
`state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
`if (state) {
`irq_timer_state[irq] = state;
`memset(state, 0, sizeof(struct timer_rand_state));
`
`}
`
`oid rand_initialize_blkdev(int major, int mode)
`
`struct timer_rand_state *state;
`
`if (major >= MAX_BLKDEV || blkdev_timer_state[major])
`return;
`
`/*
` * If kmalloc returns null, we just won't use that entropy
` * source.
` */
`state = kmalloc(sizeof(struct timer_rand_state), mode);
`if (state) {
`blkdev_timer_state[major] = state;
`memset(state, 0, sizeof(struct timer_rand_state));
`
`}
`
`} /
`
`*
` * This function adds a byte into the entropy "pool". It does not
` * update the entropy estimate. The caller must do this if appropriate.
` *
` * The pool is stirred with a primitive polynomial of degree 128
` * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
` * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
` *
` * We rotate the input word by a changing number of bits, to help
` * assure that all bits in the entropy get toggled. Otherwise, if we
` * consistently feed the entropy pool small numbers (like jiffies and
` * scancodes, for example), the upper bits of the entropy pool don't
` * get affected. --- TYT, 10/11/95
` */
`
`8
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 8
`
`

`
`static inline void fast_add_entropy_word(struct random_bucket *r,
` const __u32 input)
`
`{
`
`unsigned i;
`int new_rotate;
`__u32 w;
`
`w = rotate_left(r->input_rotate, input);
`i = r->add_ptr = (r->add_ptr - 1) & (POOLWORDS-1);
`/*
` * Normally, we add 7 bits of rotation to the pool. At the
` * beginning of the pool, add an extra 7 bits rotation, so
` * that successive passes spread the input bits across the
` * pool evenly.
` */
`new_rotate = r->input_rotate + 14;
`if (i)
`
`new_rotate = r->input_rotate + 7;
`r->input_rotate = new_rotate & 31;
`
`/* XOR in the various taps */
`w ^= r->pool[(i+TAP1)&(POOLWORDS-1)];
`w ^= r->pool[(i+TAP2)&(POOLWORDS-1)];
`w ^= r->pool[(i+TAP3)&(POOLWORDS-1)];
`w ^= r->pool[(i+TAP4)&(POOLWORDS-1)];
`w ^= r->pool[(i+TAP5)&(POOLWORDS-1)];
`w ^= r->pool[i];
`/* Rotate w left 1 bit (stolen from SHA) and store */
`r->pool[i] = (w << 1) | (w >> 31);
`
`} /
`
`*
` * For places where we don't need the inlined version
` */
`static void add_entropy_word(struct random_bucket *r,
` const __u32 input)
`
`{
`
`fast_add_entropy_word(r, input);
`
`} /
`
`*
` * This function adds entropy to the entropy "pool" by using timing
` * delays. It uses the timer_rand_state structure to make an estimate
` * of how many bits of entropy this call has added to the pool.
` *
` * The number "num" is also added to the pool - it should somehow describe
` * the type of event which just happened. This is currently 0-255 for
` * keyboard scan codes, and 256 upwards for interrupts.
` * On the i386, this is assumed to be at most 16 bits, and the high bits
` * are used for a high-resolution timer.
` *
` */
`static void add_timer_randomness(struct random_bucket *r,
` struct timer_rand_state *state, unsigned num)
`
`{
`
`int
`__u32
`
`delta, delta2, delta3;
`time;
`
`#ifdef RANDOM_BENCHMARK
`begin_benchmark(&timer_benchmark);
`
`#endif
`#if defined (__i386__)
`if (x86_capability & 16) {
`unsigned long low, high;
`
`9
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 9
`
`

`
`__asm__(".byte 0x0f,0x31"
`:"=a" (low), "=d" (high));
`time = (__u32) low;
`num ^= (__u32) high;
`} else {
`time = jiffies;
`
`}
`
`time = jiffies;
`
`#else
`
`#endif
`
`fast_add_entropy_word(r, (__u32) num);
`fast_add_entropy_word(r, time);
`
`/*
` * Calculate number of bits of randomness we probably
` * added. We take into account the first and second order
` * deltas in order to make our estimate.
` */
`if (!state->dont_count_entropy &&
` (r->entropy_count < POOLBITS)) {
`delta = time - state->last_time;
`state->last_time = time;
`if (delta < 0) delta = -delta;
`
`delta2 = delta - state->last_delta;
`state->last_delta = delta;
`if (delta2 < 0) delta2 = -delta2;
`
`delta3 = delta2 - state->last_delta2;
`state->last_delta2 = delta2;
`if (delta3 < 0) delta3 = -delta3;
`
`delta = MIN(MIN(delta, delta2), delta3) >> 1;
`/* Limit entropy estimate to 12 bits */
`delta &= (1 << 12) - 1;
`
`r->entropy_count += int_ln(delta);
`
`/* Prevent overflow */
`if (r->entropy_count > POOLBITS)
`r->entropy_count = POOLBITS;
`
`} /
`
`* Wake up waiting processes, if we have enough entropy. */
`if (r->entropy_count >= WAIT_INPUT_BITS)
`wake_up_interruptible(&random_wait);
`#ifdef RANDOM_BENCHMARK
`end_benchmark(&timer_benchmark);
`
`#endif
`
`} v
`
`{
`
`} v
`
`{
`
`} v
`
`{
`
`oid add_keyboard_randomness(unsigned char scancode)
`
`add_timer_randomness(&random_state, &keyboard_timer_state, scancode);
`
`oid add_mouse_randomness(__u32 mouse_data)
`
`add_timer_randomness(&random_state, &mouse_timer_state, mouse_data);
`
`oid add_interrupt_randomness(int irq)
`
`10
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 10
`
`

`
`if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
`return;
`
`add_timer_randomness(&random_state, irq_timer_state[irq], 0x100+irq);
`
`} v
`
`{
`
`} #
`
`oid add_blkdev_randomness(int major)
`
`if (major >= MAX_BLKDEV)
`return;
`
`if (blkdev_timer_state[major] == 0) {
`rand_initialize_blkdev(major, GFP_ATOMIC);
`if (blkdev_timer_state[major] == 0)
`return;
`
`} a
`
`dd_timer_randomness(&random_state, blkdev_timer_state[major],
` 0x200+major);
`
`define USE_SHA
`
`#ifdef USE_SHA
`
`#define HASH_BUFFER_SIZE 5
`#define HASH_TRANSFORM SHATransform
`
`/*
` * SHA transform algorithm, taken from code written by Peter Gutman,
` * and apparently in the public domain.
` */
`
`/* The SHA f()-functions. */
`
`#define f1(x,y,z) ( z ^ ( x & ( y ^ z ) ) ) /* Rounds 0-19 */
`#define f2(x,y,z) ( x ^ y ^ z ) /* Rounds 20-39 */
`#define f3(x,y,z) ( ( x & y ) | ( z & ( x | y ) ) ) /* Rounds 40-59 */
`#define f4(x,y,z) ( x ^ y ^ z ) /* Rounds 60-79 */
`
`/* The SHA Mysterious Constants */
`
`#define K1 0x5A827999L /* Rounds 0-19 */
`#define K2 0x6ED9EBA1L /* Rounds 20-39 */
`#define K3 0x8F1BBCDCL /* Rounds 40-59 */
`#define K4 0xCA62C1D6L /* Rounds 60-79 */
`
`#define ROTL(n,X) ( ( ( X ) << n ) | ( ( X ) >> ( 32 - n ) ) )
`
`#define expand(W,i) ( W[ i & 15 ] = \
` ROTL( 1, ( W[ i & 15 ] ^ W[ (i - 14) & 15 ] ^ \
` W[ (i - 8) & 15 ] ^ W[ (i - 3) & 15 ] ) ) )
`
`#define subRound(a, b, c, d, e, f, k, data) \
` ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
`
`void SHATransform(__u32 *digest, __u32 *data)
` {
` __u32 A, B, C, D, E; /* Local vars */
` __u32 eData[ 16 ]; /* Expanded data */
`
` /* Set up first buffer and local data buffer */
` A = digest[ 0 ];
`
`11
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 11
`
`

`
` B = digest[ 1 ];
` C = digest[ 2 ];
` D = digest[ 3 ];
` E = digest[ 4 ];
` memcpy( eData, data, 16*sizeof(__u32));
`
` /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */
` subRound( A, B, C, D, E, f1, K1, eData[ 0 ] );
` subRound( E, A, B, C, D, f1, K1, eData[ 1 ] );
` subRound( D, E, A, B, C, f1, K1, eData[ 2 ] );
` subRound( C, D, E, A, B, f1, K1, eData[ 3 ] );
` subRound( B, C, D, E, A, f1, K1, eData[ 4 ] );
` subRound( A, B, C, D, E, f1, K1, eData[ 5 ] );
` subRound( E, A, B, C, D, f1, K1, eData[ 6 ] );
` subRound( D, E, A, B, C, f1, K1, eData[ 7 ] );
` subRound( C, D, E, A, B, f1, K1, eData[ 8 ] );
` subRound( B, C, D, E, A, f1, K1, eData[ 9 ] );
` subRound( A, B, C, D, E, f1, K1, eData[ 10 ] );
` subRound( E, A, B, C, D, f1, K1, eData[ 11 ] );
` subRound( D, E, A, B, C, f1, K1, eData[ 12 ] );
` subRound( C, D, E, A, B, f1, K1, eData[ 13 ] );
` subRound( B, C, D, E, A, f1, K1, eData[ 14 ] );
` subRound( A, B, C, D, E, f1, K1, eData[ 15 ] );
` subRound( E, A, B, C, D, f1, K1, expand( eData, 16 ) );
` subRound( D, E, A, B, C, f1, K1, expand( eData, 17 ) );
` subRound( C, D, E, A, B, f1, K1, expand( eData, 18 ) );
` subRound( B, C, D, E, A, f1, K1, expand( eData, 19 ) );
`
` subRound( A, B, C, D, E, f2, K2, expand( eData, 20 ) );
` subRound( E, A, B, C, D, f2, K2, expand( eData, 21 ) );
` subRound( D, E, A, B, C, f2, K2, expand( eData, 22 ) );
` subRound( C, D, E, A, B, f2, K2, expand( eData, 23 ) );
` subRound( B, C, D, E, A, f2, K2, expand( eData, 24 ) );
` subRound( A, B, C, D, E, f2, K2, expand( eData, 25 ) );
` subRound( E, A, B, C, D, f2, K2, expand( eData, 26 ) );
` subRound( D, E, A, B, C, f2, K2, expand( eData, 27 ) );
` subRound( C, D, E, A, B, f2, K2, expand( eData, 28 ) );
` subRound( B, C, D, E, A, f2, K2, expand( eData, 29 ) );
` subRound( A, B, C, D, E, f2, K2, expand( eData, 30 ) );
` subRound( E, A, B, C, D, f2, K2, expand( eData, 31 ) );
` subRound( D, E, A, B, C, f2, K2, expand( eData, 32 ) );
` subRound( C, D, E, A, B, f2, K2, expand( eData, 33 ) );
` subRound( B, C, D, E, A, f2, K2, expand( eData, 34 ) );
` subRound( A, B, C, D, E, f2, K2, expand( eData, 35 ) );
` subRound( E, A, B, C, D, f2, K2, expand( eData, 36 ) );
` subRound( D, E, A, B, C, f2, K2, expand( eData, 37 ) );
` subRound( C, D, E, A, B, f2, K2, expand( eData, 38 ) );
` subRound( B, C, D, E, A, f2, K2, expand( eData, 39 ) );
`
` subRound( A, B, C, D, E, f3, K3, expand( eData, 40 ) );
` subRound( E, A, B, C, D, f3, K3, expand( eData, 41 ) );
` subRound( D, E, A, B, C, f3, K3, expand( eData, 42 ) );
` subRound( C, D, E, A, B, f3, K3, expand( eData, 43 ) );
` subRound( B, C, D, E, A, f3, K3, expand( eData, 44 ) );
` subRound( A, B, C, D, E, f3, K3, expand( eData, 45 ) );
` subRound( E, A, B, C, D, f3, K3, expand( eData, 46 ) );
` subRound( D, E, A, B, C, f3, K3, expand( eData, 47 ) );
` subRound( C, D, E, A, B, f3, K3, expand( eData, 48 ) );
` subRound( B, C, D, E, A, f3, K3, expand( eData, 49 ) );
` subRound( A, B, C, D, E, f3, K3, expand( eData, 50 ) );
` subRound( E, A, B, C, D, f3, K3, expand( eData, 51 ) );
` subRound( D, E, A, B, C, f3, K3, expand( eData, 52 ) );
` subRound( C, D, E, A, B, f3, K3, expand( eData, 53 ) );
` subRound( B, C, D, E, A, f3, K3, expand( eData, 54 ) );
`
`12
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 12
`
`

`
` subRound( A, B, C, D, E, f3, K3, expand( eData, 55 ) );
` subRound( E, A, B, C, D, f3, K3, expand( eData, 56 ) );
` subRound( D, E, A, B, C, f3, K3, expand( eData, 57 ) );
` subRound( C, D, E, A, B, f3, K3, expand( eData, 58 ) );
` subRound( B, C, D, E, A, f3, K3, expand( eData, 59 ) );
`
` subRound( A, B, C, D, E, f4, K4, expand( eData, 60 ) );
` subRound( E, A, B, C, D, f4, K4, expand( eData, 61 ) );
` subRound( D, E, A, B, C, f4, K4, expand( eData, 62 ) );
` subRound( C, D, E, A, B, f4, K4, expand( eData, 63 ) );
` subRound( B, C, D, E, A, f4, K4, expand( eData, 64 ) );
` subRound( A, B, C, D, E, f4, K4, expand( eData, 65 ) );
` subRound( E, A, B, C, D, f4, K4, expand( eData, 66 ) );
` subRound( D, E, A, B, C, f4, K4, expand( eData, 67 ) );
` subRound( C, D, E, A, B, f4, K4, expand( eData, 68 ) );
` subRound( B, C, D, E, A, f4, K4, expand( eData, 69 ) );
` subRound( A, B, C, D, E, f4, K4, expand( eData, 70 ) );
` subRound( E, A, B, C, D, f4, K4, expand( eData, 71 ) );
` subRound( D, E, A, B, C, f4, K4, expand( eData, 72 ) );
` subRound( C, D, E, A, B, f4, K4, expand( eData, 73 ) );
` subRound( B, C, D, E, A, f4, K4, expand( eData, 74 ) );
` subRound( A, B, C, D, E, f4, K4, expand( eData, 75 ) );
` subRound( E, A, B, C, D, f4, K4, expand( eData, 76 ) );
` subRound( D, E, A, B, C, f4, K4, expand( eData, 77 ) );
` subRound( C, D, E, A, B, f4, K4, expand( eData, 78 ) );
` subRound( B, C, D, E, A, f4, K4, expand( eData, 79 ) );
`
` /* Build message digest */
` digest[ 0 ] += A;
` digest[ 1 ] += B;
` digest[ 2 ] += C;
` digest[ 3 ] += D;
` digest[ 4 ] += E;
` }
`
`#else
`#define HASH_BUFFER_SIZE 4
`#define HASH_TRANSFORM MD5Transform
`
`/*
` * MD5 transform algorithm, taken from code written by Colin Plumb,
` * and put into the public domain
` *
` * QUESTION: Replace this with SHA, which as generally received better
` * reviews from the cryptographic community?
` */
`
`/* 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<<s | 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.
` */
`
`13
`
`Petitioners Great West Casualty Co., BITCO Gen. Ins. Corp., and BITCO Nat'l Ins. Co.
`Ex. 1006, p. 13
`
`

`
`static void MD5Transform(__u32 buf[4],
` __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