"Quantum-safe" encryption and decryption was attacked by computers 10 years ago

Future quantum computers have the potential to quickly crack modern codes. Now, researchers have found that an algorithm that promises to protect computers from advanced attacks can be compromised in as little as 4 minutes. Amazingly, this 4-minute crack was not done by a cutting-edge machine, but by a traditional desktop computer from 10 years ago. Researchers say this latest unexpected failure shows that post-quantum cryptography still needs to overcome many hurdles before it can be applied.

In theory, quantum computers can quickly solve problems that classical computers might take a lifetime to solve, a difference that is used as the basis of modern cryptography. The strength of cryptographic cryptography comes from certain mathematical puzzles that are difficult for traditional computers to solve, such as factoring huge numbers. However, quantum computers can, in principle, run algorithms to quickly break this type of encryption.

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

For years, researchers at organizations such as the National Institute of Standards and Technology have been studying which PQC algorithm could become the new standard the world will adopt. In 2016, the National Institute of Standards and Technology announced a call for candidates for PQC algorithms and received 82 submissions in 2017. In July 2022, after three rounds of review, the National Institute of Standards and Technology announced that 4 algorithms will become the standard, and another 4 algorithms will likely enter another round of review as additional contenders.

Now, a new study reveals a way to completely crack the Hyper-Singular Homologous Key Encapsulation (SIKE), one of the contenders under scrutiny (Amazon, Cloudflare, Microsoft, and others have been working on this algorithm). "The blow was sudden, the bullet was deadly." Christopher Peikert, a cryptographer at the University of Michigan who was not involved in the new work, said.

SIKE is a class of PQC algorithms that involve elliptic curves. "Mathematics has been studying elliptic curves for a long time." Dustin Moody, a mathematician at the National Institute of Standards and Technology who was not involved in the study, said.

In 1985, Moody's said, "mathematicians discovered a way to build cryptosystems involving elliptic curves, and those systems were widely deployed." However, it turns out that these elliptic curve cryptosystems are easily cracked by quantum computers. "Around 2010, researchers discovered a new way to use elliptic curves in cryptography." It is believed that this new idea will not be easily cracked by quantum computers. He said.

Moody's says the basis for this new approach is how to add 2 points to the elliptic curve to derive another point on the elliptic curve. "Homologous" means that the mapping from one elliptic curve to another maintains the law of elliptic curve addition.

"If you make this mapping complex enough, assuming that it is difficult to find homology between two given elliptic curves, it can be used for data encryption." Thomas Decru, a mathematical cryptographer at the University of Leuven in Belgium, said he was one of the co-authors of the paper introducing the SIKE crack.

SIKE is a homologous-based cryptographic method based on the Hypersingular Homologous Diffie-Hellman (SIDH) key exchange protocol. "SIDH/SIKE was the first practical same-origin based cryptographic protocol." DeCrewe said.

However, SIKE has a loophole: in order to work, it needs to publicly provide additional information, called auxiliary twist points. "Attackers have been trying to exploit the extra information, but have not been able to successfully crack SIKE with it." "However, this new paper [tells] a way to crack SIKE using fairly advanced mathematics." ”

De Cru explained that while elliptic curves are two-dimensional objects, in mathematics, elliptic curves can be thought of as objects of arbitrary dimensions. One can create homology between these generalized objects.

Applying a theorem from 25 years ago, this new cracking method can construct two-dimensional homology using additional information exposed by SIKE. This homogenous source can then reconstruct the key that SIKE uses to encrypt the information. On August 5, 2022, DeKru and the team's principal investigator, Wouter Castryck, detailed their findings in the Cryptology ePrint Archive.

"What surprised me the most was that this attack didn't seem to come from nowhere." Jonathan Katz, a cryptographer at the University of Maryland, College Park, who was not involved in the new work, said, "Very few previous studies have shown any weaknesses in SIKE, and then suddenly the results of this completely devastating study appeared." That is, it finds the entire key and cracks it relatively quickly without any quantum computation. ”

Using algorithms based on this new type of strike, it took only 4 minutes for an Intel desktop computer from 10 years ago to find the key protected by SIKE.

"From the first mention of SIDH to its complete breach, the attack on SIDH/SIKE has made virtually no progress in eleven or two years." Pecot said.

The reason why SIKE's vulnerability has not been discovered until now is that this new type of attack "uses a very advanced mathematical approach, and I can't think of any other scenario where an attack would have such a deep mathematical operation other than to break the system." Steven Galbraith, a mathematician at the University of Auckland in New Zealand who was not involved in the study, said, "There are fewer than 50 people in the world who can understand both the underlying mathematical method and the encryption method." ”

The reprinted content only represents the views of the author

It does not represent the position of the Institute of Physics of the Chinese Academy of Sciences

If you need to reprint, please contact the original public number

Source: Yuezhi.com

Editor: Sweeping Monk