Re: [TLS] RNG vs. PRNG

"Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu> Wed, 05 May 2010 03:38 UTC

Return-Path: <prvs=2741269883=uri@ll.mit.edu>
X-Original-To: tls@core3.amsl.com
Delivered-To: tls@core3.amsl.com
Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 3165F3A6774 for <tls@core3.amsl.com>; Tue, 4 May 2010 20:38:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.998
X-Spam-Level:
X-Spam-Status: No, score=-3.998 tagged_above=-999 required=5 tests=[BAYES_50=0.001, RCVD_IN_DNSWL_MED=-4, UNPARSEABLE_RELAY=0.001]
Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vup6UaOGfHXv for <tls@core3.amsl.com>; Tue, 4 May 2010 20:37:59 -0700 (PDT)
Received: from mx1.ll.mit.edu (MX1.LL.MIT.EDU [129.55.12.45]) by core3.amsl.com (Postfix) with ESMTP id 5B9A43A63EB for <tls@ietf.org>; Tue, 4 May 2010 20:37:59 -0700 (PDT)
Received: from LLE2K7-HUB02.mitll.ad.local (LLE2K7-HUB02.mitll.ad.local) by mx1.ll.mit.edu (unknown) with ESMTP id o453bXXL025432; Tue, 4 May 2010 23:37:33 -0400
From: "Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu>
To: Dean Anderson <dean@av8.com>, Steven Bellovin <smb@cs.columbia.edu>
Date: Tue, 4 May 2010 23:37:31 -0400
Thread-Topic: [TLS] RNG vs. PRNG
Thread-Index: Acrr76YCj/3DFas4SWGfA+xOTENxNQAFKSkj
Message-ID: <C806603B.A3E9%uri@ll.mit.edu>
In-Reply-To: <Pine.LNX.4.44.1005042046390.29670-100000@citation2.av8.net>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-Entourage/13.4.0.100208
acceptlanguage: en-US
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=1.12.8161:2.4.5, 1.2.40, 4.0.166 definitions=2010-05-04_15:2010-02-06, 2010-05-04, 2010-05-04 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 ipscore=0 phishscore=0 bulkscore=0 adultscore=0 classifier=spam adjust=0 reason=mlx engine=5.0.0-1004140000 definitions=main-1005040216
Cc: "'tls@ietf.org'" <tls@ietf.org>
Subject: Re: [TLS] RNG vs. PRNG
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 05 May 2010 03:38:01 -0000

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.


On 5/4/10  21:09 , "Dean Anderson" <dean@av8.com> wrote:

> 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

-- 
Regards,
Uri