03 August 2022• 3 min read
In the future, everything is protected by cryptography, your personal data, your banking details, your transactions, even your communications.....and in fact, most of these arise already, but there are apocryphal stories that quantum computing allows it all to be cracked and manipulated... but wait...the future is creeping in.
Researchers claim to have cracked SIKE using a single-core Xeon processor - a far cry from the exotic world of quantum computers
The US Government via the US National Institute of Standards and Technology (NIST) is trying to promote advanced algorithms to secure post-quantum cryptography (PQC), supposedly protecting the future. Like all asymmetric crypto-systems, there is use of 2 different keys to encrypt and decrypt data. Communications between two parties, Alice and Bob, are protected because supposedly it is extremely hard to calculate the private key (used for decryption) from the associated public key (encryption). These new algorithms are intended to replace asymmetric crypto-tools which are theoretically vulnerable to quantum computers because they are based on elliptic curves and prime factorisation, the results of which quantum computers (qcomputers) can effectively guess because they can calculate an enormous number of possible answers simultaneously.
In February, a PQC algorithm contender called Rainbow was cracked in 53 hours using a standard laptop and Rainbow did not make it to the next round. A few days ago, the Catholic University of Leuven (Belgium) cracked another contender SIKE using a simple CPU. There are four major contenders for the recommended public key post-quantum cryptography (PQC) algorithms:
as well as other candidates
or at least there were until recently, because SIKE (Supersingular Isogeny Key Encapsulation) which implemented Supersingular Isogeny Diffie-Hellman key exchange protocol (SIDH) and had been developed by cryptographers at Microsoft, Amazon and a number of universities around the world fell out of contention despite is two algorithms: a public key encryption algorithm and a key encapsulation mechanism being developed by these computing giants. SIKE's security relies on the difficulty in finding a specific relationship (isogeny) between two elliptic curves but the Belgian researchers, Wouter Castryck and Thomas Decru, developed an attack to recover message recipient Bob's private key, solving two challenges within the Microsoft challenge code as well as also cracking tests based on NIST's quantum security classifications using a system they call Magma. Catryk and Decru say they solved Microsoft's '$IKEp182' challenge in about 4 minutes and also claim to have solved a harder test called $IKEp217, which Microsoft has offered a reward of $50,000 for solving, in 6 minutes. (See the preliminary paper). They also managed to crack SIKE using parameters believed to correspond to four different NIST levels of quantum security, each time using a single-core Intel Xeon E5-2630v2 CPU, a processor that can be bought from a computer retailer less than £150, and not requiring the quantum computers costing hundreds of millions of dollars. Even the SIKEp434 parameters, previously believed to meet NIST's quantum security level 1, took only just over an hour using on a single core and it is claimed that SIKEp503 (level 2) was broken in just over 2 hours, SIKEp610 (level 3) in just over 8 hours and SIKEp751 (level 5) in just over 20 hours and the researchers claim their attack can also be used to recover Alice's secret key....so SIKE is dead as far as cryptology is concerned.
....but you have to ask, if the programs such as SIKE and Rainbow were even in the running and so easily cracked, how safe is current or future cryptology?