Re: [TLS] RNG vs. PRNG

From practical point of view an important difference between RNG and PRNG is that it is (in practice, realistically) impossible to compromise a "true" RNG - its random output is not reproducible, and there's no way to purposefully get the same sequence from it - regardless of what information you come by. Randomness of PRNG output depends on how secret the seed is, and if it (this secret) can be successfully attacked - all the output is compromised. (Assuming both RNG and PRNG are "ideal" - i.e. there's no known way to attack either algorithm or implementation.)

Regards,
Uri

----- Original Message -----
From: tls-bounces@ietf.org <tls-bounces@ietf.org>
To: Michael D'Errico <mike-list@pobox.com>
Cc: tls@ietf.org <tls@ietf.org>
Sent: Tue Apr 27 20:42:03 2010
Subject: Re: [TLS] RNG vs. PRNG

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
_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls