A computer with an Intel Xeon processor cracked an encryption algorithm in an hour, which in the future should have been decrypted by high-performance quantum computers.
Last month, the US National Institute of Standards and Technology (NIST) unveiled the first ever group of encryption tools that could potentially withstand a quantum computer attack. The 4 selected encryption algorithms will now become part of the NIST post-quantum cryptographic (PQC) standard, which will be introduced in 2 years.
At the same time, NIST has proposed four additional algorithms as potential replacements awaiting further testing, in the hope that one or more of them may also be suitable alternatives to encryption in the post-quantum world. The new attack breaks SIKE (Supersingular Isogeny Key Encapsulation), one of the last four additional algorithms developed by Microsoft. The attack does not affect the four PQC algorithms selected by NIST as approved standards, which are based on completely different mathematical methods than SIKE.
The SIKE algorithm is based on the use of supersingular isogeny (circling in a supersingular isogeny graph) and was considered by NIST as a candidate for standardization, as it differed from other contenders in the smallest key size and support for perfect forward secrecy (compromising one of the long-term keys does not allow decrypting a previously intercepted session) . SIDH is an analogue of the Diffie-Hellman protocol based on circling in a supersingular isogenic graph.
Over the weekend, a group of computer security and industrial cryptography researchers at KU Leuven questioned the operation of the algorithm. A paper titled “Efficient Key Recovery Attack on SIDH” describes a method that uses complex mathematics and one traditional ionic PC to recover encryption keys in transactions protected by SIKE. The whole process only takes about an hour. This research qualifies Wouter Castrick and Thomas Decree to receive a $50,000 award from NIST.
A ready-made implementation of the SIKE hacking method is published as a script for the Magma algebraic system. It took 62 minutes to recover the private key used to encrypt secure network sessions using the SIKEp434 (level 1) parameter set on a single-core system, SIKEp503 (level 2) – 2 hours 19 minutes, SIKEp610 (level 3) – 8 hours 15 minutes, SIKEp751 (level 5) – 20 hours 37 minutes. The $IKEp182 and $IKEp217 contests, developed by Microsoft, took 4 and 6 minutes, respectively.
For the developers of SIKE, the vulnerability of the algorithm to the GPST attack came as a surprise. This ArsTechnica was confirmed by his co-author David Jao (David Jao), a professor at the University of Waterloo. “The attack was a surprise,” he said.
When asked by ArsTechnica why SIKE is vulnerable to decades-old mathematical theorems, David Zhao replied: “It is true that the attack uses mathematics that was published in the 1990s and 2000s. In a sense, the attack does not require new mathematics; it could be seen at any time. One unexpected aspect of the attack is that it uses curves of the second kind to attack elliptic curves (which are curves of the first kind).”
“The relationship between the two types of curves is completely unexpected,” the professor added. – To give an example that illustrates what I mean, for decades people have tried to attack cryptography using conventional elliptic curves, including those who have tried to use approaches based on curves of the second kind. None of these attempts were successful. Thus, this attempt to succeed in the field of isogenies is an unexpected development.”