Re: [TLS] RNG vs. PRNG

Nicolas Williams <Nicolas.Williams@oracle.com> Wed, 05 May 2010 06:29 UTC

Return-Path: <Nicolas.Williams@oracle.com>
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 C6E623A67A3 for <tls@core3.amsl.com>; Tue, 4 May 2010 23:29:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.392
X-Spam-Level:
X-Spam-Status: No, score=-1.392 tagged_above=-999 required=5 tests=[AWL=-1.394, BAYES_50=0.001, 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 F+bUEQry3yCO for <tls@core3.amsl.com>; Tue, 4 May 2010 23:29:10 -0700 (PDT)
Received: from rcsinet10.oracle.com (rcsinet10.oracle.com [148.87.113.121]) by core3.amsl.com (Postfix) with ESMTP id 5D2673A6AEC for <tls@ietf.org>; Tue, 4 May 2010 23:29:09 -0700 (PDT)
Received: from rcsinet13.oracle.com (rcsinet13.oracle.com [148.87.113.125]) by rcsinet10.oracle.com (Switch-3.4.2/Switch-3.4.1) with ESMTP id o456Sfn0019434 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 5 May 2010 06:28:42 GMT
Received: from acsmt354.oracle.com (acsmt354.oracle.com [141.146.40.154]) by rcsinet13.oracle.com (Switch-3.4.2/Switch-3.4.1) with ESMTP id o44IlXZo028429; Wed, 5 May 2010 06:28:40 GMT
Received: from abhmt012.oracle.com by acsmt354.oracle.com with ESMTP id 215097531273040910; Tue, 04 May 2010 23:28:30 -0700
Received: from oracle.com (/129.153.128.104) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Tue, 04 May 2010 23:28:29 -0700
Date: Wed, 5 May 2010 01:28:24 -0500
From: Nicolas Williams <Nicolas.Williams@oracle.com>
To: "Blumenthal, Uri - 0668 - MITLL" <uri@ll.mit.edu>
Message-ID: <20100505062823.GW9429@oracle.com>
References: <Pine.LNX.4.44.1005042046390.29670-100000@citation2.av8.net> <C806603B.A3E9%uri@ll.mit.edu>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <C806603B.A3E9%uri@ll.mit.edu>
User-Agent: Mutt/1.5.20 (2010-03-02)
X-Auth-Type: Internal IP
X-Source-IP: rcsinet13.oracle.com [148.87.113.125]
X-CT-RefId: str=0001.0A090206.4BE1101B.0078:SCFMA4539811,ss=1,fgs=0
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 06:29:12 -0000

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