A major ‘post-quantum’ cryptography algorithm used by AWS, Google and CloudFlare, and developed in part by Microsoft, has been cracked in about an hour using a nine-year-old Intel Xeon processor. Known as supersingular isogeny key encapsulation (SIKE), the technique had been shortlisted as a possible encryption standard that can withstand quantum computers.
Businesses have been advised to prepare for a ‘post-quantum’ future but the apparent ease with which SIKE was cracked shows they should proceed with caution, experts told Tech Monitor.
SIKE was developed by researchers and engineers at Amazon, Infosec Global, Microsoft Research, Texas Instruments, and a number of international universities. To test its strength, Microsoft offered a $50,000 bounty to any security researcher that could crack it.
A team of researchers from KU Leuven, including Wouter Castryck and Thomas Decru, said it took about an hour of processing time using an Intel Xeon CPU at 2.60 GHz, launched in 2013, to crack the code and release the encryption keys used by SIKE to protect a transaction.
“The newly uncovered weakness is clearly a major blow to SIKE,” David Jao, one of the co-creators of the algorithm from the University of Waterloo told Ars Technica. “The attack is really unexpected.”
SIKE had been shortlisted to be certified by the US National Institute of Standards and Technology (NIST) as a standard for post-quantum encryption.
Although it was excluded after the first round of trials, it has been re-entered for consideration, as it takes a “fundamentally different approach” to the CRYSTALS-Kyber algorithm that has already been approved as a standard for general encryption. This, and the relatively small size of its encryption keys, made SIKE an attractive candidate.
Castryck and colleagues said in their paper on the attack that some of SIKE’s deficiencies “can be fixed by small modifications to the algorithm”. But that if this isn’t possible it is likely to be dropped from further consideration as a standard.
Post-quantum cryptography: cracking a few eggs
NIST has been working on the selection for the past six years and says the chosen models will “become part of the post-quantum cryptographic standard, expected to be finalised in two years”.
In addition to CRYSTALS-Kyber for general encryption, NIST has approved three other ‘post-quantum’ algorithms for digital signatures: CRYSTALS-Dilithium, FALCON and SPHINCS+. All four methods are considered to be unbreakable using classical computing, Daniel Shiu, chief cryptographer at quantum cryptography company Arqit, told Tech Monitor.
British cybersecurity firm PQShield was involved in all of the algorithms selected for inclusion as standards during round four. Dr Ali El Kaafarani, PQShield’s CEO, described the SIKE cracking as a “great success story for the NIST process”.
“Without the NIST PQC [selection process], those algorithms and others could have had very little attention and security scrutiny by cryptographers and mathematicians and likely ended up being used by some companies as proprietary encryption methods that have big non-verified security claims as often happens,” said El Kaafarani.
“The cryptography community has been doing a great job building and breaking crypto systems so that only the more secure ones are used to protect us.”
Proceed with caution
SIKE is not the first quantum cryptography algorithm to be cracked this year. In February, a deficiency was found in a digital signature algorithm called Rainbow that saw it dropped from round three of NIST’s selection process.
Many of the algorithms that have been cracked during NIST tests, or are awaiting further analysis, are still in use, Shiu explained. “For example, Rainbow is used by ABCmint cryptocurrency and SIKE is implemented by AWS Key Management Service, Cloudflare and Google.”
The fact that so many post-quantum encryption methods have been cracked reveals that the “maturity of the selected algorithms is not yet well understood,” he added.
Even the four techniques approved by NIST could come into question, Shiu argued. “Because viable attacks have arisen on various well-thought-of algorithms, it should be expected that shortlisted candidates will, at some point, face similar,” he told Tech Monitor.
Furthermore, Shiu said, it is not straightforward to swap post-quantum algorithms “in and out of a network” if they turn out to be insecure.
Organisations should therefore proceed with caution when adopting post-quantum encryption. “There is still no formal standard and US government advice is for agencies not to procure asymmetric solutions ahead of the final standards,” Shiu explained.
“As such, any choice or implementation of any algorithm that was part of the NIST process does not have any formal certification and users should be aware of the attendant risk.”
Experts predict the point of quantum supremacy, when a quantum computer can crack standard cryptography, is about 20 years away. But NIST predicts that it will take industry and government about 15 years to move to post-quantum cryptography, hence the need to find viable standards now.
Tech Monitor is hosting a roundtable in association with Intel vPro on how to integrate security into operations. For more information, visit NSMG.live.
Read more: Cryptography solutions selected to fight cyberattacks from quantum computers
