random.c bugfix

Hi,

there's a bug in random.c, I think. The third argument of extract_entropy() is supposed to be the number of _bytes_ to extract, while nwords contains the number of _bytes_ we want. This seems to lead us to transfer n bytes of entropy and credit for n*4 bytes.

René

@@ -1253,7 +1253,7 @@
 			  r == sec_random_state ? "secondary" : "unknown",
 			  r->entropy_count, nbytes * 8);
 
-		extract_entropy(random_state, tmp, nwords, 0);
+		extract_entropy(random_state, tmp, nwords * 4, 0);
 		add_entropy_words(r, tmp, nwords);
 		credit_entropy_store(r, nwords * 32);
 	}

                                       ^^^^^ words, I think you mean ;-)

OK, my bad. At least the random variable-name cleanups let you SEE where we are supposed to be using word sizes and byte sizes. Even you were confused about it ;-)

I went over your original patch good; I am surprised I missed this. :/ Nonetheless, only with the new cleanups could anyone spot this.

I think I prefer your sizeof() method, if for nothing else but that we can keep it consistent -- we can always take the sizeof a variable and not everything has its size in a define.

Furthermore, sizeof(tmp) certainly means "size of the variable temp" while TMP_BUF_SIZE could be the size of anything related to tmp -- the buffer it points to (if it were a pointer), a buffer in it (if it were a struct), etc. Since it all compiles to the same, it is not a huge issue. Just my two bits...

...but I'm not Alan or Linus ;)

Robert Love

Andreas Dilger <[email protected]> said:

[...]

I have now seen various bits and pieces about this flying around. To get it right will be hard, as over/under estimates will show up only under unusual circumstances; and as you _can't_ really know how much "entropy" there should be, testing this is very hard. So the only way to get it right is make it "obviously" right.

How hard would it be to change the API to talk _all_ in the same units, be it bits, bytes, words, or whatever? I believe bits or bytes would be best, as word sizes differ. Bytes have the advantage that a simple sizeof() will give size in bytes for any random variable.

Horst von Brand                             [email protected]
Casilla 9G, Vin~a del Mar, Chile                               +56 32 672616

Yes, I have suspected the same thing. When testing these changes, I almost always got 9-12 bits of entropy per keypress, and hundreds of bits for a mouse movement. Granted, it may be reasonable given that I have a TSC, which implies nearly random low order bits, but you would think that mouse interrupts are at a fairly standard rate, so should have low entropy?

I left discussion about the actual entropy DATA out of my patch, and focussed only on getting the accounting right. We still "discard" some entropy in places, but it is orders of magnitude smaller than before, and discarding entropy is not a danger, unless you are forced to use less-secure data as a result of not having enough entropy.

Not too hard (basic patch below). This has the drawback of passing a byte count to add_entropy(), but still using a word array for values. It wouldn't be too hard to change add_entropy() to accept a byte array (which we cast internally to a word array, don't really care about endian issues here), and then do something* with any extra bytes. As it is, add_entropy() "uses" the unset bytes at the end of the last word if we are called from random_write(). We also can't make credit_entropy_store() use bytes as a parameter, so we haven't totally fixed the problem.

(*) I don't know enough about the hash functions to know how to add a
few odd bytes into the store in a useful and safe way. We don't really want to discard them either - think if a user-space random daemon on an otherwise entropy-free system only writes one byte at a time...

The second patch (incremental to the first) changes poolwords to poolbytes in all places, but still doesn't fix add_entropy() to handle a byte array as input.

Cheers, Andreas
==========================================================================

@@ -557,13 +553,13 @@
  * 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(struct entropy_store *r, const __u32 *in, int nbytes)
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
 	unsigned i;
+	int nwords = nbytes / 4;
 	int new_rotate;
 	int wordmask = r->poolinfo.poolwords - 1;
 	__u32 w;

@@ -693,7 +689,7 @@
 							sec_random_state;
 			max_entropy = r->poolinfo.POOLBITS;
 		}
