Subject: [TLS] Simplifying the record protocol

From: Andy Lutomirski <[email-masked]>
Date: Mon, 19 May 2014 11:57:45 -0700

This is inspired ekr mentioning removing some redundant fields and by a
discussion at the interim meeting about some TLS padding tricks that
won't work unless the record type is encrypted.  Regardless of the
actual motivation, it should be both a cleanup and an efficiency
improvement.

Currently, a record is:

       struct {
           ContentType type;
           ProtocolVersion version;
           uint16 length;
           select (SecurityParameters.cipher_type) {
               case stream: GenericStreamCipher;
               case block:  GenericBlockCipher;
               case aead:   GenericAEADCipher;
           } fragment;
       } TLSCiphertext;

GenericAEADCipher encodes a TLSPlaintext, which is:

    struct {
        ContentType type;
        ProtocolVersion version;
        uint16 length;
        opaque fragment[TLSPlaintext.length];
    } TLSPlaintext;

There is a lot of redundancy here.  The type, version, and length appear
twice.  Of those, the version appears to be almost completely pointless,
and the type and length don't need to appear twice.  If I'm counting
right, fixing this will save six bytes in every record.

Fixing this may also reduce the chance that implementations screw up
checks related to record lengths: there's now only one length field.

This could be as simple as:

   struct {
       uint16 length;
       GenericAEADCipher ciphered_plaintext;
   } TLSCiphertext;

   struct {
       ContentType type;
       opaque plaintext_fragment[plaintext length - 2];
   } TLSPlaintext;

This may require some fiddling with the AAD part of the
GenericAEADCipher construction.

Doing this in a way that's backwards compatible with TLS 1.2 and below
might require some tweaks to the handshake protocol -- the redundant
fields will probably have to be-added.

Thoughts?  Should I try to write up a pull request?

--Andy

---

From: Adam Langley <[email-masked]>
Date: Mon, 19 May 2014 12:04:05 -0700

> right, fixing this will save six bytes in every record.

Putting the version in every record is a waste, but TLSPlaintext and
TLSCiphertext don't work in the way that you think: the type, version
and length aren't repeated on the wire. TLSPlaintext is more of a
conceptual structure. A TLS record, on the wire, contains only the 5
byte header of the TLSCiphertext.

Cheers

AGL

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 19 May 2014 12:25:26 -0700

> byte header of the TLSCiphertext.

Egads!  So that's what "opaque content[TLSPlaintext.legnth]" means.

In any event, the version should still be removable (at least after
the first ChangeCipherSpec), and it would still be nice to encrypt the
record type.  Of course, doing that probably means that the record
type should be removed from the additional_data bit.

--Andy

---

From: Martin Thomson <[email-masked]>
Date: Mon, 19 May 2014 12:26:12 -0700

> byte header of the TLSCiphertext.

Bad presentation in RFC 5246 notwithstanding, I think that Andy's
proposal has merit.  This drops the version, encrypts the type.

I was going to go one further and suggest collapsing the handshake
messages down into the same structure, using the ContentType to
indicate not just that the message is a handshake message, but to also
include what type.

That would have the consequence of reducing the size of a handshake
message down to 64K (from 16M), but I think that's probably
manageable.

The big challenge that this sort of proposal introduces is that it
makes it hard to do DTLS-SRTP demux.  See
http://tools.ietf.org/html/rfc5764#section-5.1.2

One potential way to address that is to reduce the maximum record size
further. and use the bits reclaimed to distinguish DTLS records.  2^14
might be workable.

---

From: Adam Langley <[email-masked]>
Date: Mon, 19 May 2014 12:33:10 -0700

> message down to 64K (from 16M), but I think that's probably

