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

[Bas Westerbaan]

On Thu, Jan 11, 2024 at 3:56 PM Mike Ounsworth  wrote:

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

The X-Wing combiner is not necessarily secure when instantiated with other
primitives. The big one is that we need a ciphertext collision resistant
KEM. Also we use that ML-KEM mixes in its own public key in the shared
secret. And then there are more assumptions: assuming fixed length
ciphertext/shared secrets, assuming we fit within the KDF block size (see
Dan's e-mail).

We could make the generic combiner simpler depending on the
primitives used, but that will make the generic combiner specification much
more complex/subtle.


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 
> *Sent:* Thursday, January 11, 2024 7:07 AM
> *To:* Mike Ounsworth 
> *Cc:* IRTF CFRG ;  ; Deirdre
> Connolly ; 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: @Bas Westerbaan
> , @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  *On Behalf Of *Bas Westerbaan
> *Sent:* Wednesday, January 10, 2024 2:14 PM
> *To:* IRTF CFRG ;  
> *Cc:* 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 

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

[Mike Ounsworth]

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  
Sent: Thursday, January 11, 2024 7:07 AM
To: Mike Ounsworth 
Cc: IRTF CFRG ;  ; Deirdre Connolly 
; 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:  
 @Bas Westerbaan,  
 @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> > On Behalf Of 
Bas Westerbaan
Sent: Wednesday, January 10, 2024 2:14 PM
To: IRTF CFRG mailto:c...@irtf.org> >; mailto:tls@ietf.org> > mailto:tls@ietf.org> >
Cc: 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; 

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

[Bas Westerbaan]

> 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
> , @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  *On Behalf Of *Bas Westerbaan
> *Sent:* Wednesday, January 10, 2024 2:14 PM
> *To:* IRTF CFRG ;  
> *Cc:* 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://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/
> 

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

[Mike Ounsworth]

Thanks for this work!

 

Speaking for myself (not for my co-authors), this feels like friendly, 
complementary work to draft-ounsworth-cfrg-kem-combiners; X-Wing could be 
viewed as a profile of ounsworth-kem-combiners that optimizes around the 
security properties of ML-KEM.

 

Bas makes a good point that ounsworth-kem-combiners is not by itself 
implementable because it does not provide concrete instantiations. 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,  
 @Deirdre Connolly, Peter, would you be open 
to merging X-Wing into the generic combiner draft, or is there value in it 
being standalone?

 

---

Mike Ounsworth

 

From: CFRG  On Behalf Of Bas Westerbaan
Sent: Wednesday, January 10, 2024 2:14 PM
To: IRTF CFRG ;  
Cc: 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://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/