-		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
+		add_entropy(r, batch_entropy_pool + 2*batch_tail, 8);
 		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
 		batch_tail = (batch_tail+1) & (batch_max-1);
 	}

@@ -1245,24 +1241,24 @@
 
 	if (r->entropy_count < nbytes * 8 &&
 	    r->entropy_count < r->poolinfo.POOLBITS) {
-		int nwords = min(r->poolinfo.poolwords - r->entropy_count/32,
-				 sizeof(tmp) / 4);
+		int cbytes = min(r->poolinfo.POOLBYTES - r->entropy_count/8,
+				 sizeof(tmp));
 
 		DEBUG_ENT("xfer %d from primary to %s (have %d, need %d)\n",
-			  nwords * 32,
+			  cbytes * 8,
 			  r == sec_random_state ? "secondary" : "unknown",
 			  r->entropy_count, nbytes * 8);
 
-		extract_entropy(random_state, tmp, nwords, 0);
-		add_entropy_words(r, tmp, nwords);
-		credit_entropy_store(r, nwords * 32);
+		extract_entropy(random_state, tmp, cbytes, 0);
+		add_entropy(r, tmp, cbytes);
+		credit_entropy_store(r, cbytes * 8);
 	}
 	if (r->extract_count > 1024) {
 		DEBUG_ENT("reseeding %s with %d from primary\n",
 			  r == sec_random_state ? "secondary" : "unknown",
 			  sizeof(tmp) * 8);
 		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, sizeof(tmp) / 4);
+		add_entropy(r, tmp, sizeof(tmp));
 		r->extract_count = 0;
 	}
 }

@@ -1343,7 +1339,7 @@
 		 */
 		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);
