An efficient key recovery attack on SIDH

#1

Post by robinhouston » Sat, Jul 30, 2022, 3:06 PM UTC

An efficient key recovery attack on SIDH
eprint.iacr.org

Re: An efficient key recovery attack on SIDH

#2

Post by jnwatson » Sat, Jul 30, 2022, 3:58 PM UTC

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

Re: An efficient key recovery attack on SIDH

#3

Post by sebsebmc » Sat, Jul 30, 2022, 4:03 PM UTC

jnwatson wrote: post #2

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.

Re: An efficient key recovery attack on SIDH

#4

Post by est31 » Sat, Jul 30, 2022, 4:04 PM UTC

jnwatson wrote: post #2

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

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...

Re: An efficient key recovery attack on SIDH

#5

Post by est31 » Sat, Jul 30, 2022, 4:15 PM UTC

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

Re: An efficient key recovery attack on SIDH

#6

Post by aildours » Sat, Jul 30, 2022, 4:33 PM UTC

est31 wrote: post #5

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

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

Re: An efficient key recovery attack on SIDH

#7

Post by zinekeller » Sat, Jul 30, 2022, 5:37 PM UTC

est31 wrote: post #4

jnwatson wrote: post #2

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

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...

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.

Re: An efficient key recovery attack on SIDH

#8

Post by dhx » Sat, Jul 30, 2022, 6:02 PM UTC

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/

Re: An efficient key recovery attack on SIDH

#9

Post by zahllos » Sat, Jul 30, 2022, 6:56 PM UTC

est31 wrote: post #5

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.

Re: An efficient key recovery attack on SIDH

#10

Post by brohee » Sat, Jul 30, 2022, 8:22 PM UTC

dhx wrote: post #8

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…

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...