Hi Peter.
Yeah, I get that; this is an optimization of the generic around the properties
of ML-KEM.
My thinking-out-loud here is twofold:
1. Let’s avoid the situation where we have both X-Wing and
generic-combiner-mlkem-x25519 floating around IETF protocols. I’m basically
suggesting to put language in the generic combiner draft to say “If one of your
KEMs is ML-KEM, then the follow optimization SHOULD be used”.
2. I’m on board with Bas, Deirdre, and Peter that X-Wing (ML-KEM-768 + X25519)
satisfies a large number of majority usecases, and having it as a standalone
document allows it to move ahead of the generics debate. HOWEVER, we will
eventually need specifications for some fuller subset of {ML-KEM-512,
ML-KEM-768, ML-KEM-1024} X {X25519, X448, P-256, P-384, Brainpool-P-256,
Brainpool-P-384, RSA}, which can all also presumably benefit from the ML-KEM
specific optimizations, so does that mean we’ll have a whole Rogue Squadron of
drafts: A-Wing, B-Wing, Y-Wing? Or should the ML-KEM optimizations be
considered in the generics draft?
Again, just thinking out loud here in front of the community.
---
Mike Ounsworth
From: Peter C <Peter.C=40ncsc.gov...@dmarc.ietf.org>
Sent: Thursday, January 11, 2024 9:38 AM
To: Mike Ounsworth <mike.ounswo...@entrust.com>; Bas Westerbaan
<b...@cloudflare.com>
Cc: IRTF CFRG <c...@irtf.org>; <tls@ietf.org> <tls@ietf.org>; k...@cupdev.net
Subject: RE: [CFRG] [EXTERNAL] X-Wing: the go-to PQ/T hybrid KEM?
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
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
<https://urldefense.com/v3/__https:/ia.cr/2024/039__;!!FJ-Y8qCqXTj2!cP8j9IZHePmHD_D-01VoJE2GJPz82LPZLZX8YLuF92hhB1eGStkDIdFnePNQQ7UZAiqZWkIsKNb8KOsgyyRNBXBY1Mv22L6QoKD1$>
) argues this holds for ML-KEM – or any similar KEM – but that depends on
decapsulation functioning correctly.
Peter
From: CFRG <cfrg-boun...@irtf.org <mailto:cfrg-boun...@irtf.org> > On Behalf Of
Mike Ounsworth
Sent: Thursday, January 11, 2024 2:57 PM
To: Bas Westerbaan <bas=40cloudflare....@dmarc.ietf.org
<mailto:bas=40cloudflare....@dmarc.ietf.org> >
Cc: IRTF CFRG <c...@irtf.org <mailto:c...@irtf.org> >; <tls@ietf.org
<mailto:tls@ietf.org> > <tls@ietf.org <mailto:tls@ietf.org> >; k...@cupdev.net
<mailto:k...@cupdev.net>
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=40cloudflare....@dmarc.ietf.org
<mailto:bas=40cloudflare....@dmarc.ietf.org> >
Sent: Thursday, January 11, 2024 7:07 AM
To: Mike Ounsworth <mike.ounswo...@entrust.com
<mailto:mike.ounswo...@entrust.com> >
Cc: IRTF CFRG <c...@irtf.org <mailto:c...@irtf.org> >; <tls@ietf.org
<mailto:tls@ietf.org> > <tls@ietf.org <mailto:tls@ietf.org> >; Deirdre Connolly
<durumcrustu...@gmail.com <mailto:durumcrustu...@gmail.com> >; k...@cupdev.net
<mailto:k...@cupdev.net>
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:
<mailto:bas=40cloudflare....@dmarc.ietf.org> @Bas Westerbaan,
<mailto:durumcrustu...@gmail.com> @Deirdre Connolly, 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 < <mailto:cfrg-boun...@irtf.org> cfrg-boun...@irtf.org> On Behalf Of
Bas Westerbaan
Sent: Wednesday, January 10, 2024 2:14 PM
To: IRTF CFRG < <mailto:c...@irtf.org> c...@irtf.org>; < <mailto:tls@ietf.org>
tls@ietf.org> < <mailto:tls@ietf.org> tls@ietf.org>
Cc: <mailto:k...@cupdev.net> k...@cupdev.net
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://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-Y-JP2DY$>
https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/
Proof:
<https://urldefense.com/v3/__https:/eprint.iacr.org/2024/039__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-Xl0zY2C$>
https://eprint.iacr.org/2024/039
[1] Full name X25519Kyber768Draft00.
<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-bUDJTlz$>
https://datatracker.ietf.org/doc/draft-tls-westerbaan-xyber768d00/
[2] Full name SecP256r1Kyber768Draft00.
<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-cpge9_6$>
https://datatracker.ietf.org/doc/draft-kwiatkowski-tls-ecdhe-kyber/
[3]
<https://urldefense.com/v3/__https:/blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-X2cJwvg$>
https://blog.chromium.org/2023/08/protecting-chrome-traffic-with-hybrid.html
<https://urldefense.com/v3/__https:/twitter.com/bwesterb/status/1734586155868287457__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-agVitjD$>
https://twitter.com/bwesterb/status/1734586155868287457
[4]
<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-axrezMz$>
https://datatracker.ietf.org/doc/draft-stebila-tls-hybrid-design/
[5]
<https://urldefense.com/v3/__https:/link.springer.com/chapter/10.1007/978-3-319-76578-5_7__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-U_tyIdl$>
https://link.springer.com/chapter/10.1007/978-3-319-76578-5_7
[6]
<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-V-p_aAA$>
https://datatracker.ietf.org/doc/draft-westerbaan-cfrg-hpke-xyber768d00/
[7]
<https://urldefense.com/v3/__https:/datatracker.ietf.org/doc/draft-ounsworth-cfrg-kem-combiners/__;!!FJ-Y8qCqXTj2!YuGyk3egE_PIU03oVixCUPtatL8PHtv4HwoB1vN5giqCIDkH6AQcs-lATDzPlozu91nN60pT2kp1AwmLESgzB4xc58lF-bx4gLTn$>
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.
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