+			add_entropy(r, &tmp[x%HASH_BUFFER_SIZE], 4);
 		}
 		
 		/*

@@ -1418,7 +1414,7 @@
 	do_gettimeofday(&tv);
 	words[0] = tv.tv_sec;
 	words[1] = tv.tv_usec;
-	add_entropy_words(r, words, 2);
+	add_entropy(r, words, sizeof(words));
 
 	/*
 	 *	This doesn't lock system.utsname. However, we are generating

@@ -1427,7 +1423,7 @@
 	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);
+		add_entropy(r, words, sizeof(words));
 		p += sizeof(words);
 	}
 }

@@ -1596,7 +1591,7 @@
 		c -= bytes;
 		p += bytes;
 
-		add_entropy_words(random_state, buf, (bytes + 3) / 4);
+		add_entropy(random_state, buf, bytes);
 	}
 	if (p == buffer) {
 		return (ssize_t)ret;

@@ -1747,8 +1742,8 @@
 	if ((ret = create_entropy_store(poolsize, &new_store)))
 		return ret;
 
-	add_entropy_words(new_store, random_state->pool,
-			  random_state->poolinfo.poolwords);
+	add_entropy(new_store, random_state->pool,
+		    random_state->poolinfo.POOLBYTES);
 	credit_entropy_store(new_store, random_state->entropy_count);
 
 	sysctl_init_random(new_store);

============================================================================

--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Andreas Dilger <[email protected]> said:

[...]

I'm no expert either, but padding with anything (zeroes?) to get the right length should be safe, no?

Dr. Horst H. von Brand                Usuario #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

No. A 4-byte accumulator is the right answer. We have to be careful here though - the actual entropy might be in the partial words, we have to account for it conservatively.

--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."

In a large majority of the cases, there are only full-word entropy additions. The only time we need to deal with sub-word additions is from random_write() and from the equivalent ioctl. It also appears that we do this when filling the secondary pool, but that is OK because we periodically dump far more entropy into the secondary pool than we could possibly lose through rounding errors.

Having an accumulator would only handle a rarely-used corner case. We could just as easily fix any user-space entropy daemon to write at least 4 bytes at a time. Alternately, we could "pad" with enough bytes from the random pool, and not accumulate at all.

In any case, this is in the noise compared to not using the input data at all (which I fixed in the other patch).

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

They're not rounding errors per se though. This is what I mean by conservative accounting. If you have three extra bytes, you must assume that they're worth a full 24 bits of entropy. Throwing them away is fairly expensive.

Padding -from the pool- is acceptable (and simple enough a slow path to add to the low-level function). Padding with constants is bad and padding with zeros tends to be really bad.

Any of this made it into recent kernels yet? Backport to 2.2 might be a good idea too..

--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."

I would rather fix this at the caller and not in the low-level code, because a large majority of the callers (esp. on the fast path) only use full word inputs. Even for the random_write() case, we would only need this at most a single time per write, instead of once per "hunk" (=64 bytes). What I have done is to accumulate bytes in random_write() until we get a full word.

Well, I just saw that the "in++" and "nwords * 4" patches went into -pre4. These are the only real non-cosmetic parts of what has been sent. The other patches were not officially submitted to Linus yet (using bytes as parameters, and removing poolwords from the struct). I have reverted those patches in my tree, and gone back to using words as units for add_entropy(), since it doesn't make sense to take bytes as a parameter and then require a multiple of 4 bytes for input sizes.

The following patch changes random_write() to accumulate partial words. It should apply against any recent kernel, and assumes the two "byte" patches I previously sent out are not applied. Haven't had a chance to test it yet, but it compiles.

Cheers, Andreas
===========================================================================

@@ -1576,34 +1576,56 @@
 }
 
 static ssize_t
-random_write(struct file * file, const char * buffer,
-	     size_t count, loff_t *ppos)
+random_write(struct file *file, const char *buffer, size_t count, loff_t *ppos)
 {
+	static char	save[4];
+	static int	nsave = 0;
 	int		ret = 0;
-	size_t		bytes;
-	__u32 		buf[16];
-	const char 	*p = buffer;
-	size_t		c = count;
+	const __u32	*p = (__u32 *)buffer;
+	size_t		w = count / 4;
+	int		tail = count & 3;
+	int		extra = 0;
+
+	while (w > 0) {
+		size_t		words;
+		__u32		buf[16];
 
-	while (c > 0) {
-		bytes = MIN(c, sizeof(buf));
+		words = min(w, sizeof(buf) / 4);
 
-		bytes -= copy_from_user(&buf, p, bytes);
-		if (!bytes) {
+		if (copy_from_user(buf, p, words * 4)) {
 			ret = -EFAULT;
-			break;
+			goto out;
 		}
-		c -= bytes;
-		p += bytes;
+		w -= words;
+		p += words;
 
-		add_entropy_words(random_state, buf, (bytes + 3) / 4);
+		add_entropy_words(random_state, p, words);
+	}
+
+	/* Accumulate partial words until we get a full word for addition */
+	while (tail) {
+		int bytes = min(tail, 4 - nsave);
+
+		if (copy_from_user(save + nsave, (char *)p + extra, bytes)) {
+			ret = -EFAULT;
+			goto out;
+		}
+		nsave += bytes;
+		extra += bytes;
+		tail -= bytes;
+
+		if (nsave >= 4) {
+			add_entropy_words(random_state, (__u32 *)save, 1);
+			nsave = 0;
+		}
 	}
-	if (p == buffer) {
+out:
+	if (p == (__u32 *)buffer && extra == 0) {
 		return (ssize_t)ret;
 	} else {
 		file->f_dentry->d_inode->i_mtime = CURRENT_TIME;
 		mark_inode_dirty(file->f_dentry->d_inode);
-		return (ssize_t)(p - buffer);
+		return (ssize_t)((p - (__u32 *)buffer) * 4 + extra);
 	}
 }
 

