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

[D. J. Bernstein]

Natanael writes:
> 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).

Sure, security tokens could move from signatures to KEMs. The security
token's public key is then a KEM public key. To prove it's online (and
optionally approve and/or send some data), the token receives a KEM
ciphertext from the verifier, and uses the KEM session key as the key
for a MAC (or for an authenticated cipher to send secret data).

For Kyber-768, communicating 1088 bytes of ciphertext at (say) 106 Kbps
(minimum-speed NFC) takes 82 ms plus lower-layer overhead.

Meanwhile the "few" cycles that you're talking about would be on, say, a
Cortex-M4 running at tens of MHz (see https://eprint.iacr.org/2022/1225
running Dilithium on an OpenSK security token), and this CPU would hash
1088 bytes with SHA3-256 in about 2 ms (even without Keccak hardware).
How is the user of the security token supposed to notice those 2 ms, or
another 2 ms to also hash the public key?

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

[Natanael]

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?

[D. J. Bernstein]

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

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

[D. J. Bernstein]

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?

[D. J. Bernstein]

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

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

[Ilari Liusvaara]

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?

[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

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

[Ilari Liusvaara]

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

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

[Eric Rescorla]

On Tue, Jan 16, 2024 at 8:24 AM D. J. Bernstein  wrote:

> Bas Westerbaan writes:
> > X-Wing is a KEM - not a combiner.
>
> Sure, but there's a combiner present inside it---and even advertised:
> see "X-Wing uses the combiner" etc. at the beginning of this thread.
>
> If people are motivated by things like http://tinyurl.com/5cu2j5hf to
> use the same combiner with a different KEM, would they be deterred by a
> presentation purely as a unified package? Or by enough warnings? Maybe,
> but a little more hashing has negligible cost and will reduce the risk.
>
> > Insisting that X-Wing use that generic combiner, is not dissimilar to
> > insisting that every KEM that uses an FO transform, should use the
> > same generic FO transform.
>
> The title and introduction of https://cr.yp.to/papers.html#tightkem
> recommend unifying FO transforms. This would have avoided various
> subsequent breaks of NIST submissions.
>
> 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?

-Ekr
___
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]

Bas Westerbaan writes:
> X-Wing is a KEM - not a combiner.

Sure, but there's a combiner present inside it---and even advertised:
see "X-Wing uses the combiner" etc. at the beginning of this thread.

If people are motivated by things like http://tinyurl.com/5cu2j5hf to
use the same combiner with a different KEM, would they be deterred by a
presentation purely as a unified package? Or by enough warnings? Maybe,
but a little more hashing has negligible cost and will reduce the risk.

> Insisting that X-Wing use that generic combiner, is not dissimilar to
> insisting that every KEM that uses an FO transform, should use the
> same generic FO transform.

The title and introduction of https://cr.yp.to/papers.html#tightkem
recommend unifying FO transforms. This would have avoided various
subsequent breaks of NIST submissions.

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.

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

[Bas Westerbaan]

>
> The arguments for multiple KEMs are
> stronger than the arguments for multiple combiners.
>

X-Wing is a KEM — not a combiner. I agree there should preferably be one
go-to generic combiner. Insisting that X-Wing use that generic combiner, is
not dissimilar to insisting that every KEM that uses an FO transform,
should use the same generic FO transform.

Best,

 Bas
___
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]

Jack Grigg writes:
> As the paper states at the top of page 4, X-Wing includes the recipient's
> X25519 public key "as a measure of security against multi-target attacks,
> similarly to what is done in the ML-KEM design".

Thanks for the data. Assuming arguendo that this matters (as in my first
message), the basic risk to consider is that people end up mixing

   * a combiner that doesn't hash the post-quantum KEM public key
 because it expects the KEM to do that and

   * a KEM that doesn't hash the public key because it expects the
 combiner to do that,

so that KEM's public key doesn't end up getting hashed at all.

Given the basic goal of helping auditors, I think we should settle on
principles of (1) always using double encryption, (2) having as few
combiners as possible, and (3) having the combiner responsible for
hashing public keys and ciphertexts along with the shared secrets.

