[CFRG] X-Wing: the go-to PQ/T hybrid KEM?

[Bas Westerbaan <[e-mail]>]

Dear tls and cfrg working groups,

With ML-KEM (née Kyber) expected to be finalized this year, it’s time to
revisit the question of which PQ/T hybrid KEMs to standardize, and which to
recommend.

# Status quo

For TLS at the time of writing there are two PQ/T hybrids registered:
X25519Kyber768 [1] and P256Kyber768 [2]. The former has been deployed
widely [3]. Both are instances of the hybrid-design draft [4], which use
the simple combiner ss_ECC || ss_Kyber, which is suitable for TLS, but not
for other applications such as HPKE, as it’s not IND-CCA2 robust [5].

For HPKE, there is a different KEM called X25519Kyber768 [6], which uses a
different combiner that mixes in the X25519 ephemeral key, by using HPKE’s
DHKEM construction instead of raw X25519.

There is also the ounsworth-kem-combiners I-D [7] that informed by [5]
proposes the generic combiner

  KDF( counter || ct1 || ss1 || ct2 || ss2 || fixedInfo, outputBits )

>From a security standpoint that would be suitable for HPKE and TLS. To TLS
it is somewhat unattractive as it requires hashing the typically large PQ
ciphertexts, and adds some extra hashing in the conversion of the ECDH into
a KEM. On the other hand, for TLS it would be nice to have a KEM that is
also suitable for HPKE, as HPKE is used in ECH.

>From a usability perspective, ounsworth-kem-combiners requires the user to
make several choices: which KEMs and in particular which method to use to
turn ECDH into a KEM, which security levels, which KDF, etc.

# The proposal: X-Wing

Let us introduce X-Wing [0]. The goal of X-Wing is to be *the* go-to PQ/T
hybrid KEM for the majority of use cases (including TLS and HPKE): no need
to make choices, or understand the subtleties.

X-Wing aims for 128-bit security, and for that combines the time-tested
X25519 with ML-KEM-768 [8]. X-Wing uses the combiner

  SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519
)

Here ss_X25519 is the plain X25519 shared secret; ct_X25519 is the
ephemeral public key; xwing-label a 6-byte label. Note that it doesn’t hash
in the ML-KEM ciphertext. For a generic KEM one cannot leave out the
ciphertext, but in the case of ML-KEM we can, assuming we can model
SHA3/SHAKE as a random oracle. This is proven in [0]. The gist is that FO
transform in ML-KEM makes it “ciphertext collision resistant”: even if the
underlying lattice problem is broken, it’s infeasible to create from one
ciphertext another different ciphertext with the same shared secret.

# Not final

We would love to hear your input: X-Wing is not final. For one, ML-KEM
itself might still change (presumably only in minor ways) before final
standardization. We think the CFRG would be a good venue to standardize
X-Wing — do you concur?

Best,

Bas, Deirdre, Karolin, Manuel, Peter


PS. We want to mention explicitly that we see value in the kem-combiners
and hybrid-design drafts as generic safe methods to construct hybrids for
those use cases where X-Wing would not suffice.


[0] Spec: https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/
Proof: https://eprint.iacr.org/2024/039
[1] Full name X25519Kyber768Draft00.
https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/
[2] Full name SecP256r1Kyber768Draft00.
https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/
[3]
https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html
https://twitter.com/bwesterb/status/1734586155868287457
[4] https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/
[5] https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7
[6] https://datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/
[7] https://datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/
[8] Following earlier deployment of X25519Kyber768, despite targeting 128
bits, we use ML-KEM-768 instead of ML-KEM-512 to hedge against advances in
lattice attacks.