Subject: [TLS] Finished stuffing/PSK Binders

From: Eric Rescorla <[email-masked]>
Date: Fri, 7 Oct 2016 08:01:43 -0700

After the discussion on PR #615, I took another pass at this with some
help from the research community. Please see:

   https://github.com/tlswg/tls13-spec/pull/672

Key changes in this PR:

1. I have merged the HMAC into the PreSharedKey message, where it is
now called "PSK Binder" to make very clear what the purpose of the
HMAC it is (this suggestion due to Karthik Bhargavan) This also makes
implementation somewhat easier and avoids creating another extension.

2. It is now possible to have >1 PSK, each with its own binder.

3. The binder is now computed over the ClientHello prefix rather than
filling the MAC with zeroes.

4. I've taken a suggestion from David Benjamin to move the negotiation
of the PSK key exchange parameters out of the PSK itself and into a
separate message. This cleans things up and also lets us drop the
currently non-useful auth_mode parameter.

This text is still a bit rough but I think shows the right direction.

As usual, comments welcome, but I think the key question we need
to resolve is whether we really need multiple PSKs. It's clearly
simpler not to support them but it seems like we need to worry about
the case where we are resuming a session created with a PSK. I've come
to the conclusion that if we want to have multiple concurrent PSKs at
all, then this is the right structure, rather than having one PSK and
using HRR to fix it.

ISTM that the other major alternatives are to say:

1. You can't resume sessions created with a PSK.
2. Tickets created in sessions created with a PSK have a hard lifetime
   value and it's a failure if the server forgets during the lifetime
   (this seems like it's going to interact badly with clock skew).

Note that if we decide that we only want one PSK, I'll just revise the
PreSharedKey section to have one, not a list [0].

Thanks,
-Ekr

[0] In fairness, it's also worth noting that if we decide to only
have one, it's possible in the future to replace the PreSharedKey
extension with a MultiplePreSharedKey extension.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Oct 2016 18:26:28 +0300

> currently non-useful auth_mode parameter.

Eeh... From the text, it seems to currently require the kex modes
extension if PSK extension is present. Which seems worse than useless
if the meaning is to get rid of the kex mode parameter from PSK
extension (since you will have the value anyway, but need to dig it
from another extension... Blech).

> This text is still a bit rough but I think shows the right direction.

I would talk about PSKs established by NST, not resumption PSKs.

Also, didn't notice what prevents pathology like this (I presume this
is not allowed):

(Assume PSK with 0RTT allowed, using AES-128-GCM-SHA256)

ClientHello[Ciphers=CHACHA20-POLY1305-SHA256, EarlyDataIndication] --->
[0-RTT data, encrypted using AES-128-GCM-SHA256]
<-- ServerHello[Cipher=CHACHA20-POLY1305-SHA256]
<-- EncryptedExtensions[EarlyDataIndication]

Note the record protection algorithm mismatch.

Also, to straightforwardly prove that collision resistance of HKDF and
HMAC (as used) follows from collision resistance of the underlying hash
function, yon need to take the output to be at least the hash output
size. As otherwise it is not guaranteed that any collision in HKDF or
HMAC can be reduced into collision of the underlying hash.

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 7 Oct 2016 09:35:40 -0700

> from another extension... Blech).

I guess this is a matter of taste, but what convinced me was that:

1. It put all the logic on the server side.
2. It removed the auth mod parameter.

Maybe david can say more.

> I would talk about PSKs established by NST, not resumption PSKs.

Willdo.

> Note the record protection algorithm mismatch.

Yes, this is forbidden by the combination of:

"The parameters for the 0-RTT data (symmetric cipher suite,
ALPN, etc.) are the same as those which were negotiated in the connection
which established the PSK.  The PSK used to encrypt the early data
MUST be the first PSK listed in the client's "pre_shared_key" extension."
(though I think I just recently added cipher suite).

and:
"Any ticket MUST only be resumed with a cipher suite that is identical
to that negotiated connection where the ticket was established."

> HMAC can be reduced into collision of the underlying hash.

Right. I have some text here but please feel free to suggest more.

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Oct 2016 20:03:23 +0300

> Maybe david can say more.

I mean if server is to accept PSK, it must now go fishing for another
extension, check that it is present and pay attention to values there.
As opposed to having the data in where it is needed.
 
> to that negotiated connection where the ticket was established."
 
If 0-RTT is used with manually provisioned PSKs (might not be allowed
currently, but might be allowed soon), does that still hold?

Also, I think it is problematic that externally provisioned PSKs can
be used with any protection with given prf-hash, while NST-provisioned
PSKs can only be used with one protection and prf-hash.

0-RTT requirements are separate matter, since those would apply to all.

The original purpose of resumption-as-PSK was AFAIK to unify the two
mechanisms to simplify things. Therefore those two should be as similar
as possible.
 
