[Cryptography] Entropy Attacks!

[Theodore Ts'o]

On Fri, Feb 21, 2014 at 01:18:22AM -0500, John Kelsey wrote:
> 
> This is probably pointless paranoia, since if the CPU you're running
> on is evil, it's probably impossible to get much security.  But
> assuming the Intel RNG is good, seeding your system RNG in this way
> would work just fine.

I'm willing to believe that the Intel RNG might be evil, since it's a
standalone component inside the CPU.  However, compromising the
execution engine such that you can snoop on memory, etc., would
require at least 10x to 100x more engineers to be able to figure out
that the CPU was doing something evil --- only one of which has to be
have the courage and bravery of Snowden to leak the information to the
whole world.

The other thing I'd note about "The Bernstein Attack" is that it
requires O(2**N) work to reduce the key strength by N bits.  That is,
suppose you have a 256 bit AES random session key.  Using his algorithm:

1. Generate a random r.
2. Try computing H(x,y,r).
3. If H(x,y,r) doesn't start with bits 0000, go back to step 1.
4. Output r as z.

Reduces the effective strength of the key to 252 bits, at the cost of
taking 16 times as long to generate the session key.  In order to
reduce the strength of the random session key to be 128 bits, the work
factor would be 2**128!

In other words, this is a straightforward brute force attack, where
you can shift some amount of the work from Fort Meade to the victim
CPU.  This is not what I would call exciting, since given the amount
of effort and the number of engineers you would have to suborn inside
Intel, and the corresponding risk of destroying one of US's larger
tech companies, and compare it to the possible benefit to the NSA, it
just isn't worth it.

The NSA could get much better bang for its buck by suborning someone
inside a certifying authority.  Give what we know of some of the
"mistakes" made by CA's, perhaps they may have done so already, and
those were really failed operations that couldn't be kept secret.

Cheers,

						- Ted