Re: [TLS] RNG vs. PRNG

Marsh Ray <marsh@extendedsubset.com> Wed, 28 April 2010 02:56 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 2F6313A6A80 for <tls@core3.amsl.com>; Tue, 27 Apr 2010 19:56:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.266
X-Spam-Level:
X-Spam-Status: No, score=-0.266 tagged_above=-999 required=5 tests=[AWL=-0.267, 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 0aahGWSf69ja for <tls@core3.amsl.com>; Tue, 27 Apr 2010 19:56:31 -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 3AB4E3A6894 for <tls@ietf.org>; Tue, 27 Apr 2010 19:56:31 -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 1O6xRi-0001vC-A2; Wed, 28 Apr 2010 02:56:18 +0000
Received: from [127.0.0.1] (localhost [127.0.0.1]) by xs01.extendedsubset.com (Postfix) with ESMTP id 0033060B6; Wed, 28 Apr 2010 02:56:15 +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: U2FsdGVkX1948YydRctV61pzqy8jXnZmk8npBoDYfsk=
Message-ID: <4BD7A3CF.8090008@extendedsubset.com>
Date: Tue, 27 Apr 2010 21:56:15 -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: mrex@sap.com
References: <201004280110.o3S1Ag8b017464@fs4113.wdf.sap.corp>
In-Reply-To: <201004280110.o3S1Ag8b017464@fs4113.wdf.sap.corp>
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: Wed, 28 Apr 2010 02:56:32 -0000

On 4/27/2010 8:10 PM, Martin Rex wrote:
> Marsh Ray wrote:
>>
>> 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.
> 
> IANAC, but I would feel very uncomfortable with such a CPRNG.

Me too! It was a thought experiment rather than an actual proposed design.

For example, if somehow the internal state were compromised (say the
hard drive was sold on Ebay) you would not want someone to be able to
work backwards to find all previous values. Using a one-way function for
advancing the state (instead of the simple 'increment' of CTR mode)
accomplishes this (provided all traces of the previous state are destroyed).

> If the CPRNG internal entropy pool has the same size as the
> CPRNG output value, then consecutive output values will have
> an extremely strong correlation, and because of that, it is
> possible, at least in theory to determine the internal state
> from looking at a "comparatively low" number of the output values.

I am continually seeking education on all these points, but my
understanding is that any "correlation" that does not require knowledge
of the secret key represents a noteworthy break in AES-256.

> If, on the other hand, your CPRNG internal entropy pool is at least
> twice as large as the CPRNG output value, and you use a cryptographic
> compression function, then it requires an unrealisticly huge amount of
> consecutive output values before one is theoretically able to determine
> the exact state of the internal entropy pool because of the
> intentional collisions during computation of output values.

If the internal pool is 256 bits, then maybe you only need about that
much output to know the state. Assuming, that is, you have infinite
computing capability or such a great attack on the one-way function that
your work is reduced from 2**256 to something practical.

So I don't think the theoretical minimum needed to determine "the exact
state of the internal entropy pool" is really relevant if it ignores the
actual work it will take.

An analogy is sending 128 characters of ASCII using AES-128. In theory,
the attacker now knows 128 bits of plaintext (the upper bit is always 0)
and he can reliably distinguish the actual secret key among trial
candidate keys. But in practice, the entire design of AES-128 is to
ensure the attacker can do no better than trying all possible keys in
sequential order.

> Btw. I assume it is much easier to gather "the equivalent of 256 bits"
> of real entropy within a 512-bit "entropy pool" than to condense it
> lossless into a 256-bit value.

SHA-256 should do nicely. In theory.

> And if one is a little conservative
> in assessing the amount of entropy, then it probably makes sense
> to use an entropy pool that can hold more than the equivalent of
> 256-bit of real entropy instead of using a container that is
> guaranteed to unconditionally crush spare entropy.

http://linux.die.net/man/4/random
Suggests that Linux uses a 4096-bit pool. Sounds like a healthy safety
factor to me.

- Marsh