implement /margin/ to greatly improve output entropy density

1 files changed, 30 insertions, 0 deletions

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
 };