Re: [TLS] RNG vs. PRNG

Martin Rex <mrex@sap.com> Thu, 06 May 2010 18:37 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 C65033A6A42 for <tls@core3.amsl.com>; Thu, 6 May 2010 11:37:12 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -7.879
X-Spam-Level:
X-Spam-Status: No, score=-7.879 tagged_above=-999 required=5 tests=[AWL=-0.230, 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 TuD9QIhwl-sC for <tls@core3.amsl.com>; Thu, 6 May 2010 11:37:12 -0700 (PDT)
Received: from smtpde01.sap-ag.de (smtpde01.sap-ag.de [155.56.68.171]) by core3.amsl.com (Postfix) with ESMTP id 983503A69A0 for <tls@ietf.org>; Thu, 6 May 2010 11:37:11 -0700 (PDT)
Received: from mail.sap.corp by smtpde01.sap-ag.de (26) with ESMTP id o46Iann7005700 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 6 May 2010 20:36:49 +0200 (MEST)
From: Martin Rex <mrex@sap.com>
Message-Id: <201005061836.o46IamDe006444@fs4113.wdf.sap.corp>
To: dean@av8.com (Dean Anderson)
Date: Thu, 6 May 2010 20:36:48 +0200 (MEST)
In-Reply-To: <Pine.LNX.4.44.1005061259060.30940-100000@citation2.av8.net> from "Dean Anderson" at May 6, 10 01:14:47 pm
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Scanner: Virus Scanner virwal05
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: Thu, 06 May 2010 18:37:12 -0000

Dean Anderson wrote:
> 
> > > 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.  

True RNG values can not be attacked by "guessing" them.
But it is likely possible to make a RNG produce less output values
or output values with less entropy.

Possibilities to collect "true RNG values" is measuring
thermal noise.  While it may appear difficult to influence the
actual physical process, it is usually much easier to impact
the sensor that "measures" the physical process.

A potential means to make an RNG based on thermal noise produce
less entropy is cooling the entire device down.

But maybe it is also possible to trick the sensor, either with an
strong RF signal using a constant-fequency sine wave (contact-less)
or by ultra-sonic motions (i.e with contact).

> 
> 
> > The simplest thing to do is to couple an RNG to a PRNG.
> 
> No. A PRNG only generates a subset of the input: equal in size to the
> size of the seed. PRNGs reduce entropy to the size of the seed. 

I don't think that is generally true.

This would imply that the size of the "loop" depends on the amount
of entropy in the seed -- which is probably wrong.

A PRNG is by design limited to a certain number of internal
states (e.g. size of the entropy pool), and there is a deterministic
correlation between the PRNG output values and the PRNG internal state.

Usually PRNGs modify their internal state each time that a PRNG output
value is requested.

Leaving re-seeding aside, when requesting enough output values,
at some point the output values will start repeating.

Let's say you use a PRNG with 256-bit of internal state.

If you're lucky, and your PRNG has only one single loop, then
output values will repeat after 2^256 extractions.  The seed will
only determine where on this single loop you start.

But if your PRNG has 2^128 loops of length 2^128, then your output
values will start repeating after 2^128 extractions.  The seed will
determine on which of the 2^128 loops you start, but it will not
affect that your output values repeat after 2^128 extractions.


-Martin