[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