Re: [TLS] RNG vs. PRNG

[Marsh Ray <[e-mail]>]

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

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
> exhaustively treated before, thus we're just annoying uninterested TLS
> WG list subscribers and wasting our own time.

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


On 5/5/2010 1:28 AM, Nicolas Williams wrote:
> 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.
> 
> On Tue, May 04, 2010 at 11:37:31PM -0400, Blumenthal, Uri - 0668 - MITLL wrote:
>> 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.
> 
> 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.)
> 
>> 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. :-)
> 
> 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.)
> 
>> 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
> 
> True, but:
> 
>> 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.
> 
>> 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.
> 
> 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