| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 31 Mar 2020 08:56:59 GMT
From: George Spelvin <lkml@....org>
To: "Theodore Ts'o" <tytso@....edu>
Cc: Andy Lutomirski <luto@...nel.org>,
Yangtao Li <tiny.windzz@...il.com>,
linux-kernel@...r.kernel.org, lkml@....org
Subject: [PATCH 2/3] random: Factor helper calc_entropy_frac() out of
credit_entropy_bits()
The helper is mathematically complex, with a large comment
explaining it. credit_entropy_bits() has atomicity complexity.
Breaking them apart makes both easier to read and understand.
No functional change.
Signed-off-by: George Spelvin <lkml@....org>
---
And it makes the approximation easier to change in the next patch.
drivers/char/random.c | 114 +++++++++++++++++++++++-------------------
1 file changed, 63 insertions(+), 51 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 273dcbb4a790..de90bab5af36 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -653,6 +653,64 @@ static void process_random_ready_list(void)
spin_unlock_irqrestore(&random_ready_list_lock, flags);
}
+/*
+ * Add some new entropy to an existing pool with finite capacity. We have
+ * to account for the possibility of overwriting already present entropy.
+ * Even in the ideal case of pure Shannon entropy, new contributions
+ * approach the pool capacity asymptotically:
+ *
+ * entropy += (capacity - entropy) * (1 - exp(-add/capacity))
+ *
+ * To avoid evaluating an exponential in interrupt context, we use a
+ * simple fixed-point underestimate.
+ *
+ * For add <= capacity/2 then
+ * (1 - exp(-add/capacity)) >= (add/capacity)*0.7869...
+ * so we can approximate the exponential with 3/4*add/capacity and still
+ * be on the safe side by adding at most capacity/2 at a time.
+ */
+static int calc_entropy_frac(int add, int entropy,
+ struct entropy_store const *r)
+{
+ struct poolinfo const *info = r->poolinfo;
+ const int capacity = info->poolfracbits;
+
+ if (add < 0) {
+ /* Debit */
+ entropy += add;
+ } else {
+ const int s = info->poolbitshift + ENTROPY_SHIFT + 2;
+ /* The +2 corresponds to the denominator of the 3/4 */
+
+ do {
+ unsigned int frac = min(add, capacity/2);
+ unsigned int delta = ((capacity - entropy)*frac*3) >> s;
+
+ entropy += delta;
+ add -= frac;
+ } while (unlikely(add) && entropy < capacity-2);
+ /*
+ * Because we're careful to always round down, the pool
+ * will never be completely full. In fact, the maximum
+ * delta is 3/8 of the space remaining, which means that 3
+ * fractional bits remaining will round to +1, but 2 will
+ * round to +0, so there's no sense continuing.
+ *
+ * Stopping at capacity-2 also limits the loop to
+ * log2(pool_size)/log2(5/8) = 1.475*log2(pool_size)
+ * iterations no matter how large add is.
+ */
+ }
+
+ if (WARN_ON(entropy < 0)) {
+ pr_warn("negative entropy/overflow: pool %s count %d\n",
+ r->name, entropy);
+ entropy = 0;
+ } else if (unlikely(entropy > capacity))
+ entropy = capacity;
+ return entropy;
+}
+
/*
* Credit (or debit) the entropy store with n bits of entropy.
* Use credit_entropy_bits_safe() if the value comes from userspace
@@ -661,61 +719,15 @@ static void process_random_ready_list(void)
static void credit_entropy_bits(struct entropy_store *r, int nbits)
{
int entropy_count, orig;
- const int pool_size = r->poolinfo->poolfracbits;
- int nfrac = nbits << ENTROPY_SHIFT;
if (!nbits)
return;
-retry:
- entropy_count = orig = READ_ONCE(r->entropy_count);
- if (nfrac < 0) {
- /* Debit */
- entropy_count += nfrac;
- } else {
- /*
- * Credit: we have to account for the possibility of
- * overwriting already present entropy. Even in the
- * ideal case of pure Shannon entropy, new contributions
- * approach the full value asymptotically:
- *
- * entropy <- entropy + (pool_size - entropy) *
- * (1 - exp(-add_entropy/pool_size))
- *
- * For add_entropy <= pool_size/2 then
- * (1 - exp(-add_entropy/pool_size)) >=
- * (add_entropy/pool_size)*0.7869...
- * so we can approximate the exponential with
- * 3/4*add_entropy/pool_size and still be on the
- * safe side by adding at most pool_size/2 at a time.
- *
- * The use of pool_size-2 in the while statement is to
- * prevent rounding artifacts from making the loop
- * arbitrarily long; this limits the loop to log2(pool_size)*2
- * turns no matter how large nbits is.
- */
- int pnfrac = nfrac;
- const int s = r->poolinfo->poolbitshift + ENTROPY_SHIFT + 2;
- /* The +2 corresponds to the /4 in the denominator */
-
- do {
- unsigned int anfrac = min(pnfrac, pool_size/2);
- unsigned int add =
- ((pool_size - entropy_count)*anfrac*3) >> s;
-
- entropy_count += add;
- pnfrac -= anfrac;
- } while (unlikely(entropy_count < pool_size-2 && pnfrac));
- }
-
- if (WARN_ON(entropy_count < 0)) {
- pr_warn("negative entropy/overflow: pool %s count %d\n",
- r->name, entropy_count);
- entropy_count = 0;
- } else if (entropy_count > pool_size)
- entropy_count = pool_size;
- if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
- goto retry;
+ do {
+ orig = READ_ONCE(r->entropy_count);
+ entropy_count = calc_entropy_frac(nbits << ENTROPY_SHIFT,
+ orig, r);
+ } while (cmpxchg(&r->entropy_count, orig, entropy_count) != orig);
entropy_count >>= ENTROPY_SHIFT; /* Convert to bits */
trace_credit_entropy_bits(r->name, nbits, entropy_count, _RET_IP_);
--
2.26.0
Powered by blists - more mailing lists