Re: [TLS] PRF in 1.3

[Andy Lutomirski <[e-mail]>]

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