> Right. I have some text here but please feel free to suggest more.

Yes, but the text says 256 bit output is enough. One isn't guaranteed
to be able to reduce such collision to collision of >256 bit hash.

(In fact, if the hash is e.g. 384 bit, 256-bit collisions are extremely
unlikely to reduce).

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 7 Oct 2016 10:08:02 -0700

> As opposed to having the data in where it is needed.

This is a reasonable argument (and the reason I stuffed the binder here).
However, David's argument was that this applied to *all* PSKs even new ones.

-Ekr

> (In fact, if the hash is e.g. 384 bit, 256-bit collisions are extremely

Right. I can update.

-Ekr

---

From: Benjamin Kaduk <[email-masked]>
Date: Fri, 7 Oct 2016 15:39:57 -0500

On 10/07/2016 12:08 PM, Eric Rescorla wrote:
>
>
> On Fri, Oct 7, 2016 at 10:03 AM, Ilari Liusvaara
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     > On Fri, Oct 7, 2016 at 8:26 AM, Ilari Liusvaara
>     <[email-masked] <mailto:[email-masked]>>
>     > wrote:
>     >

I was going to ask whether this also includes the decision on whether to
send a Certificate to authenticate the server (even for PSK modes), but
it looks like this change is intentionally removing the ability to do
PSK keyex and auth with a certificate?

> However, David's argument was that this applied to *all* PSKs even new

Implementations already have to do some amount of "scan through all
extensions to detect certain things, do some initial processing, and
then finish process everything [else]", not least because SNI can change
what cert types you have, configuration knobs, etc..  So, yes it's bad,
but how bad is it in a relative sense?

I think there is some value in the client indicating to the server
whether it doesn't want to do psk_dhe (or doesn't want to do pure psk)
for future NSTs, though it's perhaps not of the utmost importance.  That
property does support a separate psk_key_exchange_modes extension in
preference  to rolling it into pre_shared_keys (as a separate list next
to identities and binders), but it seems to only be a weak argument for
separation.  I do think that keeping the psk kex mode orthogonal to the
individual keys is helpful, though.

Anyway, maybe it's time to bite the bullet and actually write up the
description of the proper procedure for ClientHello processing (scan
extensions for SNI, load up servername-specific config+cert/key, etc.). 
Which would make this stuff any prettier, but would at least help people
not get it wrong.

-Ben

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 7 Oct 2016 13:41:48 -0700

On Fri, Oct 7, 2016 at 1:39 PM, Benjamin Kaduk <[email-masked]> wrote:

> On Fri, Oct 7, 2016 at 10:03 AM, Ilari Liusvaara <[email-masked]
> > wrote:
>
> send a Certificate to authenticate the server (even for PSK modes), but it
> looks like this change is intentionally removing the ability to do PSK
> keyex and auth with a certificate?
>

Yes, while preserving the ability to add it later by adding a PskAuthMode
extension parallel to this one.

-Ekr

> extensions to detect certain things, do some initial processing, and then
> finish process everything [else]", not least because SNI can change what
> cert types you have, configuration knobs, etc..  So, yes it's bad, but how
> bad is it in a relative sense?
>
> I think there is some value in the client indicating to the server whether
> it doesn't want to do psk_dhe (or doesn't want to do pure psk) for future
> NSTs, though it's perhaps not of the utmost importance.  That property does
> support a separate psk_key_exchange_modes extension in preference  to
> rolling it into pre_shared_keys (as a separate list next to identities and
> binders), but it seems to only be a weak argument for separation.  I do
> think that keeping the psk kex mode orthogonal to the individual keys is
> helpful, though.
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Sat, 8 Oct 2016 17:16:23 +0300

> extension parallel to this one.

But unlike the KexMode extension, the AuthMode one would not be
mandatory if PSK extension is included (the KexMode extension has no
sane defaults!).

And the semantics of authentication with PSK are much more subtle than
semantics of key exchange with PSK.

-Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 9 Oct 2016 16:58:17 +0300

>    https://github.com/tlswg/tls13-spec/pull/672

Also, an observation: This seems to interact in somewhat annoying way
with stateless HRR.

Basically, CH reconstruction no longer works properly, so one needs to
have a  freezeable PRF hash (and most implementations of hashes can not
be frozen).

And server not supporting PSK does not help here.

(BTW: Simlar thing comes up if you try to freeze an established TLS
session: Currently you need to freeze a hash due to post-handshake
authentication, even if you don't support it. Nothing else in TLS
1.2 or 1.3 needs hash freezing for established session).

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 9 Oct 2016 07:10:59 -0700

