Post-quantum cryptography candidate cracked in hours using simple CPU
Researchers claim to have cracked SIKE using a single-core Xeon processor - a far cry from the exotic world of quantum computers
One of the algorithms advanced by the US National Institute of Standards and Technology (NIST) to the fourth round of its post-quantum cryptography (PQC) competition has been successfully cracked by researchers at the Catholic University if Leuven in Belgium using a simple CPU.
Last month, NIST announced four candidates that will be standardised as recommended public key post-quantum cryptography (PQC) algorithms: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON and SPHINCS+.
These algorithms are recommended to replace asymmetric cryptosystems based on elliptic curves and prime factorisation which are theoretically vulnerable to quantum computers, as these devices can effectively guess a huge number of possibilities at once.
Four alternative key-establishment candidate algorithms were also entered into a fourth round of evaluation for possible future standardisation: Classic McEliece, HQC, BIKE and SIKE.
SIKE (Supersingular Isogeny Key Encapsulation) is an implementation of Supersingular Isogeny Diffie-Hellman key exchange protocol (SIDH). It was developed by cryptographers at Microsoft, Amazon and a number of universities around the world. It consists of two algorithms: a public key encryption algorithm and a key encapsulation mechanism.
Like all asymmetric cryptosystems, it uses different keys to encrypt and decrypt data. Communications between two parties, Alice and Bob, are protected because it is extremely hard to calculate the private key (used for decryption) from the associated public key (encryption). With SIKE, security relies on the difficulty in finding a specific relationship (isogeny) between two elliptic curves in a way that is thought to be quantum-safe.
Belgian researchers Wouter Castryck and Thomas Decru developed an attack to recover message recipient Bob's private key, solving two challenges set by Microsoft and also cracking tests based on NIST's quantum security classifications using a system they call Magma.
In a preliminary paper, Catryk and Decru say they solved Microsoft's '$IKEp182' challenge in about 4 minutes. They also claim to have solved a harder test called $IKEp217 in 6 minutes. Microsoft has offered a reward of $50,000 for solving the latter challenge.
Furthermore, the researchers managed to crack SIKE using parameters believed to correspond to four different NIST levels of quantum security categorisation, each time using a single-core Intel Xeon E5-2630v2 CPU, a processor that can be bought from a computer retailer less than £100 - a far cry from the exotic world of quantum computers.
"Ran on a single core, the appended Magma code breaks the Microsoft SIKE challenges $IKEp182 and $IKEp217 in about 4 minutes and 6 minutes, respectively," say the researchers.
"A run on the SIKEp434 parameters, previously believed to meet NIST's quantum security level 1, took about 62 minutes, again on a single core. We also ran the code on random instances of SIKEp503 (level 2), SIKEp610 (level 3) and SIKEp751 (level 5), which took about 2h19m, 8h15m and 20h37m, respectively."
The researchers claim their attack can also be used to recover Alice's secret key.
The successful attack will likely mark the end of the road for SIKE in the NIST process. In February, another PQ algorithm, a signature scheme called Rainbow, was cracked in 53 hours using a standard laptop. Rainbow did not make it to the next round.