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

[Dean Anderson <[e-mail]>]

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.

I don't assert any revelation about PRNG properties. I think all I have
discovered is that in TLS, one can get an essentially unlimited amount
of the PRNG sequence by mere snooping (no decryption).  The
already-known properties of pseudo-random sequences are that one can
compute the whole sequence given knowledge of an unlimited amount of the
sequence because they are not random.

The tests on for "cryptographic security" of PRBG are complicated, but
roughly summarized as based on statistical expectations for the next bit
in the sequence. The 'next-bit' test posits that there are no polynomial
time algorithms for calculating the next bit.  But this is assumed, not
proven property. It was also assumed to be true of Linear Feedback Shift
Registers, but was found false.  There is nothing that proves the PRNG
isn't predictable if you can see a whole lot of its sequence, or that
calculating the next bit is computationally infeasible given a lot of
sequence.

>From "Handbook of Applied Cryptography" Section 5.1.1 on Pseudo Random
Bit Generators:

  "The output of a PRBG is not random; in fact the number of possible
  output sequences is at most a small fraction 2^k/2^l, of all possible
  binary sequences of length l."

So one can see, as l gets larger with k constant, the fraction of all
output sequences gets smaller.  The pre_master_secret is 384 bits and
the Random value is presently 256 bits. So the random exposes 40% of the
sequence.  Paul's proposal increases the exposure. That seems like a bad
idea.  Exposing any part of the sequence seems like a bad idea.

Full enumeration of the PRBG is probably infeasible. But it is not clear
that full enumeration is necessary to predict the sequence. It wasn't
necessary to have very much of the sequence for LFSR.  It may indeed
prove to be computationally infeasible, but it not proven so far.  Some
generators may be better than others. Or not. Not so long ago, linear
feedback shift registers were thought to be computationally infeasible
to break and were the stream cipher for GSM, but then that was
discovered to be wrong, and that calculation was really pretty easy.

When all we need are unique master_secrets across sessions, this seems
like an unnecessary risk.  Why not alter TLS to require a different
pseudo-random sequence generator for Random values?

		--Dean


-- 
Av8 Internet   Prepared to pay a premium for better service?
www.av8.net         faster, more reliable, better service
617 256 5494