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

[Bas Westerbaan]

>  Because for embedded devices that don’t have enough memory to hold all
> of those objects in simultaneously, this is likely the order in which it
> would have those things available to stream into SHA3.
>

That will not make a difference: the SHA3-256 rate is 136 bytes.


> Another thing to consider: thinking of how crypto libraries and HSMs are
> structures, will an X25519 decrypter necessarily have access to its own
> public key? For example I could imagine that to do X25519 based protocols
> today, an HSM only needs to store the X25519 private key. It’s probably
> worth a bit of a survey to see if adding a requirement for the HSM to know
> the X25519 public key will cause chaos with existing X25519 implementations.
>

Good point. Filippo also pointed out that having the pk as an argument to
decapsulate is inconvenient. He suggests to simply add the X25519 public
key to the X-Wing private key (similar to what ML-KEM also does), and that
makes sense to me.
https://github.com/dconnolly/draft-connolly-cfrg-xwing-kem/issues/8


>
>
> ---
>
> *Mike* Ounsworth
>
>
>
> *From:* CFRG  *On Behalf Of *D. J. Bernstein
> *Sent:* Thursday, January 11, 2024 6:47 AM
> *To:* c...@irtf.org; tls@ietf.org
> *Subject:* [EXTERNAL] Re: [CFRG] X-Wing: the go-to PQ/T hybrid KEM?
>
>
>
> Do we have a survey of hybrid patents? To be clear, for security reasons I
> recommend a straightforward policy of always using hybrids (https:
> //urldefense. com/v3/__https: //blog. cr. yp. to/20240102-hybrid.
> html__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHAo-X8km$).
>
>
> Do we have a survey of hybrid patents?
>
>
>
> To be clear, for security reasons I recommend a straightforward policy
>
> of always using hybrids 
> (https://urldefense.com/v3/__https://blog.cr.yp.to/20240102-hybrid.html__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHAo-X8km$
>  
> ).
>
> NIST reportedly bought out some hybrid patents; I'm not aware of hybrid
>
> patents that predate the clear prior art; and in any case it has been
>
> obvious for many years to try hashing any selection of the available
>
> inputs that both sides see, such as ciphertexts, public keys, session
>
> keys, and/or context labels. But I worry that a profusion of hybrid
>
> mechanisms could have someone getting into trouble with a non-bought-out
>
> patent on some specific hybrid mechanism, because of an unfortunate
>
> choice of details matching what the patent happens to cover. A patent
>
> survey would reduce concerns here.
>
>
>
> Bas Westerbaan writes:
>
> > SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519
>
> > )
>
>
>
> 1. I'd include the post-quantum ciphertext (or a hash of it). Rationale:
>
> This makes the construction more generic, and simplifies security
>
> review. There's negligible performance cost compared to the cost of
>
> communicating the ciphertext in the first place. (For quantification of
>
> costs of communication etc., see 
> https://urldefense.com/v3/__https://cr.yp.to/papers.html*pppqefs__;Iw!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHM0iBL7o$
>  
> .)
>
>
>
> 2. I think it's good that both of the X25519 public keys are included
>
> where some hybrid constructions would include just one (labeled as
>
> ciphertext). Rationale: less chance of confusion regarding which key to
>
> include; better fit with some existing uses of X25519; might marginally
>
> simplify security review; even smaller performance cost than including
>
> the post-quantum ciphertext.
>
>
>
> 3. There are papers that recommend also including at least a 32-byte
>
> prefix of the post-quantum pk: (1) 
> https://urldefense.com/v3/__https://eprint.iacr.org/2021/708__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHFgGO8fn$
>  
> 
>
> recommends including some sort of user identifier and claims that it
>
> isn't "robust" to have ciphertexts that might be decryptable by multiple
>
> users; (2) 
> https://urldefense.com/v3/__https://eprint.iacr.org/2021/1351__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHGLYF4Sp$
>  
> 
>  recommends including a pk
>
> prefix for a different reason, namely to ensure that certain types of
>

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

