Researchers from KU Leuven have proposed an efficient key recovery attack method against the SIDH protocol, capable of breaking the SIKE post-quantum cryptographic algorithm using a standard single-core CPU in just one hour.
The key encapsulation mechanism is a protocol that securely exchanges symmetric keys using asymmetric cryptographic techniques. SIKE (Supersingular Isogeny Key Encapsulation) is a widely used key encapsulation mechanism that was selected in July 2022 for the NIST post-quantum cryptography algorithm round 4. There are multiple industrial implementations and experimental deployments. Compared to symmetric key algorithms, the currently used key encapsulation is vulnerable to attacks from quantum computers. The supersingular isogeny graph, constructed using complex mathematics, is believed to be resistant to attacks from quantum computers.
The correctness and security of the SIKE protocol rely on SIDH (Supersingular Isogeny Diffie-Hellman), which is based on the difficulty of computing isogenies between supersingular elliptic curves. The security of SIDH is closely related to the problem of finding isogeny mappings between two supersingular elliptic curves with the same number of points.
The attack exploits the known degree of auxiliary points and secret isogenies in SIDH. The known auxiliary points shared by both parties in the SIDH protocol represent a potential security weakness, which has been utilized in GPST adaptive attacks, fault attacks, and others.
The researchers implemented the attack algorithm—Magma, which successfully cracked SIKEp434. Magma solved the Microsoft SIKE challenge problems $IKEp182 and $IKEp217 in 4 minutes and 6 minutes, respectively. The researchers deployed Magma on an Intel Xeon CPU E5-2630v2 (2.60GHz) single-core CPU, and after approximately 62 minutes, successfully recovered the SIKEp434 parameters (meeting NIST post-quantum security level 1). For SIKEp503 (security level 2), SIKEp610 (security level 3), and SIKEp751 (security level 5), the keys were recovered in 2 hours 19 minutes, 8 hours 15 minutes, and 21 hours 37 minutes, respectively.
The inventors of SIDH confirmed that the attack does not affect other isogeny-based cryptographic algorithms such as CSIDH or SDISign. The paper notes that a variant of SIDH—B-SIDH may also be susceptible to attacks, indicating that merely changing the prime number does not prevent such attacks.
This attack does not affect other post-quantum cryptographic algorithms that rely on different mathematical problems.
References and sources: https://ellipticnews.wordpress.com/2022/07/31/breaking-supersingular-isogeny-diffie-hellman-sidh/
https://eprint.iacr.org/2022/975
