Re: [TLS] RNG vs. PRNG

Martin Rex <mrex@sap.com> Wed, 28 April 2010 00:42 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 1E0373A680E for <tls@core3.amsl.com>; Tue, 27 Apr 2010 17:42:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.125
X-Spam-Level:
X-Spam-Status: No, score=-8.125 tagged_above=-999 required=5 tests=[AWL=-0.476, 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 L7LhQWb8HH2G for <tls@core3.amsl.com>; Tue, 27 Apr 2010 17:42:21 -0700 (PDT)
Received: from smtpde03.sap-ag.de (smtpde03.sap-ag.de [155.56.68.140]) by core3.amsl.com (Postfix) with ESMTP id EBD563A63EB for <tls@ietf.org>; Tue, 27 Apr 2010 17:42:20 -0700 (PDT)
Received: from mail.sap.corp by smtpde03.sap-ag.de (26) with ESMTP id o3S0g5ik024470 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 28 Apr 2010 02:42:05 +0200 (MEST)
From: Martin Rex <mrex@sap.com>
Message-Id: <201004280042.o3S0g4Co015823@fs4113.wdf.sap.corp>
To: mike-list@pobox.com (Michael D'Errico)
Date: Wed, 28 Apr 2010 02:42:03 +0200 (MEST)
In-Reply-To: <4BD6359C.7070008@pobox.com> from "Michael D'Errico" at Apr 26, 10 05:53:48 pm
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Scanner: Virus Scanner virwal06
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 00:42:22 -0000

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):
> 
>      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 am not a cryptographer either, but I believe that it should
be OK to use CPRNG output for all of the uses in TLS, provided
the CPRNG starts with a sufficiently large seed (like the
equivalent of 128+ bits of real entropy) and an sufficiently
large internal pool size (256+ bits) and peridical addition
of fresh entropy to the pool.

Concerning the terminology:

  RNG   supposedly stands for a random number generator that produces
        consecutive output values that are completely uncorrelated


  CPRNG  "cryptographic pseudo random number generator"
        supposedly stands for unpredictable random values
        that are mathematically correlated to the internal
        state of the CPRNG -- which reproduces in a mathematical
        correlation of consecutive CPRNG output values.
        Output values are normally derived with a compression function
        from a significantly larger internal state in a cryptographically
        secure fashion so that it is mathematically infeasible to
        determine the internal state of the CPRNG even for a larger
        sequence of output values, but some correlation remains.

If randomness is needed for the creation of cryptographic keying
material that is larger than the CPRNG output value, then a
concatenation of consecutive CPRNG output values may leave tiny
white spots in the resulting keyspace, caused by the intrinsic
correlation of consecutive CPRNG output values.

Increasing the size of the internal CPRNG state likely reduces the
area of white spots in the resulting keyspace of concatenated
CPRNG output values.  Concatenating more CPRNG output values will
likely increases the area of white spots.

Although it might be extremely difficult to limit
a brute force keyspace search to the non-white areas for
a 3072 DSA or 4096 RSA keypair generated from concatenated
CPRNG instead of concatenated RNG output values.

For the premaster-secret and master-secret computations with
the help of the PRF, I'm more concerned about the overall
entropy than about correlation between concatenated CPRNG
output values (unless, of course, the CPRNG internal state
and output value sizes are patheticalls small (like 128/64 bits).


-Martin