[TLS]Meta deploying -hybrid-design

[Deirdre Connolly <[e-mail]>]

Starting with internal connections:

https://engineering.fb.com/2024/05/22/security/post-quantum-readiness-tls-pqr-meta/

> For our deployment, we have chosen Kyber with X25519 in a hybrid setting.
Kyber is the only key encapsulation mechanism selected by NIST for
standardization so far. Kyber comes in different parameterizations:
Kyber512, Kyber768, and Kyber1024. Larger parameterizations provide
stronger security but also require more computational resources and
communication bandwidth. We aim to use Kyber768 by default, while using
Kyber512 in some cases where larger parameterizations lead to prohibitive
performance impact, to accelerate the deployment of PQC hybrid key exchange.

Challenges include large packet sizes:

> After evaluating various alternatives and workarounds, and given the
prohibitive key size of Kyber768, we opted to use Kyber512 in internal
communications affected by this problem for now, allowing us to accelerate
the PQC deployment. Kyber512’s 800-bytes-long public keys help with fitting
the ClientHello into a single TCP packet, while still being considered
secure by NIST. This choice ensures both security and efficient
communication. In the future, an increase in MTU, or utilizing QUIC, which
allows for multiple initial packets, may allow for larger ClientHellos
without an additional round trip.


and cross-domain session resumption handshake thrashing:

> As previously mentioned, we do Ephemeral Diffie-Hellman key exchange on
resumption. To facilitate efficient use of computation resources, the
client will send only the minimally required default keyshares, which in
the resumption case means the keyshare for the previously negotiated named
group. This means that when a client connects to a particular server and
negotiates a classical named group, then subsequently resumes on a server
with which the client should use a hybrid named group, the client would
advertise the hybrid named group but send only the keyshare for the
classical named group. This leads to the server negotiating the hybrid
named group and replying with a HelloRetryRequest to ask the client for the
hybrid keyshare, resulting in an additional 1-RTT to perform the key
exchange.

> To address this, we had the client split each service into different TLS
session scopes – one using classical key exchange, and one using hybrid key
exchange. Each session scope thus uses only one named group each, avoiding
the keyshare thrashing behavior described above. The tradeoff is space
consumption due to having to store more session tickets, but this has been
acceptable given the small size of each session ticket (a few hundred
bytes).

They also included more in-the-wild data on Kyber768 computational costs:

> Meta currently uses X25519 in Elliptic Curve Diffie-Hellman key exchange.
During the initial rollout of hybrid key exchange with the hybrid named
group X25519_kyber768, we observed a roughly 40 percent increase in CPU
cycles. Although this may seem like an undesirable result, it actually
indicates that Kyber768 standalone key exchange is faster than x25519,
which lines up with results others have found.