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, 05 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 --
- Re: [TLS] RNG vs. PRNG Blumenthal, Uri - 0668 - MITLL
- Re: [TLS] RNG vs. PRNG Nicolas Williams
- Re: [TLS] RNG vs. PRNG Marsh Ray
- Re: [TLS] RNG vs. PRNG Steven Bellovin
- Re: [TLS] RNG vs. PRNG Dean Anderson
- Re: [TLS] RNG vs. PRNG Blumenthal, Uri - 0668 - MITLL
- Re: [TLS] RNG vs. PRNG Nicolas Williams
- Re: [TLS] RNG vs. PRNG Kemp, David P.
- Re: [TLS] RNG vs. PRNG Marsh Ray
- Re: [TLS] RNG vs. PRNG Nicolas Williams
- Re: [TLS] RNG vs. PRNG Dean Anderson
- Re: [TLS] RNG vs. PRNG Martin Rex