Rationale for assigning responsibility to the combiner rather than to
the underlying KEM: (1) KEM designs and analyses are already hard, with
breaks often taking years to appear---see the graph on slide 11 of

   https://cr.yp.to/talks/2024.01.11/slides-djb-20240111-pqcrypto-4x3.pdf

for the timeline of breaks so far of round-1 NIST submissions---and
adding more goals makes it harder. (2) KEM designs typically focus on
IND-CCA2. Properties beyond IND-CCA2 might be achieved as experiments or
accidents, but treating those as stable commitments is unjustified and
unsafe. (3) We know how to convincingly analyze a combiner as a separate
module, as in https://eprint.iacr.org/2018/024, starting purely from
IND-CCA2 assumptions on KEMs. (4) The arguments for multiple KEMs are
stronger than the arguments for multiple combiners. Having just one
combiner, and thus just one universal review of whether ciphertexts and
public keys are adequately hashed, seems more feasible than having just
one KEM.

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

[Jack Grigg]

On Mon, Jan 15, 2024 at 11:21 PM D. J. Bernstein  wrote:

> If the goal is maximum streamlining for IND-CCA2 then
> one shouldn't include the _recipient's_ X25519 public key in the hash,
> so why exactly does X-Wing include it?
>

As the paper states at the top of page 4, X-Wing includes the recipient's
X25519 public key "as a measure of security against multi-target attacks,
similarly to what is done in the ML-KEM design".

Cheers,
Jack
___
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]

> > 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).
> And it is required for the IND-CCA robustness: without it, it's not.

Well, that depends on _which_ X25519 key is included in the hash.

If the recipient's KEM public key is an X25519 public key, and the
sender's KEM ciphertext is an X25519 public key, and the KEM session key
is the X25519 shared secret, then the KEM obviously isn't IND-CCA2: it
has what https://www.shoup.net/iso/ calls "benign malleability".

The normal way to upgrade from benign malleability to IND-CCA2 is to
also hash the ciphertext---i.e., the sender's X25519 public key---into
the session key. If the goal is maximum streamlining for IND-CCA2 then
one shouldn't include the _recipient's_ X25519 public key in the hash,
so why exactly does X-Wing include it?

I don't think the goal here should be maximum streamlining for IND-CCA2.
The point of hybrids is to do a bit more work to reduce the damage from
screwups; I think the scope of screwups under consideration should go
beyond mathematical breaks and also include implementation issues.

In particular, what happens if protocol designers confuse the two X25519
public keys here, and hash the _recipient's_ public key instead of the
_sender's_ public key? The upgrade to IND-CCA2 doesn't work. Hopefully
the protocol is okay with benign malleability, but there has been so
much emphasis on IND-CCA2 that it's hard to blame a protocol designer
for assuming that KEMs have that property.

So, as I said, I'm happy with a combiner hashing both of the X25519
public keys (along with the shared secret, obviously). But the same
perspective also makes me ask what happens when people replace Kyber
with a different post-quantum KEM. The combiner

   H = SHA3-256,
   hybridpk = (receiverpkECDH,receiverpkKEM),
   hybridct = (senderpkECDH,senderctKEM),
   hybridss = H(ssECDH,ssKEM,H(hybridct),H(hybridpk),context)

is then safer than X-Wing. Even for people using Kyber, this KEM makes
security review easier than X-Wing does. This combiner also satisfies
requests (see my first message for references) to include KEM public
keys (or at least prefixes of those) in the hash for other reasons.

I don't see how the cost of hashing hybridct can be an issue next to the
cost of communicating it. Same for hybridpk (and obviously the hash can
be saved whenever the public key is saved). I worry about complicating
KEM analyses since they're already complicated and error-prone in the
first place---we've seen many breaks of KEM proposals---but this
combiner is a separate module, and the IND-CCA2 property that it's
requesting from the input KEM is what we're asking a KEM to do anyway. I
think that the potential review benefit of _omitting_ hybridct and/or
hybridpk will be outweighed by the review complication of ending up with
more combiners than necessary.

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

