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

2024-01-11 Thread Mike Ounsworth 
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  
Sent: Thursday, January 11, 2024 9:38 AM
To: Mike Ounsworth ; Bas Westerbaan 

Cc: IRTF CFRG ;  ; 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 

 ) argues this holds for ML-KEM – or any similar KEM – but that depends on 
decapsulation functioning correctly.

 

Peter  

 

From: CFRG mailto:cfrg-boun...@irtf.org> > On Behalf Of 
Mike Ounsworth
Sent: Thursday, January 11, 2024 2:57 PM
To: Bas Westerbaan mailto:bas=40cloudflare@dmarc.ietf.org> >
Cc: IRTF CFRG mailto:c...@irtf.org> >; mailto:tls@ietf.org> > mailto:tls@ietf.org> >; 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 mailto:bas=40cloudflare@dmarc.ietf.org> > 
Sent: Thursday, January 11, 2024 7:07 AM
To: Mike Ounsworth mailto:mike.ounswo...@entrust.com> >
Cc: IRTF CFRG mailto:c...@irtf.org> >; mailto:tls@ietf.org> > mailto:tls@ietf.org> >; Deirdre Connolly 
mailto:durumcrustu...@gmail.com> >; 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,

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

2024-01-11 Thread Peter C 
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  On Behalf Of Mike Ounsworth
Sent: Thursday, January 11, 2024 2:57 PM
To: Bas Westerbaan 
Cc: IRTF CFRG ;  ; 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 
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