Re: [TLS] RNG vs. PRNG

Martin Rex <mrex@sap.com> Wed, 28 April 2010 01:11 UTC

Return-Path: <mrex@sap.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 7D1B13A6A77 for <tls@core3.amsl.com>; Tue, 27 Apr 2010 18:11:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.072
X-Spam-Level:
X-Spam-Status: No, score=-8.072 tagged_above=-999 required=5 tests=[AWL=-0.423, BAYES_50=0.001, HELO_EQ_DE=0.35, RCVD_IN_DNSWL_HI=-8]
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 K6CUCEOny1Ud for <tls@core3.amsl.com>; Tue, 27 Apr 2010 18:11:01 -0700 (PDT)
Received: from smtpde03.sap-ag.de (smtpde03.sap-ag.de [155.56.68.140]) by core3.amsl.com (Postfix) with ESMTP id 364443A6A6A for <tls@ietf.org>; Tue, 27 Apr 2010 18:10:59 -0700 (PDT)
Received: from mail.sap.corp by smtpde03.sap-ag.de (26) with ESMTP id o3S1AhoR007178 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 28 Apr 2010 03:10:43 +0200 (MEST)
From: Martin Rex <mrex@sap.com>
Message-Id: <201004280110.o3S1Ag8b017464@fs4113.wdf.sap.corp>
To: marsh@extendedsubset.com (Marsh Ray)
Date: Wed, 28 Apr 2010 03:10:42 +0200 (MEST)
In-Reply-To: <4BD71C8D.4050409@extendedsubset.com> from "Marsh Ray" at Apr 27, 10 12:19:09 pm
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Scanner: Virus Scanner virwal07
X-SAP: out
Cc: tls@ietf.org
Subject: Re: [TLS] RNG vs. PRNG
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
Reply-To: mrex@sap.com
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 01:11:06 -0000

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.

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.

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.

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

-Martin