Scott Fluhrer (sfluhrer) writes:
> If we have a combiner with a proof that “if either of the primitives
> we have meet security property A, then the output of the combiner
> meets security property B”, and we have proofs that both our
> primitives meet security property A”, then doesn’t that mean that our
> system has a proof that it meets security property B?

Certainly those proofs would compose. Even better, _one_ of the
primitives having property A would be enough.

However, the logic relies on a match between the two A properties that
you mention: the property provided by the KEMs, and the property assumed
by the combiner. The situation is different when

   * KEM designers and reviewers focus primarily on IND-CCA2, and then
   * a combiner comes along requiring its input KEM to provide some
 property _beyond_ IND-CCA2.

Then more review time is needed to see which KEMs have that property.
There's no reason to think that KEMs will always have that property.
There's a clear risk of people making the mistake of using the combiner
with a KEM that doesn't have that property.

We already know how to avoid this risk by changing the combiner to hash
more data, as in the

   hybridss = H(ECDHss,KEMss,H(hybridct),H(hybridpk),context)

construction that I mentioned before. Sure, for Kyber this is kilobytes
of extra hashing; how can this matter next to the cost of communicating
those kilobytes through the Internet in the first place?

Note also that real KEMs _aren't_ proven to be IND-CCA2 (never mind
properties beyond IND-CCA2); they aren't even proven to resist a
narrower class of attacks, namely QROM IND-CCA2. For example,

   
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/C0D3W1KoINY/m/GuWevJfPAQAJ

plausibly claims provability for the statement that an attacker limited
to (say) 2^90 hash calls can't carry out a high-probability QROM
IND-CCA2 attack against Kyber _if_ the attacker can't carry out an
IND-CPA attack with probability around 2^-92---but there's no proof that
such a low-probability IND-CPA attack is hard. Right now one can't even
find a clear statement of the resources required for the best _known_
low-probability IND-CPA attack.

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

Bas Westerbaan writes:
> At the moment the choice of hybrid is left to the application/protocol.
> This has led to many different proposals for hybrids, which wastes a lot of
> engineering, standardisation and security review time. I think it's better
> if hybridisation is done at the level of cryptographic primitive.

I agree that it's desirable to have KEMs that are internally using
double encryption and that can be reviewed independently of the target
application---not relying on details of TLS 1.3, for example.

For the same reasons (reducing security-review time, simplifying
standardization, etc.), it's desirable to minimize the number of
different double-encryption mechanisms. So I'd think that the default
path forward would be to pick a single combiner such as

   hybridss = H(ssECDH,ssKEM,H(hybridct),H(hybridpk),context)

where H is SHA3-256, hybridpk is (receiverpkECDH,receiverpkKEM), and
hybridct is (senderpkECDH,senderctKEM).

If there's instead a mechanism where the security analysis makes
reference to the Kyber details, then that's more effort to review, and
people plugging in KEMs other than Kyber (for good reasons: worrying
about the Kyber patent claim from http://tinyurl.com/5cu2j5hf, trusting
McEliece more, etc.) will need a different mechanism, so we end up with
more mechanisms than necessary. What's the advantage justifying this?

I saw the "hashing the typically large PQ ciphertexts" comment, but the
dollar-cost calculations from https://cr.yp.to/papers.html#pppqefs imply
that several thousand cycles to hash 1KB cost roughly 2^-38 dollars,
whereas sending or receiving 1KB costs roughly 2^-30 dollars. Is there
evidence of applications where the hashing cost is an issue?

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

[Bas Westerbaan]

On Thu, Jan 11, 2024 at 10:48 PM Martin Thomson  wrote:

>
>
> On Thu, Jan 11, 2024, at 07:13, Bas Westerbaan wrote:
> > 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 )
>
> At least for TLS, I'm not convinced that any combiner is necessary, in
> line with the analysis done for draft-ietf-tls-hybrid-design.
>

I agree, for TLS this is not required for security.

For TLS the trade-off is this: we add one single keccak permutation, so
that we can eliminate the need of two different KEMs both called
X25519Kyber768, which are both used in PQ TLS with PQ ECH.

Best,

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

[Scott Fluhrer (sfluhrer)]

I can’t say I agree with this argument.

