Subject: Re: [TLS] RNG vs. PRNG

From: Steven Bellovin <[email-masked]>
Date: Tue, 4 May 2010 09:10:36 -0400

On Apr 27, 2010, at 10:22 26PM, Nicolas Williams wrote:

> On Tue, Apr 27, 2010 at 08:54:54PM -0400, Blumenthal, Uri - 0668 - MITLL wrote:
>> From practical point of view an important difference between RNG and
>> PRNG is that it is (in practice, realistically) impossible to
>> compromise a "true" RNG - its random output is not reproducible, and
>> there's no way to purposefully get the same sequence from it -
> 
> But there may be ways to attack the method by which the RNG works so as
> to bias it.  Whereas there's no way to do that for a PRNG.  In general
> it seems best to couple an RNG to a PRNG, using the former to seed and
> periodically replenish the entropy pool of the latter, thus removing
> biases from the RNG stream.

That's right.  Put differently, PRNGs have high behavioral assurance; if they're right, they'll continue to be right.  An RNG can be affected by the environment in all sorts of nasty analog ways.  This is one reason why in the Clipper chip design, the NSA used a PRNG to generate the unit keys.

		--Steve Bellovin, http://www.cs.columbia.edu/~smb

---

From: Dean Anderson <[email-masked]>
Date: Tue, 4 May 2010 21:09:19 -0400 (EDT)

Inline:

> >> there's no way to purposefully get the same sequence from it -

If the RNG is truely random, it can not be biased either.  The bias is
the introduction of a non-random input; and by definition, a true RNG
has no non-random inputs. So a 'biased RNG' is just the discovery that
the device once thought to be an RNG was not one after all.

> That's right.  Put differently, PRNGs have high behavioral assurance;
> if they're right, they'll continue to be right.  An RNG can be
> affected by the environment in all sorts of nasty analog ways.  This
> is one reason why in the Clipper chip design, the NSA used a PRNG to
> generate the unit keys.
> 

Actually, the above is precisely wrong. 

PRNG's have statistical behaviors, as I described in an earlier post.  
However, some PRNGs (with statistically good behavior) have been
successfully analyzed by various methods, most impressively (to me) by
phase space analysis.

This claim by Bellovin's is most definitely not true of PRNGs: "if
they're right, they'll continue to be right".  PRNGs that are 'right'
have been broken in the past.  PRNGs can have bitwise statistical
properties and appear hard to predict, and still be subject to (eg)
phase space analysis.

I suspect the NSA most likely used PRNG's in Clipper because PRNGs were
practical to implement whereas RNGs are not. Or perhaps it was a mistake
altogether; Recall that Clipper was broken.  
http://findarticles.com/p/articles/mi_m0CGN/is_n140/ai_20909989/

It is definitely not because PRNGs can't be biased or analyzed.  Just
look at phase space analysis for DNS servers (BIND and DJBDNS), as well
as similar cracking on the GPS PRNG 'variation' that prevents commercial
units from getting the most accurate readings.  The GPS variation is
programmed into and corrected by military units, but not commercial
units. The 'variation' feature was supposed to prevent our enemies from
getting a super-accurate position.  GPS was broken shortly after 
commercial units became widely available.

		--Dean

-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 256 5494

---

From: "Blumenthal, Uri - 0668 - MITLL" <[email-masked]>
Date: Tue, 4 May 2010 23:37:31 -0400

In general I have to agree with Dean.

True RNG "itself" can't be attacked - though its implementations could
(depending on many circumstances). Attacks against PRNG could be both
cryptanalytic and implementation-directed.

PRNG can't have higher behavioral assurance than RNG because if one can bias
RNG output then the attacker got (or drastically reduced the search space
for) the PRNG seed - and thus can be highly assured of predicted PRNG
output. :-)

Unlike RNG, PRNG security has critical dependence on secrecy of its seed -
in addition to all other concerns (such as algorithm strength, correctness
of implementation, defense - or lack of - against attackers who can lay
hands on the box, etc - some of which are shared with RNG and some are
PRNG-unique). 

PRNGs are so popular because RNG are hard to come by (and those available
typically trickle output bits, and the closer to consumer they are - the
more vulnerable to implementation attacks), and collecting decent amount of
randomness from an RNG is even harder. So naturally hybrid approach is
embraced, when one uses whatever little he can get from a true RNG (if he
can get hold of it) and seeds with it PRNG to get as much of "acceptable"
randomness as necessary.

-- 
Regards,
Uri

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 5 May 2010 01:28:24 -0500

I'm not sure what the point of this sub-thread is.  TLS can't really
mandate that implementations use real RNGs, and I suspect many (myself
included) would object to a requirement that implementors use real RNGs
not coupled with PRNGs (as a bias removal / RNG stream post-processing
technique).  Also, none of this is new; the subject has been
exhaustively treated before, thus we're just annoying uninterested TLS
WG list subscribers and wasting our own time.

