Post-quantum cryptography: candidate SIKE cracked with laptop
Cryptologists managed to find an efficient attack on the quantum computer-resistant method SIKE and to carry it out entirely without a quantum computer.
The National Institute of Standards and Technology (NIST) has been searching for quantum computer-resistant encryption and digital signatures since 2016. Four methods have already been standardized, but now it seems that one of the most promising remaining candidates has been cracked. However, no quantum computer was involved in this, only two scientists with a laptop, who sealed the fate of the SIKE key exchange process in just under an hour.
Over the weekend, Wouter Castryck and Thomas Decru published a paper entitled: “An Efficient Key Recovery Attack on SIDH”. In this they describe a not at all trivial attack on SIDH (Supersingular Isogeny Diffie-Hellman), on which the key exchange method SIKE is based.
Bosses: A laptop and a weekend
The authors were able to break SIKEp434 (NIST’s lowest required security level) in 62 minutes on a single core laptop with their attack. Larger versions like SIKEp503 (2h 19m), SIKEp610 (8h 15m) and SIKEp751 (20h 37m) didn’t hold up either.
Just last month, NIST has CRYSTALS-Kyber encryption and CRYSTALS-Dilithium, Falcon, and SPHINCS digital signatures+ standardized. None of them are based on the same mathematical problem as SIKE, which is why the recommendations are still considered safe.
Two procedures in six months
SIKE was one of the four candidates to go through another round. The key exchange process shone with small keys, but suffered from comparatively long runtimes. Originally, NIST was positive about future standardization of SIKE, but the attack will most likely herald the end of the process.
Incidentally, this is not the first time that a promising candidate has suddenly fallen: in early 2022, Ward Beullens described a successful attack on the digital signature RAINBOW in his paper “Breaking Rainbow Takes a Weekend on a Laptop”. RAINBOW was one of the finalists in the NIST selection process and, like SIKE, was one of the alternative processes that are not based on grids.
