Re: [PATCH 3/6] random: do extraction before mixing

[Theodore Tso <tytso@mit.edu>]

On Sat, Dec 08, 2007 at 05:20:17PM -0600, Matt Mackall wrote:
> random: do extraction before mixing
> 
> If an attacker manages to capture the current pool state, she can
> determine the last 10 bytes extracted from the pool. 

That's not true; we aren't just extracting data in the
__add_entropy_words() call.  In fact, above that, the bulk of the
extraction comes form when we hash the entire pool, feeding back a
portion of the hash into the pool here:

	for (i = 0; i < r->poolinfo->poolwords; i += 16) {
		/* hash blocks of 16 words = 512 bits */
		sha_transform(buf, (__u8 *)(r->pool + i), buf + 5);
		/* feed back portion of the resulting hash */
		add_entropy_words(r, &buf[i % 5], 1);
	}

So the buf[0..5] contains a hash of the entire pool, and every 16
words, we're already mixing 32 bits into the pool.  So even if the
attacker captures the current pool state, she's not going to be able
to undo the intermediate SHA values that had been mixed into the pool.

> By mixing after
> the extraction, this is made substantially harder.

Not that much harder; as I mentioned as comments in my last patch, we
are doing a linear polynomial mixing for speed purposes, so relying on
the mixing to obscure the extraction isn't going to help much.

But that's OK, we don't need to depend on that.  Note the amount of
feedback that we do in the above loop.

					- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/