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

[Theodore Tso <tytso@mit.edu>]

On Sun, Dec 09, 2007 at 11:05:20AM -0600, Matt Mackall wrote:
> Ahh, but this an attack on the output! You know only:
> 
>  pool' (including a fortuitously placed add_ptr)
> 
> and from that, you can get all but 64 bits of pool. By 2**64 iterations of:
> 
>  pool = pool' + guess
>  hash = SHA1(init, pool) # simplified
>  pool^ = add(pool, hash)
>  if pool^ = pool':
>   success!

Yes, you're right.  I thought O(2**64) shortcut attack required
knowledge of the output to unwind an interation, but looking again at
the paper, I was incorrect.  You can indeed roughly half of the time,
be able to go backwards in O(2**64) operations, instead of O(2**96)
operations.  Note BTW, that if you assume that you can do SHA in 11
cycles per second (source: http://www.cryptopp.com/benchmarks.html)
and this requires you to hash approximatly half the pool, 11 cycles *
64 bytes * 2^64 operations is approximately 190.7 *centuries* assuming
a 2 gigahertz processor.  Obviously that's much better than 7 million
*millenia* (i.e., 7 billion years) for O(2**96), but 190,669 years is
quite a long time. 

I suppose if the NSA had 20,000 2Ghz processors in the basement
cranking for 10 years, then 50% of the time *after* they did a black
bag job to crack the random pool state, they could get the last 80
bits generated from /dev/random, but it just seems that if you are
assuming the power to grab the pool plus add_ptr, there would be much
more useful things you could --- like for example having the black bag
job trojaning the software to grab the private key directly.

So, I still view this as an academic weakness, and not a real-life
threat.  :-)

> Let's do that. But let's also do this because it makes the code more
> readable and somewhat stronger (for instance the first word fed back
> will be cascaded from the whole pool rather than the first 512 bits).
> We also only need to grab the lock once.

Yeah, fair enough.  Mixing in the whole hash doesn't actually cost
that much more.  It might have a theoretical chance of potentially
losing slightly more entropy, but that is really a theoretical issue
as well --- and the fact that we are mixing in the time each time we
extract more than makes up for that.  Oh, wait.  Right, I forgot, you
took that out at some point after you took over maintainership.

Can you add this patch, too?  (Compile tested, not boot tested, but
it's pretty obviously correct.)

							- Ted


commit 499aa1b63923ff8a2309b3a1eccacb54db159c58
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Mon Dec 10 08:35:53 2007 -0500

    random: Mix in the time of extraction into the entropy pool
    
    We don't actually add any entropy credit, but we do mix in the time of
    extraction to add further jitter and make life harder for an attacker
    by making the extraction process time-dependent.  This means that any
    attacks on the /dev/random pool can't use a static analysis.
    
    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 5fee056..b05f05c 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -767,6 +767,14 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 {
 	int i;
 	__u32 data[16], buf[5 + SHA_WORKSPACE_WORDS];
+	struct {
+		cycles_t cycles;
+		long jiffies;
+	} sample;
+
+	sample.jiffies = jiffies;
+	sample.cycles = get_cycles();
+	add_entropy_words(&input_pool, (u32 *)&sample, sizeof(sample)/4);
 
 	sha_init(buf);
 	/*