From 3195d27811a6e8a43925ca28004f29bf6ecbb823 Mon Sep 17 00:00:00 2001 From: John Denker Date: Sun, 20 Oct 2013 13:26:36 -0700 Subject: implement /margin/ to greatly improve output entropy density --- drivers/char/random.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) diff --git a/drivers/char/random.c b/drivers/char/random.c index 0275a98..7637412 100644 --- a/drivers/char/random.c +++ b/drivers/char/random.c @@ -146,6 +146,35 @@ * possibility. Nonetheless, a pseudorandom distribution of numbers * should be useful for a wide range of purposes. + * Low-entropy case; startup transient + * =================================== + + * The following applies to the input pool. + + * Scenario #1: Suppose the pool starts out with all zeros, or in some + * other state that the attacker knows or could readily guess. This + * is a definite possibility immediately after startup. If we add N=8 + * bits of entropy to the pool and then extract one 8-bit byte, that + * byte will have an entropy of approximately 7.18 bits, as can be + * verified by Monte Carlo integration over the ensemble. That is an + * entropy density of just under 90%, which we consider too low. + + * Scenario #2: Same as above, except that we load 18 bits before + * extracting the first byte. In other words, there is 10 bits of + * /margin/. Then the first byte will contain 7.99935 bits. That is + * an entropy density of 99.992%, which should be acceptable for a + * wide range of purposes. + + * The idea of margin extends to larger N. Let's keep the margin at + * 10 bits. If we load 16+10 = 26 bits into the pool before + * extracting the first two bytes, the output entropy will be + * approximately 15.9993 bits. The entropy density will be + * approximately 99.996%. Again, you can verify this by Monte Carlo + * integration over the ensemble. + + * The margin is easily implemented by initializing the entropy_count + * of the input pool to a negative number. + * Strategy for reseeding the PRNG * =============================== * @@ -658,6 +687,7 @@ static struct Pool input_pool = { .name = "input", .blockable = 1, .lock = __SPIN_LOCK_UNLOCKED(input_pool.lock), + .entropy_count = -10, .pooldata = input_pool_data }; -- cgit v1.2.3