An efficient key recovery attack on SIDH

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

by robinhouston • 4 years ago

52 14 4 years ago

eprint.iacr.org

jnwatson• 4 years ago

For background, SIKE, an implementation of SIDH, was selected as a winner of the latest NIST quantum cryptography competition.

sebsebmc• 4 years ago

Not exactly, it moved on to round 4 of the competition as a potential backup.

est312• 4 years ago

Detail: SIKE was admitted to round 4 but was never part of the selected algorithms for standardization: https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standar...

https://csrc.nist.gov/projects/post-quantum-cryptography/sel...

zinekeller• 4 years ago

And I guess unless this is mitigated (this attack seems to be broad enough to disqualify SIKE altogether even with heavy alterations) it will not be standardised.

est312• 4 years ago

Does this have an impact on CSIDH? I couldn't find it mentioned in the paper.

aildours• 4 years ago

It does not seem to have a direct impact. See https://nitter.it/ChrisPeikert/status/1553410345330524160#m

zahllos• 4 years ago

No but CSIDH doesn't use torsion point images because the class group action is already commutative. So there's no need to resolve the lack of commutativity.

Let me extend that comment a bit. SIDH operates over the 'full endomorphism graph' which doesn't have enough structure to form a class group. What we do know about it is that the ring in question is isomorphic to a sub algebra that is a quaternion algebra. Quaternion algebras are not commutative and this property is inherited.

To compare to diffie hellman, imagine that when you combine public material the order matters. If Alice and Bob don't find a way to agree on the order the secret is computed in, they get different results.

SIDH's torsion point images are how that agreement happens but they also depend on curve parameters that relate to the secret isogenies under use. It is this that is being attacked. A special case was found back in 2017, but no clear way to SIDH.

Warning on CSIDH: like CRS before it is vulnerable to Kuperberg attacks, so there's a subexpontential time attack. It's arguable therefore whether it is post quantum and what parameter choices are appropriate, if any.

This is all fine though. SIDH was never a practical contender for many use cases like say smart cards, because waiting 5 minutes for your payment to be authorised on a 40MHz smartcard processor is a bit of a no-go. SIDH is orders of magnitude slower than all other options.

dhx• 4 years ago

From the paper:

  "on a single core, the appended Magma code breaks the Microsoft SIKE challenges $IKEp182 and $IKEp217 in about 4 minutes and 6 minutes, respectively. A run on the SIKEp434 parameters, previously believed to meet NIST’s quantum security level 1, took about 62 minutes, again on a single core. We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively."

Security level 1 is meant to provide security equivalent to where AES-128 is used today, security level 3 being AES-192 and security level 5 being AES-256.[1]

If the paper is correct, it would be a brutal knockout of the Microsoft team[2] from NIST PQC round 4 leaving just Kyber (selected in round 3) and potentially one or more of BIKE, Classic McEliece and HQC that have gone into round 4 as selected PKE/KEM schemes.

[1] https://csrc.nist.gov/CSRC/media/Presentations/Let-s-Get-Rea... (page 16)

[2] https://www.microsoft.com/en-us/research/project/sike/

brohee• 4 years ago

It's over AFAIK, announcement here https://www.nist.gov/news-events/news/2022/07/nist-announces... and CloudFlare blog here https://blog.cloudflare.com/nist-post-quantum-surprise/.

I wonder if NIST got advance notice or if SIKE was excluded on other ground, but in any case it wasn't standardized. The fact SIKE went to round 4 means that NIST likely ignored the attack...

tptacek• 4 years ago

There's another phase of the NIST event.

dogeprotocol• 4 years ago

This paper was posted only yesterday, 3 weeks after NIST announcement.

throwaway6543292• 4 years ago

This is an epic result. One of the authors, Ward Beullens, also recently broke the Rainbow signature scheme: “Breaking Rainbow Takes a Weekend on a Laptop” - https://eprint.iacr.org/2022/214

He is on a roll at breaking post-quantum candidates and he and his coauthors will hopefully keep going. That this guy is able to do this kind of work in the open is a public good. Note that he has broken schemes after NIST has declared the systems safe enough to advance to the next round. This is really embarrassing for NIST. Do they really not have the capacity for doing this kind of research? One or two people can only do so much, no? One can only imagine what is being done in private.

Thanks for working in public Ward! You’re doing a better job at cryptanalysis than NIST can do with a team of people who do this as a full time job! You deserve a medal, along with other cryptanalysts who work in public and release results in public.

It’s a little sad that he uses Magma for his attacks since it isn’t Free Software but it’s not so important. The result is what is important.

Already as of today one group using SIKE is now considering switching to CSIDH: https://forum.xx.network/t/paper-an-efficient-key-recovery-a...

This underscores a recently reiterated point from djb on the NIST post-quantum mailing list: we should not have confidence in the security of these post-quantum schemes.

These kinds of breaks are a strong argument for the use of hybrid constructions such as ECC or even more conservative systems. Note that NSA opposes hybrid constructions and is pushing for post-quantum schemes to be deployed without hybrid protections.

SIKE, like Rainbow, both supposedly post-quantum have turned out to be less secure than currently deployed contemporary systems. They are neither post-quantum nor currently secure. Very impressive results!

TontonNestor• 4 years ago

Ward Beullens is not an author of this paper.

throwaway6543292• 4 years ago

Oh wow, I completely made a mistake here. Ward is amazing, but I should have properly credited Wouter Castryck and Thomas Decru for this paper. Embarrassing. I wish I could edit my comment now, the shame will last forever.

An efficient key recovery attack on SIDH

Related Stories