Paper "An efficient key recovery attack on SIDH (preliminary version)" affects xx messenger quantum security

Security
1

Earlier today, a paper was released which describes how to break the cryptography used in the quantum secure part of the xxDK and xx messenger.

High Level Summary:

  • The xx consensus and xx sleeve are NOT impacted.
  • The conventional part of the xx messenger’s key negotiation is not broken - your messages are safe.
  • The quantum secure portion of the xx messenger’s key exchange will need to be replaced.
  • This has no impact on the privacy of cMix.
  • The team will upgrade to an alternate scheme as soon as possible, likely CSIDH.

The preprint paper can be found here:

https://eprint.iacr.org/2022/975

First, the xx team would like to congratulate and thank the authors for finding this attack and publishing it. While we wish you had not posted this attack on a Saturday morning, work like this is critical to ensuring the cryptography we use is safe and secure.

Second, this attack ONLY partially impacts the xx messenger and the xxDK. No other xx network software is affected. The xx consensus (when deployed) and sleeve uses hash based cryptography exclusively, which is believed to be the strongest and least vulnerable post quantum cryptography.

Given the experimental nature of all currently proposed quantum resistant algorithms (excluding the hash based algorithms), the team did not rely solely on SIDH for the security of its key exchange and paired it with a 3072 bit classical log based DiffieHelman, which is not impacted. As a result, under classical assumptions, the xx messenger is still secure.

The xx messenger and the xxDK use more experimental algorithms to achieve quantum security because its tasks, like key negotiation, cannot be accomplished with hash based cryptography. That is not the case with xx consensus.

It is also important to note that even with this break, the xx messenger is far more secure against quantum computers than most competitors due to its use of a 3072 bit discrete log DiffieHelman instead of an ECC based one. The 3072 bit discrete log DiffieHelman likely will require significantly more qubits to break than more common ECC based solutions.

The breaking of these post-quantum schemes is natural when working with cutting edge research. SIDH was considered secure and was a 4th round finalist in the NIST process to select quantum secure public key systems, which ended only a few weeks ago. It also is not the only finalist to be broken recently. For example, Rainbow has a similar break of similar severity.

It looks like a different algorithm using supersingular isogeny, CSIDH, may not be vulnerable, and we are looking into making an upgrade soon. It would be relatively quick to move to CSIDH due to its similar structure and we still believe that the underlying post-quantum protection techniques used by supersingular isogeny are functional.

You can find a more detailed incident report here:

xx network security advisory 30 July 2022.pdf (47.9 KB)

This post has been reviewed by mysef, David Chaum, Will Carter, Mario Yaksetig, and Ben Wenger.

4 Likes
2

https://eprint.iacr.org/2019/725

Our main conclusion is that the proposed CSIDH parameters provide
relatively little quantum security beyond what is given by the cost of
quantumly evaluating the CSIDH group action itself (on a uniform
superposition). For example, the cost of CSIDH-512 key recovery is
only about 2^16 quantum evaluations using 2^40 bits of
quantumly accessible classical memory (plus relatively small
other resources). This improves upon a prior estimate of 2^32.5
evaluations and 2^31 qubits of quantum memory, for a
variant of Kuperberg’s original sieve.

This strongly invalidates its claimed NIST level 1 quantum security, especially when
accounting for the MAXDEPTH restriction. Moreover, under analogous assumptions for CSIDH-1024
and -1792, which target higher NIST security levels, except near the high end of the MAXDEPTH range
even these instantiations fall short of level 1.

Why not the NIST selection of Kyber, or NTRU, or even both? I won’t claim to be fully versed on CSIDH, nor PQ in general, but I believe CSIDH has been largely dismissed thanks to the above work.

3

Great question — That paper is a discussion on parameter selection suggestions not meeting security requirement definitions and doesn’t “largely dismiss” CSIDH. Parameter selection is a significant issue which we will need to look into before we make decisions regarding next steps. We’ve not committed to CSIDH for this reason and we also want to re-evaluate all the recent research in the field before making a final decision.

