Re: [TLS] RNG vs. PRNG

Marsh Ray <marsh@extendedsubset.com> Tue, 27 April 2010 17:19 UTC

Return-Path: <marsh@extendedsubset.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 9E92A3A6B74 for <tls@core3.amsl.com>; Tue, 27 Apr 2010 10:19:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.319
X-Spam-Level:
X-Spam-Status: No, score=-0.319 tagged_above=-999 required=5 tests=[AWL=-0.320, BAYES_50=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 RsAs14YLe++u for <tls@core3.amsl.com>; Tue, 27 Apr 2010 10:19:29 -0700 (PDT)
Received: from mho-01-ewr.mailhop.org (mho-01-ewr.mailhop.org [204.13.248.71]) by core3.amsl.com (Postfix) with ESMTP id 74D4A3A6A11 for <tls@ietf.org>; Tue, 27 Apr 2010 10:19:24 -0700 (PDT)
Received: from xs01.extendedsubset.com ([69.164.193.58]) by mho-01-ewr.mailhop.org with esmtpa (Exim 4.68) (envelope-from <marsh@extendedsubset.com>) id 1O6oRD-0001fo-JN; Tue, 27 Apr 2010 17:19:11 +0000
Received: from [127.0.0.1] (localhost [127.0.0.1]) by xs01.extendedsubset.com (Postfix) with ESMTP id 35CF760B6; Tue, 27 Apr 2010 17:19:10 +0000 (UTC)
X-Mail-Handler: MailHop Outbound by DynDNS
X-Originating-IP: 69.164.193.58
X-Report-Abuse-To: abuse@dyndns.com (see http://www.dyndns.com/services/mailhop/outbound_abuse.html for abuse reporting information)
X-MHO-User: U2FsdGVkX19NXXDp5kCc79eWQcpjHeKa8tE2zDDvpoo=
Message-ID: <4BD71C8D.4050409@extendedsubset.com>
Date: Tue, 27 Apr 2010 12:19:09 -0500
From: Marsh Ray <marsh@extendedsubset.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1.8) Gecko/20100216 Thunderbird/3.0.2
MIME-Version: 1.0
To: Michael D'Errico <mike-list@pobox.com>
References: <Pine.LNX.4.44.1004261355330.14419-100000@citation2.av8.net> <4BD5E3BD.2030605@extendedsubset.com> <4BD5EDB5.50409@pobox.com> <4BD60329.3030403@extendedsubset.com> <4BD6359C.7070008@pobox.com>
In-Reply-To: <4BD6359C.7070008@pobox.com>
X-Enigmail-Version: 1.0.1
OpenPGP: id=1E36DBF2
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Cc: 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: Tue, 27 Apr 2010 17:19:35 -0000

On 4/26/2010 7:53 PM, Michael D'Errico wrote:
> Here are all the places within my code that generate random values 
> and whether they are purely random or pseudo-random (via a CPRNG):

I can't find a definition of 'CPRNG'. I suspect we may be in agreement
but for use of the terminology.

> RNG    generate RSA premaster secrets RNG    generate encryption key
>  and HMAC secret used for session ticket protection
> 
> CPRNG  generate (part of) session IDs CPRNG  generate initialization
>  vectors
> 
> CPRNG  generate hello random values CPRNG  generate random premaster
>  secret in server (as part of defense against Bleichenbacher attack 
> and version rollback detection)
> 
> These last two are debatable.  Marsh would have the hello randoms be
>  purely random, not just unpredictable, and the OpenSSL 
> implementation uses a CPRNG for the last one, but has a note that it 
> /should/ use an RNG.
> 
> IANAC, but wonder why the hello randoms would need to be purely 
> random, versus just unpredictable, since they go over the wire in the
> clear?
> 
> Also, does anyone know why the random premaster secret should be 
> generated with a real RNG versus a CPRNG?

I read the spec as having two types of number generation sequences for
TLS implementations:

1. The pseudo-random function 'PRF'. This gets initialized/seeded with
arbitrary data, but then produces a deterministic sequence.

2. A cryptographic quality random number generator. Every bit output
represents one bit of entropy to an attacker on the network. This is a
nondeterministic sequence from the perspective of everyone outside the
implementation itself, which is not to say that there can be no
deterministic methods used in the generation of the sequence.

Because real hardware entropy sources are typically bandwidth-limited,
typically a sufficient real hardware entropy (say hundreds or thousands
of bits) will be accumulated and used to initialize the generator state.
The generator state is secret, at least as large as the needed
initialization entropy, and is advanced as output is extracted. The use
of real hardware entropy reduces the attacker to just that much brute
force guessing in attempts to find the initial state. Using hundreds of
bits of real hardware entropy makes this impractical.

The random number sequence is extracted from the state using secure
one-way functions such that the observer cannot work backwards to learn
anything about the state from the generated sequence.

In this way, a limited-but-sufficient amount of real hardware entropy
can be expanded to arbitrary length-sequences without concern for
"entropy depletion".

This assumes the chosen one-way function works as designed, or at least
any weaknesses don't affect this usage:

KELS98:
> We will treat MD5 as a random function. While there have been 
> interesting cryptanalytic results on MD5 in the last several years, 
> none of them offer an obvious way to attack the RSAREF PRNG.
> 
> [KELS98] John Kelsey, Bruce Schneier, David Wagner, Chris Hall, 
> Cryptanalytic Attacks on Pseudorandom Number Generators, March 1998, 
> available from <http://www.schneier.com/paper-prngs.html>;.

As an example, initialize an AES-256 block cipher with a perfectly
random 256 bit key. Encrypt successive counter values starting with 0
("CTR mode") to obtain the random output in blocks. Any method by which
one can predict or otherwise distinguish this output stream from "purely
random bits" with less than 2**256 work represents a weakness in AES-256.

If you're using AES-256 for your TLS cipher, and the attacker knows a
weakness in it, then you might have bigger problems than the quality of
your RNG.

- Marsh