From: Jean-Luc Cooke <jlcooke@certainkey.com>
To: "Theodore Ts'o" <tytso@mit.edu>, linux-kernel@vger.kernel.org
Subject: Re: [PROPOSAL/PATCH] Fortuna PRNG in /dev/random
Date: Fri, 24 Sep 2004 09:44:57 -0400 [thread overview]
Message-ID: <20040924134457.GQ28317@certainkey.com> (raw)
In-Reply-To: <20040924043851.GA3611@thunk.org>
[-- Attachment #1: Type: text/plain, Size: 753 bytes --]
On Fri, Sep 24, 2004 at 12:38:51AM -0400, Theodore Ts'o wrote:
> I'm also a bit concerned about how much time AES takes over the
> cut-down MD4, as this may affect networking benchmarks. (And we don't
> need super-strength crypto here.)
Oh,
openssl speed md4 aes shows:
type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
md4 10708.72k 38240.96k 111170.47k 215872.85k 296828.93k
aes-128 cbc 32121.81k 32678.31k 33119.49k 33221.29k 33210.59k
aes-192 cbc 27915.92k 27868.52k 28418.08k 28677.12k 28721.15k
aes-256 cbc 24599.57k 25142.38k 25381.80k 25474.88k 25392.46k
Since we're using small blocks.
Attached is the patch with the problems Ted pointed out.
JLC
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fortuna-2.6.8.1.patch --]
[-- Type: text/plain; charset=unknown-8bit, Size: 93297 bytes --]
diff -uNr linux-2.6.8.1-orig/include/linux/sysctl.h linux-2.6.8.1-fortuna/include/linux/sysctl.h
--- linux-2.6.8.1-orig/include/linux/sysctl.h 2004-08-14 12:55:33.000000000 +0200
+++ linux-2.6.8.1-fortuna/include/linux/sysctl.h 2004-09-13 18:55:43.000000000 +0200
@@ -198,7 +198,8 @@
RANDOM_READ_THRESH=3,
RANDOM_WRITE_THRESH=4,
RANDOM_BOOT_ID=5,
- RANDOM_UUID=6
+ RANDOM_UUID=6,
+ RANDOM_DERIVE_SEED=7
};
/* /proc/sys/kernel/pty */
--- linux-2.6.8.1/drivers/char/random.c 2004-09-24 08:32:30.222610504 -0400
+++ linux-2.6.8.1-rand2/drivers/char/random.c 2004-09-24 09:31:30.251444320 -0400
@@ -2,9 +2,11 @@
* random.c -- A strong random number generator
*
* Version 1.89, last modified 19-Sep-99
+ * Version 2.01, last modified 24-Sep-2004
*
* Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999. All
* rights reserved.
+ * Copyright Jean-Luc Cooke, 2004. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -40,61 +42,157 @@
*/
/*
- * (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
- * 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 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
- * be computationally infeasible to derive any useful information
- * about the input of SHA from its output. Even if it is possible to
- * analyze SHA 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 SHA, 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.
- *
+ * The entire PRNG used in this file was replaced using a variant of the Fortuna
+ * PRNG described in Practical Cryptography by Ferguson and Schnier.
+ *
+ * The changes to their design include:
+ * - feeding the output of each pool back into their input to carry entropy
+ * forward (avoids pool overflow attacks like
+ * "dd if=/dev/zero of=/dev/random"
+ *
+ * Also, the entropy estimator was removed since it is not needed for
+ * cryptographically secure random data and such constructions are
+ * historically prone to attack
+ * [read Practical Cryptography].
+ *
+ * The Fortuna PRNG as described in Practical Cryptography is implemented here.
+ *
+ * Pseudo-code follows.
+ *
+<b>create_entropy_pool(r)</b>
+ - create an entropy pool in "r"
+
+ r.pool0_len = 0;
+ r.reseed_count = 0;
+ r.derive_count = 0;
+ r.digestsize = // digest size for our hash
+ r.blocksize = // block size for our cipher
+ r.keysize = // key size for our cipher
+ for (i=0; i<32; i++) {
+ crypto_digest_init(r.pool[i]);
+ }
+ memset(r.key, 0, r.keysize);
+ crypto_cipher_setkey(r.cipher, r.key, r.keysize);
+
+<b>add_entropy_words(r, in, nwords)</b>
+ - mix 32bit word array "in" which is "nwords" long into pool "r"
+
+ crypto_digest_update(r.pool[i], in, nwords*sizeof(in[0]));
+ if (r.pool_index == 0)
+ r.pool0_len += nwords*sizeof(in[0]);
+ r.pool_index = r.pool_index + 1 mod (2<sup>number of pools</sup> - 1)
+
+<b>random_reseed(r)</b>
+ - reseed the key from the pooling system
+
+ r.reseed_count++;
+
+ crypto_digest_init(hash);
+ crypto_digest_update(hash, r.key, r.keysize);
+
+ for (i=0; i<32; i++) {
+ if (2<sup>i</sup> is a factor of r.reseed_count) {
+ crypto_digest_final(r.pool[i], tmp);
+ crypto_digest_init(r.poo[i]);
+ crypto_digest_update(hash, tmp, r.digestsize);
+
+ // jlcooke: small change from Ferguson
+ crypto_digest_update(r.pool[i], tmp, r.digestsize);
+ }
+ }
+
+ crypto_digest_final(hash, tmp);
+ crypto_cipher_setkey(r.cipher, tmp, r.keysize);
+ r.ctrValue = r.ctrValue + 1 mod (2<sup>number of pools</sup> - 1)
+
+<b>extract_entropy(r, buf, nbytes, flags)</b>
+ - fill byte array "buf" with "nbytes" of random data from entropy pool "r"
+
+ random_reseed(r);
+ r.pool0_len = 0;
+
+ while (nbytes > 0) {
+ crypto_cipher_encrypt(r.cipher, tmp, r.ctrValue, r.blocksize);
+ r.ctrValue++; // modulo 2<sup>r.blocksize/8</sup>
+
+ //
+ // Copy r.blocksize of tmp to the user
+ // Unless nbytes is less than r.blocksize, in which case only copy nbytes
+ //
+
+ nbytes -= r.blocksize;
+ }
+
+ // generate a new key
+ crypto_cipher_encrypt(r.cipher, r.key, r.ctrValue, r.blocksize);
+ crypto_cipher_setkey(r.cipher, r.key, r.keysize);
+
+<b>derive_pool(r, buf)</b>
+ - Fill "buf" with the output from a 1-way transformation of all 32-pools
+
+ memset(tmp, 0, r.digestsize);
+ r.pool0_len = 0;
+
+ for (i=0; i<32; i++) {
+ crypto_digest_init(hash);
+
+ crypto_digest_update(hash, tmp, r.digestsize);
+
+ crypto_digest_final(r.pool[i], tmp);
+ crypto_digest_init(r.pool[i]);
+ crypto_digest_update(hash, tmp, r.digestsize);
+
+ crypto_digest_update(hash, r.derive_count, sizeof(r.derive_count));
+
+ crypto_digest_final(hash, tmp);
+
+ // Replace all 0x00 in "tmp" with "0x01" because the API to return a byte
+ // array does not exist. Only a "return string" API is provided. This
+ // reduces the effective entropy of the output by 0.39%.
+ //
+
+ memcpy(&buf[i*r.digestsize], tmp, r.digestsize);
+ r.derive_count++;
+ }
+ *
+ * Draft Security Statement/Analysis (Jean-Luc Cooke <jlcooke@certainkey.com>)
+ *
+ * The Fortuna PRNG is resilliant to all known and preventable PRNG attacks.
+ * Proof of strength to these attacks can be done by reduction to the security
+ * of the underlying cryptographic primitives.
+ * * H = HASH(M)
+ * + M={0,1}^Mlen 0 <= Mlen < infinity
+ * + H={0,1}^Hlen 256 <= Hlen
+ * * C = ENCRYPT(K,M)
+ * + K={0,1}^Klen 256 <= Klen
+ * + M={0,1}^Mlen Mlen = 128
+ * + C={0,1}^Clen Clen = 128
+ *
+ * - Invertability of the output function
+ * The state of the output function Output[i] = ENCRYPT(KEY, CTR++) is
+ * {KEY,CTR} To recover the state {KEY,CTR} the attacker must be able to
+ * mount a known-plaintext or a known-ciphertext attack on the block cipher
+ * C=ENCRYPT(K,M) with N blocks.
+ * N = ReseedIntervalInSeconds * OutputRateInBytesPerSecond / BytesPerBlock
+ * AES256 in CTR is secure from known-plaintext/ciphertext key recovery
+ * attacks with N < 2^128
+ * However, After 2^64 blocks (2^71 bits) an attacker would have a 0.5 chance
+ * to guessing the next 128bit output. N <<< 2^64
+ *
+ * - Invertability of the pool mixing function
+ * The pool mixing function H' = HASH(H' || M) is said to be non-inveretable
+ * if H=HASH(MSG) is invertable.
+ * There have been no invertability discoveries in SHA-256.
+ *
+ * - Manipulating pool mixing
+ * An attack who has access to one or all of the entropy event sources may
+ * be able to input mallicious event data to alter any one of the pool states
+ * into a degenerate state. This requires that the underlying H=HASH(MSG)
+ * function is suseptible to a 1st pre-image attack. SHA-256 has no such
+ * known attacks.
+ */
+
+/*
* Exported interfaces ---- output
* ===============================
*
@@ -107,17 +205,13 @@
* 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.
+ * /dev/urandom. They are synonymous with eachother for legacy reasons
+ *
+ * Both the devices 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
* ==============================
@@ -160,32 +254,28 @@
* following lines an appropriate script which is run during the boot
* sequence:
*
- * echo "Initializing random number generator..."
- * random_seed=/var/run/random-seed
- * # Carry a random seed from start-up to start-up
- * # Load and then save the whole entropy pool
- * if [ -f $random_seed ]; then
- * cat $random_seed >/dev/urandom
- * else
- * 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
+ * echo "Initializing random number generator..."
+ * random_seed=/var/run/random-seed
+ * # Carry a random seed from start-up to start-up
+ * # Load and then save the whole entropy pool
+ * if [ -f $random_seed ]; then
+ * cat $random_seed >/dev/urandom
+ * else
+ * touch $random_seed
+ * fi
+ * chmod 600 $random_seed
+ * dd if=/proc/sys/kernel/random/derive_seed of=$random_seed
*
* and the following lines in an appropriate script which is run as
* the system is shutdown:
*
- * # Carry a random seed from shut-down to start-up
- * # Save the whole entropy pool
- * echo "Saving random seed..."
- * 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
+ * # Carry a random seed from shut-down to start-up
+ * # Save the whole entropy pool
+ * echo "Saving random seed..."
+ * random_seed=/var/run/random-seed
+ * touch $random_seed
+ * chmod 600 $random_seed
+ * dd if=/proc/sys/kernel/random/derive_seed of=$random_seed
*
* For example, on most modern systems using the System V init
* scripts, such code fragments would be found in
@@ -215,22 +305,11 @@
* Acknowledgements:
* =================
*
- * Ideas for constructing this random number generator were derived
- * from 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 PGPfone. Dale Worley has also contributed many
- * useful ideas and suggestions to improve this driver.
+ * The design for this RNG come from Fortuna as explined above.
+ * Cryptographic implementations are used from the CryptoAPI.
*
* 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".
+ * not be attributed to the Ted, Phil, Colin, or any of authors of PGP.
*
* Further background information on this topic may be obtained from
* RFC 1750, "Randomness Recommendations for Security", by Donald
@@ -254,137 +333,43 @@
#include <linux/interrupt.h>
#include <linux/spinlock.h>
#include <linux/percpu.h>
+#include <linux/crypto.h>
+#include <../crypto/internal.h>
+#include <asm/scatterlist.h>
#include <asm/processor.h>
#include <asm/uaccess.h>
#include <asm/irq.h>
#include <asm/io.h>
-/*
- * Configuration information
- */
-#define DEFAULT_POOL_SIZE 512
-#define SECONDARY_POOL_SIZE 128
-#define BATCH_ENTROPY_SIZE 256
-#define USE_SHA
-
-/*
- * The minimum number of bits of entropy before we wake up a read on
- * /dev/random. Should be enough to do a significant reseed.
- */
-static int random_read_wakeup_thresh = 64;
-
-/*
- * If the entropy count falls under this number of bits, then we
- * should wake up processes which are selecting or polling on write
- * access to /dev/random.
- */
-static int random_write_wakeup_thresh = 128;
-
-/*
- * When the input pool goes over trickle_thresh, start dropping most
- * samples to avoid wasting CPU time and reduce lock contention.
- */
-
-static int trickle_thresh = DEFAULT_POOL_SIZE * 7;
-
-static DEFINE_PER_CPU(int, trickle_count) = 0;
+#if 0
+ #define DEBUG_PRINTK printk
+#else
+ #define DEBUG_PRINTK debug_printk
+static inline void debug_printk(const char *a, ...) {}
+#endif
/*
- * A pool of size .poolwords is stirred with a primitive polynomial
- * of degree .poolwords over GF(2). The taps for various sizes are
- * defined below. They are chosen to be evenly spaced (minimum RMS
- * distance from evenly spaced; the numbers in the comments are a
- * scaled squared error sum) except for the last tap, which is 1 to
- * get the twisting happening as fast as possible.
+ * Configuration information
*/
-static struct poolinfo {
- 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 },
-
- /* 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 },
-};
-
-#define POOLBITS poolwords*32
-#define POOLBYTES poolwords*4
+#define BATCH_ENTROPY_SIZE 512 /* how many events do we buffer? BATCH_ENTROPY_SIZE/2 == how many we need before batch-submitting them */
+#define RANDOM_RESEED_INTERVAL 600 /* reseed the PRNG output state every 5mins */
+#define RANDOM_DEFAULT_CIPHER_ALGO "aes"
+#define RANDOM_DEFAULT_DIGEST_ALGO "sha256"
+
+#define DEFAULT_POOL_NUMBER 5 /* 2^{5} = 32 pools */
+#define MAXIMUM_POOL_NUMBER DEFAULT_POOL_NUMBER
+#define MINIMUM_POOL_NUMBER 2 /* 2^{2} = 4 pools */
+#define USE_SHA256
+#define RANDOM_MAX_DIGEST_SIZE 64 /* SHA512/WHIRLPOOL have 64bytes == 512 bits */
+#define RANDOM_MAX_BLOCK_SIZE 16 /* AES256 has 16byte blocks == 128 bits */
+#define RANDOM_MAX_KEY_SIZE 32 /* AES256 has 32byte keys == 256 bits */
+#define USE_AES256
/*
- * For the purposes of better mixing, we use the CRC-32 polynomial as
- * well to make a twisted Generalized Feedback Shift Reigster
- *
- * (See M. Matsumoto & Y. Kurita, 1992. Twisted GFSR generators. ACM
- * Transactions on Modeling and Computer Simulation 2(3):179-194.
- * Also see M. Matsumoto & Y. Kurita, 1994. Twisted GFSR generators
- * 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
- * we expect to see. As long as the pool state differs for different
- * inputs, we have preserved the input entropy and done a good job.
- * The fact that an intelligent attacker can construct inputs that
- * will produce controlled alterations to the pool's state is not
- * important because we don't consider such inputs to contribute any
- * randomness. The only property we need with respect to them is that
- * the attacker can't increase his/her knowledge of the pool's state.
- * Since all additions are reversible (knowing the final state and the
- * input, you can reconstruct the initial state), if an attacker has
- * any uncertainty about the initial state, he/she can only shuffle
- * that uncertainty about, but never cause any collisions (which would
- * decrease the uncertainty).
- *
- * The chosen system lets the state of the pool be (essentially) the input
- * modulo the generator polymnomial. Now, for random primitive polynomials,
- * this is a universal class of hash functions, meaning that the chance
- * of a collision is limited by the attacker's knowledge of the generator
- * polynomail, so if it is chosen at random, an attacker can never force
- * a collision. Here, we use a fixed polynomial, but we *can* assume that
- * ###--> it is unknown to the processes generating the input entropy. <-###
- * Because of this important property, this is a good, collision-resistant
- * hash; hash collisions will occur no more often than chance.
+ * Throttle mouse/keyboard/disk/interrupt entropy input to only add after this many jiffies/rdtsc counts
*/
+#define RANDOM_INPUT_THROTTLE 1000
/*
* Linux 2.2 compatibility
@@ -399,8 +384,10 @@
/*
* Static global variables
*/
+static int random_entropy_count; // jlc & cam have been together for 5 and 2/3 years as of the time this was written;
+static int random_read_wakeup_thresh = 0; // ignored now.
+static int random_write_wakeup_thresh = 0; // ignored now.
static struct entropy_store *random_state; /* The default global store */
-static struct entropy_store *sec_random_state; /* secondary store */
static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
@@ -411,71 +398,6 @@
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)
#else
@@ -490,15 +412,28 @@
**********************************************************************/
struct entropy_store {
- /* mostly-read data: */
- struct poolinfo poolinfo;
- __u32 *pool;
+ const char *digestAlgo;
+ unsigned int digestsize;
+ struct crypto_tfm *pools[1<<MAXIMUM_POOL_NUMBER];
+ /* optional, handy for statistics */
+ unsigned int pools_bytes[1<<MAXIMUM_POOL_NUMBER];
+
+ const char *cipherAlgo;
+ unsigned char key[RANDOM_MAX_DIGEST_SIZE]; /* the key */
+ unsigned int keysize;
+ unsigned char iv[16]; /* the CTR value */
+ unsigned int blocksize;
+ struct crypto_tfm *cipher;
+
+ unsigned int pool_number; /* 2^pool_number # of pools */
+ unsigned int pool_index; /* current pool to add into */
+ unsigned int pool0_len; /* size of the first pool */
+ unsigned int reseed_count; /* number of time we have reset */
+ struct crypto_tfm *reseedHash; /* digest used during random_reseed() */
+ struct crypto_tfm *networkCipher; /* cipher used for network randomness */
+ char networkCipher_ready; /* flag indicating if networkCipher has been seeded */
- /* read-write data: */
spinlock_t lock ____cacheline_aligned_in_smp;
- unsigned add_ptr;
- int entropy_count;
- int input_rotate;
};
/*
@@ -507,151 +442,107 @@
*
* Returns an negative error if there is a problem.
*/
-static int create_entropy_store(int size, struct entropy_store **ret_bucket)
+static int create_entropy_store(int pool_number_arg, struct entropy_store **ret_bucket)
{
struct entropy_store *r;
- struct poolinfo *p;
- int poolwords;
+ unsigned long pool_number;
+ int keysize, i, j;
- 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;
+ pool_number = pool_number_arg;
+ if (pool_number < MINIMUM_POOL_NUMBER)
+ pool_number = MINIMUM_POOL_NUMBER;
r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
- if (!r)
+ if (!r) {
return -ENOMEM;
+ }
memset (r, 0, sizeof(struct entropy_store));
- r->poolinfo = *p;
+ r->pool_number = pool_number;
+ r->digestAlgo = RANDOM_DEFAULT_DIGEST_ALGO;
- r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
- if (!r->pool) {
- kfree(r);
- return -ENOMEM;
+DEBUG_PRINTK("create_entropy_store() pools=%u index=%u\n", 1<<pool_number, r->pool_index);
+ for (i=0; i<(1<<pool_number); i++) {
+DEBUG_PRINTK("create_entropy_store() i=%i index=%u\n", i, r->pool_index);
+ r->pools[i] = crypto_alloc_tfm(r->digestAlgo, 0);
+ if (r->pools[i] == NULL) {
+ for (j=0; j<i; j++) {
+ if (r->pools[j] != NULL) {
+ kfree(r->pools[j]);
+ }
+ }
+ kfree(r);
+ return -ENOMEM;
+ }
+ crypto_digest_init( r->pools[i] );
}
- memset(r->pool, 0, POOLBYTES);
r->lock = SPIN_LOCK_UNLOCKED;
*ret_bucket = r;
- return 0;
-}
-/* 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 __u32 const twist_table[8] = {
- 0, 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;
- __u32 w, next_w;
- unsigned long flags;
+ r->cipherAlgo = RANDOM_DEFAULT_CIPHER_ALGO;
+ if ((r->cipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+ return -ENOMEM;
+ }
- /* 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;
- next_w = *in++;
+ /* If the HASH's output is greater then the cipher's keysize, truncate
+ * to the cipher's keysize */
+ keysize = crypto_tfm_alg_max_keysize(r->cipher);
+ r->digestsize = crypto_tfm_alg_digestsize(r->pools[0]);
+ r->blocksize = crypto_tfm_alg_blocksize(r->cipher);
- spin_lock_irqsave(&r->lock, flags);
- prefetch_range(r->pool, wordmask);
- input_rotate = r->input_rotate;
- add_ptr = r->add_ptr;
-
- while (nwords--) {
- w = rotate_left(input_rotate, next_w);
- if (nwords > 0)
- next_w = *in++;
- i = add_ptr = (add_ptr - 1) & wordmask;
- /*
- * 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 = input_rotate + 14;
- if (i)
- new_rotate = input_rotate + 7;
- input_rotate = new_rotate & 31;
-
- /* XOR in the various taps */
- w ^= r->pool[(i + tap1) & wordmask];
- w ^= r->pool[(i + tap2) & wordmask];
- w ^= r->pool[(i + tap3) & wordmask];
- w ^= r->pool[(i + tap4) & wordmask];
- w ^= r->pool[(i + tap5) & wordmask];
- w ^= r->pool[i];
- r->pool[i] = (w >> 3) ^ twist_table[w & 7];
+ r->keysize = (keysize < r->digestsize) ? keysize : r->digestsize;
+
+ if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+ return -EINVAL;
}
- r->input_rotate = input_rotate;
- r->add_ptr = add_ptr;
+ /* digest used duing random-reseed() */
+ if ((r->reseedHash=crypto_alloc_tfm(r->digestAlgo, 0)) == NULL) {
+ return -ENOMEM;
+ }
+ /* cipher used for network randomness, init to key={zerovector}
+ * for now */
+ if ((r->networkCipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+ return -ENOMEM;
+ }
- spin_unlock_irqrestore(&r->lock, flags);
+ return 0;
}
/*
- * Credit (or debit) the entropy store with n bits of entropy
+ * This function adds a byte into the entropy "pool".
*/
-static void credit_entropy_store(struct entropy_store *r, int nbits)
+static void add_entropy_words(struct entropy_store *r, const __u32 *in,
+ int nwords)
{
unsigned long flags;
+ struct scatterlist sg[1];
+ static unsigned int totalBytes=0;
+
+ if (r == NULL) {
+ return;
+ }
spin_lock_irqsave(&r->lock, flags);
- if (r->entropy_count + nbits < 0) {
- 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 {
- r->entropy_count += nbits;
- if (nbits)
- DEBUG_ENT("%04d %04d : added %d bits to %s\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- nbits,
- r == sec_random_state ? "secondary" :
- r == random_state ? "primary" : "unknown");
+ totalBytes += nwords * sizeof(__u32);
+ r->pools_bytes[r->pool_index] += nwords * sizeof(__u32);
+
+ sg[0].page = virt_to_page(in);
+ sg[0].offset = offset_in_page(in);
+ sg[0].length = nwords*sizeof(__u32);
+ crypto_digest_update(r->pools[r->pool_index], sg, 1);
+
+ if (r->pool_index == 0) {
+ r->pool0_len += nwords*sizeof(__u32);
}
+ /* idx = (idx + 1) mod ( (2^N)-1 ) */
+ r->pool_index = (r->pool_index + 1) & ((1<<r->pool_number)-1);
+
spin_unlock_irqrestore(&r->lock, flags);
+DEBUG_PRINTK("0 add_entropy_words() nwords=%u pool[i].bytes=%u total=%u\n",
+ nwords, r->pools_bytes[r->pool_index], totalBytes);
}
/**********************************************************************
@@ -668,10 +559,10 @@
};
static struct sample *batch_entropy_pool, *batch_entropy_copy;
-static int batch_head, batch_tail;
+static int batch_head, batch_tail;
static spinlock_t batch_lock = SPIN_LOCK_UNLOCKED;
-static int batch_max;
+static int batch_max;
static void batch_entropy_process(void *private_);
static DECLARE_WORK(batch_work, batch_entropy_process, NULL);
@@ -703,19 +594,20 @@
int new;
unsigned long flags;
- if (!batch_max)
+ 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;
+ batch_entropy_pool[batch_head].credit = 0;
if (((batch_head - batch_tail) & (batch_max-1)) >= (batch_max / 2)) {
/*
- * Schedule it for the next timer tick:
- */
+ * Schedule it for the next timer tick:
+ */
schedule_delayed_work(&batch_work, 1);
}
@@ -733,13 +625,11 @@
/*
* 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.
+ * store (normally random_state).
*/
static void batch_entropy_process(void *private_)
{
- struct entropy_store *r = (struct entropy_store *) private_, *p;
- int max_entropy = r->poolinfo.POOLBITS;
+ struct entropy_store *r = (struct entropy_store *) private_;
unsigned head, tail;
/* Mixing into the pool is expensive, so copy over the batch
@@ -750,7 +640,7 @@
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;
@@ -758,61 +648,30 @@
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
*
*********************************************************************/
-/* There is one of these per entropy source */
-struct timer_rand_state {
- __u32 last_time;
- __s32 last_delta,last_delta2;
- int 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 *irq_timer_state[NR_IRQS];
-
/*
* 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.
+ * delays.
*
* 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.
- *
+ * the type of event which just happened.
*/
-static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
+static void add_timer_randomness(unsigned num)
{
- __u32 time;
- __s32 delta, delta2, delta3;
- int entropy = 0;
-
- /* if over the trickle threshold, use only 1 in 4096 samples */
- if ( random_state->entropy_count > trickle_thresh &&
- (__get_cpu_var(trickle_count)++ & 0xfff))
- return;
+ static __u32 lasttime=0;
+ __u32 time;
#if defined (__i386__) || defined (__x86_64__)
if (cpu_has_tsc) {
@@ -822,480 +681,57 @@
} else {
time = jiffies;
}
-#elif defined (__sparc_v9__)
- unsigned long tick = tick_ops->get_tick();
-
- time = (unsigned int) tick;
- num ^= (tick >> 32UL);
#else
time = jiffies;
#endif
- /*
- * 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;
-
- delta2 = delta - state->last_delta;
- state->last_delta = delta;
-
- delta3 = delta2 - state->last_delta2;
- state->last_delta2 = delta2;
-
- if (delta < 0)
- delta = -delta;
- if (delta2 < 0)
- delta2 = -delta2;
- if (delta3 < 0)
- delta3 = -delta3;
- if (delta > delta2)
- delta = delta2;
- if (delta > delta3)
- delta = delta3;
-
- /*
- * delta is now minimum absolute delta.
- * 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);
+ /* Throttle our input to add_entropy_words() */
+ if ((time-lasttime) < RANDOM_INPUT_THROTTLE) {
+ return;
}
- batch_entropy_store(num, time, entropy);
+ lasttime = time;
+
+ batch_entropy_store(num, time, 0);
}
void add_keyboard_randomness(unsigned char scancode)
{
- 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);
- }
+ /* jlcooke: we don't care about auto-repeats,
+ * they can't hurt us anymore */
+ add_timer_randomness(scancode);
}
EXPORT_SYMBOL(add_keyboard_randomness);
void add_mouse_randomness(__u32 mouse_data)
{
- add_timer_randomness(&mouse_timer_state, mouse_data);
+ add_timer_randomness(mouse_data);
}
EXPORT_SYMBOL(add_mouse_randomness);
void add_interrupt_randomness(int irq)
{
- if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
+ if (irq >= NR_IRQS)
return;
- add_timer_randomness(irq_timer_state[irq], 0x100+irq);
+ /* jlcooke: no need to add 0x100 ... not random! :P */
+ add_timer_randomness(irq);
}
EXPORT_SYMBOL(add_interrupt_randomness);
void add_disk_randomness(struct gendisk *disk)
{
- if (!disk || !disk->random)
+ if (!disk)
return;
- /* first major is 1, so we get >= 0x200 here */
- add_timer_randomness(disk->random, 0x100+MKDEV(disk->major, disk->first_minor));
+
+ /* jlcooke: no need to add 0x100 ... not random! :P */
+ add_timer_randomness(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
-
-/* 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<<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.
- */
-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;
-}
-
-#undef F1
-#undef F2
-#undef F3
-#undef F4
-#undef MD5STEP
-
-#endif /* !USE_SHA */
-
/*********************************************************************
*
* Entropy extraction routines
@@ -1305,169 +741,145 @@
#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)
+#define CRYPTO_MAX_BLOCK_SIZE 32
static ssize_t extract_entropy(struct entropy_store *r, void * buf,
size_t nbytes, int flags);
+static inline void increment_iv(unsigned char *IV, const unsigned int IVsize) {
+ unsigned int i;
+ for (i=0; i<IVsize; i++) {
+ if ( ++(IV[i]) ) {
+ break;
+ }
+ }
+}
+
/*
- * 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)
-{
- if (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));
-
- DEBUG_ENT("%04d %04d : going to reseed %s with %d bits "
- "(%d of %d requested)\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- r == sec_random_state ? "secondary" : "unknown",
- bytes * 8, nbytes * 8, r->entropy_count);
-
- bytes=extract_entropy(random_state, tmp, bytes,
- EXTRACT_ENTROPY_LIMIT);
- add_entropy_words(r, tmp, bytes);
- credit_entropy_store(r, bytes*8);
+ * Fortuna's Reseed is ...
+ */
+static void random_reseed(struct entropy_store *r) {
+ struct scatterlist sg[1];
+ int i;
+ unsigned char tmp[RANDOM_MAX_DIGEST_SIZE];
+
+ r->reseed_count++;
+
+ crypto_digest_init(r->reseedHash);
+
+ sg[0].page = virt_to_page(r->key);
+ sg[0].offset = offset_in_page(r->key);
+ sg[0].length = r->keysize;
+ crypto_digest_update(r->reseedHash, sg, 1);
+
+#define TESTBIT(VAL, N)\
+ ( ((VAL) >> (N)) & 1 )
+ for (i=0; i<(1<<r->pool_number); i++) {
+ /* using pool[i] if r->reseed_count is divisible by 2^i
+ * since 2^0 == 1, we always use pool[0]
+ */
+ if ( (i==0) || TESTBIT(r->reseed_count,i)==0 ) {
+ crypto_digest_final(r->pools[i], tmp);
+
+ sg[0].page = virt_to_page(tmp);
+ sg[0].offset = offset_in_page(tmp);
+ sg[0].length = r->keysize;
+ crypto_digest_update(r->reseedHash, sg, 1);
+
+ crypto_digest_init(r->pools[i]);
+ /* should each pool carry it's past state forward? */
+ crypto_digest_update(r->pools[i], sg, 1);
+ } else {
+ /* pool N can only be used once every 2^N times */
+ break;
+ }
}
+#undef TESTBIT
+
+ crypto_digest_final(r->reseedHash, r->key);
+ crypto_cipher_setkey(r->cipher, r->key, r->keysize);
+ increment_iv(r->iv, r->blocksize);
}
/*
* 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
+ * returns it in a buffer. If the EXTRACT_ENTROPY_USER
* flag is given, then the buf pointer is assumed to be in user space.
- *
- * 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.
- *
- * 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;
+ __u32 tmp[CRYPTO_MAX_BLOCK_SIZE];
unsigned long cpuflags;
+ struct scatterlist sgiv[1],
+ sgtmp[1];
-
- /* Redundant, but just in case... */
- if (r->entropy_count > r->poolinfo.POOLBITS)
- r->entropy_count = r->poolinfo.POOLBITS;
-
- if (flags & EXTRACT_ENTROPY_SECONDARY)
- xfer_secondary_pool(r, nbytes, tmp);
-
- /* Hold lock while accounting */
+ /* lock while we're reseeding */
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,
- nbytes * 8,
- r == sec_random_state ? "secondary" :
- r == random_state ? "primary" : "unknown");
-
- if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8)
- nbytes = r->entropy_count / 8;
-
- if (r->entropy_count / 8 >= nbytes)
- r->entropy_count -= nbytes*8;
- else
- r->entropy_count = 0;
+ random_reseed(r);
+ r->pool0_len = 0;
- if (r->entropy_count < random_write_wakeup_thresh)
- wake_up_interruptible(&random_write_wait);
+ spin_unlock_irqrestore(&r->lock, cpuflags);
- DEBUG_ENT("%04d %04d : debiting %d bits from %s%s\n",
- random_state->entropy_count,
- sec_random_state->entropy_count,
- nbytes * 8,
- r == sec_random_state ? "secondary" :
- r == random_state ? "primary" : "unknown",
- flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)");
+ /*
+ * don't output any data until we reseed at least once
+ * But this causes problems at boot-time. So weĺl assume since they
+ * don't wait to the PRNG to setup, they don't really new strong random
+ * data
+ */
+ /*
+ if (r->reseed_count == 0)
+ return 0;
+ */
- spin_unlock_irqrestore(&r->lock, cpuflags);
+ sgiv[0].page = virt_to_page(r->iv);
+ sgiv[0].offset = offset_in_page(r->iv);
+ sgiv[0].length = r->blocksize;
+ sgtmp[0].page = virt_to_page(tmp);
+ sgtmp[0].offset = offset_in_page(tmp);
+ sgtmp[0].length = r->blocksize;
ret = 0;
while (nbytes) {
- /*
- * Check if we need to break out or reschedule....
- */
- if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) {
- if (signal_pending(current)) {
- if (ret == 0)
- ret = -ERESTARTSYS;
- break;
- }
+ crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+ increment_iv(r->iv, r->blocksize);
- 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);
- }
-
- /*
- * 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);
+ i = (nbytes < 16) ? nbytes : 16;
if (flags & EXTRACT_ENTROPY_USER) {
i -= copy_to_user(buf, (__u8 const *)tmp, i);
if (!i) {
ret = -EFAULT;
break;
}
- } else
+ } else {
memcpy(buf, (__u8 const *)tmp, i);
+ }
nbytes -= i;
buf += i;
ret += i;
}
+
+ /* generate a new key */
+ /* take into account the possibility that keysize >= blocksize */
+ for (i=0; i+r->blocksize<=r->keysize; i+=r->blocksize) {
+ sgtmp[0].page = virt_to_page( r->key+i );
+ sgtmp[0].offset = offset_in_page( r->key+i );
+ sgtmp[0].length = r->blocksize;
+ crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, 1);
+ increment_iv(r->iv, r->blocksize);
+ }
+ sgtmp[0].page = virt_to_page( r->key+i );
+ sgtmp[0].offset = offset_in_page( r->key+i );
+ sgtmp[0].length = r->blocksize-i;
+ crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, 1);
+ increment_iv(r->iv, r->blocksize);
+
+ if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+ return -EINVAL;
+ }
/* Wipe data just returned from memory */
memset(tmp, 0, sizeof(tmp));
@@ -1482,10 +894,7 @@
*/
void get_random_bytes(void *buf, int nbytes)
{
- if (sec_random_state)
- extract_entropy(sec_random_state, (char *) buf, nbytes,
- EXTRACT_ENTROPY_SECONDARY);
- else if (random_state)
+ if (random_state)
extract_entropy(random_state, (char *) buf, nbytes, 0);
else
printk(KERN_NOTICE "get_random_bytes called before "
@@ -1500,57 +909,16 @@
*
*********************************************************************/
-/*
- * Initialize the random pool with standard stuff.
- *
- * NOTE: This is an OS-dependent function.
- */
-static void init_std_data(struct entropy_store *r)
-{
- struct timeval tv;
- __u32 words[2];
- char *p;
- int i;
-
- do_gettimeofday(&tv);
- words[0] = tv.tv_sec;
- words[1] = tv.tv_usec;
- add_entropy_words(r, words, 2);
-
- /*
- * 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);
- }
-}
-
static int __init rand_initialize(void)
{
- int i;
-
- if (create_entropy_store(DEFAULT_POOL_SIZE, &random_state))
- goto err;
- if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
- goto err;
- if (create_entropy_store(SECONDARY_POOL_SIZE, &sec_random_state))
+ if (create_entropy_store(DEFAULT_POOL_NUMBER, &random_state))
goto err;
- clear_entropy_store(random_state);
- clear_entropy_store(sec_random_state);
- init_std_data(random_state);
+ if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
+ goto err;
+
#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;
return 0;
err:
return -1;
@@ -1559,139 +927,33 @@
void 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) {
- memset(state, 0, sizeof(struct timer_rand_state));
- irq_timer_state[irq] = state;
- }
+ /* we don't use timers anymore, we just use the current time */
}
void rand_initialize_disk(struct gendisk *disk)
{
- struct timer_rand_state *state;
-
- /*
- * If kmalloc returns null, we just won't use that entropy
- * source.
- */
- state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
- if (state) {
- memset(state, 0, sizeof(struct timer_rand_state));
- disk->random = state;
- }
-}
-
-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;
-
- if (nbytes == 0)
- return 0;
-
- while (nbytes > 0) {
- n = nbytes;
- 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);
-
- 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,
- n*8, (nbytes-n)*8);
-
- if (n == 0) {
- if (file->f_flags & O_NONBLOCK) {
- 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);
-
- set_current_state(TASK_INTERRUPTIBLE);
- add_wait_queue(&random_read_wait, &wait);
-
- if (sec_random_state->entropy_count / 8 == 0)
- schedule();
-
- 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;
- }
-
- if (n < 0) {
- retval = n;
- break;
- }
- count += n;
- buf += n;
- nbytes -= n;
- break; /* This break makes the device work */
- /* like a named pipe */
- }
-
- /*
- * If we gave the user some bytes, update the access time.
- */
- if (count)
- file_accessed(file);
-
- return (count ? count : retval);
+ /* we don't use timers anymore, we just use the current time */
}
static ssize_t
urandom_read(struct file * file, char __user * buf,
size_t nbytes, loff_t *ppos)
{
- return extract_entropy(sec_random_state, buf, nbytes,
+ return extract_entropy(random_state, buf, nbytes,
EXTRACT_ENTROPY_USER |
EXTRACT_ENTROPY_SECONDARY);
}
+static ssize_t
+random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
+{
+ return urandom_read(file, buf, nbytes, ppos);
+}
+
static unsigned int
random_poll(struct file *file, poll_table * wait)
{
- unsigned int mask;
-
- 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)
- mask |= POLLIN | POLLRDNORM;
- if (random_state->entropy_count < random_write_wakeup_thresh)
- mask |= POLLOUT | POLLWRNORM;
- return mask;
+ return POLLIN | POLLRDNORM | POLLOUT | POLLWRNORM;
}
static ssize_t
@@ -1701,12 +963,13 @@
int ret = 0;
size_t bytes;
__u32 buf[16];
- const char __user *p = buffer;
+ const char __user *p = buffer;
size_t c = count;
while (c > 0) {
bytes = min(c, sizeof(buf));
+DEBUG_PRINTK("random_write() %p, %p, %u\n", &buf, p, bytes);
bytes -= copy_from_user(&buf, p, bytes);
if (!bytes) {
ret = -EFAULT;
@@ -1730,67 +993,25 @@
random_ioctl(struct inode * inode, struct file * file,
unsigned int cmd, unsigned long arg)
{
- int *tmp, size, ent_count;
- int __user *p = (int __user *)arg;
+ int size, ent_count;
+ int __user *p = (int __user *) arg;
int retval;
- unsigned long flags;
switch (cmd) {
case RNDGETENTCNT:
- ent_count = random_state->entropy_count;
- if (put_user(ent_count, p))
+ if (put_user(random_entropy_count, p))
return -EFAULT;
return 0;
case RNDADDTOENTCNT:
- if (!capable(CAP_SYS_ADMIN))
- return -EPERM;
- if (get_user(ent_count, p))
- return -EFAULT;
- credit_entropy_store(random_state, ent_count);
- /*
- * Wake up waiting processes if we have enough
- * entropy.
- */
- if (random_state->entropy_count >= random_read_wakeup_thresh)
- wake_up_interruptible(&random_read_wait);
+ /* entropy accounting removed. */
return 0;
case RNDGETPOOL:
- if (!capable(CAP_SYS_ADMIN))
- return -EPERM;
- if (get_user(size, p) ||
- put_user(random_state->poolinfo.poolwords, p++))
- return -EFAULT;
- if (size < 0)
- return -EFAULT;
- if (size > random_state->poolinfo.poolwords)
- size = random_state->poolinfo.poolwords;
-
- /* prepare to atomically snapshot pool */
-
- tmp = kmalloc(size * sizeof(__u32), GFP_KERNEL);
-
- if (!tmp)
- return -ENOMEM;
-
- spin_lock_irqsave(&random_state->lock, flags);
- ent_count = random_state->entropy_count;
- memcpy(tmp, random_state->pool, size * sizeof(__u32));
- spin_unlock_irqrestore(&random_state->lock, flags);
-
- if (!copy_to_user(p, tmp, size * sizeof(__u32))) {
- kfree(tmp);
- return -EFAULT;
- }
-
- kfree(tmp);
-
- if(put_user(ent_count, p++))
- return -EFAULT;
-
+ /* jlcooke: never get the raw pool!!! */
return 0;
case RNDADDENTROPY:
if (!capable(CAP_SYS_ADMIN))
return -EPERM;
+ p = (int *) arg;
if (get_user(ent_count, p++))
return -EFAULT;
if (ent_count < 0)
@@ -1801,25 +1022,12 @@
size, &file->f_pos);
if (retval < 0)
return retval;
- credit_entropy_store(random_state, ent_count);
- /*
- * Wake up waiting processes if we have enough
- * entropy.
- */
- if (random_state->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;
+ /* entropy accounting removed. */
return 0;
case RNDCLEARPOOL:
- /* Clear the entropy pool and associated counters. */
- if (!capable(CAP_SYS_ADMIN))
- return -EPERM;
- clear_entropy_store(random_state);
- init_std_data(random_state);
+ /* jlcooke: this is maddness! Never clear the entropy pool */
return 0;
default:
return -EINVAL;
@@ -1875,71 +1083,111 @@
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, &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;
+ int ret;
- sysctl_poolsize = random_state->poolinfo.POOLBYTES;
+ if (write) {
+ /* you can't change the poolsize, but we'll let you think
+ * you can for legacy reasons.
+ */
+ return 0;
+ }
+ sysctl_poolsize = (1<<random_state->pool_number) *
+ random_state->pools[0]->__crt_alg->cra_ctxsize;
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);
+ return ret;
}
-static int poolsize_strategy(ctl_table *table, int __user *name, int nlen,
+static int poolsize_strategy(ctl_table *table, int *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).
+ /* you can't set a poolsize strtegy because it doesn't change in
+ * size anymore
*/
- if (newval && newlen) {
- len = newlen;
- if (len > table->maxlen)
- len = table->maxlen;
- if (copy_from_user(table->data, newval, len))
- return -EFAULT;
+ return 0;
+}
+
+static int proc_derive_seed(ctl_table *table, int write, struct file *filp,
+ void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+ static unsigned char *hextab = "0123456789abcdef";
+ static unsigned int derive_count=0;
+ /* hex length of derived seed */
+ static unsigned char buf[(1<<MAXIMUM_POOL_NUMBER) *
+ RANDOM_MAX_DIGEST_SIZE *8/4];
+ unsigned long flags;
+ ctl_table fake_table;
+ unsigned char tmp[RANDOM_MAX_DIGEST_SIZE];
+ unsigned int i,j;
+ struct scatterlist sg[3];
+ int ret;
+ void *p;
+
+DEBUG_PRINTK("proc_derive_seed() 0\n");
+
+ spin_lock_irqsave(&random_state->lock, flags);
+ random_state->pool0_len = 0;
+
+ memset(buf, 0, random_state->pool_number * 2*random_state->digestsize);
+
+ /* the carry-state from pool to pool */
+ memset(tmp, 0, random_state->digestsize);
+
+ for (i=0; i<(1<<random_state->pool_number); i++) {
+ crypto_digest_init(random_state->reseedHash);
+
+ /*
+ * carry the digest from the previous output so a derive seed
+ * from a lightly seeded state is indistinguishavble from a
+ * heavily seeded one
+ */
+ p = &tmp;
+ sg[0].page = virt_to_page(p);
+ sg[0].offset = offset_in_page(p);
+ sg[0].length = sizeof(tmp);
+
+ /* finalize and digest the i-th pool */
+ crypto_digest_final(random_state->pools[i], tmp);
+ crypto_digest_init(random_state->pools[i]);
+ p = &tmp;
+ sg[1].page = virt_to_page(p);
+ sg[1].offset = offset_in_page(p);
+ sg[1].length = sizeof(tmp);
+
+ /*
+ * digest in a counter to ensure the final hash can change even if the
+ * message does not
+ */
+ p = &derive_count;
+ sg[2].page = virt_to_page(p);
+ sg[2].offset = offset_in_page(p);
+ sg[2].length = sizeof(derive_count);
+
+ crypto_digest_digest(random_state->reseedHash, sg, 3, tmp);
+ for (j=0; j<random_state->digestsize; j++) {
+ buf[2*(i*random_state->digestsize +j) ] = hextab[ (tmp[j] >> 4) & 0xf ];
+ buf[2*(i*random_state->digestsize +j)+1] = hextab[ (tmp[j] ) & 0xf ];
+ }
+ derive_count++;
}
- if (sysctl_poolsize != random_state->poolinfo.POOLBYTES)
- return change_poolsize(sysctl_poolsize);
+ spin_unlock_irqrestore(&random_state->lock, flags);
- return 0;
+ fake_table.data = buf;
+ fake_table.maxlen = (1<<random_state->pool_number) *
+ 2*random_state->digestsize;
+
+ ret = proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
+
+ return ret;
}
+
/*
* 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,
@@ -1975,7 +1223,7 @@
return proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
}
-static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
+static int uuid_strategy(ctl_table *table, int *name, int nlen,
void __user *oldval, size_t __user *oldlenp,
void __user *newval, size_t newlen, void **context)
{
@@ -2011,38 +1259,41 @@
.procname = "poolsize",
.data = &sysctl_poolsize,
.maxlen = sizeof(int),
+ /* you can't change the poolsize, but we'll let you think you
+ * can for legacy reasons.
+ */
.mode = 0644,
.proc_handler = &proc_do_poolsize,
.strategy = &poolsize_strategy,
},
{
- .ctl_name = RANDOM_ENTROPY_COUNT,
- .procname = "entropy_avail",
- .maxlen = sizeof(int),
- .mode = 0444,
- .proc_handler = &proc_dointvec,
- },
+ .ctl_name = RANDOM_ENTROPY_COUNT,
+ .procname = "entropy_avail",
+ .maxlen = sizeof(int),
+ .mode = 0444,
+ .proc_handler = &proc_dointvec,
+ },
{
- .ctl_name = RANDOM_READ_THRESH,
- .procname = "read_wakeup_threshold",
- .data = &random_read_wakeup_thresh,
- .maxlen = sizeof(int),
- .mode = 0644,
- .proc_handler = &proc_dointvec_minmax,
- .strategy = &sysctl_intvec,
- .extra1 = &min_read_thresh,
- .extra2 = &max_read_thresh,
+ .ctl_name = RANDOM_READ_THRESH,
+ .procname = "read_wakeup_threshold",
+ .data = &random_read_wakeup_thresh,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = &proc_dointvec_minmax,
+ .strategy = &sysctl_intvec,
+ .extra1 = &min_read_thresh,
+ .extra2 = &max_read_thresh,
},
{
- .ctl_name = RANDOM_WRITE_THRESH,
- .procname = "write_wakeup_threshold",
- .data = &random_write_wakeup_thresh,
- .maxlen = sizeof(int),
- .mode = 0644,
- .proc_handler = &proc_dointvec_minmax,
- .strategy = &sysctl_intvec,
- .extra1 = &min_write_thresh,
- .extra2 = &max_write_thresh,
+ .ctl_name = RANDOM_WRITE_THRESH,
+ .procname = "write_wakeup_threshold",
+ .data = &random_write_wakeup_thresh,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = &proc_dointvec_minmax,
+ .strategy = &sysctl_intvec,
+ .extra1 = &min_write_thresh,
+ .extra2 = &max_write_thresh,
},
{
.ctl_name = RANDOM_BOOT_ID,
@@ -2061,15 +1312,25 @@
.proc_handler = &proc_do_uuid,
.strategy = &uuid_strategy,
},
+ {
+ .ctl_name = RANDOM_DERIVE_SEED,
+ .procname = "derive_seed",
+ .maxlen = MAXIMUM_POOL_NUMBER * RANDOM_MAX_DIGEST_SIZE,
+ .mode = 0400,
+ .proc_handler = &proc_derive_seed,
+ },
{ .ctl_name = 0 }
};
-static void sysctl_init_random(struct entropy_store *random_state)
+static void sysctl_init_random(struct entropy_store *r)
{
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;
+ random_entropy_count =
+ max_read_thresh =
+ max_write_thresh = (1<<r->pool_number) *
+ r->pools[0]->__crt_alg->cra_ctxsize;
+ random_table[1].data = &random_entropy_count;
}
#endif /* CONFIG_SYSCTL */
@@ -2081,135 +1342,23 @@
/*
* TCP initial sequence number picking. This uses the random number
- * generator to pick an initial secret value. This value is hashed
- * along with the TCP endpoint information to provide a unique
- * starting point for each pair of TCP endpoints. This defeats
- * attacks which rely on guessing the initial TCP sequence number.
- * This algorithm was suggested by Steve Bellovin.
+ * generator to pick an initial secret value. This value is encrypted
+ * with the TCP endpoint information to provide a unique starting point
+ * for each pair of TCP endpoints. This defeats attacks which rely on
+ * guessing the initial TCP sequence number.
*
* Using a very strong hash was taking an appreciable amount of the total
- * TCP connection establishment time, so this is a weaker hash,
- * compensated for by changing the secret periodically.
+ * TCP connection establishment time, so this now uses AES256
+ *
+ * openssl spped md4 aes shows aes256 is 2.5 times faster then basic md4 for
+ * the block sizes we're dealing with.
+ * type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes
+ * md4 10708.72k 38240.96k 111170.47k 215872.85k 296828.93k
+ * aes-128 cbc 32121.81k 32678.31k 33119.49k 33221.29k 33210.59k
+ * aes-192 cbc 27915.92k 27868.52k 28418.08k 28677.12k 28721.15k
+ * aes-256 cbc 24599.57k 25142.38k 25381.80k 25474.88k 25392.46k
*/
-/* F, G and H are basic MD4 functions: selection, majority, parity */
-#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
-#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
-#define H(x, y, z) ((x) ^ (y) ^ (z))
-
-/*
- * The generic round function. The application is so specific that
- * we don't bother protecting all the arguments with parens, as is generally
- * good macro practice, in favor of extra legibility.
- * 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)))
-#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];
-
- /* 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(F, a, b, c, d, in[ 8] + K1, 3);
- ROUND(F, d, a, b, c, in[ 9] + K1, 7);
- ROUND(F, c, d, a, b, in[10] + K1, 11);
- ROUND(F, b, c, d, a, in[11] + 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[ 9] + K2, 3);
- ROUND(G, d, a, b, c, in[11] + K2, 5);
- ROUND(G, c, d, a, b, in[ 0] + K2, 9);
- ROUND(G, b, c, d, a, in[ 2] + K2, 13);
- ROUND(G, a, b, c, d, in[ 4] + K2, 3);
- ROUND(G, d, a, b, c, in[ 6] + K2, 5);
- ROUND(G, c, d, a, b, in[ 8] + K2, 9);
- ROUND(G, b, c, d, a, in[10] + 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[11] + K3, 11);
- ROUND(H, b, c, d, a, in[ 2] + K3, 15);
- ROUND(H, a, b, c, d, in[ 6] + K3, 3);
- ROUND(H, d, a, b, c, in[10] + K3, 9);
- ROUND(H, c, d, a, b, in[ 1] + K3, 11);
- ROUND(H, b, c, d, a, in[ 5] + K3, 15);
- ROUND(H, a, b, c, d, in[ 9] + K3, 3);
- ROUND(H, d, a, b, c, in[ 0] + K3, 9);
- 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 */
- /* Alternative: return sum of all words? */
-}
-#endif
-
-#undef ROUND
-#undef F
-#undef G
-#undef H
-#undef K1
-#undef K2
-#undef K3
/* This should not be decreased so low that ISNs wrap too fast. */
#define REKEY_INTERVAL 300
@@ -2237,79 +1386,70 @@
#define HASH_BITS 24
#define HASH_MASK ( (1<<HASH_BITS)-1 )
-static struct keydata {
- time_t rekey_time;
- __u32 count; // already shifted to the final position
- __u32 secret[12];
-} ____cacheline_aligned ip_keydata[2];
-
static spinlock_t ip_lock = SPIN_LOCK_UNLOCKED;
-static unsigned int ip_cnt;
-static struct keydata *__check_and_rekey(time_t time)
+static __u32 network_random_read32(void)
{
- struct keydata *keyptr;
+ static u8 ctr[16]; /* max block size? */
+ static struct scatterlist sgctr[1];
+ static unsigned int master_count=0;
+ static time_t lastRekey=0;
+
+ struct scatterlist sgtmp[1];
+ unsigned int count;
+ unsigned char tmp[16];
+ struct timeval tv;
+
+ rmb();
spin_lock_bh(&ip_lock);
- keyptr = &ip_keydata[ip_cnt&1];
- if (!keyptr->rekey_time || (time - keyptr->rekey_time) > REKEY_INTERVAL) {
- keyptr = &ip_keydata[1^(ip_cnt&1)];
- keyptr->rekey_time = time;
- get_random_bytes(keyptr->secret, sizeof(keyptr->secret));
- keyptr->count = (ip_cnt&COUNT_MASK)<<HASH_BITS;
+
+ count = ++master_count;
+ increment_iv(ctr, random_state->blocksize);
+
+ do_gettimeofday(&tv);
+ if (lastRekey==0 || (tv.tv_sec - lastRekey) < REKEY_INTERVAL) {
+ lastRekey = tv.tv_sec;
+
+ sgctr[0].page = virt_to_page(ctr);
+ sgctr[0].offset = offset_in_page(ctr);
+ sgctr[0].length = 16;
+
+ if (!random_state->networkCipher_ready) {
+ u8 secret[32]; /* max key size? */
+ get_random_bytes(secret, random_state->keysize);
+ crypto_cipher_setkey(random_state->networkCipher,
+ (const u8*)secret,
+ random_state->keysize);
+ random_state->networkCipher_ready = 1;
+ }
+
mb();
- ip_cnt++;
- }
- spin_unlock_bh(&ip_lock);
- return keyptr;
-}
+ }
-static inline struct keydata *check_and_rekey(time_t time)
-{
- struct keydata *keyptr = &ip_keydata[ip_cnt&1];
+ spin_unlock_bh(&ip_lock);
- rmb();
- if (!keyptr->rekey_time || (time - keyptr->rekey_time) > REKEY_INTERVAL) {
- keyptr = __check_and_rekey(time);
- }
+ sgtmp[0].page = virt_to_page(tmp);
+ sgtmp[0].offset = offset_in_page(tmp);
+ sgtmp[0].length = random_state->blocksize;
+ /* tmp[]/sg[0] = Enc(Sec, CTR++) */
+ crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgctr, 1);
+ increment_iv(ctr, random_state->blocksize);
- return keyptr;
+ /* seq# needs to be random-ish, but incresing */
+ return (tmp[0] & COUNT_MASK) + (count << (32-COUNT_BITS));
}
#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
__u32 secure_tcpv6_sequence_number(__u32 *saddr, __u32 *daddr,
__u16 sport, __u16 dport)
{
- struct timeval tv;
- __u32 seq;
- __u32 hash[12];
- struct keydata *keyptr;
-
- /* The procedure is the same as for IPv4, but addresses are longer.
- * Thus we must use twothirdsMD4Transform.
- */
-
- do_gettimeofday(&tv); /* We need the usecs below... */
- keyptr = check_and_rekey(tv.tv_sec);
-
- memcpy(hash, saddr, 16);
- hash[4]=(sport << 16) + dport;
- memcpy(&hash[5],keyptr->secret,sizeof(__u32)*7);
-
- seq = twothirdsMD4Transform(daddr, hash) & HASH_MASK;
- seq += keyptr->count;
- seq += tv.tv_usec + tv.tv_sec*1000000;
-
- return seq;
+ return network_random_read32();
}
EXPORT_SYMBOL(secure_tcpv6_sequence_number);
__u32 secure_ipv6_id(__u32 *daddr)
{
- struct keydata *keyptr;
-
- keyptr = check_and_rekey(get_seconds());
-
- return halfMD4Transform(daddr, keyptr->secret);
+ return network_random_read32();
}
EXPORT_SYMBOL(secure_ipv6_id);
@@ -2319,75 +1459,20 @@
__u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
__u16 sport, __u16 dport)
{
- struct timeval tv;
- __u32 seq;
- __u32 hash[4];
- struct keydata *keyptr;
-
- /*
- * Pick a random secret every REKEY_INTERVAL seconds.
- */
- do_gettimeofday(&tv); /* We need the usecs below... */
- keyptr = check_and_rekey(tv.tv_sec);
-
- /*
- * 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
- * then mixed with a partial MD4 over random data.
- */
- hash[0]=saddr;
- hash[1]=daddr;
- hash[2]=(sport << 16) + dport;
- hash[3]=keyptr->secret[11];
-
- seq = halfMD4Transform(hash, keyptr->secret) & HASH_MASK;
- seq += keyptr->count;
- /*
- * As close as possible to RFC 793, which
- * suggests using a 250 kHz clock.
- * Further reading shows this assumes 2 Mb/s networks.
- * For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
- * That's funny, Linux has one built in! Use it!
- * (Networks are faster now - should this be increased?)
- */
- seq += tv.tv_usec + tv.tv_sec*1000000;
-#if 0
- printk("init_seq(%lx, %lx, %d, %d) = %d\n",
- saddr, daddr, sport, dport, seq);
-#endif
- return seq;
+ return network_random_read32();
}
EXPORT_SYMBOL(secure_tcp_sequence_number);
-/* The code below is shamelessly stolen from secure_tcp_sequence_number().
- * All blames to Andrey V. Savochkin <saw@msu.ru>.
- */
__u32 secure_ip_id(__u32 daddr)
{
- struct keydata *keyptr;
- __u32 hash[4];
-
- keyptr = check_and_rekey(get_seconds());
-
- /*
- * 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 halfMD4Transform(hash, keyptr->secret);
+ return network_random_read32();
}
#ifdef CONFIG_SYN_COOKIES
/*
* Secure SYN cookie computation. This is the algorithm worked out by
- * Dan Bernstein and Eric Schenk.
+ * Jean-Luc Cooke
*
* 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.
@@ -2396,50 +1481,54 @@
#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];
-
__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;
-
- /*
- * 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;
- }
+ struct scatterlist sg[1];
+ __u32 tmp[4];
/*
* 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.
+ *
+ * Output is the 32bit tag of a CBC-MAC of PT={count,0,0,0} with IV={addr,daddr,sport|dport,sseq}
+ * cookie = <8bit count> || truncate_24bit( Encrypt(Sec, {saddr,daddr,sport|dport,sseq}) )
+ *
+ * DJB wrote (http://cr.yp.to/syncookies/archive) about how to do this with hash algorithms
+ * - we can replace two SHA1s used in the previous kernel with two AESs and make things 3x faster
+ * - I'd like to propose we remove the use of two whittenings with a single operation since we
+ * were only using addition modulo 2^32 of all these values anyways. Not to mention the hashs
+ * differ only in that the second processes more data... why drop the first hash? We did learn
+ * that addition is commutative and associative long ago.
+ * - by replacing two SHA1s and addition modulo 2^32 with encryption of a 32bit value using AES-CTR
+ * we've made it 1,000,000,000 times easier to understand what is going on.
+ * - Todo: we should rekey the cipher peridoically... if we do this, some packets will now fail
+ * our checking system... is this ok? How can we get around this? Rekey's would ideally happen
+ * once per minute (6 million TCP connections per minute is a unrealistic enough security margin)
*/
- 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);
+ tmp[0] = saddr;
+ tmp[1] = daddr;
+ tmp[2] = (sport << 16) + dport;
+ tmp[3] = sseq;
+
+ sg[0].page = virt_to_page(tmp);
+ sg[0].offset = offset_in_page(tmp);
+ sg[0].length = 16;
+ if (!random_state->networkCipher_ready) {
+ u8 secret[32];
+ get_random_bytes(secret, sizeof(secret));
+ if (crypto_cipher_setkey(random_state->networkCipher,
+ secret, random_state->keysize)) {
+ return 0;
+ }
+ random_state->networkCipher_ready = 1;
+ }
+ /* tmp[]/sg[0] = Enc(Sec, {saddr,daddr,sport|dport,sseq}) */
+ crypto_cipher_encrypt(random_state->networkCipher, sg, sg, 1);
- /* Add in the second hash and the data */
- return seq + ((tmp[17] + data) & COOKIEMASK);
+ /* cookie = CTR encrypt of 8-bit-count and 24-bit-data */
+ return tmp[0] ^ ( (count << COOKIEBITS) |
+ (data >> (sizeof(__u32)*8-COOKIEBITS)) );
}
/*
@@ -2454,32 +1543,32 @@
__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;
+ struct scatterlist sg[1];
+ __u32 tmp[4], thiscount, diff;
- if (syncookie_init == 0)
+ if (random_state == NULL || !random_state->networkCipher_ready)
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);
+ tmp[3] = sseq;
+ sg[0].page = virt_to_page(tmp);
+ sg[0].offset = offset_in_page(tmp);
+ sg[0].length = 16;
+ crypto_cipher_encrypt(random_state->networkCipher, sg, sg, 1);
+
+ /* CTR decrypt the cookie */
+ cookie ^= tmp[0];
+
+ /* top 8 bits are 'count' */
+ thiscount = cookie >> COOKIEBITS;
+
+ diff = count - thiscount;
+ if (diff >= maxdiff)
+ return (__u32)-1;
- return (cookie - tmp[17]) & COOKIEMASK; /* Leaving the data behind */
+ /* bottom 24 bits are 'data' */
+ return cookie >> (sizeof(__u32)*8-COOKIEBITS);
}
#endif
next prev parent reply other threads:[~2004-09-24 13:50 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-09-23 23:43 [PROPOSAL/PATCH] Fortuna PRNG in /dev/random Jean-Luc Cooke
2004-09-24 4:38 ` Theodore Ts'o
2004-09-24 12:54 ` Jean-Luc Cooke
2004-09-24 17:43 ` Theodore Ts'o
2004-09-24 17:59 ` Jean-Luc Cooke
2004-09-24 20:44 ` Scott Robert Ladd
2004-09-24 21:34 ` Theodore Ts'o
2004-09-25 14:51 ` Jean-Luc Cooke
2004-09-24 18:43 ` James Morris
2004-09-24 19:09 ` Matt Mackall
2004-09-24 20:03 ` Lee Revell
2004-09-24 13:44 ` Jean-Luc Cooke [this message]
2004-09-27 4:58 ` Theodore Ts'o
[not found] ` <20040927133203.GF28317@certainkey.com>
2004-09-27 14:55 ` Theodore Ts'o
2004-09-27 15:19 ` Jean-Luc Cooke
-- strict thread matches above, loose matches on Subject: below --
2004-09-24 0:59 linux
2004-09-24 2:34 ` Jean-Luc Cooke
2004-09-24 6:19 ` linux
2004-09-24 21:42 ` linux
2004-09-25 14:54 ` Jean-Luc Cooke
2004-09-25 18:43 ` Theodore Ts'o
2004-09-26 1:42 ` Jean-Luc Cooke
2004-09-26 5:23 ` Theodore Ts'o
2004-09-27 0:50 ` linux
2004-09-27 13:07 ` Jean-Luc Cooke
2004-09-27 14:23 ` Theodore Ts'o
2004-09-27 14:42 ` Jean-Luc Cooke
2004-09-26 6:46 ` linux
2004-09-26 16:32 ` Jean-Luc Cooke
2004-09-26 2:31 ` linux
2004-09-27 18:53 Manfred Spraul
2004-09-27 19:45 ` Jean-Luc Cooke
2004-09-28 0:07 ` Theodore Ts'o
2004-09-28 2:24 ` Jean-Luc Cooke
2004-09-28 13:46 ` Herbert Poetzl
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20040924134457.GQ28317@certainkey.com \
--to=jlcooke@certainkey.com \
--cc=linux-kernel@vger.kernel.org \
--cc=tytso@mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.