Re: [TLS] New drafts: adding input to the TLS master secret

[Eric Rescorla <[e-mail]>]

At Mon, 8 Feb 2010 18:16:53 -0500 (EST),
Dean Anderson wrote:
> 
> On Mon, 8 Feb 2010, Eric Rescorla wrote:
> > > 
> > > I'll see if I can find a better reference.  I think the
> > > cryptographic fact I'm looking for is that a pseudo-random sequence
> > > is compromised by having part of the sequence known.
> > 
> > Well, this isn't true. In fact, it's a basic design requirement of
> > CSPRNGs that this not be so (up to the input entropy of the PRNG). If
> > you have any evidence that the standard PRNGs/PRFs fall significantly
> > short of this requirement, this would be a result worthy of
> > publication in a good conference.
> 
> Actually, it appears to me that it is an unproven assumption of the
> next-bit test. ("it" being that there is no polynomial time algorithm to
> calculate the next bit)  I believe the key phrase is "up to the input
> entropy of the PRNG". If you have enough of the sequence, you can get
> the whole sequence.  The TLS random exposes an essentially unlimited
> amount of the pseudo-random sequence.

Again, this is the distinction between information theoretic security
and security based on complexity-theoretic assumptions.  Effectively
all cryptography (with the exception of one time pads) only offers
security up to at best complexity theoretic bounds.

As a non-PRNG example, given a small number of plaintext/ciphertext
pairs it is in principle possible to derive the AES key that performed
the encryption. However, if this were possible to do in less than
2^{k} operations (where k is the size of the key) than this would
constitute a severe weakness in AES.

Similarly, in principle with unlimited computational power one can
derive the PRNG state from the output, as long as the output is longer
than the PRNG internal state. However, in a properly designed PRNG,
actually reversing the state of the PRNG should be computationally
infeasible. (And given that PRNGs are generally based on 
a similar set of cryptographic primitives [e.g., message digests])
it's not crazy to think that PRNGs indeed do have these properties.
If one has a PRNG which does not meet this property, it would be
better to fix that, rather than worry about all possible ways
in which output could leak.

-Ekr