Re: [TLS] RNG vs. PRNG

[Dean Anderson <[e-mail]>]

Inline:

On Tue, 4 May 2010, Steven Bellovin wrote:

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

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.

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


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