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

[Deirdre Connolly <[e-mail]>]

I'm going to echo Bas to highlight that X-Wing is not generic to any
IND-CCA KEM, it is a particular primitive construction based on the
internal construction of ML-KEM in particular:

> 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.

While we have put some of this in the I-D the paper has the meat of this
analysis: https://eprint.iacr.org/2024/039.pdf

On Thu, Jan 11, 2024, 11:58 AM Kampanakis, Panos <kpanos=
[e-mail]> wrote:

> +1 on making X-Wing a generic construction and stir in the KEM ciphertext.
>
>
>
> In the ML-KEM case, the SHAKE256 cost of an additional 1-1.5KB ciphertext
> c2 will be miniscule compared to the other operations. And this will be
> similar for other KEMs are well.
>
>
>
> For example, from https://bench.cr.yp.to/results-sha3.html it seems the
> total additional cost would be ~15 Kcycles for ML-KEM-1024 in most
> platforms which is pretty small compared to the
> sk2<-random(32)+ske<-random(32)+X25519.DH(ske, gX25519)+X25519.DH(sk2,
> gX25519) costs which amount to 400-1200 Kcycles (using
> https://bench.cr.yp.to/results-dh.html). Is a 5% savings worth the ML-KEM
> specific combiner?
>
>
>
>
>
>
>
> *From:* TLS <[e-mail]> *On Behalf Of * Peter C
> *Sent:* Thursday, January 11, 2024 10:38 AM
> *To:* Mike Ounsworth <Mike.Ounsworth=[e-mail]>; Bas
> Westerbaan <bas=[e-mail]>
> *Cc:* IRTF CFRG <[e-mail]>; <[e-mail]> <[e-mail]>;
> [e-mail]
> *Subject:* RE: [EXTERNAL] [TLS] [CFRG] [EXTERNAL] X-Wing: the go-to PQ/T
> hybrid KEM?
>
>
>
> *CAUTION*: This email originated from outside of the organization. Do not
> click links or open attachments unless you can confirm the sender and know
> the content is safe.
>
>
>
> Mike,
>
>
>
> X-Wing is not a profile of the generic construction.  Dropping the ML-KEM
> ciphertext changes the security assumptions you need to make.  If X25519 is
> secure then, in the generic construction, ML-KEM doesn’t need to satisfy
> any security properties at all for the hybrid to be secure.  In X-Wing, it
> still needs to be ciphertext collision resistant.  The X-Wing paper (
> https://ia.cr/2024/039) argues this holds for ML-KEM – or any similar KEM
> – but that depends on decapsulation functioning correctly.
>
>
>
> Peter
>
>
>
> *From:* CFRG <[e-mail]> *On Behalf Of *Mike Ounsworth
> *Sent:* Thursday, January 11, 2024 2:57 PM
> *To:* Bas Westerbaan <bas=[e-mail]>
> *Cc:* IRTF CFRG <[e-mail]>; <[e-mail]> <[e-mail]>;
> [e-mail]
> *Subject:* Re: [CFRG] [EXTERNAL] X-Wing: the go-to PQ/T hybrid KEM?
>
>
>
> Right. I’m just thinking out loud here.
>
>
>
> If the Generic is
>
>
>
> KDF(counter || KEM1_ct || KEM1_ss || KEM2_ct  || KEM2_ss || fixedInfo)
>
>
>
> And X-Wing is:
>
>
>
> SHA3-256( “\.//^\” || ML-KEM_ss || X25519_ss || X25519_ct || X25519_pk )
>
>
>
> It looks pretty close to me; you’ve dropped the ML-KEM CT, added the
> X25519 recipient public key, and moved the fixedInfo from the end to the
> beginning.
>
>
>
> The question is: is that close enough to be considered a profile? Do we
> want to adapt the Generic so that X-Wing is properly a profile? Binding to
> the ECC public keys is probably not a bad idea in general. Certainly it
> would make no sense for some IETF protocols to use X-Wing while others use
> the ML-KEM + X25519 instantiation of the generic. I think I’m convincing
> myself that the Generic should be adjusted so that X-Wing is the obvious
> instantiation for ML-KEM + X25519.
>
>
>
> Aside: do you have an opinion about fixedInfo as a prefix vs a suffix? We
> chose suffix simply because it more obviously aligns with SP 800-56Cr2, and
> we’ve all had the experience of FIPS labs being picky about things like
> that.
>
>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* Bas Westerbaan <bas=[e-mail]>
> *Sent:* Thursday, January 11, 2024 7:07 AM
> *To:* Mike Ounsworth <[e-mail]>
> *Cc:* IRTF CFRG <[e-mail]>; <[e-mail]> <[e-mail]>; Deirdre
> Connolly <[e-mail]>; [e-mail]
> *Subject:* Re: [EXTERNAL] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?
>
>
>
> Speaking for myself (not for my co-authors), this feels like friendly,
> complementary work to draft-ounsworth-cfrg-kem-combiners; I agree. We could
> consider adding a section with concrete instantiations, and the first one
> would be X-Wing 😊 (followed
>
>
>
>
>
> Speaking for myself (not for my co-authors), this feels like friendly,
> complementary work to draft-ounsworth-cfrg-kem-combiners;
>
>
>
> I agree.
>
>
>
> We could consider adding a section with concrete instantiations, and the
> first one would be X-Wing 😊 (followed by ML-KEM + P-256, Brainpool, and
> RSA variants).
>
>
>
> I guess that leads to the following question: @Bas Westerbaan
> <bas=[e-mail]>, @Deirdre Connolly
> <[e-mail]>, Peter, would you be open to merging X-Wing
> into the generic combiner draft, or is there value in it being standalone?
>
>
>
> X-Wing explicitly trades genericity for simplicity. We will not get such a
> simple and efficient construction if it is the instantiation of an
> easy-to-use generic construction.
>
>
>
> Best,
>
>
>
>  Bas
>
>
>
>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* CFRG <[e-mail]> *On Behalf Of *Bas Westerbaan
> *Sent:* Wednesday, January 10, 2024 2:14 PM
> *To:* IRTF CFRG <[e-mail]>; <[e-mail]> <[e-mail]>
> *Cc:* [e-mail]
> *Subject:* [EXTERNAL] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?
>
>
>
> 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
>
> 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/
> <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-Y-JP2DY$>
> Proof: https://eprint.iacr.org/2024/039
> <https://urldefense.com/v3/__https:/eprint.iacr.org/2024/039__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-Xl0zY2C$>
> [1] Full name X25519Kyber768Draft00.
> https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/
> <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-bUDJTlz$>
> [2] Full name SecP256r1Kyber768Draft00.
> https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/
> <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-cpge9_6$>
> [3]
> https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html
> <https://urldefense.com/v3/__https:/blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-X2cJwvg$>
> https://twitter.com/bwesterb/status/1734586155868287457
> <https://urldefense.com/v3/__https:/twitter.com/bwesterb/status/1734586155868287457__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-agVitjD$>
> [4] https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/
> <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-axrezMz$>
> [5] https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7
> <https://urldefense.com/v3/__https:/link.springer.com/chapter/10.1007/978-3-319-76578-5_7__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-U_tyIdl$>
> [6]
> https://datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/
> <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-V-p_aAA$>
> [7] https://datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/
> <https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-bx4gLTn$>
> [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.
>
> _______________________________________________
> TLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tls
>