If we have a combiner with a proof that “if either of the primitives we have 
meet security property A, then the output of the combiner meets security 
property B”, and we have proofs that both our primitives meet security property 
A”, then doesn’t that mean that our system has a proof that it meets security 
property B?  Wouldn’t that proof still apply even if one of our primitives 
fails due to some cryptanalytic attack?

Wouldn’t that also mean that if we have several primitives that all have proofs 
of security property A, we could mix-and-match as convenient, and that we don’t 
need to generate N^2 proofs to handle each of the combinations?  [Note: I’m not 
arguing that we should have this level of flexibility; only that we could]

As an analogy, consider the current TLS 1.3 situation.  There are multiple key 
agreements allowable (DH and ECDH), multiple ways to do authentication (PSK and 
certificate), multiple signature types (RSA and ECDSA), multiple data 
protection algorithms (GCM, ChaCha20).  For some reason, they don’t feel the 
need to prove each specific combination separately, but instead show that the 
various primitives meet some security assumptions, and go from there…


From: CFRG  On Behalf Of Orie Steele
Sent: Thursday, January 11, 2024 2:58 PM
To: Sophie Schmieg 
Cc: Salz, Rich ; Karolin Varner 
; Peter C ; IRTF CFRG 
; Bas Westerbaan ; 
 ; Kampanakis, Panos 

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

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.

OS



On Thu, Jan 11, 2024 at 1:35 PM Sophie Schmieg 
mailto:40google@dmarc.ietf.org>> 
wrote:
I very much appreciate having a concrete hybrid scheme that is intentionally 
not generic. This avoids the explosion of ciphertext suites that would 
otherwise occur, and allows for better compatibility of libraries. Fixing the 
key sizes to ML-KEM 768 and X25519 is aligned with our preferred choices as 
well, and further increases interoperability.

On Thu, Jan 11, 2024 at 9:31 AM Salz, Rich 
mailto:40akamai@dmarc.ietf.org>> wrote:
I'm going to echo Bas to highlight that X-Wing is not generic to any IND-CCA 
KEM, it is a particular primitive construction based on the internal 
construction of ML-KEM in particular:

I don’t think it’s our place to try to shoe-horn everything into one construct. 
 Particularly when we are in the experimentation phase of things.

If people want to have ML-KEM as a material in their composites, it sounds like 
they might want to learn from X-Wing, but not try to chop them to fit into that 
one keyhole, as it were.

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


--

Sophie Schmieg | Information Security Engineer | ISE Crypto | 
sschm...@google.com<mailto:sschm...@google.com>

___
CFRG mailing list
c...@irtf.org<mailto:c...@irtf.org>
https://mailman.irtf.org/mailman/listinfo/cfrg


--



ORIE STEELE
Chief Technology Officer
www.transmute.industries<http://www.transmute.industries>

