Post-quantum encryption algorithms under rigorous scrutiny: expect more hacks

Researchers cracked a post-quantum algorithm in an hour. Experts believe it is not such a bad thing.

SIKE, a contender algorithm with a possibility to be included in the post-quantum cryptography (PQC) standard, was hacked using a traditional computer in an hour. It marked the second time this year that researchers have cracked a post-quantum encryption algorithm.

This is a shining example that even quantum cryptography is not a silver bullet and needs to be further tested to withstand attacks from classical computers, let alone quantum ones.

At the same time, companies are urged to do their homework to prepare for the imminent transition to post-quantum cryptography.

Finish line

In July, after a six-year-long competition, the National Institute of Standards and Technology (NIST) announced four algorithms designed to withstand the assault of a future quantum computer.

NIST has selected the CRYSTALS-Kyber algorithm for general encryption and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signatures. Post-quantum cryptographic standard is expected to be finalized in about two years.

NIST also announced an advancement of four additional algorithms that might be suitable for post-quantum encryption standard.

One of those, SIKE (Supersingular Isogeny Key Encapsulation,) has just been hacked by scientists from the Computer Security and Industrial Cryptography group at KU Leuven.

“Our Magma implementation breaks the instantiation SIKEp434, which aims at security level 1 of the Post-Quantum Cryptography standardization process currently ran by NIST, in about one hour on a single core,” researchers said in their preliminary paper An efficient key recovery attack on SIDH.

A co-inventor of SIKE, David Jao, told ArsTechnica, an outlet that first broke the news about the hack, that this is a significant blow to SIKE. “The attack is really unexpected,” he said.

In February, an IBM researcher Ward Beullens broke another cryptographic signature scheme, Rainbow, which was eliminated from the NIST competition during the third round. Beullens said it took 53 hours (one weekend) and a laptop to crack the algorithm.

The rush

In theory, the arrival of quantum computers, while a fully functioning and fault tolerant one might still be decades away, could lead to the massive leakage of secrets. Experts believe that malicious hackers are storing the information they can’t decrypt now, such as intellectual property and corporate secrets, and will be able to crack classical encryption that now protects data with a quantum computer.

With the world’s fastest supercomputers, it would take around 300 trillion years to break the 2048-bit RSA encryption. A quantum computer would be finished with a similar task in merely eight hours. Given the money and resources that states and tech giants throw into building quantum computers, the transition to post-quantum cryptography needs to happen sooner than later.

“The NIST protocols have undergone rigorous scrutiny over the past six years by groups of the world’s top mathematicians and cryptography experts. Some of the finalists like CRYSTALS-KYBER were clearly expected to advance, and others like Rainbow were expected to be dismissed. Another protocol called SPHINCS from the group of alternates was put right away into the standardization process,” Jack Hidary, CEO of Sandbox AQ, Google’s spin-out, told Cybernews.

The scrutiny is necessary to build a solid foundation for post-quantum encryption, which will take a long time for companies to transition.

“Good news overall”

“The Supersingular Isogeny Key Encapsulation (SIKE) candidate algorithm aims at Security Level 1 of the post-quantum cryptography standardization, which provides the lowest level of security in its design,” Alon Nachmany, CISO of AppViewX, explained. “As it was already discovered there's a flaw in the algorithm, allowing it to be hacked by a simple single-core PC in an hour, there is no need to wait for quantum computers.”

Tommaso Gagliardoni, senior cryptography expert and global lead of quantum security at Kudelski Security, said that NIST’s process of selecting algorithms was meant to get a great deal of scrutiny on the candidate algorithms, and that it “gives a fairly good confidence that the process has not been tampered with, for example by NSA or similar agencies, by willingly introducing hidden vulnerabilities, as it happened in the past.”

There’s no such thing as “unhackable” in cybersecurity and cryptography.

“That said, the international community has a good confidence that the selected NIST candidates are very hard to break,” Gagliardoni said. SIKE broke “quite brutally”, however, it was not among the finalist schemes chosen by NIST.