> have a  freezeable PRF hash (and most implementations of hashes can not

I've been coming to the conclusion that CH reconstruction is a bad idea.
It's
tricky to get right and in the common case involves a lot of bloat in the CH
(because of duplicating the Key Shares). I think we would be better off just
removing it and replacing (rather than appending to ) KeyShares in HRR.
This was primarily intended as an attempt to avoid the need to continue
the hash in any case.

Best,
-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 9 Oct 2016 18:44:55 +0300

> This was primarily intended as an attempt to avoid the need to continue

That creates a bit of a edge case, where the server might need to pull
client's share accross retry.

(Since if group is OK, the group is not included in HRR, which presumably
causes the client to blank its KeyShare).

Also, doing some size calculations:

ClientHello with "smallest group" rule is ~200 bytes with reasonable
parameters (I got a dump of one TLS 1.3 draft-16 CH from my TLS stack,
it is 265 bytes, but would be 196 with "smallest group" rule).

The amount of space needed to freeze (octet) SHA-256 is 32+63+8=103
octets. And the space needed to freeze (octet) SHA-384 is 64+127+16=207
bytes (for full SHA-256 and SHA-384, add one more byte).

So if selecting ciphersuite using SHA-384, the state size might be
comparable to ClientHello size.

-Ilari

---

From: Eric Rescorla <[email-masked]>
Date: Sun, 9 Oct 2016 08:50:35 -0700

> causes the client to blank its KeyShare).

I think we would change that rule, probably.

-Ekr

---

From: Hugo Krawczyk <[email-masked]>
Date: Sun, 9 Oct 2016 16:23:34 -0400

>> (In fact, if the hash is e.g. 384 bit, 256-bit collisions are extremely

​
​I think that allowing truncation (e.g. for SHA-512) with at least 256-bit
output should be fine too without forcing implementations to work with,
say, 512-bit keys.
While I agree that we don't have generic reductions from collision
resistance of a hash function to its truncations, such (long enough)
truncations are believed to inherit collision resistance. For example,
SHA-512 is "officially" allowed to be truncated and it is the way SHA-384
is defined. Also, a collision on a 256-bit truncated output would be a
MAJOR weakness for any hash function, in particular "breaking" the
treatment of the function as a random oracle (such weakness must lead to
abandoning that hash function).

What do cryptanalysts think?

Hugo
​
 ​

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

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 11 Oct 2016 06:51:26 -0700

> This was primarily intended as an attempt to avoid the need to continue

See:
https://github.com/tlswg/tls13-spec/pull/678

-Ekr

---

From: Martin Thomson <[email-masked]>
Date: Wed, 12 Oct 2016 11:16:05 +1100

> https://github.com/tlswg/tls13-spec/pull/678

I'm convinced that this is the right change.  Reconstruction was
always going to be brittle.  I will note that I don't think that the
change gets the error codes right though.  I explained why on the PR.

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 11 Oct 2016 19:48:05 -0700

Thanks, I'll look at this. I'll be merging this change (modulo your
comments) Friday unless there is significant objection.

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 12 Oct 2016 11:50:47 +0300

> comments) Friday unless there is significant objection.

Well, if reject with in-list group is spurious or not depends on if
there is some hello-altering extension other than key share group
(it isn't if any other extension alters CH).

I also noticed another edge case: What is to prevent server from
omitting key share group (emitting a cookie, so the restart is
not spurious), presumably causing the client to blank its key_share
and then proceed to accept DH versus client's previously sent share?

(That kind of thing really plays hell if client has explicit list
of keypairs it considers active for connection).

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Wed, 12 Oct 2016 21:43:05 +1100

> and then proceed to accept DH versus client's previously sent share?

How about: If key_share isn't in the HRR, the client should replay
it's old key_share verbatim.  Though I agree that the text should say
as much.

Maybe we should require text for every extension that can appear in
the HRR: what to do if the extension is in the HRR, and what to do if
it isn't.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 12 Oct 2016 17:27:48 +0300

> it's old key_share verbatim.  Though I agree that the text should say

Yeah, would work.

> the HRR: what to do if the extension is in the HRR, and what to do if

Or have every extension be "no change" if not present, and do the
specified thing to CH if prsent and known, abort if present and
unknown.

That would waste a bit of space with extensions signaling support
for some rewrites if the server doesn't use those but retries the
handshake.

-Ilari

---

From: Benjamin Kaduk <[email-masked]>
Date: Wed, 12 Oct 2016 10:13:57 -0500

> specified thing to CH if prsent and known, abort if present and

This is an instance of the "require text for every extension" case,
though I think either would work.

> for some rewrites if the server doesn't use those but retries the

I'm having trouble parsing this.  The idea is that the client would
waste some space in the new CH because the server doesn't have a way to
indicate that the client only needs to send a subset of what it sent the
first time around?

-Ben

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 12 Oct 2016 18:45:23 +0300

> indicate that the client only needs to send a subset of what it sent the

Well, depends on the extension...

Actually, not a major issue, given that there is usually a great amount
of bloat in the second CH (just to make it look like CH, instead of
just transporting what is needed).

-Ilari