[CFRG] Re: Taking X-Wing to Independent Stream

["D. J. Bernstein" <[e-mail]>]

Sophie Schmieg writes:
> X-Wing has been well analyzed in academia [1], I don't think there are
> any concerns about the cryptographic correctness that would warrant
> further reviews here.

I have three basic security concerns regarding X-Wing. I don't think the
right way to address these concerns is "further reviews" (and I'm also
puzzled by the word "further"); I think X-Wing (and its descendants in
the hybrid-kems draft) should be eliminated in favor of Chempat.

1. The fact that there's a paper presenting a cryptosystem doesn't mean
the system is "well analyzed". Consider the fact that 33 of the 69
round-1 submissions in 2017 to NIST's competition have been publicly
broken (for details and links see https://cr.yp.to/papers.html#qrcsp)
often the breaks were years after the papers presenting the systems.

"Provably secure" constructions aren't some sort of magical exception to
the importance of review. See, e.g., https://eprint.iacr.org/2020/1578
efficiently breaking NTS-KEM's IND-CCA2 claim by exploiting a flaw in a
simple-sounding proof of security; the proof had appeared two years
before the flaw was pointed out. https://eprint.iacr.org/2019/1336
surveys many more "provable security" failures where proofs were wrong,
or were correct but made stronger assumptions than people realized, or
were correct but provided weaker conclusions than people realized.

X-Wing is a new proposal (https://eprint.iacr.org/2024/039) The
statement of X-Wing's "Theorem 1" includes the word "roughly" without a
definition, violating the mathematical requirement of clarity in theorem
statements; is labeled as being a ROM theorem; and relies on nonstandard
KEM hypotheses such as the hardness of "C2PRI". Even if the theorem can
be replaced by something clear and formally verified, where are the
papers probing the weaknesses in the new hypotheses and conclusions? For
example, looking for lower-cost attacks breaking "C2PRI" for Kyber, or
for lower-cost attacks breaking X-Wing's security claims?

2. NIST's explicit security target for KEMs was IND-CCA2, but the X-Wing
construction obviously needs to assume more than IND-CCA2 to provide the
security properties that X-Wing claims. The X-Wing paper claims merely
that it's safe _using Kyber_ (since Kyber supposedly provides "C2PRI"
etc.). Even if this turns out to survive review, what happens when
people plug in other KEMs?

Trying to address this with documentation (~"use this only for Kyber")
creates higher risks for the user than switching to a combiner that has
fewer sharp edges. The objective here shouldn't be blaming someone else;
the objective should be security.

There are many reasons that people have deployed other KEMs, including
the patent minefield surrounding Kyber, security concerns regarding
Kyber, security concerns regarding Kyber software, and performance
benefits of other options. The tendency of X-Wing to promote Kyber (via
blaming other KEMs for not being able to replace Kyber in X-Wing) seems
coupled to ignoring all of these issues, including the security issues.

3. It's a systemic security problem to be habitually overloading the
people who are reviewing the security of cryptographic constructions and
implementations. _One_ combiner is much less code than a KEM, and
whatever extra risks of screwups it brings are amply justified by the
reduction of damage if the KEM is broken---but this doesn't mean that we
should be casually rolling out more combiners. On the contrary, if we
tolerate a "wild west of hybrids" (to borrow a phrase from a recent
anti-hybrid panel) then we'll have much more hybrid code to worry about,
possibly even more hybrid code than code for all of the deployed KEMs.

It's safest to focus attention on _one_ combiner that works for a wide
range of KEMs and protocols. We already know how to do this: hash the
transcript. Complaints about the cost of hashing long public keys and
long ciphertexts (1) aren't responsive to the security concerns and (2)
are addressed by Chempat, which hashes each of those objects upon
receipt; hashing has negligible cost compared to communication.

I'm not saying Chempat is risk-free. It's worrisome that "Theorem 1" in
https://eprint.iacr.org/2018/024 resorts to the word "roughly", for
example, and that it's hard to find papers putting any real effort into
cryptanalysis. (Chempat needs Theorem 1 and Lemma 6 from that paper.)
But the X-Wing combiner has those risks _plus_ the risks that come from
asking the KEM to satisfy new security hypotheses. This makes review of
X-Wing by itself unnecessarily difficult, and unnecessarily fractures
the combiner ecosystem.

---D. J. Bernstein