[TLS] Comments on draft-wagner-tls-keysharepqc-08.txt

[Eric Rescorla <[e-mail]>]

Document: draft-wagner-tls-keysharepqc-08.txt

Thank you for sending this draft.

I am ambivalent on whether it is actually important for TLS to support
PQ algorithms with keys > 64KB. I think it's clear that the
performance implications would be quite bad in many cases (e.g., the
Web), though perhaps there are some environments where it doesn't
matter. I understand people might be concerned about ML-KEM, but there
are other alternative PQ algorithms that do not have quite so dire
performance properties.

However, if we are to do so, I do not believe that any of the
proposals you have here work very well. As you note in your
introduction, there are two size limits in play here:

1. The maximum size of a HandshakeMessage (2^24-1)
2. The maximum size of an extension (2^16^1)
3. The maximum collective size of all the extensions (also 2^16-1)

I don't think that the HandshakeMessage size is really relevant, as
algorithms with keys that exceed 16MB are not likely to be
practical. The basic problem here is the maximum collective size of
the extensions [0]. As a result, it is simply not possible for a
client to transmit more than about 64K of material in its initial
ClientHello and also have it be compatible with existing servers. IMO,
the right approach is to address this head-on, as follows:

1. Modify the ClientHello format to remove the limit.
2. Have a way for the client to learn it can use the new ClientHello
   format.

The fix for (1) is straightforward: replace some if not all of the
variable-length vectors with fixed limits with ones with
variable-length limits as in MLS's `T<V>` syntax (see RFC 9420 S
2.1.2). Once you have done this, then you can just naturally carry
arbitrarily large extensions. We can discuss whether this would be a
global replacement (all vectors) or a targeted one
("large_extensions").

The first of these is obvious, so let's focus on the second. The
natural way to do this is with HRR. In particular, the idea would be
to create a new extension that indicated that you supported the new
format. For concreteness, say we use the "large_extensions" extension,
which just redefines Extensions as:

    struct {
        ExtensionType extension_type;
        opaque extension_data<V>;
    } Extension;

    and then the various extensions fields as:

    Extension extensions<V>;

The semantics of the large_extensions extension are that the client
offers it and if the server accepts it, future messages use the new
format. The resulting handshake looks like this (with some fields
elided):

Client                                                      Server

ClientHello
  + large_extensions
  + supported_groups[X25519, McEliece]
  + key_share[X25519]              -------->

                                                 HelloRetryRequest
                                                + large_extensions
                                      + supported_groups[McEliece]


ClientHello (large extensions version)
  + large_extensions
  + supported_groups[X25519, McEliece]
  + key_share[McEliece]            -------->

...

This fits naturally into our existing pattern and reflects the fact
that you can't safely send the big key share in the first message
anyway, and you most likely don't want to if you don't know the other
side supports it because it's a waste of bandwidth. Moreover, because
it's a generic solution, you don't need to change anything else.

It's slightly irritating that even if you know that the server
supports large extensions you can't just start out with that. I think
that's a problem we could figure out how to solve if we really had to,
but TBH I doubt it's worth it because you're already absorbing
a bunch of round trips. It *might* be worth it for ECH, but I'd
want to see some evidence that ECH was really going to exceed 64K.

As an aside, I think the material in S 3.1.1 about changing
PskKeyExchangeMode
is misguided. The right approach is just to treat these PQ algorithms
as if they were DH and overload psk_dhe_ke.

-Ekr


[0] Were the problem the individualized size of extensions, we could
split things up between extensions.