Re: [TLS] PRF in 1.3

Andy Lutomirski <luto@amacapital.net> Tue, 29 July 2014 18:45 UTC

Return-Path: <luto@amacapital.net>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 65D7D1A0547 for <tls@ietfa.amsl.com>; Tue, 29 Jul 2014 11:45:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Level:
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id LQNDsVHbTAlm for <tls@ietfa.amsl.com>; Tue, 29 Jul 2014 11:45:02 -0700 (PDT)
Received: from mail-pa0-f41.google.com (mail-pa0-f41.google.com [209.85.220.41]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 03D6A1A02DD for <tls@ietf.org>; Tue, 29 Jul 2014 11:45:01 -0700 (PDT)
Received: by mail-pa0-f41.google.com with SMTP id rd3so74227pab.28 for <tls@ietf.org>; Tue, 29 Jul 2014 11:45:01 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :subject:references:in-reply-to:content-type :content-transfer-encoding; bh=v/1HOUWSTb9BJWFRqcrEbhaEKq0uSVy458D9Fd6NgNE=; b=E2OaNRKpcfAlCpmX5xZijI/j7qJgL84nRhHVKdoII+UuL1tNgnSjfBcv4aYzvX6W+K LmXeEvxYIQeSZZch21/hSQ9FFEJDK6EC0wg2kYKZUEd87EJS+92xvTpIa/YaNiXXMop5 2TNaPiX0blBgjxv13+5LM4WlThD8jtoWP+Rv6vdXMJWwPRxGH6Sqa90WXVDd2/e+j832 sN1oMyp4CwzOb5Y1MfVOwR390LIEfzxt3TlNBaM/2gPNWxjW5OIJ8Bdk82cc+4No3br0 uI51JXKTUaTE8NfNv1sIJH5HU49AT2kvVpN/qE9wPaDLcaE8rYghZ6AQeh+gWNQU8Lq+ 1O5g==
X-Gm-Message-State: ALoCoQmPZpnH/D2AD/HKVfDdNH43QgPPTSUrLAOD7Q71Zh/rE5YlUx35uayet3nI2X9SHDzPLN2F
X-Received: by 10.70.98.232 with SMTP id el8mr3805537pdb.119.1406659501659; Tue, 29 Jul 2014 11:45:01 -0700 (PDT)
Received: from amaluto.corp.amacapital.net (50-76-60-73-ip-static.hfc.comcastbusiness.net. [50.76.60.73]) by mx.google.com with ESMTPSA id nt15sm30012552pdb.63.2014.07.29.11.44.59 for <multiple recipients> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 29 Jul 2014 11:45:00 -0700 (PDT)
Message-ID: <53D7EBAA.1090705@amacapital.net>
Date: Tue, 29 Jul 2014 11:44:58 -0700
From: Andy Lutomirski <luto@amacapital.net>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Dave Garrett <davemgarrett@gmail.com>, tls@ietf.org
References: <201407281624.10986.davemgarrett@gmail.com>
In-Reply-To: <201407281624.10986.davemgarrett@gmail.com>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/Zgchb-P2J_zdbbLG79F3Pprb63g
Subject: Re: [TLS] PRF in 1.3
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
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/options/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, 29 Jul 2014 18:45:04 -0000

On 07/28/2014 01:24 PM, Dave Garrett wrote:
> https://github.com/tlswg/tls13-spec/issues/26
> 
> Issue #26 notes complication with the usage of a negotiable PRF. The
> current suggestion mentioned was to consider removing PRF
> negotiation in favor of SHA-256, calling it "good enough" until the next
> protocol version. I agree that this is quite possibly the case, however
> I would like to suggest future proofing things a bit. Old versions of TLS
> used the strategy of dual hash algorithms "to ensure that
> non-catastrophic flaws in one algorithm will not break the overall
> protocol" [RFC4346 F.1.5]. TLS 1.1 used MD5+SHA1. For TLS 1.3, I
> would like to suggest SHA2-256+SHA3-256 or similar for consideration.
> Picking a single combo allows the removal of negotiation, fixing any issues
> that causes, provides a simpler spec for this feature, and allows both the
> current standard and new SHA functions to be used without having to
> rely 100% on either. Adoption rates of new TLS versions are less than
> ideal, so future proofing in manners like this that don't add a fantastic
> amount of additional complexity seems like an idea worth consideration.

I asked this on the CFRG list and didn't get too much of a response, but
we could ask the CFRG to recommend a PRF.  If so, I think that we should
ask that it be a suitable hash combiner that provides whatever
properties TLS needs (or would want for purpose of provable security) if
*either* SHA3-<bits> or SHA2-256 is secure.

There is a decent amount of literature on this, and the TLS 1.0
construction is *not* the way to do it.

We could further request that the construction be immune to generic
attacks even if SHA3 is completely broken.  In particular, a SHA-3 break
should not result in a length extension attack.  I believe that there
are multiple constructions here that would work.

Also, IMO we should ask for it to be reasonably likely that breaking the
PRF takes well over 2^128 effort to break, even with parallel attacks,
and even with a quantum computer [1].  This particular part of TLS is
easy to make post-quantum secure [2] and, if it can't be negotiated and
we're considering using a new PRF, then let's get it right.

In other words, I don't think it's time to fully specify how TLS 1.3
would work if the attackers have quantum computers, but we should be
able to get decent-sized pieces of it right.  That means at least using
an appropriate PRF and having a mandatory-to-implement cipher with
enough bits of key.


[1] No 256-bit hash function is comfortably secure against collisions in
a post-quantum world.  There's a straightforward algorithm that will
find a collision in 2^(256/3) hash queries.  I suspect that there are
similar issues with hash functions with smallish amounts of internal state.

[2] As far as I know, and I did try to search the literature for it a
couple years ago, there is no proof that *any* standard classical crypto
construction still works against quantum adversaries.  An n-bit random
oracle indeed requires 2^(n/3) quantum queries to find a collision (the
lower bound has a very nice proof), but there is no quantum analogue to,
say, the Luby-Rackoff Theorem.  On the other hand, there's no reason to
suspect that anything better than generic oracle attacks against the
entire PRF are particularly likely, so let's at least get that part right.

--Andy