Add hybrid KEMTLS

[claucece]

We need to add a version of a hybrid KEMTLS. This needs to:

• Define an specification for how Hybrid KEMTLS works
• Add the appropriate changes to the KEMTLS code.

Depends on #66

[claucece]

cc./ @armfazh @bwesterb @thomwiggers

[thomwiggers]

"hybrid KEMTLS" is just KEMTLS with hybrid KEMs for the ephemeral and static (leaf cert) KEM, and and hybrid signature schemes in the signature chain.

The security proof does not rely on fancy properties of the KEMs or signature schemes, so we don't need to make any protocol changes in that sense. We might need to pick some identifiers but that's not any different from what needs to be done for PQ-only KEMs.

This is probably most easily implemented by treating the hybrid KEM as a completely independent algorithm from its constituent components. Treat "KyberX25519" is a "proper" algorithm and do not give it any special treatment on the wire compared to "X25519" or "Kyber". If that means duplicate X25519 public keys: so be it.

So that means following the same strategy as is proposed for draft-ietf-tls-hybrid-design. This draft only covers the (ephemeral) key exchange, of course, so we need to adjust also for the static KEM key exchange: just slap two keys together in the certificate as well and do the same for the ciphertext sent back to the server/client.

For certificates we can probably also do something similar: just slap two signatures together and verify both.

[thomwiggers]

So my previous post covers the specification more-or-less 😉

With regards to implementation changes that'd then be:

• Add hybrid algorithms
• Add algorithms to negotiation (i.e. supported algorithm lists)

[bwesterb]

I agree with Thom. Circl already supports some hybrid KEMs (eg. Kyber512-X25519) and Signatures (eg. Ed25519-Dilithium3.). For the latter we have also have OIDs (see Old() in Circl.) For the former not yet — Cloudflare can just register them though — it's on the internal wiki how to.

We also need internal TLS identifiers, but we can just pick some in the reserved space. See TLSIdentifier in Circl.

[claucece]

yes! thanks you @thomwiggers @bwesterb

For the former not yet — Cloudflare can just register them though — it's on the internal wiki how to.

I'll check about this.

We also need internal TLS identifiers, but we can just pick some in the reserved space. See TLSIdentifier in Circl.

Perfect!

I'll add this to our KEMTLS draft ;)

[claucece]

On our next meeting, I'll like to talk about this questions, as taken from https://datatracker.ietf.org/doc/html/draft-ietf-tls-hybrid-design#section-4:

• Duplication of key shares: Concatenation of public keys in the "HybridKeyExchange" struct can result in sending duplicate key shares. For example, if a client wanted to offer support for two combinations, say "secp256r1+sikep503" and "x25519+sikep503", it would end up sending two sikep503 public keys, since the "KeyShareEntry" for each combination contains its own copy of a sikep503 key. This duplication may be more problematic for post-quantum algorithms which have larger public keys.

• Resumption: TLS 1.3 allows for session resumption via a PSK. When a PSK is used during session establishment, an ephemeral key exchange can also be used to enhance forward secrecy. If the original key exchange was hybrid, should an ephemeral key exchange in a resumption of that original key exchange be required to use the same hybrid algorithms?

• Failures: Some post-quantum key exchange algorithms have non- trivial failure rates: two honest parties may fail to agree on the same shared secret with non-negligible probability. Does a non-negligible failure rate affect the security of TLS? How should such a failure be treated operationally? What is an acceptable failure rate?

Putting it here for people to think about it prior to our meeting.

Also, cc./ @chris-wood

[thomwiggers]

Failures

Failures aiui only occur in IND-CPA secure KEMs, but you need an IND-CCA secure KEM (src: KEMTLS paper). This means failures would be cryptographically negligible