> cryptanalytic and implementation-directed.

A true RNG depends on physical processes.  Therefore it can be attacked
by physical means.  Now, the obvious retort is that without physical
security you can't have cryptographic security, and that is true, but
there's degrees of physical access that a device ought to be able to
tolerate.  The simplest thing to do is to couple an RNG to a PRNG.
Other post-processing of RNG outputs to remove bias are also possible.

(Also, one could conceive of RNG devices that can be affected without
direct access.  For example, thermal RNGs might get biased when the
system runs hot.)

> for) the PRNG seed - and thus can be highly assured of predicted PRNG

But the attacker would have to have prolonged physical access to the
RNG, and from the get-go; if at any point the attacker does not then the
attacker loses (assuming a well-constructed entropy pool, mixer and
extractor, which should have PRNG characteristics).

Let's put it this way: what rationale is there to not have a PRNG
coupled to an RNG?  (An "SRNG" in John Denker's terminology[0], but that
term isn't very common.  Even in the "true" RNG that Denker describes
there's still a cryptographic hash function in use.)

> typically trickle output bits, and the closer to consumer they are - the

a trickle of entropy over hours, coupled to a PRNG, can produce decent
results.  Also, I doubt the rate of entropy gathering from sensors is as
low as all that for, say, a cell phone -- maybe for one that just sits
there unused.  And consumer devices have enough ROM and flash storage
that a seed, counter, timestamp, ... can be stored and used to uniquely
seed a PRNG at bootup, which, combined with even a fairly low rate of
entropy gathering results in a system that's more easily attacked via
other vulnerabilities in the very rapidly growing OSes, TCBs and apps
that these devices run.

> can get hold of it) and seeds with it PRNG to get as much of "acceptable"

Consumer devices and desktops don't usually get attacked via PRNG
attacks (except, of course, when the PRNG or seeding process is flawed
and the result is well-known keys, as in the Debian OpenSSL problem from
a while back).  This sub-thread might as well be about how many angels
can dance on a pinhead :)

[0] http://www.av8n.com/turbid/paper/turbid.htm#htoc47

Nico
--

---

From: "Kemp, David P." <[email-masked]>
Date: Wed, 5 May 2010 09:09:36 -0400

-----Original Message-----
From: Dean Anderson

> the device once thought to be an RNG was not one after all.

Sophistry.  A television that has been fried by lightning is still a TV,
albeit a broken one.  A 'biased RNG' may generate no entropy at all, in
which case it is broken.  Or it may generate entropy along with bias
that can be conditioned out.  If I take a true, fully functioning RNG
and add a constant value to every number it produces, the output becomes
biased.  But that bias is easily removed.  Adding zero or a small amount
of entropy to a sequence containing entropy does not remove *any*
entropy from that sequence.

> http://findarticles.com/p/articles/mi_m0CGN/is_n140/ai_20909989/

Speaking from fact rather than uninformed speculation, RNGs are
practical to implement.  

http://csrc.nist.gov/groups/STM/cmvp/documents/140-1/140sp/140sp004.pdf
says:

  12.
     c. Random Number Generator Test: Functional testing of ring
oscillators and
LFSR is performed.

Dave

---

From: Marsh Ray <[email-masked]>
Date: Wed, 05 May 2010 17:02:37 -0500

On 5/5/2010 1:28 AM, Nicolas Williams wrote:
> I'm not sure what the point of this sub-thread is.

The currently language in the spec is broken and misleading to the point
that people (implementers) are unclear about the requirements for
various protocol structures.

> TLS can't really
> included) would object to a requirement that implementors use real
> RNGs not coupled with PRNGs (as a bias removal / RNG stream
> post-processing technique).

It's entirely within the scope of the spec to specify what properties of
various structures (e.g., premaster secret) are required for security.
The current specs do talk about it, but people seem to come away with
different meanings because the terminology is inconsistent.

In the case of client_hello.random and server_hello.random, I believe
that even though they are sent in-the-clear they need to be
crypto-quality unpredictable (and of course reveal no information about
any secret internal state).

> Also, none of this is new; the subject has been

I agree that some of this is a tiny bit annoying, it bugs me that
everyone isn't on the same page with the terminology. I don't understand
why anyone would confuse a raw thermal noise source with a
well-constructed RNG (e.g., a healthy /dev/random), with a deterministic
PRNG (e.g. TLS's PRF), and so on.

Still, it seems pretty important that the next revision of the spec (or
some other IETF document) conveys the requirements clearly enough that
insecure implementations don't get shipped.

- Marsh

---

From: Nicolas Williams <[email-masked]>
Date: Wed, 5 May 2010 17:24:00 -0500

> any secret internal state).

