Subject: [TLS] PRF in 1.3

From: Dave Garrett <[email-masked]>
Date: Mon, 28 Jul 2014 16:24:10 -0400

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.

- Dave

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 29 Jul 2014 11:44:58 -0700

> 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

---

From: Michael StJohns <[email-masked]>
Date: Wed, 30 Jul 2014 11:51:23 -0400

> amount of additional complexity seems like an idea worth consideration.

I don't believe this is the right place to start asking the questions.  
Instead, let's look at where the PRF is used and in what context, and 
then figure out whether or not what we have is good enough.

TLS uses three (or four) logical constructs during handshaking - a key 
derivation function (1) to derive the master secret from the premaster, 
and the session keys from the master secret; a MAC function (2) to 
"sign" the handshake (Finished message verify_data), and a pseudo-random 
data generator (PRDG) (3) to generate coordinated IVs and nonces for 
some crypto suites.  There's also the hash function (4)  used to 
summarize the handshake prior to it being signed.  (3), in TLS1.2 and 
before, is a generated as part of key stream derived from the master secret.

All of these constructs except the hash use the keyed TLS PRF (a keyed 
recursive HMAC PRDG function), but the hash function is currently the 
same as the underlying hash function for HMAC in the TLS PRF.

So breaking it down:

Is (1) secure enough to derive keys?   The construct used in TLS is 
similar to the section 5.2 construct of NIST SP800-108.  But the SP800 
construct has one extra piece missing from this one - the L parameter 
which ensures that the key stream changes if the number of output bits 
change.  There's also expanded guidance on the context field - the 
equivalent values in TLS are currently just the client and server 
random.   I've got some issues with that - see 
http://tools.ietf.org/html/draft-stjohns-tls-tls13-crypto-infra-00, and 
I would add information about the types and lengths of the keys to be 
derived from the key stream to the context.  With those changes, a 
recursive based HMAC PRDG at the heart of the KDF is probably 
sufficiently secure for key derivation going forward.

Is (2) secure enough to sign the handshake? (2) is probably overkill in 
its current state.  It also uses the TLS PRF and should instead just use 
the HMAC - there's no added security using the TLS PRF. There is another 
issue with the fact that the master secret is used to key both (1) and 
(2) - that's generally considered bad cryptographic practice.

Is (3) secure enough to generate IV and nonce data?  (3) is probably 
overkill.  It uses the master secret to key the PRDG.  Discussions with 
various folks as well as perusing the literature suggest that a key of 
'0's used with the client and server random as context data is 
sufficient as all is needed is an extraction of entropy from other 
random values.   This is NOT a random data source in the general 
cryptographic meaning, but a way of getting the same public data out on 
both sides simultaneously without needing to include them in the 
handshake.  There is a current issue with this in that the master secret 
is used to key this function as well as (1) and (2).

In general, (1), (2), and (3) are probably secure if the TLS PRF 
recursive HMAC is secure, and that's probably secure (if the issues 
above are addressed) assuming (4) is secure.

Is (4) secure enough?  The general comment is that you can negotiate a 
better one if (4) isn't secure.  However, the hash is necessary to 
summarize the handshake because the key for (2) isn't available to the 
server until a substantial portion of the handshake has been 
sent/received. If the client is trying to negotiate a new hash, then the 
client will need to maintain separate hash contexts until it gets the 
server acknowledgement of the hash (PRF) selection and can throw the 
ones it won't use for that away.

The requirements for (2) (key not available until later) argues that the 
TLS PRF has to continue to be built on a hash function unless the data 
signed by (2) changes.  The discussion for (4) suggests that we can't 
just say that SHA256 will always be the value.

Mike

>
>
> - Dave
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

---

From: Michael StJohns <[email-masked]>
Date: Wed, 30 Jul 2014 11:53:57 -0400

So breaking it down:

Mike

---

From: [email-masked] (Martin Rex)
Date: Thu, 31 Jul 2014 18:22:47 +0200 (CEST)

Dave Garrett wrote:
> protocol version.

The PRF was already negotiable (i.e. depending on the cipher suite)
in TLSv1.0.  While this isn't spelled out in the TLSv1.0 spec, it
is clear from the TLS WG discussions about TLSv1.0 and there is
nothing in the TLSv1.0 spec that precludes it.

There are implementations in active use with GOST-based TLS cipher suites,
which replace the TLS PRF (and the hashes used within), and this is
used with TLSv1.0.  The I-D describing the cipher suites has never been
completed, though:
   http://tools.ietf.org/html/draft-chudov-cryptopro-cptls-04

and there also exist no code point assignments in the TLS registry,
so using this with TLSv1.2 is not possible (only TLSv1.0 and TLSv1.1).

The GOST signature algorithms described in that I-D have also been
superseded by more recent ones, but there currently is no description
for those either.

Our TLS (v1.0) implementation contains a plugin interface which can
replace the TLS PRF, just like Microsoft Windows XP(!) has such an
interface.  AFAIK, OpenSSL 1.0.0 also had support for GOST ciphersuites
from the above draft.

-Martin