[https://ci3.googleusercontent.com/mail-sig/AIorK4xqtkj5psM1dDeDes_mjSsF3ylbEa5EMEQmnz3602cucAIhjLaHod-eVJq0E28BwrivrNSBMBc]<https://transmute.industries/>
___
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?

[Orie Steele]

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.

OS




On Thu, Jan 11, 2024 at 1:35 PM Sophie Schmieg  wrote:

> I very much appreciate having a concrete hybrid scheme that is
> intentionally not generic. This avoids the explosion of ciphertext suites
> that would otherwise occur, and allows for better compatibility of
> libraries. Fixing the key sizes to ML-KEM 768 and X25519 is aligned with
> our preferred choices as well, and further increases interoperability.
>
> On Thu, Jan 11, 2024 at 9:31 AM Salz, Rich  40akamai@dmarc.ietf.org> wrote:
>
>> I'm going to echo Bas to highlight that X-Wing is not generic to any
>> IND-CCA KEM, it is a particular primitive construction based on the
>> internal construction of ML-KEM in particular:
>>
>>
>>
>> I don’t think it’s our place to try to shoe-horn everything into one
>> construct.  Particularly when we are in the experimentation phase of things.
>>
>>
>>
>> If people want to have ML-KEM as a material in their composites, it
>> sounds like they might want to learn from X-Wing, but not try to chop them
>> to fit into that one keyhole, as it were.
>>
>>
>> ___
>> TLS mailing list
>> TLS@ietf.org
>> https://www.ietf.org/mailman/listinfo/tls
>>
>
>
> --
>
> Sophie Schmieg | Information Security Engineer | ISE Crypto |
> sschm...@google.com
>
> ___
> CFRG mailing list
> c...@irtf.org
> https://mailman.irtf.org/mailman/listinfo/cfrg
>


-- 


ORIE STEELE
Chief Technology Officer
www.transmute.industries


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

[Sophie Schmieg]

I very much appreciate having a concrete hybrid scheme that is
intentionally not generic. This avoids the explosion of ciphertext suites
that would otherwise occur, and allows for better compatibility of
libraries. Fixing the key sizes to ML-KEM 768 and X25519 is aligned with
our preferred choices as well, and further increases interoperability.

On Thu, Jan 11, 2024 at 9:31 AM Salz, Rich  wrote:

> I'm going to echo Bas to highlight that X-Wing is not generic to any
> IND-CCA KEM, it is a particular primitive construction based on the
> internal construction of ML-KEM in particular:
>
>
>
> I don’t think it’s our place to try to shoe-horn everything into one
> construct.  Particularly when we are in the experimentation phase of things.
>
>
>
> If people want to have ML-KEM as a material in their composites, it sounds
> like they might want to learn from X-Wing, but not try to chop them to fit
> into that one keyhole, as it were.
>
>
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>


-- 

Sophie Schmieg | Information Security Engineer | ISE Crypto |
sschm...@google.com
___
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?

[Salz, Rich]

I'm going to echo Bas to highlight that X-Wing is not generic to any IND-CCA 
KEM, it is a particular primitive construction based on the internal 
construction of ML-KEM in particular:

I don’t think it’s our place to try to shoe-horn everything into one construct. 
 Particularly when we are in the experimentation phase of things.

If people want to have ML-KEM as a material in their composites, it sounds like 
they might want to learn from X-Wing, but not try to chop them to fit into that 
one keyhole, as it were.

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

[Deirdre Connolly]

I'm going to echo Bas to highlight that X-Wing is not generic to any
IND-CCA KEM, it is a particular primitive construction based on the
internal construction of ML-KEM in particular:

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

While we have put some of this in the I-D the paper has the meat of this
analysis: https://eprint.iacr.org/2024/039.pdf

On Thu, Jan 11, 2024, 11:58 AM Kampanakis, Panos  wrote:

> +1 on making X-Wing a generic construction and stir in the KEM ciphertext.
>
>
>
> In the ML-KEM case, the SHAKE256 cost of an additional 1-1.5KB ciphertext
> c2 will be miniscule compared to the other operations. And this will be
> similar for other KEMs are well.
>
>
>
> For example, from https://bench.cr.yp.to/results-sha3.html it seems the
> total additional cost would be ~15 Kcycles for ML-KEM-1024 in most
> platforms which is pretty small compared to the
> sk2<-random(32)+ske<-random(32)+X25519.DH(ske, gX25519)+X25519.DH(sk2,
> gX25519) costs which amount to 400-1200 Kcycles (using
> https://bench.cr.yp.to/results-dh.html). Is a 5% savings worth the ML-KEM
> specific combiner?
>
>
>
>
>
>
>
> *From:* TLS  *On Behalf Of * Peter C
> *Sent:* Thursday, January 11, 2024 10:38 AM
> *To:* Mike Ounsworth ; Bas
> Westerbaan 
> *Cc:* IRTF CFRG ;  ;
> k...@cupdev.net
> *Subject:* RE: [EXTERNAL] [TLS] [CFRG] [EXTERNAL] X-Wing: the go-to PQ/T
> hybrid KEM?
>
>
>
> *CAUTION*: This email originated from outside of the organization. Do not
> click links or open attachments unless you can confirm the sender and know
> the content is safe.
>
>
>
> 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 

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

[Kampanakis, Panos]

+1 on making X-Wing a generic construction and stir in the KEM ciphertext.

In the ML-KEM case, the SHAKE256 cost of an additional 1-1.5KB ciphertext c2 
will be miniscule compared to the other operations. And this will be similar 
for other KEMs are well.

For example, from https://bench.cr.yp.to/results-sha3.html it seems the total 
additional cost would be ~15 Kcycles for ML-KEM-1024 in most platforms which is 
pretty small compared to the sk2<-random(32)+ske<-random(32)+X25519.DH(ske, 
gX25519)+X25519.DH(sk2, gX25519) costs which amount to 400-1200 Kcycles (using 
https://bench.cr.yp.to/results-dh.html). Is a 5% savings worth the ML-KEM 
specific combiner?



From: TLS  On Behalf Of Peter C
Sent: Thursday, January 11, 2024 10:38 AM
To: Mike Ounsworth ; Bas 
Westerbaan 
Cc: IRTF CFRG ;  ; k...@cupdev.net
Subject: RE: [EXTERNAL] [TLS] [CFRG] [EXTERNAL] X-Wing: the go-to PQ/T hybrid 
KEM?


CAUTION: This email originated from outside of the organization. Do not click 
links or open attachments unless you can confirm the sender and know the 
content is safe.


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

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

[Bas Westerbaan]

Hi Dan,

Thanks for your detailed comments.

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,


This construction is not meant to be generic, and we have security proof of
the IND-CCA robustness. I would be in favor of having Mike's draft
alongside X-Wing, so that people that are not satisfied with X-Wing, have a
safe recipe to create their own.


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

And it is required for the IND-CCA robustness: without it, it's not.


> 3. There are papers that recommend also including at least a 32-byte
> prefix of the post-quantum pk:


ML-KEM already includes the public key in the derivation of the shared
secret (line 6 algorithm 17), so we see no need to include it a second
time. Again, we do not aim to be a generic construction with X-Wing.


> I think the hybrid construction is a good place to put this hash. If
> there are many different hybrid constructions then factoring out another
> layer might be useful for reviewers, but I'd rather settle on a minimal
> number of hybrid constructions.
>

At the moment the choice of hybrid is left to the application/protocol.
This has led to many different proposals for hybrids, which wastes a lot of
engineering, standardisation and security review time. I think it's better
if hybridisation is done at the level of cryptographic primitive.


> 4. I'd put ss_X25519 before the post-quantum session key. This has a
> two-part rationale.
>

All inputs fit within one SHA3-256 block. Because of that, if I understand
correctly, the order is inconsequential.

Best,

 Bas
___
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]

Do we have a survey of hybrid patents?

To be clear, for security reasons I recommend a straightforward policy
of always using hybrids (https://blog.cr.yp.to/20240102-hybrid.html).
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://cr.yp.to/papers.html#pppqefs.)

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://eprint.iacr.org/2021/708
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://eprint.iacr.org/2021/1351 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 won't have to worry
about the possibility of protocols where omitting it causes issues.

There's a layering question regarding who's responsible for this hash. 
https://classic.mceliece.org/mceliece-security-20221023.pdf says the
following: "Classic McEliece follows the principle that any generic
transformation aiming at a goal beyond IND-CCA2 is out of scope for a
KEM specification. This is not saying that further hashing should be
avoided; it is saying that cryptographic systems should be appropriately
modularized."

I think the hybrid construction is a good place to put this hash. If
there are many different hybrid constructions then factoring out another
layer might be useful for reviewers, but I'd rather settle on a minimal
number of hybrid constructions.

4. I'd put ss_X25519 before the post-quantum session key. This has a
two-part rationale.

First, there's a rule of thumb saying to start with the input that's
least predictable for the attacker. This provides a principled way to
settle the order even in situations where there's no reason to think
that the order matters.

Second, available evidence such as https://kyberslash.cr.yp.to indicates
that the post-quantum session key is more likely to be predictable than
the X25519 shared secret. It's of course reasonable to argue that this
situation will be reversed eventually by a combination of quantum
computing and any required upgrades to the post-quantum KEMs, the same
way that it's reasonable to argue that hybrids will eventually be
unnecessary, but hybrid designs should disregard those arguments.

---D. J. Bernstein

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