Two researchers have succeeded in cracking an encryption algorithm that the scientific community had hoped would ward off the threat of quantum computing.
If the latest encryption algorithm is cracked, it means that there is a threat to network security, especially the sending of confidential information, financial security transactions, verification data, etc., anyone’s private information will no longer be kept secret, and Trojan programs and malicious attack software are rampant on the network. Running rampant, the future digital network economy will face collapse.
Networks face a security crisis if people use functionally advanced quantum computer systems, so in 2017 the U.S. government and the National Institute of Standards and Technology (NIST) launched an international competition to find implementations of “post-quantum encryption (post-quantum encryption). post-quantum cryptography)”.
In July of this year, the U.S. government and the National Institute of Standards and Technology selected the first batch of winners — four encryption algorithms that, after a series of amendments, will be deployed as Quantum Shield. At the same time, the agency Four candidate algorithms under consideration were also announced.
On July 30, two researchers disclosed that they could crack one of the encryption algorithms using a single computer in under an hour (other researchers have since begun cracking the security algorithm, and the time is faster, sometimes in just a few minutes). minutes), it is worth noting that the record was not created by an advanced computer, but from a desktop computer with a 10-year “old” CPU, and it was running on a single core. This time cracking the encryption algorithm allowed the researchers to Realize that post-quantum cryptography needs to overcome many hurdles before it can be adopted.
Steven Galbraith, a mathematician and computer scientist at the University of Auckland in New Zealand, said: “An attack of this magnitude and power…is quite shocking, not least because of the mathematics used to break the security algorithm. It’s amazing, but also reduces the diversity of post-quantum cryptography, eliminating an encryption algorithm that works very differently from the vast majority of schemes in the NIST competition.”
“It’s a bit of a disappointment,” said Christopher Peikert, a cryptographer at the University of Michigan. “The results are both shocking and exciting for the post-quantum cryptography community because the break was unexpected. , suddenly turning what looked like a digital iron gate into a wet newspaper.”
Dustin Moody, director of standardization efforts for the U.S. government and the National Institute of Standards and Technology, said: “It’s unbelievable that it took researchers only an hour to crack an encryption algorithm. Crack it, preferably before it is put into widespread use, or you will face significant losses.”
“Secret Curve”
David Jao, a mathematician at the University of Waterloo in Canada, and his colleagues began to focus on cracking cryptographic systems that resemble well-known conventional algorithms with appropriate differences, an algorithmic scheme dubbed “Supersingular Synchronization.” The source of the Diffie-Hellman algorithm (SIDH)”, which mainly deals with elliptic curves, the same mathematical objects used in the most widespread types of cryptography today. It is reported that the SIDH algorithm was originally proposed in 2011. The designer proposed a cryptographic system to resist quantum attacks from the perspective of supersingular homologous elliptic curves. The cryptographic system relies on the difficulty of computing the homology between supersingular elliptic curves. And the key length is significantly shorter than other post-quantum ciphers.
“Mathematically speaking, ellipses are very elegant curves, and the encryption algorithm that uses elliptic curves as the theorem is very good,” David said.
If there are two elliptic curves (E1 and E2), we can create a function that maps a point P on the E1 curve to a point Q on the E2 curve, this function is called a homology function, if we can map this function, Every point of the E1 curve can be mapped to the E2 curve, the secret key is the same source, and the public secret source is the elliptic curve. Then assume that the two key exchange parties are Alice and Bob, who wish to exchange a message secretly, even under the surveillance of a potential attacker. For the key exchange, Alice and Bob mix the homology curves with each other. , thereby generating a “secret curve”.
Alice and Bob’s key exchange starts with a set of points connected by edges called “graphs”, each point represents a different elliptic curve, if you can convert a curve into Another curve (via homology map), draws an edge between two points, the resulting “graph” is very large and complex, and if you follow the edge a relatively short distance, you will see Ends at a seemingly completely random location.
Alice’s and Bob’s graphs have the same points, but the edges are different, the situation is defined as non-homologous, Alice and Bob’s exchange keys start from the same point and follow the lines on their respective graphs. Random edge jumps, tracing paths from one point to another, after which Alice and Bob both announce where the key ends, but keep the associated paths secret.
Now Alice and Bob switch places: Alice to Bob’s final point, Bob to Alice’s final point, repeating the “secret curve” each time so they end up at the same point. This point has been cracked so Alice and Bob can use it as a secret key – allowing each other’s messages to be encrypted and decrypted securely, even if a cyber attacker sees the intermediate points they send to each other. would know their “secret step count”, so cyber attackers would not be able to figure out the final endpoint.
But in order to run the SIDH algorithm, Alice and Bob also need to exchange extra information about the “secret curve” that causes the SIDH algorithm to be broken.
“New Twist” of Traditional Mathematical Theory
Researcher Thomas Decru did not intend to break the SIDH algorithm. He tried to further apply the method to enhance another type of cryptography on this basis, but it did not succeed, but inspired a new idea that the method might be useful for Attacking the SIDH algorithm works. So he approached his colleague Wouter Castryck at the University of Leuven in Belgium, and they started digging through the literature.
They stumbled across a 1997 paper by mathematician Ernst Kani with a theorem that “applies almost to the SIDH algorithm,” says Castrick: “We thought it Cracking the encryption algorithm is very fast, it can take 1-2 days.”
Finally, in order to recover Alice’s “secret step count”, as well as the shared secret key, Castric and Decru examined the results of two elliptic curves – Alice’s starting curve, and her public transmission curves to Bob, the combination produced a surface called a “swap face”, after which they used the “swap face”, Kani’s theorem (elliptic curve theorem related to the “swap face”), and the extra that Alice gave to Bob information, revealing every step Alice takes.
Kristin Lauter, a mathematician and cryptographer at Meta AI Research, said: “I’m very excited to see this technology in use! Not only does it help develop co-living-based cryptography, The swap side was also studied, so I’m ashamed that I didn’t use that algorithm as a solution to breaking the encryption algorithm.”
At present, De Crew and Castrick have cracked the algorithm with the lowest security level of the SIDH algorithm in 62 minutes, and cracked the algorithm with the highest security level in less than 1 day. Shortly thereafter, another security expert adjusted the cyber attack, breaking the algorithm with the lowest security level in just 10 minutes and the highest security level in a few hours. Over the past few weeks, more general cyber attacks have brought the SIDH algorithm close to collapse.
Jeffrey Hoffstein, a mathematician at Brown University, said: “We can’t guarantee that a cryptographic system is unconditionally secure. Instead, cryptographers rely on sufficient time and human effort to try to crack to generate confidence. That means when you wake up tomorrow morning, you can’t guarantee that someone won’t be able to crack the encryption with some new algorithm.”
So it’s important to have competitions like the US government and the National Institute of Standards and Technology, and in the last round, IBM cryptographer Ward Beullens designed a cyberattack that disrupted The rainbow signature algorithm, like Castrick and Decru, Berens only made an attack on the encryption algorithm effective after analyzing the underlying mathematical problem from a different angle. Like the attack on the SIDH algorithm, this attack compromises a mathematical system that relies on a different post-quantum algorithm than most proposed.
Thomas Prest, a cryptography expert at start-up PQShield, said: “The recent cracking of encryption algorithms is a watershed, and it is very difficult to study post-quantum cryptography, while analyzing the security of various algorithmic systems is not simple. Things, a mathematical object may have no obvious structure in one angle, but develop structure in another, and the hardest part is finding the right new perspective.”
GIPHY App Key not set. Please check settings