[Cryptography] PRNG WYTM

John Denker jsd at av8n.com
Sat Oct 19 14:21:15 PDT 2013


On 10/19/2013 09:55 AM, Sandy Harris wrote:
 
> Mixing in the clock makes a machine behave a bit
> differently each time it is rebooted.  Again, there
> are better fixes such as mixing in a saved file, but
> again this is still worth doing.
> 
> These are reasonably cheap and done only once
> at boot time. They can do no harm and are useful
> in at least some cases, so worth doing.

OK, the next step in any such discussion is to ask the
famous question, What's Your Threat Model (WYTM).

Several different reasonable answers are possible.

1) At one extreme, we have the "no threat at all" model,
aka the "non-adversarial" model.  Examples include
 *) Doing a Monte Carlo integral in the context of 
  a molecular dynamics calculation.  The molecules 
  are not going to attack our PRNG.  They are not 
  going to cryptanalyze it.  Almost any PRNG is
  "random enough" for this purpose.
 *) Cooperative situations, such as friendly computers
  on a LAN, doing random exponential backoff as part
  of the layer-1 Ethernet CSMA/CD.  Everybody has a
  shared interest in implementing the protocol properly,
  so even if they could break the PRNG they wouldn't
  want to.
 *) Et cetera.  There are tons of examples in this 
  category.

A PRNG in category (1) could be considered "random" but 
not "secure".  It is usually adequate to seed this type 
of PRNG with things like the MAC address, serial number, 
and time-of-day.


2) At the opposite extreme we have high-stakes adversarial
applications, including military cryptography, banking,
other high-value business communications, high-stakes
gaming, etc. etc. etc.  A PRNG in this category needs to
be *secure* against a wide range of threats.

For tasks in this category, seeding the PRNG with things 
like the MAC address, serial number, and time-of-day is
nowhere near good enough.  It is a band-aid or worse.
It is security theater.  It gives you "randomness" in 
some weak sense, but it does not give you security.

The typical modern PRNG in this category consists of a
seed, a counter, a hash function, and a reseeding
mechanism.  Sometimes there is a block cipher in there 
somewhere, but to a sufficient approximation this is 
the same basic architecture, just with a fancier hash 
function.

So let's look in more detail at the threats against such
a PRNG.

*) For starters we have the threat of direct cryptanalysis
of the output.  If the preimage can be found, all further
outputs will be known to the attacker, and probably 
all past outputs as well, over the span bounded by the 
nearest past and present reseedings.

The feasibility of finding a preimage depends on the 
number of bits output by the PRNG.  Therefore there
should be a limit on the number of output bits between
reseedings.

*) Another type of threat is more indirect.  For example,
suppose the PRNG was seeded at boot time from the saved
random-seed file.  It may be possible for the attacker 
to find this, perhaps by sneaking a peek at an old backup 
tape or whatever.  Such a threat is independent of the 
number of bits emitted by the PRNG.  It is hard to say 
what it /does/ depend on, but in the absence of anything 
better, wall-clock time is a plausible proxy.  Therefore 
there should be a time limit on how long a seed file is 
allowed to remain on disk before it is regenerated, and 
a time limit between reseedings of the PRNG.

On 10/19/2013 01:37 PM, James A. Donald wrote:
> 
> Any system that needs crypto, communicates.  Any system that
> communicates, sees events whose details are difficult to predict for
> anyone not in physical possession of the system.
> 
> Solution:  Block for a short period after startup.  Possibly a small
> number of systems will freeze up and fail to boot.  This is almost
> always fixable by moving the blocking process in the bootup so that
> it no longer blocks other processes while it is blocked waiting for
> /dev/urandom, while /dev/urandom is blocked waiting for entropy.

That might be a "solution" in certain favorable cases, but
it is nowhere near being a reliable, general solution.  I
can think of five failure modes in five minutes.  Perhaps
the most obvious is this:  Suppose my system is sitting in
a rack at some colocation provider.  All the attacker needs
to do is rent a box in the same rack, on the same LAN
segment.  Then he knows my MAC address, the time at which
I booted up, and (to a good approximation) the arrival time
of every network packet addressed to me.

Similarly for my laptop on the corporate wifi network.  The
bad guy in the loft across the street has a nontrivial
chance of figuring out everything he needs to know about 
my network traffic.  If anybody has a proof that this
cannot happen, please explain.

Here's the only thing that has ever made sense to me:
 a) Any device that wants to have any security whatsoever
  needs to be able to store a seed, even when powered off.
 b) The seed needs to be provisioned on a per-device
  basis, much like the MAC address is provisioned.
 c) The seed needs to be big enough, randomly-chosen, and 
  secret, very unlike the MAC address, RTC, and device 
  serial number.

_______________________________________________
The cryptography mailing list
cryptography at metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography



More information about the cypherpunks mailing list