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

[Peter Schwabe]

"D. J. Bernstein"  wrote:
> Peter Schwabe writes:

Dear Dan, dear all,

> > we would like to have an answer to the question "What KEM should
> > I use" that is as simple as
> >   "Use X-Wing."
> 
> Having an easy-to-use, prepackaged answer is great! 

Glad to hear that we agree!

> What I'm saying is that the easy-to-use, prepackaged answer should
> _internally_ use a combiner that includes the full ciphertext and
> public key in the hash:
> 
>H = SHA3-256,
>hybridpk = (receiverpkECDH,receiverpkKEM),
>hybridct = (senderpkECDH,senderctKEM),
>hybridss = H(ssECDH,ssKEM,H(hybridct),H(hybridpk),context)
> 
> This reduces load on security reviewers: everyone can see that the full
> ct is included in the hash, without having to worry about KEM details.

Here I disagree: the security analysis needs to be done *once* (and has
been done, but of course still needs review; ideally also
computer-verification). Once this review has been done, the savings in
cycle counts come for free.

The idea that hashes come for free is simply no longer true in a PQ
world and if we manage to eliminate a significant (albeit not huge)
amount of cycles through a careful security analysis that needs to be
done once, I expect this to be helpful for adoption.

> It also reduces risks for people who rip out the KEM (for example,
> because of patent concerns) and swap in another KEM.

This is why it's very important to standardize (and communicate) X-Wing
as a KEM, not as a combiner. This is also why I wouldn't want QSF or the
very specific combiner to be added to any other standard as a standalone
"combiner primitive".

>   [ regarding TLS ]
> > I would trust that careful
> > evaluations of the pros and cons lead to the decision to *not* use a
> > generic combiner to build a hybrid KEM from Kyber768 and X25519.
> 
> When and where would this comparison of combiners have happened?
> Citation needed, especially if the previous evaluation is supposed to
> serve as a substitute for current evaluation.

I was not involved in the decision-making process of the current TLS
deployment, so I will have to let people answer who did make those
design decisions.

All the best,

Peter

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

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

[Peter Schwabe]

Ilari Liusvaara  wrote:
> On Tue, Jan 16, 2024 at 08:49:24AM -0800, Eric Rescorla wrote:
> > On Tue, Jan 16, 2024 at 8:24 AM D. J. Bernstein  wrote:

Dear Ilari, dear all,

> > > To be clear, I think other concerns such as efficiency _can_ outweigh
> > > the advantages of unification, but this has to be quantified. When I see
> > > a complaint about "hashing the typically large PQ ciphertexts", I ask
> > > how this compares quantitatively to communicating the ciphertexts, and
> > > end up with a cost increment around 1%, which is negligible even in the
> > > extreme case that the KEM is the main thing the application is doing.
> > >
> > 
> > Responding to Dan but really this is a question to the draft authors. Do
> > you agree with Dan on the approximate overhead here?
> 
> I am not one of draft authors, but I tried to estimate the overhead and
> ended up with in ballpark of 7%.

The 7% sound about right as a ballpark number, but will also highly
depend on the environment. However, I don't think that the question
about the cost of hashing the ciphertext is the right question to ask,
because it misses the point of why we propose X-Wing.

There is, without a doubt, value in standardizing a generic combiner that
can be used with any two CCA-secure KEMs to obtain a hybrid CCA-secure
KEM. I expect many contraints (performance, policy, certification) that
will make different applications choose different KEMs or parameter sets
and they will need precisely such a standard of a generic combiner.

There may also be value in solutions that exploit protocol features to
maximize performance. This is what the currently deployed combination of
Kyber768 and X25519 in TLS uses and I would trust that careful
evaluations of the pros and cons lead to the decision to *not* use a
generic combiner to build a hybrid KEM from Kyber768 and X25519.

With X-Wing, we're aiming at something else, namely a "cryptographically
opinionated" go-to solution for anybody who wants a KEM that is as
simple to integrate and deploy as any other, non-hybrid, KEM. In other
words, we would like to have an answer to the question "What KEM should
I use" that is as simple as 

  "Use X-Wing." 

and not as complicated as 

  "Use Kyber768, but of course you should go for a hybrid solution
  together with some ECDH; look at this standard for a generic combiner,
  but if your protocol hashes full transcripts into the session key, it
  might be OK to not hash in the long ciphertext and gain some
  performance, except there is no formal proof of that".

I believe that such a simple go-to solution is exactly what many
applications will want and that standardizing X-Wing as a KEM (which
simply happens to be hybrid), will be helpful for a sensible migration
to PQC.

All the best,

Peter

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls