Encryption failed: the supercomputer was hacked

One of the outstanding capabilities of the quantum computers of the future will be the ability to break the encryption used in today’s conventional computers very quickly. However, encryption is a very useful thing, so even before the advent of quantum computers, the development of encryption algorithms that cannot be easily broken by a quantum computer began. However, when a conventional computer with a single-core processor breaks an encryption in an hour, which should be possible on quantum computers, it is essentially the complete opposite of what should happen.

In mid-summer, the US Department of Commerce and the National Institute of Standards (NIST) announced that they had selected four post-quantum cryptographic algorithms that could replace the RSA and Diffie-Hellman algorithms. At the same time, four additional algorithms were announced, which may also enter the post-quantum toolkit if they pass rigorous multi-round tests.

However, the first of the candidates, SIKE, failed. The name SIKE stands for supersingular isogeny key encapsulation, a form of the Diffie-Hellman key exchange protocol protected by supersingular isogeny.

The asymmetric, open-key encryption that appeared in the 70s was a major breakthrough because it allowed parties completely unknown to each other to communicate in total security by combining public and private keys. however, the system proved cumbersome in practice, so other systems use symmetric keys, which are protected by a process called encapsulation. Encapsulation is easily broken by quantum computers, new algorithms solve this problem with the help of complex mathematical constructions.

Old math

The SIKE algorithm was broken by researchers from the Catholic University of Leuven, Wouter Castryck and Thomas Decru, which won them the 50,000 dollar prize from NIST. The theoretical background for breaking encryption is mathematics, which is off-limits to non-mathematicians. In any case, it is known that the vulnerability of the method using the properties of ellipses used in encryption was discovered by Ernst Kani in 1997 in his theorem called “gluing and cutting”, which mathematicians developed into an attack tool in 2000, based on which a “GPST adaptive attack” was published in 2016. fracture method called The beauty of the method is that the attack does not require a quantum computer at all.

This is the second candidate for post-quantum encryption to fail this year. In February, IBM researcher Ward Beullens published a report in which he broke the encryption of Rainbow, a solution based on the solutions of a complex system of quadratic equations. Rainbow fell in the third round of tests, while SIKE fell in the fourth round. The latter is an egregious case because it went through three previous rounds in such a way that it was finally cracked using a classic algorithm.

David Jao, a professor at the University of Waterloo and the inventor of SIKE, called the blow to his encryption unexpected and very modestly said only this about the case:

In general, there is a lot of deep mathematics that has been published in the mathematical literature, but is not well understood by cryptographers. I place myself in the broad group of mathematicians who do not understand mathematics as well as they should. So sometimes it is enough for someone to recognize the applicability of existing theoretical mathematics in new cryptographic systems. That happened here too.

(Ars Technica)

(Cover image: Our image is an illustration. Photo: Gavin Roberts/PC Plus Magazine/Getty Images)

Leave a Reply