Subject: [TLS] Fwd: New Version Notification for draft-whyte-qsh-tls13-01.txt

From: William Whyte <[email-masked]>
Date: Sun, 20 Sep 2015 22:59:58 -0400

Hi all,

We've updated the TLS 1.3 Quantum Safe Handshake draft to use extensions as
suggested by DKG in Prague. All comments welcome.

There's an interesting issue here: McEliece keys, which should be
permissible, are larger in size (about 2^20 bytes) than the maximum
permissible extension size (2^16-1). In order to support McEliece keys it
might be worth increasing the maximum extension size to 2^24-1 for TLS 1.3.
Is there a strong reason for keeping the maximum size at 2^24-1, other than
saving one byte on all the relevant length fields?

Cheers,

William

---------- Forwarded message ----------
From: <[email-masked]>
Date: Sun, Sep 20, 2015 at 10:32 PM
Subject: New Version Notification for draft-whyte-qsh-tls13-01.txt
To: Zhenfei Zhang <[email-masked]>, William Whyte <
[email-masked]>, "John M. Schanck" <
[email-masked]>

A new version of I-D, draft-whyte-qsh-tls13-01.txt
has been successfully submitted by William Whyte and posted to the
IETF repository.

Name:           draft-whyte-qsh-tls13
Revision:       01
Title:          Quantum-Safe Hybrid (QSH) Ciphersuite for Transport Layer
Security (TLS) version 1.3
Document date:  2015-09-20
Group:          Individual Submission
Pages:          18
URL:
https://www.ietf.org/internet-drafts/draft-whyte-qsh-tls13-01.txt
Status:         https://datatracker.ietf.org/doc/draft-whyte-qsh-tls13/
Htmlized:       https://tools.ietf.org/html/draft-whyte-qsh-tls13-01
Diff:           https://www.ietf.org/rfcdiff?url2=draft-whyte-qsh-tls13-01

Abstract:
   This document describes the Quantum-Safe Hybrid ciphersuite, a new
   cipher suite providing modular design for quantum-safe cryptography
   to be adopted in the handshake for the Transport Layer Security (TLS)
   protocol version 1.3.  In particular, it specifies the use of the
   NTRUEncrypt encryption scheme in a TLS handshake.

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

The IETF Secretariat

---

From: Geoffrey Keating <[email-masked]>
Date: 20 Sep 2015 20:48:00 -0700

> saving one byte on all the relevant length fields?

That would affect the initial client hello, which I think we're trying
to keep backwards compatible.  It might be better to just define a
rule like "if multiple extensions with the same number are present,
their values are concatenated".

---

From: Dave Garrett <[email-masked]>
Date: Mon, 21 Sep 2015 00:20:21 -0400

> permissible extension size (2^16-1). In order to support McEliece keys it

The max _total_ payload size of all extensions is 2^16-1. There are also mandatory extensions for TLS 1.3, as well as others that will customarily be used, thus the max available space is less.

> might be worth increasing the maximum extension size to 2^24-1 for TLS 1.3.

No, I don't think the limit can be raised. The general ClientHello format has to stay frozen for interoperability with other versions, and unless I'm misreading things, the size of the length of a vector can't change. A separate message seems like what would be needed to have a larger first-flight payload. (and any new messages would need to be signaled via an extension, though it could have a 0-length payload)

Also, 16MiB sounds kinda crazy for a first flight, especially one that you can't guarantee the server will understand. Something more like a 21-bit limit sounds less nuts, but that's still 2MiB. I don't think it's a good idea to allow this to be effectively unbounded, so a reasonable (arbitrary) limit should probably be imposed.

> saving one byte on all the relevant length fields?

Typo? Did you mean "keeping the maximum size at 2^16-1"?

A strong reason is it not being possible to change due to the need for TLS 1.3 clients to be able to connect to TLS 1.2 servers that won't understand a format change. Even if it were technically possible, I wouldn't expect all implementations to safely handle it.

---

