Re: [TLS] RNG vs. PRNG

[Marsh Ray <[e-mail]>]

On 4/26/2010 7:53 PM, 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):

I can't find a definition of 'CPRNG'. I suspect we may be in agreement
but for use of the terminology.

> 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 read the spec as having two types of number generation sequences for
TLS implementations:

1. The pseudo-random function 'PRF'. This gets initialized/seeded with
arbitrary data, but then produces a deterministic sequence.

2. A cryptographic quality random number generator. Every bit output
represents one bit of entropy to an attacker on the network. This is a
nondeterministic sequence from the perspective of everyone outside the
implementation itself, which is not to say that there can be no
deterministic methods used in the generation of the sequence.

Because real hardware entropy sources are typically bandwidth-limited,
typically a sufficient real hardware entropy (say hundreds or thousands
of bits) will be accumulated and used to initialize the generator state.
The generator state is secret, at least as large as the needed
initialization entropy, and is advanced as output is extracted. The use
of real hardware entropy reduces the attacker to just that much brute
force guessing in attempts to find the initial state. Using hundreds of
bits of real hardware entropy makes this impractical.

The random number sequence is extracted from the state using secure
one-way functions such that the observer cannot work backwards to learn
anything about the state from the generated sequence.

In this way, a limited-but-sufficient amount of real hardware entropy
can be expanded to arbitrary length-sequences without concern for
"entropy depletion".

This assumes the chosen one-way function works as designed, or at least
any weaknesses don't affect this usage:

KELS98:
> We will treat MD5 as a random function. While there have been 
> interesting cryptanalytic results on MD5 in the last several years, 
> none of them offer an obvious way to attack the RSAREF PRNG.
> 
> [KELS98] John Kelsey, Bruce Schneier, David Wagner, Chris Hall, 
> Cryptanalytic Attacks on Pseudorandom Number Generators, March 1998, 
> available from <http://www.schneier.com/paper-prngs.html>.

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.

- Marsh