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

[Jerry Leichter]

On Nov 1, 2013, at 1:20 AM, Nico Williams <nico at cryptonector.com> wrote:
> 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.
> 
> 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....
These are good points.  I would, however, suggest an alternate axis of differentiation:  Targeted vs. bulk attacks.  In practice, the two axes are highly correlated:  Even the NSA can't afford to pay $10^4 per attack if it needs to attack 10^7 targets.  However, for a high-value target, paying $10^6 would likely be seen as cheap.

An interesting point along this line:  The easiest machine to target is one that's just been imaged.  But it's generally extremely difficult to know which brand new machines will prove to be valuable in the future!  So attacks on newly-imaged machines will have to have fairly low costs to be worth doing.

Note, however, the "generally".  If, for example, you have a subnet reserved for your "most secure, highest value" machines, booting a new machine onto that network is telegraphing its future value, thus making attacking it worth much more.

> 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.
An excellent point - but be careful of the terminology here.  In careful terminology, a random value must be unpredictable to any opponent, while a nonce simply needs to never be repeated within a given cryptographic context.  Using a nonce where a random value is needed makes an otherwise-secure protocol insecure.  Using a random number where all that's needed is a nonce wastes what is, in some contexts, a precious commodity.  Also, nonces computed in a deterministic, documented way cannot be used as subliminal channels - and you can check that they follow the rules.  There's no way, even in principle, to check that a random value isn't being used as a subliminal channel.

                                                        -- Jerry