From: Dave Garrett <[email-masked]>
Date: Mon, 21 Sep 2015 00:25:11 -0400

> their values are concatenated".

Duplicate extensions are explicitly prohibited:
https://tools.ietf.org/html/rfc5246#section-7.4.1.4

Attempting to do that feels like a good way to find an implementation to choke on it.

See also the other email I just sent, as this suggestion won't help.

Dave

---

From: Peter Gutmann <[email-masked]>
Date: Mon, 21 Sep 2015 04:52:04 +0000

Geoffrey Keating <[email-masked]> writes:

>That would affect the initial client hello, which I think we're trying to
>keep backwards compatible.  It might be better to just define a rule like "if
>multiple extensions with the same number are present, their values are
>concatenated".

A better one would be "if you're planning on introducing some new crypto
mechanism, make it one that will fit into the TLS framework".

Peter.

---

From: Brian Smith <[email-masked]>
Date: Sun, 20 Sep 2015 21:53:49 -0700

On Sun, Sep 20, 2015 at 7:59 PM, William Whyte <
[email-masked]> wrote:

> Hi all,
>
> We've updated the TLS 1.3 Quantum Safe Handshake draft to use extensions
> as suggested by DKG in Prague. All comments welcome.
>

William, I suggest you first do an experiment:

Create a TLS client that contains all the stuff a browser puts in its TLS
handshake. Then, add your new a maximally-sized (2^16-1 bytes) extension,
but don't otherwise change the client. What percentage of handshakes fail?

I suspect that a huge percentage of the handshakes will fail. First, some
implementations won't accept a ClientHello larger than 1KB (IIRC) due to
artificial limit imposed presumably as a DoS measure. Secondly, I suspect
many implementation will fail to handle a ClientHello that is split across
multiple records. Keep in mind that since the maximum record size is less
than the maximum extension size, a ClientHello with a maximally-sized
extension must require more than one record to be encoded.

In general, I would expect most implementations don't want to receive a 1MB
message of any sort unless they've advertised that they want such messages.
So, a different design that doesn't require including a huge extension in
the initial ClientHello would probably be better.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Dave Garrett <[email-masked]>
Date: Mon, 21 Sep 2015 00:57:48 -0400

> The max _total_ payload size of all extensions is 2^16-1. There are also mandatory extensions for TLS 1.3, as well as others that will customarily be used, thus the max available space is less.
[...]
> No, I don't think the limit can be raised. The general ClientHello format has to stay frozen for interoperability with other versions, and unless I'm misreading things, the size of the length of a…

To amend my previous email:

Another option might be to implement things as an encrypted-only TLS extension. This would restrict it to 0-RTT mode only, meaning clients would need the server's semi-static config in order to use it. (retrieved from a previous connection or possibly through an out-of-bound method, yet to be specified) This would, however, put it in the EncryptedExtensions message which currently has a similar 2^16-1 limit, but this is new so it could be changed. Again, though, that might not be the best idea.

-----

In case you're confused as to where the limit I'm referring to comes from:
https://tools.ietf.org/html/rfc5246#section-4.3

The notation is somewhat atypical. The value/range in angle brackets is the length, in bytes, of the vector, rather than the length in total number of elements.

The ClientHello.extensions vector max size is 2^16-1:
https://tools.ietf.org/html/rfc5246#section-7.4.1.2

Each Extension.extension_data vector max size is also 2^16-1:
https://tools.ietf.org/html/rfc5246#section-7.4.1.4

And... actually, looking at this, I think that could be considered wrong. The max individual extension payload size would be 2^16-5, to account for overhead. Less, of course, taking into account other extensions in the same hello.

Dave

---

From: Hubert Kario <[email-masked]>
Date: Mon, 21 Sep 2015 13:22:03 +0200

On Monday 21 September 2015 00:20:21 Dave Garrett wrote:
> No, I don't think the limit can be raised. The general ClientHello
> format has to stay frozen for interoperability with other versions,
> and unless I'm misreading things, the size of the length of a vector
> can't change. A separate message seems like what would be needed to
> have a larger first-flight payload. (and any new messages would need
> to be signaled via an extension, though it could have a 0-length
> payload)

