An efficient key recovery attack on SIDH(eprint.iacr.org)
eprint.iacr.org
An efficient key recovery attack on SIDH
https://eprint.iacr.org/2022/975
14 comments
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...
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...
There's another phase of the NIST event.
This paper was posted only yesterday, 3 weeks after NIST announcement.
Does this have an impact on CSIDH? I couldn't find it mentioned in the paper.
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.
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.
It does not seem to have a direct impact. See https://nitter.it/ChrisPeikert/status/1553410345330524160#m
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!
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!
Ward Beullens is not an author of this paper.
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.
For background, SIKE, an implementation of SIDH, was selected as a winner of the latest NIST quantum cryptography competition.
Not exactly, it moved on to round 4 of the competition as a potential backup.
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...
https://csrc.nist.gov/projects/post-quantum-cryptography/sel...
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.
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/