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

Eric Rescorla <ekr@networkresonance.com> Tue, 09 February 2010 03:34 UTC

Return-Path: <ekr@networkresonance.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 8175C3A74A6 for <tls@core3.amsl.com>; Mon, 8 Feb 2010 19:34:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.018
X-Spam-Level:
X-Spam-Status: No, score=0.018 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_COM=0.553, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.1]
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 M4t1F-ep3YLt for <tls@core3.amsl.com>; Mon, 8 Feb 2010 19:34:54 -0800 (PST)
Received: from kilo.networkresonance.com (74-95-2-169-SFBA.hfc.comcastbusiness.net [74.95.2.169]) by core3.amsl.com (Postfix) with ESMTP id B85443A6B3D for <tls@ietf.org>; Mon, 8 Feb 2010 19:34:54 -0800 (PST)
Received: from kilo.local (localhost [127.0.0.1]) by kilo.networkresonance.com (Postfix) with ESMTP id 659516E7D95; Mon, 8 Feb 2010 19:38:06 -0800 (PST)
Date: Mon, 08 Feb 2010 19:38:02 -0800
From: Eric Rescorla <ekr@networkresonance.com>
To: Dean Anderson <dean@av8.com>
In-Reply-To: <Pine.LNX.4.44.1002081632060.17664-100000@citation2.av8.net>
References: <20100208204426.01C756E7CFA@kilo.networkresonance.com> <Pine.LNX.4.44.1002081632060.17664-100000@citation2.av8.net>
User-Agent: Wanderlust/2.15.5 (Almost Unreal) Emacs/22.3 Mule/5.0 (SAKAKI)
MIME-Version: 1.0 (generated by SEMI 1.14.6 - "Maruoka")
Content-Type: text/plain; charset=US-ASCII
Message-Id: <20100209033806.659516E7D95@kilo.networkresonance.com>
Cc: tls@ietf.org, Paul Hoffman <paul.hoffman@vpnc.org>
Subject: Re: [TLS] New drafts: adding input to the TLS master secret
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.9
Precedence: list
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: Tue, 09 Feb 2010 03:34:55 -0000

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