we still would need to wait for server to reply before we could send 
them, so no way to do 1RTT

> > Is there a strong reason for keeping the maximum size at 2^24-1,
> > other than saving one byte on all the relevant length fields?
> 
> A strong reason is it not being possible to change due to the need for
> TLS 1.3 clients to be able to connect to TLS 1.2 servers that won't
> understand a format change. Even if it were technically possible, I
> wouldn't expect all implementations to safely handle it.

the TLS1.2 standard says that the ClientHello MUST match either 
extension-less or an extension-present format and server MUST check that 
the overall length of message matches the processed data, so we can't 
have extensions-after-extensions (which theoretically could have 3 byte 
length field). That limitation is present since RFC 3546 [Extensions], 
which explicitly says:

   This overrides the "Forward compatibility note" in [TLS].

-- 
Regards,
Hubert Kario
Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

---

From: Dave Garrett <[email-masked]>
Date: Mon, 21 Sep 2015 15:04:17 -0400

On Monday, September 21, 2015 07:22:03 am Hubert Kario wrote:
> length field).

Yeah, adding a second extensions vector in addition to the existing one was my other thought, but it's too messy for me to think it'd be worth trying. Looks like that's not even possible. I think we're stuck with the current TLS extension size limits forever.

I doubt anyone would really want to use any keys in the megabyte range anyway. Post-quantum crypto research/experimentation for TLS & other network protocols should really focus on systems with smaller keys. Even if a giant-key scheme was ideal, you'll have a very hard time convincing people to actually use it, no matter how much they might need it. :/

Dave

---

From: Hubert Kario <[email-masked]>
Date: Mon, 21 Sep 2015 22:43:20 +0200

On Monday 21 September 2015 15:04:17 Dave Garrett wrote:
> > > A strong reason is it not being possible to change due to the need
> > > for TLS 1.3 clients to be able to connect to TLS 1.2 servers that
> > > won't understand a format change. Even if it were technically
> > > possible, I wouldn't expect all implementations to safely handle
> > > it.
> > 
> > extension-less or an extension-present format and server MUST check
> > that the overall length of message matches the processed data, so
> > we can't have extensions-after-extensions (which theoretically
> > could have 3 byte length field).
> 
> Yeah, adding a second extensions vector in addition to the existing
> one was my other thought, but it's too messy for me to think it'd be
> worth trying. Looks like that's not even possible. I think we're
> stuck with the current TLS extension size limits forever.
> 
> I doubt anyone would really want to use any keys in the megabyte range
> anyway. Post-quantum crypto research/experimentation for TLS & other
> network protocols should really focus on systems with smaller keys.
> Even if a giant-key scheme was ideal, you'll have a very hard time
> convincing people to actually use it, no matter how much they might
> need it. :/

true, that being said, I can see 64KiB total being limiting for 
different stuff in the future

and while sending 2MiB packets as "just a hello" is unlikely, I can see 
us sending 64KiB or 128KiB packets...

maybe we should reintroduce the forwards compatibility clause for client 
hello? it won't help us now, but when TLS1.2 gets broken then we'll be 
able to move forward with higher sizes for extensions (whatever that 
happens)

---

From: Douglas Stebila <[email-masked]>
Date: Tue, 22 Sep 2015 08:14:45 +0000

> us sending 64KiB or 128KiB packets...

Bernstein et al. needed 64 KiB public keys for McBits [http://binary.cr.yp.to/mcbits-20130616.pdf].  We needed 4 KiB public keys for ring learning with errors [https://eprint.iacr.org/2014/599]; a switch to learning with errors would make the keys much bigger, but I can't say how much bigger at this point.  It is too soon to rule out 64 KiB or larger public keys, although getting smaller key sizes is a very important goal for post-quantum crypto research.

Douglas