“Moreover, it was based on a relatively new mathematical problem that has certainly not been tested like some of the others, so part of the community was already suspicious. SIKE’s break was, in a certain sense, exactly what the open process organized by NIST expects. It was good news overall,”

Gagliardoni added.

Expect more flaws

Cybersecurity risk management provider Inversion6 director and CISO Chris Clymer said he was very excited to see NIST investing time and putting a lot of attention into developing post-quantum algorithms.

“Encryption is really, really hard to get right. It's an esoteric field that requires a lot of scrutiny, and even the most scrutinized algorithms are found to have flaws over time. It's been known for years that quantum computers were going to fundamentally change the feasibility of the difficult math that makes the algorithms we rely upon today work,” he said.

Clymer ensures that more and more flaws will be discovered even after we start using these new algorithms.

“The vetting that is going on right now is all part of the process. We will trust the algorithms that are ultimately chosen specifically because of all this scrutiny, because of the hacks that have been found and either addressed, or caused contenders to be discarded.”

Anurag Gurtu, CPO at cybersecurity firm StrikeReady, believes we’ve only seen the surface from the efforts of ethical hackers.

“The industry knows never to underestimate highly motivated and persistent bad actors to find unforeseeable gaps, thus serving as a force to evolve the notion of quantum-resistant cryptography,” he said.

SIKE algorithm weakness alluded that there’s no need to wait for quantum computing to fully mature to test.

“Every effort to test against powerful conventional computing that exists today is essential to help uncover issues. Thus, preparing a robust algorithm to be tested against an actual quantum-based computer,” Gurtu added.

Jacob Ansari, Security Advocate and Emerging Cyber Trends Analyst for Schellman, said that NIST’s selection process was designed to uncover these potential problems now vs. later while in use securing someone’s important data.

“Even if it’s somewhat troublesome that this particular problem was discovered relatively late in the process, it still shows the success of the NIST selection process.”

Ansari said it’s likely that actual quantum computing will uncover cryptographic problems that are difficult to theorize or model currently.

“Modern cryptography and theoretical mathematics allows experts in the field to posit both the potential problems that quantum computing could pose and potential solutions to those problems. Further, organizations like NIST specifically engage with these sorts of problems to find solutions that can be used in both the public and private sectors, and NIST has a long track record of producing excellent guidance on computing and security,” he added.

Companies should start preparing

Sandbox AQ has been in regular communication with NIST throughout the entire process as their cryptography research team leader, Carlos Aguilar Melchor, is involved with two of the algorithms being considered in the fourth round.

“Our engineers have been working on solutions for each of the third-round finalists, but now that we know CRYSTALS-KYBER will be the new encryption standard, we are moving forward with that algorithm,” Hidary told me.

Enterprises, he said, can and should begin the discovery process to inventory where they are using vulnerable Public Key Cryptography (PKC) security protocols.

“Following discovery, they can then prioritize which areas to migrate first to the new standards. It is important that enterprises begin the process now to protect their most vulnerable data from Store New Decrypt Later (SNDL) attacks,” Hidary said.

The discovery process at a large enterprise could take six months or more to identify and inventory all the instances where vulnerable PKC protocols are being used.

“This process is critical so that CISOs can formulate their migration strategies. The time required is unique to each organization: Some might not have the budget to do a full migration and will transition critical systems on a rolling basis. Others might partner with a professional services firm like Deloitte or EY to manage the implementation.”

Hidary said that the migration will take several years, given that more than 20 billion devices -- including phones, PCs, servers, IoT devices, ATMs, and other technologies -- will need their software upgraded to the new PQC standards for both key exchange and digital signatures.

Sandbox AQ co-authored the paper titled Transitioning Organizations to Post-Quantum Cryptography, stressing the need for companies to upskill their cyber staff and detailing the quantum threat horizon and the steps that organizations need to take to migrate to PQC.

“Another approach is to consult with large professional services firms like Deloitte, EY, or others. These firms are extremely aware of the impact of quantum – across all facets of business and government – and can advise enterprises on PQC migration strategies and technologies. But the critical first step that organizations must take is to understand where they are vulnerable. Armed with this information, they can make better decisions as to how to protect their organizations from emerging quantum threats.”