A post-quantum cipher was broken by a 2013 processor in an hour

Just a few weeks ago the NISTthe US standards-setting body, announced the first four algorithms for post-quantum cryptography. Such algorithms promise to solve one of the biggest problems created by the advent of quantum computers: their ability to break public key cryptography used today, among other things, for communications on the Internet. Four further algorithms are being considered for standardization to have greater variety and, therefore, a better overall security level. One of these, SIKE, was unexpectedly broken and therefore cannot become a standard. Not without some irony, the cipher was broken by a traditional computer of limited power.

An important aspect to keep in mind is that this attack does not affect in any way the already standardized ciphers: they are, in fact, based on completely different mathematical techniques and without any relationship with that used for SIKE. The ciphers already approved, therefore, remain safe, at least until proven otherwise.

SIKE is broken from a normal computer in just an hour

Public key cryptography involves the use of complex mathematical techniques that allow the use of two keys, one public and one private, to encrypt a data: using the public key, only those in possession of the private one will be able to read the data; on the other hand, anyone can verify that the data has been encrypted by the owner of the private key through the public key, thus guaranteeing the authenticity of the data itself. The important thing is that when using public-key cryptography, it is not necessary for two parties to have already shared a “traditional” cryptographic key in advance: it is thanks to this feature that public-key cryptography has become essential for communications on the Internet.

The calculations necessary for the use of public key cryptography are, however, often demanding and for this reason protocols for the exchange of symmetric keys are often used. To give a practical example, by connecting to the bank’s site, the first exchange takes place using public keys, but the use of another key is then agreed to encrypt subsequent communications using a symmetric key algorithm such as AES. In this way, a high level of safety is achieved, coupled with superior performance. This process is called “encapsulation”.

SIKE, an acronym that stands for Supersingular Isogeny Key Encapsulation (encapsulation of keys through supersingular isogenies), a proposed algorithm for standardization designed to replace the current ones, vulnerable to attacks by quantum computers. Part of the SIKE protocol SIDHor Supersingular Isogeny Diffie-Hellman (Diffie-Hellman via supersingular isogenies): in fact, the symmetric key exchange protocol explained above using an attack-proof encryption algorithm by quantum computers.

Or so it was believed. During the weekend, in fact, some researchers from the University of Leuven, in the Netherlands, have published a preliminary study in which they claim to have succeeded in break the new algorithm with a traditional computer in less than an hour. To be specific, the researchers used a single core from an Intel Xeon E5-2630v2 processor, launched in 2013. The researchers will now receive $ 50,000, up for grabs from NIST.

SIKE uses isogenies: simplifying a lot, mathematical transformations (morphisms of algebraic groups, in technical jargon) to carry out transformations from curve A to curve B. The attack found by the researchers is based on the fact that these transformations are not performed directly , but through intermediate steps: by determining the intermediate curves it is possible to trace the key used for the encryption and, in fact, break the algorithm.

The attack is valid for the published algorithm, which involves the use of a step to generate the key. In theory, it is possible that using a two-step algorithm is not susceptible to the same attack and is therefore safe. However, for the moment SIKE to be considered out of the game, at least in the current incarnation.

Difficult problems (also to be analyzed for problems)

1659641854 543 A post quantum cipher was broken by a 2013 processor in

Not the first case where algorithms considered for standardization in the NIST competition are broken. In February it was the turn of Rainbowwho was considered among the favorites and had already been adopted, very prematurelyeven for some blockchains.

Why have these attacks only come to light now, after years of intense and continuous scrutiny? The answer is that the algorithms used for encryption are based on problems difficult: this term is used to talk about the extreme difficulty in solving them by computers, with resolution times reaching billions of years, but in this case we can say that they are difficult even in the approach by people.

Speaking to Ars TechnicaDavid Jao, one of the inventors of SIKE, explained that “It is true that the attack uses mathematical concepts that were published in the 1990s and 2000s. In a sense, the attack does not require new mathematics; it could have been noticed at any time. An unexpected aspect of the attack that uses curves of genus 2 to attack elliptic curves (which are curves of genus 1). A rather unexpected connection between the two types of curves. To give an example of what I mean, for decades there has been an attempt to attack cryptography based on elliptic curves, and some have tried to use approaches based on gender curves 2. None of these attempts have been successful, hence an unexpected development that this attempt has been successful in the field of isogenies. In general there is a lot of mathematics that has been published in the literature but which has not well understood by cryptographers. I put myself in this category of the many researchers who work in the field of cryptography but do not understand mathematics as well as they should. , all it takes is for someone to recognize the possibility of applying existing theoretical mathematics to these new cryptosystems. what happened in this case. “

It is important to note that this result may appear negative, but it is actually exactly the reason why cryptographic algorithms are subjected to stages of public criticism. If we did not proceed in this way, the risk would be that weak algorithms were standardized, perhaps even implemented in hardware, only to later discover that there was an attack capable of breaking them. therefore it is necessary, once again, to underline how active and open collaboration leads to the best results. Thanks to open and public processes it is possible to involve people with different experiences and knowledge, so as to arrive at the best possible results.

We want to thank the author of this write-up for this incredible content

A post-quantum cipher was broken by a 2013 processor in an hour

Discover our social media accounts as well as the other related pageshttps://prress.com/related-pages/