Re: Concurrent access to /dev/urandom

[Matt Mackall <mpm@selenic.com>]

On Fri, Dec 10, 2004 at 04:28:15PM -0500, Theodore Ts'o wrote:
> On Fri, Dec 10, 2004 at 10:28:04AM -0800, Matt Mackall wrote:
> > 
> > Fair enough. s/__add/mix/, please.
> > 
> 
> Why?  Fundamentally, it's all about adding entropy to the pool.  I
> don't have an strong objection to calling it __mix_entropy_words, but
> if we're going to change it, we should change the non-__ variant for
> consistency's sake, and I'd much rather do that in a separate patch if
> we're going to do it all.  I don't see the point of the rename,
> though.

I suppose I don't really care. The __add is no longer just add, and
mix was the word that came to mind. But it doesn't really describe it
well either.

> Still, I'd feel better if we did initialize more data via
> init_std_data(), and then cranked the LFSR some number of times so
> that we don't have to worry about analyzing the case where a good
> portion of the pool might contain consecutive zero values.  But yeah,
> we can save that for another patch, as it's not absolutely essential.
> 
> Are we converging here?

I'm gonna call this last iteration done. Repasted below for akpm's
benefit. Urgency: medium-ish.

---

This patch fixes a problem where /dev/urandom can return duplicate
values when two processors read from it at the same time.  It relies
on the fact that we already are taking a lock in add_entropy_words(),
and atomically hashes in some freshly mixed in data into the returned
randomness.

Signed-off-by: Matt Mackall <mpm@selenic.com>
Signed-off-by: Theodore Ts'o <tytso@mit.edu>

--- 1.60/drivers/char/random.c	2004-11-18 17:23:14 -05:00
+++ edited/drivers/char/random.c	2004-12-10 16:26:51 -05:00
@@ -572,8 +572,8 @@ static void free_entropy_store(struct en
  * 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 void __add_entropy_words(struct entropy_store *r, const __u32 *in,
+				int nwords, __u32 out[16])
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
@@ -626,9 +626,23 @@ static void add_entropy_words(struct ent
 	r->input_rotate = input_rotate;
 	r->add_ptr = add_ptr;
 
+	if (out) {
+		for (i = 0; i < 16; i++) {
+			out[i] = r->pool[add_ptr];
+			add_ptr = (add_ptr - 1) & wordmask;
+		}
+	}
+
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
+static inline void add_entropy_words(struct entropy_store *r, const __u32 *in,
+				     int nwords)
+{
+	__add_entropy_words(r, in, nwords, NULL);
+}
+
+
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
@@ -1342,7 +1356,7 @@ static ssize_t extract_entropy(struct en
 			       size_t nbytes, int flags)
 {
 	ssize_t ret, i;
-	__u32 tmp[TMP_BUF_SIZE];
+	__u32 tmp[TMP_BUF_SIZE], data[16];
 	__u32 x;
 	unsigned long cpuflags;
 
@@ -1422,7 +1436,15 @@ static ssize_t extract_entropy(struct en
 			HASH_TRANSFORM(tmp, r->pool+i);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
-		
+
+		/*
+		 * To avoid duplicates, we atomically extract a
+		 * portion of the pool while mixing, and hash one
+		 * final time.
+		 */
+		__add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1, data);
+		HASH_TRANSFORM(tmp, data);
+
 		/*
 		 * In case the hash function has some recognizable
 		 * output pattern, we fold it in half.


-- 
Mathematics is the supreme nostalgia of our time.