Ten years of desktop computer, single-core quantum encryption algorithm cracked in 1 hour, cryptographer: It’s too sudden

Future quantum computers could quickly break modern cryptography. Therefore, mathematicians and cryptographers have been looking for suitable new encryption algorithms to resist quantum computer attacks. This new generation of cryptographic algorithms that can resist quantum computer attacks on existing cryptographic algorithms is called "post-quantum cryptography (PQC, postquantum cryptography)" algorithm.

But recently, researchers from the University of Leuven in Belgium discovered that a promising PQC encryption algorithm can be completely cracked in just 1 hour (some versions can be cracked in just 4 minute). The problem is, this record was not set by a high-end computer, but by a desktop computer with a ten-year-old CPU, running on a single core. Researchers say this latest and surprising failure highlights the many hurdles that post-quantum cryptography needs to overcome before it can be adopted.

## Paper link: https://eprint.iacr.org/2022/975

Theoretically, quantum computers can quickly solve problems that would take traditional computers a lot of time to solve. For example, modern cryptography relies heavily on the extreme difficulty classical computers face in dealing with complex mathematical problems, such as factoring large numbers. And quantum computers could in principle run algorithms that could quickly break this encryption technique.

To counter this threat, cryptographers around the world have spent 20 years designing post-quantum encryption algorithms. These algorithms are based on new mathematical problems that are difficult to solve for both quantum and classical computers.

For years, researchers at institutions such as the National Institute of Standards and Technology (NIST) have been studying which PQC algorithms should become the new standard that the world can adopt. The agency announced in 2016 that it was seeking candidate PQC algorithms and received 82 proposals in 2017. Afterwards, after three rounds of review, NIST announced four algorithms that will soon become standards, and four more that will enter the next round of review as possible contenders.

The review isn’t over yet, and one of the contenders has gone down, and it was compromised by a 10-year-old desktop. The algorithm is called SIKE (Supersingular Isogeny Key Encapsulation) and has been studied by Microsoft, Amazon, Cloudflare and other companies. Christopher Peikert, a cryptographer at the University of Michigan in Ann Arbor, said: "This attack came so suddenly that it was a silver bullet (a solution with extreme effectiveness)."

The SIKE algorithm is What?

SIKE is a family of PQC algorithms involving elliptic curves. “Elliptic curves have been a subject of study by mathematicians for a long time,” says Dustin Moody, a mathematician at NIST. "They are described by an equation similar to y^2 = x^3 Ax B, where A and B are numbers. For example, an elliptic curve can be y^2 = x^3 3x 2."

In 1985, “mathematicians figured out a way to make cryptosystems involving elliptic curves that are now widely deployed,” Moody said. "However, these elliptic curve cryptosystems are vulnerable to attacks from quantum computers."

Around 2010, researchers discovered a new way to use elliptic curves in cryptography. method. It is believed that this new idea is not vulnerable to attacks by quantum computers.

This new method is based on the problem of how to add two points on an elliptic curve to get another point on the elliptic curve. The "isogeny" in the name of the algorithm means homology, a mapping from one elliptic curve to another, which preserves the addition law.

"If you make this mapping complex enough, then the challenge of data encryption becomes that, given two elliptic curves, it is difficult to find the homology between them ," said study co-author Thomas Decru, a mathematical cryptographer at the University of Leuven in Belgium.

SIKE is a form of homology-based cryptography based on the Super Singular Homology Diffie-Hellman (SIDH) key exchange protocol. "SIDH/SIKE is one of the earliest practical origin-based encryption protocols," Decru said.

One weakness of SIKE, however, is this: in order for it to work, it needs to provide additional information to the public, namely auxiliary twist points. "Adversaries have been trying to exploit this additional information for some time but have been unsuccessful in using it to defeat SIKE," Moody said. "But this new paper finds a way, and they use some pretty advanced mathematical methods."

To explain the new attack, Decru said that while elliptic curves are one-dimensional objects, in mathematics, elliptic curves can be visualized as objects in two or any other dimension. One can also create homologs between these generalized objects.

By applying a 25-year-old theorem, the new attack uses the additional information exposed by SIKE to construct a two-dimensional homology. This homology can then be used to reconstruct the key used by SIKE to encrypt the message.

“The most surprising thing to me is that this attack seemed to come out of nowhere,” said Jonathan Katz, a cryptographer at the University of Maryland, College Park. Although he was not involved in the new research, he said: "There were very few previous results indicating that SIKE had any weaknesses, and this result suddenly gave SIKE a completely devastating attack because it found the complete key. And it was found very quickly without any quantum computing."

Attacked for more than ten years, cracked in four minutes

Using an algorithm based on the new attack method mentioned above , researchers found that a desktop computer equipped with a ten-year-old CPU (Intel Xeon CPU E5-2630v2) only needs at least 4 minutes to find a key protected by a certain SIKE algorithm, and the breakthrough is considered to reach NIST The quantum security level one standard SIKE algorithm also took only 62 minutes. These experiments are run on one core of the CPU.

