Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?
Den ons 17 jan. 2024 21:11D. J. Bernstein skrev: > > > 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. > > I don't see how this argument survives quantification regarding the > hashes that we're talking about. Sending 1KB of ciphertext has roughly > the same dollar cost as 2 million CPU cycles; why would the application > care about a combiner spending 1 or even 2 cycles on hashing? > This assumes performance requirements only comes from settings like datacenters, but this is also likely to eventually get used in embedded devices some of which may be battery powered. Consider NFC devices such as security keys (typically 1-10 mW, less than 100 Kbps, and few available cycles). > ___ 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?
> > 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).
To clarify, what I'm talking about is the extra review load that comes
from having more combiners than necessary in the ecosystem.
For example, if Situation A asks security reviewers to look at a generic
combiner, and Situation B asks security reviewers to look at a generic
combiner _plus_ a 20-page paper about a Kyber-specific combiner, then
Situation A clearly reduces review load compared to Situation B.
In Situation A, with the combiner that I'm talking about, everyone can
look at the hybridss formula and immediately see that everything is
hashed in. In Situation B, reviewers have to look at the generic formula
_and_ look at how Kyber details interact with another combiner.
Of course we hope that any particular piece of security review can be
done just once and that's the end of it (OK Google, please read once
through the Chrome source code and remove the buffer overflows), but the
bigger picture is that many security failures are easily explained by
reviewer overload, so minimizing the complexity of what has to be
reviewed is a useful default policy. Minimizing TCBs is another example
of the same approach.
> 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.
I don't see how this argument survives quantification regarding the
hashes that we're talking about. Sending 1KB of ciphertext has roughly
the same dollar cost as 2 million CPU cycles; why would the application
care about a combiner spending 1 or even 2 cycles on hashing?
Another way to save a similar amount of CPU time would be to use a
universal hash to compress the input to Kyber's implicit-rejection hash
("J"). This has well-known proofs, and it can be decided separately by
each secret key without any interoperability issues---but I don't see
how applications would care: the KEM bottleneck is the communication
cost, not the cycle count.
> > 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.
And yet the combiner appeared explicitly in the first message in this
thread! I do think that adding enough warnings can reduce risks, but
it's even better to take the sharp edges out of the underlying tool.
---D. J. Bernstein
___
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?
"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 writes: > 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! 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. It also reduces risks for people who rip out the KEM (for example, because of patent concerns) and swap in another KEM. [ 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. ---D. J. Bernstein ___ 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?
Ilari Liusvaara writes: > I am not one of draft authors, but I tried to estimate the overhead > and ended up with in ballpark of 7%. To clarify, you mean that the _cycle_ counts go up by 7%? My comparison was explicitly against the cost of "communicating the ciphertexts". That's a much larger cost. Quantitatively (see https://cr.yp.to/papers.html#pppqefs), sending a byte through the Internet costs roughly 2^(-40) dollars, while a cycle of CPU time costs roughly 2^(-51) dollars. Sending a kilobyte, for example, costs roughly 2^(-30) dollars. Hashing a kilobyte, at roughly 2^3 cycles/byte, costs roughly 2^(-38) dollars, which is hundreds of times smaller. As another example of the same type of comparison, spending 2^15 cycles on Kyber enc or dec costs roughly 2^(-36) dollars, which is still a very small percentage of roughly 2^(-30) dollars for communicating the Kyber ciphertext (never mind the scenarios where the key is sent too). This is very different from the situation with (e.g.) X25519, where the cost of CPU time is much more noticeable next to communication cost. ---D. J. Bernstein ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
[TLS] tls - New Meeting Session Request for IETF 119
A new meeting session request has just been submitted by Deirdre Connolly, a Chair of the TLS Working Group. - Working Group Name: Transport Layer Security Area Name: Security Area Session Requester: Deirdre Connolly Number of Sessions: 1 Length of Session(s): 2 Hours Number of Attendees: 120 Conflicts to Avoid: Chair conflict: wish masque emu mls pearg privacypass dult cfrg wimse Technology overlap: quic lamps lake dnsop dprive cfrg oauth cfrg Key participant conflict: ppm maprg gendispatch privacypass webtrans saag secdispatch httpbis ohai cfrg Can't meet: Wednesday morning, Wednesday early afternoon, Wednesday late afternoon, Thursday morning, Thursday early afternoon, Thursday late afternoon, Friday morning, Friday early afternoon, Friday late afternoon Participants who must be present: Eric Rescorla Resources Requested: Special Requests: Please dont conflict with the WIMSE BOF - ___ 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?
On Thu, Jan 11, 2024 at 01:58:07PM -0600, Orie Steele wrote: > Hybrids by their very nature are the explosion. > > If there will only ever be X-Wing, I think it's fine to not make it generic > (since we admit that it is a special case, not an instance of a generic). > > However, if B-Wing (brainpool + kyber) and P-Wing (p curve + kyber) also > end up getting made, we never stopped the explosion, and we made it harder > to evaluate the security properties, and we delayed the rollout against > harvest and decrypt... for the cases where X-Wing could not fit. > > Yes, we will need proofs for all those other hybrids, sounds like that will > keep people busy for a while... It feels like promising false hope to say > that making X-Wing not generic will stop all that other work from > happening... If anything, making X-Wing generic will reduce the cost of > doing the work, that seems inevitable at this point. > > I do think it's important for this to not end up as "crabs in a bucket", > where each candidate holds the others back, and then they all get cooked > together. > > If arguing over generic's causes that, I suggest we not make generics a > requirement. It is actually worse than that. It seems hard to make generic composition mechanism that explodes only in its components, not in protocols as well. That is, it probably will not be better than the mess that exists now. Even having low and high variants for each of x, p and b curves would only be 6 KEMs. There are more protocols than that interested in hybrid KEM stuff. Plus I am not aware of any protocol where consensus is that generic composition is a great idea, let's do that. -Ilari ___ 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?
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
Re: [TLS] [CFRG] X-Wing: the go-to PQ/T hybrid KEM?
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: > > > 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%. -Ilari ___ TLS mailing list TLS@ietf.org https://www.ietf.org/mailman/listinfo/tls