The situation where a >64KB handshake message often arises is in the
CertificateRequest message from a server to a client. Some servers
have a full root-set installed (say, Mozilla's set) and listing the
names of all the roots takes a lot of space.

In that situation, it's almost the case that it would be better if the
server didn't send any CAs at all in the cert request. Although I
guess it does allow clients to exclude any credentials issued by
private authorities.

Also, in the future, a post-quantum certificate chain, or PQ
key-agreement may exceed 64KB. The short keys and signatures that we
currently enjoy might be gone in a few decades.

Cheers

AGL

---

From: Geoffrey Keating <[email-masked]>
Date: 19 May 2014 13:58:55 -0700

> names of all the roots takes a lot of space.

There are also certificates today that exceed 64K, due to long lists
of valid domain names; that would be the ServerCertificate message.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 19 May 2014 14:17:23 -0700

> guess it does allow clients to exclude any credentials issued by

The set of distinguished names isn't particularly useful.  I don't
find that particularly compelling.

> currently enjoy might be gone in a few decades.

Yes, I heard several people complaining about the size of keys in a
post quantum computing world.

---

From: Martin Thomson <[email-masked]>
Date: Mon, 19 May 2014 14:21:06 -0700

> of valid domain names; that would be the ServerCertificate message.

That worries me more that the CertificateRequest.

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 19 May 2014 17:21:10 -0400

> Yes, I heard several people complaining about the size of keys in a post quantum computing world.

Handling post-quantum is a design requirement of TLS 1.3?

	/r$

--  
Principal Security Engineer
Akamai Technologies, Cambridge, MA
IM: [email-masked]; Twitter: RichSalz

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 19 May 2014 14:23:17 -0700

> Handling post-quantum is a design requirement of TLS 1.3?

Not to my knowledge.

-Ekr

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

---

From: Hubert Kario <[email-masked]>
Date: Tue, 20 May 2014 07:49:43 -0400 (EDT)

----- Original Message -----
> From: "Rich Salz" <[email-masked]>
> To: "Martin Thomson" <[email-masked]>, "Adam Langley" <[email-masked]>
> Cc: [email-masked], "Andy Lutomirski" <[email-masked]>
> Sent: Monday, May 19, 2014 11:21:10 PM
> Subject: Re: [TLS] Simplifying the record protocol
> 

Don't think so, but if not only all the algorithms but all the protocols
will have to be scrapped too, it won't make our future lives any easier.

This would also make it a rather surprising regression compared to TLS 1.2

-- 
Regards,
Hubert Kario

---

From: Watson Ladd <[email-masked]>
Date: Tue, 20 May 2014 06:25:44 -0700

> This would also make it a rather surprising regression compared to TLS 1.2

There are two impacts PQ has. The first is doubling the size of block
cipher keys due to Grover's algorithm. I don't know off the top of my
head what to do about hashes: its either triple the size or double.
But this we can deal with.

The second impact is encryption with small keys is based on NTRU, so
keys are not that big. Signatures on MVQ variants like HFE+ or Quartz
have short signatures: 128 bits for 128 bits of security. However,
they have big keys: Quartz has a public key of approximately 2^21
bits. Certificate chains will feel the squeeze the most: we shouldn't
reduce their size if we want TLS 1.3 (or TLS 1.0 even) to last into
the PQ era.

Perfect forwards secrecy needs some cleverness to ensure. Parameters
are less well understood then in the classical case.

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 20 May 2014 16:31:07 +0200

> actual motivation, it should be both a cleanup and an efficiency

Keep in mind that by cleaning up and simplifying parts of a complex
protocol, means that current implementations will not be  simpler, but
even more complex as they will have to additionally support the new
options. While theoretically you could have a TLS 1.3-only
implementation that could be simpler, in practice you will not.

regards,
Nikos

---

From: Andy Lutomirski <[email-masked]>
Date: Tue, 20 May 2014 17:24:22 -0700

> But this we can deal with.

The quantum complexity for general preimages is O(2^(n/2)) and for
collisions is O(2^(n/3)) for an n-bit hash, assuming that there's
nothing about the hash in question that allows attacks better than the
best possible generic attacks.  So doubling the size is fine.

> are less well understood then in the classical case.

NTRUEncrypt can do it: one party generates an ephemeral key pair; the
other party generates a session key and encrypts it.  This doesn't allow
both operations to happen at once the way that DH does, but this might
not matter.

A fancier approach preserves the property that neither party controls
the key:

Alice generates a key pair (pub, priv)
Bob generates r, a random string

Alice -> Bob: pub
Bob -> Alice: Enc_pub(r)

The session key is H(pub || r) for any PRF H.

This can be dropped directly in to TLS where Enc_pub is the NTRUEncrypt
primitive with any appropriate padding and where H is any PRF.  Alice is
whichever party is expected to send a DH share first and Bob is
whichever party is expecdsted to send a DH share second.

This also works if Enc_pub is any other public-key encryption algorithm
with appropriate security properties.  Of course, using McEliece here
would be insane.

Of course, this has all kinds of IPR issues.  Under my extremely weak
understanding of this stuff, the patents should expire some time in
2020.  OTOH, it may actually pay to standardize this and to implement it
in, say, GnuTLS, which can possibly use the existing patent license.

In any event, I think that TLS should not lose the ability to support
fairly long Handshake messages.

--Andy