# "Usually, serious attacks on cryptographic systems occur soon after the system is proposed, or when the system first starts to attract everyone's attention. Over time, attacks gradually become stronger, or significantly weaken the system. But this attack, without any warning, the cryptographic system was suddenly completely broken. Peikert said: "Since SIDH was first proposed, there has been a lot of research on SIDH/SIKE. The attack had made little progress in nearly 12 years until this complete breach."

Although researchers have been testing SIKE for more than a decade, SIKE has not been selected as a standard One reason is the concern that it is too new and not studied enough. "People were worried that SIKE might be at risk of a major attack, and it turns out they were right," says Steven Galbraith, a mathematician at the University of Auckland. So why hasn't it been detected until now? SIKE vulnerability? Galbraith believes that an important reason is that the new attack "applies very advanced mathematics." Katz agreed, saying: "I suspect there are fewer than 50 people in the world who have both the underlying mathematics of PQC and the necessary cryptography knowledge."

In addition, PQC startup Sandbox AQ Cryptozoologist David Joseph once said: "The same origin problem is "notoriously difficult" both from an implementation and theoretical perspective, which makes its fundamental flaws more likely to be discovered later. ."

In addition, "It should also be noted that before NIST conducts several rounds of screening reviews, there are many PQC algorithms available for analysis, so research efforts are diluted. . And after several rounds of screening, researchers have been able to focus on a small set of algorithms." Joseph said.

David Jao, one of the inventors of SIKE and a professor at the University of Waterloo in Canada, said: "I think this new result is an amazing work, and I give the authors the highest praise. .At first, I was sad that SIKE was cracked because it was such an elegant scheme mathematically."

"But the new findings simply reflect the way science works: We came up with a system that everyone thought seemed fine at the time, and then after analysis, someone found a weakness in it. It took them over 10 years to find the weakness, which is unusual, but other than that , this matter is not beyond the scope of ordinary scientific progress." David Jao added.

In Jao's view, it is a good thing that SIKE has been cracked now, after all, it has not been widely deployed.

What does it mean if SIKE is cracked?

SIKE is the second NIST PQC candidate algorithm to be cracked this year. In February this year, Ward Beullens, a cryptographer at IBM Research in Zurich, revealed that he could use his laptop to crack the Rainbow algorithm participating in the third round of NIST review. "This suggests that all PQC options require further study," Katz said.

However, Moody pointed out that although SIKE has been cracked, other cryptosystems based on homology, such as CSIDH or SQIsign, have not been cracked. "Some people may think that cryptography based on homology is dead. , but this is far from the case, and I think there is still a lot to be studied in homology-based cryptography,” Decru said.

Additionally, this new work may not reflect the level of NIST’s PQC research. As Decru noted, SIKE was the only homology-based cryptosystem among the 82 proposals NIST received; likewise, Rainbow was the only multivariate algorithm among those submissions.

Algorithms adopted as "standards" by NIST or entering its fourth round of review are based on mathematical ideas that have been studied and analyzed by cryptographers for a long time, Galbraith said. "That doesn't guarantee they're safe, it just means they withstand attacks for longer." Moody agrees, noting that "there's always something surprising to be discovered. Breakthrough results to crack the cryptosystem. For any cryptosystem, we have no absolute security guarantee. The best thing to say is that after a lot of research by many smart people, no one has found any loopholes in the cryptosystem."

"Our programs are designed to allow for attacks and cracks," Moody said. "We've seen them in every round of evaluations. It's the only way to gain confidence in safety." Galbraith agreed, noting that studies like this "are working."

Nonetheless, “I think the demise of both Rainbow and SIKE will make more people seriously consider the need for a backup plan for any winners that emerge from NIST’s post-quantum standardization process. ," Decru said. "It might be too risky to rely solely on a mathematical concept or scheme. This is also NIST's own thinking - their main scheme is probably based on lattice cryptography (lattice-based), but they want a non-lattice cryptography scheme to prepare Select."

Decru noted that other researchers have begun developing new versions of SIDH/SIKE, which they believe may prevent this new type of attack. "I expected what would happen as the attacks escalated and people tried to patch SIDH/SIKE," Decru said.

In summary, it turns out that the starting point of this new attack is a theorem that is "completely unrelated to cryptography" and "reveals the importance of conducting purely mathematical fundamental research to understand cryptosystems" ", Galbraith said.

Decru agrees, stating "In mathematics, not everything is immediately applicable. Some things will almost never be applicable to any real-life situation. But this Doesn't mean we shouldn't let research lead to these more obscure issues."

The above is the detailed content of Ten years of desktop computer, single-core quantum encryption algorithm cracked in 1 hour, cryptographer: It’s too sudden. For more information, please follow other related articles on the PHP Chinese website!