This is really the province of RFC4086/BCP0106.  TLS has no business
having different entropy requirements than other security protocols (set
aside for now the fact that having weak entropy sources will have
varying impact depending on the use).  As such there are better fora
than the TLS WG for this discussion.

In any case, we've not exactly been debating what properties we need for
*RNGs for TLS.  We've instead ratholed into a "true RNGs are better"
"are not" situation.

> everyone isn't on the same page with the terminology. I don't understand

Welcome to the world of... well, this world.

> PRNG (e.g. TLS's PRF), and so on.

We don't have good, standard terminology.  Some people don't mean
PRNG-seeded-with-static-seed-and-maybe-a-counter when they speak of
PRNGs, but others interpret "PRNG" to mean just that and then treat the
first as idiots.  Trouble ensues.  I agree, we need common terminology.

> insecure implementations don't get shipped.

I don't agree.  The next revision, like the current one, should
reference RFC4086, though we might want a normaitive reference instead
of an informative one.  We might also want a standard, rather than just
a BCP, on entropy.  Also, BCP0106 should have a glossary.

Nico
--

---

From: Dean Anderson <[email-masked]>
Date: Thu, 6 May 2010 13:14:47 -0400 (EDT)

> I'm not sure what the point of this sub-thread is.  

The point of the draft is to extend the random bits.  So a question 
related to that is: "Is anything to be gained by having more 'random' 
bits?"  This sub-thread, in part, answers that question.

The real random value is pre_master_secret. The purpose of the 
*Hello.random additions is to ensure a unique master_secret on 
additional channels. These have no contribution to the security of the 
random set chosen for pre_master_secret:

master_secret = PRF(pre_master_secret, "master secret",
                          ClientHello.random + ServerHello.random)
                          [0..47];

The master_secret has 48 bytes, the pre_master_secret has 48 bytes. One 
cannot add "more randomness".  Hence the conclusion is this:

1) One cannot add more "randomness" into the calculation. Either 
pre_master_secret is a true random number or it isn't. 

2) Since the *Hello.random bit set is publicly exposed, using the same 
random generator for these as for pre_master_secret would potentially 
expose the [P]RNG to analysis and thereby expose pre_master_secret as 
well as *Hello.random. If all the inputs to the PRF are known, then 
master_secret is known.

> TLS can't really mandate that implementations use real RNGs

I agree. So we have to assume that some [many] implementers will use 
PRNGs and so exposing these bits to analysis is a very bad thing(tm).

> by physical means.  

Perhaps in principle, the RNG could be tampered with so future bits
aren't random. But the past bits would remain secure. So having a log of
messages encrypted with a true RNG remain unbreakable, even if you
subseqently tamper with the RNG.  This would not be true of a PRNG. Once
you gain the seed, you can compute any output.

> The simplest thing to do is to couple an RNG to a PRNG.

No. A PRNG only generates a subset of the input: equal in size to the
size of the seed. PRNGs reduce entropy to the size of the seed. 

Design Rule: You can't get better than a real RNG. Once you have that,
you can only make it worse. (I suspect that stems from thermodynamics)

		--Dean

---

From: Martin Rex <[email-masked]>
Date: Thu, 6 May 2010 20:36:48 +0200 (MEST)

> > A true RNG depends on physical processes.  Therefore it can be attacked

True RNG values can not be attacked by "guessing" them.
But it is likely possible to make a RNG produce less output values
or output values with less entropy.

Possibilities to collect "true RNG values" is measuring
thermal noise.  While it may appear difficult to influence the
actual physical process, it is usually much easier to impact
the sensor that "measures" the physical process.

A potential means to make an RNG based on thermal noise produce
less entropy is cooling the entire device down.

But maybe it is also possible to trick the sensor, either with an
strong RF signal using a constant-fequency sine wave (contact-less)
or by ultra-sonic motions (i.e with contact).

> size of the seed. PRNGs reduce entropy to the size of the seed. 

I don't think that is generally true.

This would imply that the size of the "loop" depends on the amount
of entropy in the seed -- which is probably wrong.

A PRNG is by design limited to a certain number of internal
states (e.g. size of the entropy pool), and there is a deterministic
correlation between the PRNG output values and the PRNG internal state.

Usually PRNGs modify their internal state each time that a PRNG output
value is requested.

Leaving re-seeding aside, when requesting enough output values,
at some point the output values will start repeating.

Let's say you use a PRNG with 256-bit of internal state.

If you're lucky, and your PRNG has only one single loop, then
output values will repeat after 2^256 extractions.  The seed will
only determine where on this single loop you start.

But if your PRNG has 2^128 loops of length 2^128, then your output
values will start repeating after 2^128 extractions.  The seed will
determine on which of the 2^128 loops you start, but it will not
affect that your output values repeat after 2^128 extractions.

-Martin