[Mike Ounsworth]

Bas Westerbaan writes:
> SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519
> )

 

 

One critique:

 

I would consider changing the order of the X25519 params to

 

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

 

Because for embedded devices that don’t have enough memory to hold all of those 
objects in simultaneously, this is likely the order in which it would have 
those things available to stream into SHA3.

 

Another thing to consider: thinking of how crypto libraries and HSMs are 
structures, will an X25519 decrypter necessarily have access to its own public 
key? For example I could imagine that to do X25519 based protocols today, an 
HSM only needs to store the X25519 private key. It’s probably worth a bit of a 
survey to see if adding a requirement for the HSM to know the X25519 public key 
will cause chaos with existing X25519 implementations.

 

---

Mike Ounsworth

 

From: CFRG  On Behalf Of D. J. Bernstein
Sent: Thursday, January 11, 2024 6:47 AM
To: c...@irtf.org; tls@ietf.org
Subject: [EXTERNAL] Re: [CFRG] X-Wing: the go-to PQ/T hybrid KEM?

 

Do we have a survey of hybrid patents? To be clear, for security reasons I 
recommend a straightforward policy of always using hybrids (https: 
//urldefense. com/v3/__https: //blog. cr. yp. to/20240102-hybrid. 
html__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHAo-X8km$).
  



Do we have a survey of hybrid patents?
 
To be clear, for security reasons I recommend a straightforward policy
of always using hybrids 
(https://urldefense.com/v3/__https://blog.cr.yp.to/20240102-hybrid.html__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHAo-X8km$
 

 ).
NIST reportedly bought out some hybrid patents; I'm not aware of hybrid
patents that predate the clear prior art; and in any case it has been
obvious for many years to try hashing any selection of the available
inputs that both sides see, such as ciphertexts, public keys, session
keys, and/or context labels. But I worry that a profusion of hybrid
mechanisms could have someone getting into trouble with a non-bought-out
patent on some specific hybrid mechanism, because of an unfortunate
choice of details matching what the patent happens to cover. A patent
survey would reduce concerns here.
 
Bas Westerbaan writes:
> SHA3-256( xwing-label || ss_ML-KEM || ss_X25519 || ct_X25519 || pk_X25519
> )
 
1. I'd include the post-quantum ciphertext (or a hash of it). Rationale:
This makes the construction more generic, and simplifies security
review. There's negligible performance cost compared to the cost of
communicating the ciphertext in the first place. (For quantification of
costs of communication etc., see 
https://urldefense.com/v3/__https://cr.yp.to/papers.html*pppqefs__;Iw!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHM0iBL7o$
 

 .)
 
2. I think it's good that both of the X25519 public keys are included
where some hybrid constructions would include just one (labeled as
ciphertext). Rationale: less chance of confusion regarding which key to
include; better fit with some existing uses of X25519; might marginally
simplify security review; even smaller performance cost than including
the post-quantum ciphertext.
 
3. There are papers that recommend also including at least a 32-byte
prefix of the post-quantum pk: (1) 
https://urldefense.com/v3/__https://eprint.iacr.org/2021/708__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHFgGO8fn$
 

 
recommends including some sort of user identifier and claims that it
isn't "robust" to have ciphertexts that might be decryptable by multiple
users; (2) 
https://urldefense.com/v3/__https://eprint.iacr.org/2021/1351__;!!FJ-Y8qCqXTj2!eCunOU4zfX1vpARMymMYJyVdkjDscfW5QfvZotQ6soJwvvD8HKo-4gGHPJmhOhHuQVi78yuEHGLYF4Sp$
 

  recommends including a pk
prefix for a different reason, namely to ensure that certain types of
cryptanalytic attacks have to commit to the key they're attacking, which
might make multi-key attacks harder.
 
These arguments are weak, but the counterarguments that I see are also
weak. On balance, I'd think that it's best to just include the pk (or a
hash of the pk) in the hybrid-hash input, so people w