--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Note that the 2.2 kernel code is (AFAIK) quite different from the 2.4 kernel code for drivers/char/random.c. The serious bug - not incrementing "in" was introduced in 2.3.16. The other real bug - trunctating the pool entropy to the number of words in the pool, does not exist in 2.2. It correctly compares it agains POOLBITS.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Oops, ouch. Thanks for catching the in++ bug; I can't believe that remained unnoticed for so long.

Could you send me a pointer to the proposed change to remove poolwords from the struct? I'm not sure why that wwould be a good thing at all.

Also, the reason why add_entropy_words did stuff in multiple of 4 bytes was simply because it made the code much more efficient. Zero-padding isn't a problem, since it's perfectly safe to mix in zero bytes into the pool. It is an issue for the entropy credit calculation, but that's completely separate from add_entropy_words()....

- Ted

No point - I reverted them and will not use them. The goal was to simplify the "unit" issue in random.c becuase the previous bug about truncating "entropy_count" to "poolwords" instead of "poolbits" was caused specifically by a misunderstanding about the unit sizes of function parameters.

add_entropy_words -> words == 4 bytes
credit_entropy_store -> bits
extract_entropy -> bytes

What I have done instead of changing "poolwords" to "poolbytes" everywhere, is rename "credit_entropy_store" to "credit_entropy_bits" and rename the struct field "entropy_count" to "entropy_bits".

I didn't disagree with that at all. All that I tried (and ended up not using) was to change all the word units to be bytes. The algorithm was not changed. In the end, one of the reasons to not use it was that it introduced a few cases where we scaled a variable value instead of a constant value, and introduced a small run-time overhead. It also didn't make sense to pass a byte value to add_entropy_words() and then restrict it to being a multiple of 4. Ugh.

Well, Oliver tends to disagree. I don't know enough either way. It _does_ seem bad that if you wrote continually wrote 1-byte values into /dev/random and padded out the end of the word that it would be bad. However, in the end this is no worse than cat /dev/zero > /dev/random, which is also allowed.

The only place were we submit non-word-sized values to add_entropy_words() is in random_write(), and I fixed that to accumulate bytes until we have a full word to mix in. One possible "optimization" that could be done in that function is instead of copy_from_user(), we could use verify_area() instead, directly add any fully-aligned words into the pool, and then "accumulate" any misaligned or partial words. This saves us a memcpy() of all the data being written into /dev/random, but whether the performance improvement is noticable on this non-fast-path is important is questionable. Another question is whether "rounding" a char pointer to a multiple of 4 is legal/portable. Maybe I'll put in a comment and wait until someone else wants to do it...

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

That was just conservatism on my part. There are a large number of hashes and ciphers for which zero inputs are suboptimal so my gut feel was that it was a bad idea. That was silly of me, given the way the mixing works.

--
"Love the dolphins," she advised him. "Write by W.A.S.T.E.."

                ********** LATE BREAKING NEWS ***********

Is add_entropy_words() broken for multi-word input??? That would be very bad. In one most cases we are only dealing with two word inputs, but is really bad where it counts - transferring values to the secondary pool, which is where we really get data from for /dev/random.

It appears that we repeatedly add the first word to the entropy pool, no matter how many words are passed!!! I checked the kernel CVS repository, and it has been like this since a big change in 2.3.16. Ugh!!!

http://innominate.org/cgi-bin/lksr/linux/drivers/char/random.c.diff?r1=1.1.1.4&r2=1.1.1.5&cvsroot=v2.3

Is there something I'm missing? Even in the 2.3.16 version, we never change "in" from its initial value, so we only use the first input word. The older (2.2, 2.3.15-) code had it correct, in that it explicitly worked on both of the input words.

A quick patch to fix this is below.

Cheers, Andreas

PS: what's up with new_rotate? Why not just do it like:

	r->input_rotate = (r->input_rotate + (i ? 7 : 14)) & 31;

===========================================================================

@@ -564,7 +564,7 @@
 	__u32 w;
 
 	while (nwords--) {
-		w = rotate_left(r->input_rotate, *in);
+		w = rotate_left(r->input_rotate, *in++);
 		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/