With respect to why choose it over others, the primary reason is the key sizes as they fit into a single packet. The engineering to work around the large key sizes in the other algorithms and the associated inefficiencies are significant. For example, NTRU’s key sizes are ~2k bytes and CRYSTALS-Kyber’s are ~1k bytes. It’s possible we’ll be using one of these for our link layer as soon as they are available in a hybrid form, but it is harder to work with these key exchange systems over cMix.

There is also good reason to be skeptical of NIST, and It’s clearer (to me at least) why SI as a technical approach is quantum resistant to me than it is for other approaches.

4

I believe the commentary, while against its parameters, is that it’s not feasible to select parameters which are secure and reasonable. This is comparable to SIDH potentially being sufficiently secure with a trusted setup/Alice provided curve (though there other reductions in security still possible).

I’d personally be interested in Kyber + NTRU, being robust in that regard.

5

It’s specific to the initial parameter suggestions and none of them hitting NISTs level 1 security requirements according to that analysis which makes some assumptions that limit its utility… Those parameters were aggressive with comparatively small keys to all other algorithms. Can you explain where it indicates it would be impossible to modify the parameters to e.g., meet level 1 requirements?

The reason I ask is that the paper itself even admits that 1792 would meet level 1 at the high range of MAXDEPTH, and it has a huge unknown in that it relies on an oracle with no defined computational/memory costs.

As stated, we are heading back to the drawing board on all of this, so any information or insight I might be missing is welcomed.

6

Unfortunately, my understanding is largely limited to what other people comment on the matter. In this case, I’d cite Komlo who has this older thread:

https://twitter.com/chelseakomlo/status/1444670623976853505

Like other schemes (CSI-FiSh), our CSIDH construction requires the class group structure to be known to prevent leakage of the secret key after updates. What surprised me is how far away we are from stronger parameters- a quantum computer is needed to perform that computation

From the paper that thread was highlighting:

At the present time, this requirement limits us to the CSIDH-512 parameter set, which claims 64 bits of
post-quantum security. Peikert [32] has questioned this security claim, and more recent analysis [9]
indicates that CSIDH-4096 is necessary for NIST level 1 security. Computing the structure of the
class group is a sub-exponential computation, and so becomes feasible with the availability of
a quantum computer to perform the computation. As such, the scheme may not be able to be
instantiated until it is most needed.

[9] is https://eprint.iacr.org/2020/1520.pdf, stating 512-byte keys for level 1 and 768 byte keys for level 2. Considering I’d prefer the discussion match SHA-256 security, at least, I’ll continue with level 2. Kyber768 is 1184 bytes for level 2. NTRU level 3 is 1230. The more interesting note is despite CSIDH maintaining its space efficiency, it’s no where near performant. The provided C implementation took 94-154 million cycles for its median run with a 6144-bit prime, depending on strategy count (9 or 11). NTRU was 34 million cycles for gen + enc + dec. Kyber was <1m.

So you’re discussing shaving 416 bytes, slimming down to 768, if you pick level 2 CSIDH over level 2 Kyber, yet taking a performance hit of multiple orders of magnitude, from my understanding. Really not my field…

7

Looks like we’re now on the same page, and can conclude that parameters secure to NIST levels do exist under the free oracle analysis, but it’s slower by ~100 million cycles or so (according to what you’re citing… I think it’s even slower).

Now we get to the engineering dilemmas – 2 packets v. 1 can mean up to several seconds of delay in cMix (there’s exceptions to this and i’m also ignoring other factors, but i’m simplifying to give insight into our considerations). That 3 seconds is a ~100 billion cycle delay on a modern cell phone, making NTRU potentially substantially “slower” in practice. Also, some of that 100 million might be precomputable so that it doesn’t affect user experience.

I’m currently working through the parameter set problem, which is why we had initially held off on CSIDH. The class group being uncomputable without a quantum computer is a concern, and a reason to make a different decision. It will take time to review the literature, design a solution, and execute it.