Re: [PATCH 4/6] random: make backtracking attacks harder

[Theodore Tso <tytso@mit.edu>]

On Sat, Dec 08, 2007 at 05:20:38PM -0600, Matt Mackall wrote:
> random: make backtracking attacks harder
> 
> At each extraction, we change (poolbits / 16) + 32 bits in the pool,
> or 96 bits in the case of the secondary pools. Thus, a brute-force
> backtracking attack on the pool state is less difficult than breaking
> the hash. In certain cases, this difficulty may be is reduced to 2^64
> iterations.

OK, a backtracking attack assumes a fairly catastrophic case where the
attacker has managed to compromise the internal pool state.  In Linux,
if an attacker has this much access, in most scenarios the attacker
probably has the ability to gain write access to kernel memory as
well, at which point you have far worse problems.

The definition of a backtracking attack is when the attacker uses the
current pool state to try to recover the last entropy extraction.  As
you point out, at each extraction, 96 bits are changed in the pool.
But at each extraction, only 80 bits are extracted.

If you are trying to find the value of the 80 bits that were
extracted, and you know the current state of the pool, yes, you can
take the 96 bits that were changed after the last extraction, and try
all possible 2**96 combinations of the bits; but you probably won't
rule anything out, since after you iterate over all of the 2**96
combinations, you'll probably be able to generate all of the 2**80
possible output bits.  So you won't gain anything by trying to do a
backtracking attack.  So I don't think there's anything to worry about
here.

What you describe in your comments:

> +	 * We mix the hash back into the pool to prevent backtracking
> +	 * attacks (where the attacker knows the state of the pool
> +	 * plus the current outputs, and attempts to find previous
> +	 * ouputs), unless the hash function can be inverted. By
> +	 * mixing at least a SHA1 worth of hash data back, we make
> +	 * brute-forcing the feedback as hard as brute-forcing the
> +	 * hash.
>  	 */

.... sounds like not a backtracking attack, but an Iterative guessing
attack, where "knowledge of internal state at some point and the
intervening PRNG outputs, to learn internal state at a later point
when the inputs collected during this span of time are guessable by
the attacker."  (Definition taken from:
http://www.ee.oulu.fi/research/ouspg/frontier/sota/whitepaper-prng/)

But note first of all, all this lets you do is unwind to an earlier
state just before the known PRNG outputs.  In order to use this to
guess PRNG output, you still have to solve the above mentioned
backtracking attack --- where you have 96 bits that changed, and 80
possible extraction bits.  

Secondly, the fact that we use catastrophic reseeding means that even
if the state was compromised, at some point in time, every so often
when we do a "catastrophic reseed", this acts as a firewall to limit
the damage caused by a internal state exposure, both in the past and
the future.

						- 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/