A candidate algorithm for post quantum cryptography cracked in one hour with a single-core CPU

A U.S. government agency is working on alternative encryption schemes to at least begin averting a crypto apocalypse : in the future, the current cryptography that protects bank transactions, chat messages and medical records from eyes. prying will break like an egg shell with the advent of quantum computing. Among the candidate algorithms to resist decryption by powerful quantum computers in the future, one was trivially hacked using a simple, not-so-powerful computer today, equipped with an Intel Xeon CPU, in an hour .


Post quantum cryptography: a problem of tomorrow for today

The algorithm in question is SIKE, short for Supersingular Isogeney Key Encapsulation, which has arrived at the fourth round of the Post-Quantum Cryptography (PQC) standardization process initiated by the National Institute of Standards and Technology ( NIST ) of the United States Department of Commerce. .

According to research conducted by KU Leuven researchers Wouter Castryck and Thomas Decru and published in a new article :

"Run on a single core, the attached Magma code breaks the Microsoft SIKE $ IKEp182 and $ IKEp217 challenges in about 4 minutes and 6 minutes respectively (…) An execution on the SIKEp434 parameters, which were previously believed to meet the quantum security level 1 of NIST, took about 62 minutes, always on a single core ”.

The code ran on a 2.60 GHz Intel Xeon E5-2630v2 CPU, released in 2013 using the chip maker's Ivy Bridge microarchitecture, the academics also noted. These results came in conjunction with NIST's early July announcement of the first set of quantum-resistant cryptographic algorithms: CRYSTALS-Kyber for general cryptography and CRYSTALS-Dilithium, FALCON and SPHINCS + for digital signatures.

Microsoft, which is one of the main collaborators of the algorithm , stated that SIKE uses arithmetic operations on elliptic curves defined on finite fields and compute maps, the so-called isogenies between these curves. In particular, the official website states that SIKE is an isogenic-based key-encapsulation suite based on pseudo-random "walks" in supersingular isogenic graphs. SIKE's safety is therefore based on the difficulty of finding a specific isogenesis between two of these elliptic curves, or equivalently, of finding a path between them in the isogenesis plot, as explained by the tech giant's research team. In particular, S IKE is based on a problem identified as Supersingular Isogeney Diffie-Hellman (SIDH) (the analogue of the 'difficult problem' on which RSA is based with its integer factorization) .

Quantum cryptography is an attempt to develop cryptographic systems that are secure against both quantum and traditional computing machines , while also interoperating with existing communication protocols and networks. The idea is to ensure that data encrypted today using current algorithms such as RSA, Elliptic Curve Cryptography (ECC), AES, and ChaCha20 are not made vulnerable to brute force attacks in the future with the advent of quantum computers.

“Each of these systems is based on some sort of math problem that is easy to solve in one direction but difficult in the reverse. Quantum computers can easily solve the difficult problems underlying RSA and ECC, which would affect about 100% of encrypted Internet traffic if quantum computers were to be built "

That said, the US Cybersecurity and Infrastructure Security Agency (CISA), along with NIST, is “strongly” recommending organizations to start preparing for the transition by following the Post-Quantum Cryptography Roadmap.

Post Quantum Cryptography Candidate Algorithm Cracked in Hour with Single Core CPU was written on: Tech CuE | Close-up Engineering .