An efficient key recovery attack on SIDH
eprint.iacr.org
eprint.iacr.org
"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."
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)
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...
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.
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!
https://csrc.nist.gov/projects/post-quantum-cryptography/sel...