[Cryptography] What's a Plausible Attack On Random Number Generation?

[Nico Williams]

I've asked this before and maybe we can make it very short and sweet:

   How hard is an attacker fitting your threat model[*] willing to work
   to attack you via your RNG?

   [*] The person answering this question gets to pick their threat model.

Considering Dual_EC, assuming it's an attack on the wider community (as
opposed to a secret self-key escrow that happens to also escrow other
Dual_EC users' keys)...  the answer appears to be: not too hard.  This
particular attacker, well-funded and all, apparently wanted to have to
see just 32 bytes of RNG output to be able to recover its state with
little effort.

That's NOT evidence that no attacker is willing to work much harder than
that to attack you via your RNG.  But it's suggestive.

Consider RNGs specifically designed to make some attack plausible:

 - Dual_EC-like -> observe small amount of output (plausibly, as TLS
   nonces) and you're done.  Easy.

 - Not like Dual_EC -> might have to observe lots of outputs (less
   plausible without subverting application implementations as well),
   and possibly have to gather data on the victim (e.g., CPUID, ...),
   mount some active attacks, and so on just to get to a brute-force
   search within reach.

   Of course, if the attacker can do some of this off-line, then maybe
   it's not a big deal to them.

   If then can only do this in real-time (e.g., active attacks), then it
   may be too much work (and if the RNG is good enough, infeasibly too
   much) relative to the alternatives:
   
    break in & install keylogger, content yourselve with traffic
    analysis + whatever cleartext you can get a hold of, bribe someone,
    use social engieering, use a rubber hose, ...

Now consider an RNG where there's multiple sources of entropy at least
one of which would be too much work or impossible for the attacker to
compromise in any way, and where the RNG mixes its sources, extracts,
and stretches entropy in cryptographically-secure ways.  In this case
attacking via the RNG is not likely going to be of interest.
Quantifying this will depend on the sources of entropy, but it's easy to
see that with just a few (seed file, RDRAND, jitter, ...) it quickly
becomes impossible for the attacker to use this path.

Note that robustnes (in the sense that got these threads going recently)
is important in this case: assuming the attacker has all initial state
and slowly (better, quickly) loses track of some entropy inputs, then
the attacker should get no meaningful improvement over brute-force for
guessing next RNG outputs.

In other words:

 - be liberal as to entropy sources -- the more the better, at least one
   of them decent,

 - be conservative in wanting as many of them and as much output from
   them as possible while low-balling estimates of total entropy,

 - be conservative as to mixer/pool/extractor/stretcher crypto design,
   not only in /dev/*random, but in apps consuming it as well (to
   protect themselves against a weak /dev/*random).

   (Note that it's not good to constantly poll for new entropy: that
   would be bad for power management.)

This should be clear.

Related tangent: it will also help if we start designing protocols to
need/use fewer nonces (and random IVs) so as to limit subliminal
channels.

Nico
--