Subject: [TLS] MTI kx groups, HelloRetryRequest and "Incorrect DHE Share"

From: Joseph Birr-Pixton <[email-masked]>
Date: Tue, 27 Dec 2016 21:43:27 +0000

Hi folks,

It appears to me that HRR is a pretty large and tricky source of
complexity in TLS1.3. Judging by the implementations page, 40% don't
support it right now. It's *precisely the kind of thing* that vendors
could easily ship broken/missing support for, and they'd get away with
it for years until it causes a interop problem.

The only case where it is used is (4.1.1):

  If there is overlap in the "supported_groups" extension but the client
  did not offer a compatible "key_share" extension, then the server will
  respond with a HelloRetryRequest

We could entirely remove HRR if we slightly strengthen the MTI
language covering kx groups:

- Clients must not only "implement", but actually offer a key share
for NISTP-256 for every ClientHello.

Note: Obviously, this doesn't apply to PSK-only connections where
psk_key_exchange_modes was provided and did not contain psk_dhe_ke.

This need not have any additional computational overhead, because the
client can amortise the key generation over all handshakes where the
server does not select P-256 (hopefully most of them!). In any case,
it's one fixed-base pointmul. It obviously costs 64 bytes-odd on the
wire, but only if the client wasn't going to send a NISTP-256 share
otherwise.

Did I miss something? Are there any other uses of HRR in TLS1.3 which
means we can't get rid of it in this way?

Cheers,
Joe

---

From: Xiaoyin Liu <[email-masked]>
Date: Tue, 27 Dec 2016 22:27:13 +0000

Hi Joe,

My understanding is that we can't get rid of HRR unless we require clients to send a key_share for every key exchange group in the supported_groups extension. This would be a quite large overhead if the client wants to support lots of groups.

Also HRR allows servers to request clients to echo Cookies. See section 4.2.2 Cookie.

Best,

Xiaoyin

From: Joseph Birr-Pixton<mailto:[email-masked]>
Sent: Tuesday, December 27, 2016 4:44 PM
To: [email-masked]<mailto:[email-masked]>
Subject: [TLS] MTI kx groups, HelloRetryRequest and "Incorrect DHE Share"

Hi folks,

Cheers,
Joe

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

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 27 Dec 2016 14:29:09 -0800

On Tue, Dec 27, 2016 at 2:27 PM, Xiaoyin Liu <[email-masked]> wrote:

> Hi Joe,
>
>
>
> My understanding is that we can't get rid of HRR unless we require clients
> to send a key_share for every key exchange group in the supported_groups
> extension. This would be a quite large overhead if the client wants to
> support lots of groups.
>
This is true, but an additional concern is that it makes it basically
impossible to switch MTI groups. I.e., people will have to support P-256
forever.

Also HRR allows servers to request clients to echo Cookies. See section
> 4.2.2 Cookie.

This too.

-Ekr

>
>
> Best,
>
> Xiaoyin
>
>
>
> *From: *Joseph Birr-Pixton <[email-masked]>
> *Sent: *Tuesday, December 27, 2016 4:44 PM
> *To: [email-masked]
> *Subject: *[TLS] MTI kx groups, HelloRetryRequest and "Incorrect DHE
> Share"
>
>
> Hi folks,
>

---

From: David Benjamin <[email-masked]>
Date: Wed, 28 Dec 2016 03:06:20 +0000

On Tue, Dec 27, 2016 at 4:44 PM Joseph Birr-Pixton <[email-masked]>
wrote:

Hi folks,

This is indeed a problem. HRR costs an RTT, so enforcing server support is
tricky. Realistically, removing groups from the initial ClientHello will
probably be impossible, which makes the proposed P-256 mandate especially
unappealing.

(We hope to try some ideas in Chrome here, but they'll be more complex than
GREASE. My current thought is to send the occasional empty key shares
ClientHello, either as a parallel probe or just with low probability. Then,
once we have any evidence that a server can't HRR, sticky this and refuse
to offer it initial key shares until it demonstrates HRR support.)

Chrome/BoringSSL does not offer P-256 in the initial ClientHello, only
X25519. Early in development, we offered P-256 too but intentionally
trimmed it to X25519. I do not think this is a good reason to reverse that.

On low-end devices, the CPU cost of ECDH starts showing up. X25519 admits
simpler and faster implementations than P-256. It wouldn't be okay to waste
cycles on a P-256 key share that hopefully tomorrow's TLS 1.3 servers will
just ignore anyway. (And today's servers, though predominantly P-256, will
also ignore it because they're TLS 1.2.)

You are right that one can amortize the cost, but this adds a pile of
complexity (make sure to never offer the same key share twice in parallel,
cached key shares need lifetimes, limits on cache size, etc). It may end up
worthwhile for other reasons, but not just so servers can cut corners to
use an unfavored group.

TLS 1.3 requires selecting favored group(s), with all the unfortunate
results that has. Let's at least get what good effects we can and encourage
the current best practice while we have no legacy baggage preventing it.

David

Cheers,
Joe

---

From: david wong <[email-masked]>
Date: Tue, 27 Dec 2016 21:08:14 -0600

HRR is a pretty simple message to implemement. Including it into a ServerHello would complexify the protocol without much gain imo. 

I also think that forcing a client to use one of the curve is not a good idea either. Who is going to agree on what curve it should be here :) ? 

Probably browsers and server implementations will end up agreeing on the same set anyway. And client/server controlled infrastructures can enforce that to avoid using HRR as well. 

David

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 27 Dec 2016 20:05:19 -0800

On Tue, Dec 27, 2016 at 7:06 PM, David Benjamin <[email-masked]>
wrote:

> (We hope to try some ideas in Chrome here, but they'll be more complex
> than GREASE. My current thought is to send the occasional empty key shares

It also creates a potential supercookie in the clear part of the handshake
which is obviously problematic, and becomes more problematic the more
biased the ecosystem is. E.g., if you always offer P256 + X25519 but
practically everyone chooses X25519, then you could be offering the P256
share for a very long time before someone picks it up. And of course if you
do the straightforward thing and amortize both shares then you have the
pattern:

ClientHello    Server Picks
P1 X1            X
P1 X2            X
P1 X3            P
P2 X3            X
P2 X4            X

This makes it easy to bridge across share selections.

-Ekr