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

Nico Williams nico at cryptonector.com
Fri Nov 1 12:11:31 EDT 2013


On Fri, Nov 01, 2013 at 10:17:11AM -0400, Jerry Leichter wrote:
> 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:
> > 
> 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.

Right.  I did not state goals for attack complexity, but clearly 2^64
work factor is in the domain of the feasible for targeted attacks and
not for bulk attacks.  So we should want 2^128 as a baseline.

A high-quality entropy source with 1 bit/s bandwidth will get the host
up to that baseline in just over two minutes of run-time.  Even jitter
alone can provide higher bandwidth than that.  But this highlights the
importance of delaying things like ssh host authentication key
generation (and even ephemeral DH keys) until we have reached that goal.

A blocking-until-properly-seeded-then-non-blocking stretched RNG device
would be very nice to have!  (I manage this on some systems by holding
up boot progress until /dev/random (and urandom) are seeded.)

However, it's not always possible to wait until a very conservative
estimate of entropy reaches 128 bits: some kit might not reach it in
acceptable times.  How conservative to be in this estimate may well have
to be a configuration knob.  It might help to have RNG interfaces that
allow applications to state a mininum entropy requirement, a
/dev/random128, /dev/random512, ... for example.

> [...]
>
> 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.

Yes.  But then you're probably already taking good care to build that
machine with a decent source of entropy + a decent seed just to be sure,
and you might even use network entropy beacons for extra assurance.

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

I deliberately mentioned both nonces and random IVs because both can
be used as subliminal channels to leak RNG outputs.

An attacker might try to get you to run an application that uses RNG
outputs as nonces so they can observe RNG outputs directly.  You might
not notice this in an audit.  Remember, the easiest way for a Dual_EC-
like backdoored RNG to be used cheaply is to use its outputs as TLS
nonces.  This probably means it actually happens somewhere.

Eliminating or minimizing these subliminal channels makes it harder to
attack via the RNG.  Without them the attacker has only a brute-force
search attack -- that might still be feasible (e.g., if the attacker
gets you to use an RNG with very few bits of entropy), depending on your
RNG construction, but eliminating Dual_EC-type attacks is an
improvement.

> 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

Agreed.

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

Right.  That was Perry's suggestion, a few weeks back, for a new cipher
mode construction: transmit a counter (which presumably is checked
against a sequence number window) and use it to derive the random IV for
CBC decryption. 

Nico
-- 


More information about the cryptography mailing list