Experts call to prepare for cryptoapocalypse

At the Black Hat conference in Las Vegas, four cybersecurity researchers made a special statement: Alex Stamos, Tom Ritter, Thomas Ptacek and Javed Samuel. The essence of their request was as follows: the existing algorithms underlying modern cryptography may be in danger of progress in solving mathematical problems, so all of us should abandon the existing SSL certificates in favor of newer cryptography methods.

It is well known that the basis of asymmetric cryptography is two keys: one can encrypt data, the other is used to decrypt them. This is possible due to the properties of one-way functions. It is assumed that some mathematical operations are difficult and can be performed only in exponential time, that is, in a time that increases exponentially with a linear increase in the dimension of the problem. However, the existence of such functions, that is, the property of an exponential increase in complexity, remains an unproved hypothesis.
')
There is a non-zero probability that in the future there will be a similar solution possible in polynomial time, which promises a cryptographic apocalypse. The essence of the report of the quartet of researchers boiled down to the fact that this moment may not be so distant from the present time, while alternative and more modern methods of cryptography are not widely used.

The most common asymmetric algorithms — the Diffie – Hellman algorithm, RSA, DSA — rely on the complexity of two problems: factorization of integers and discrete logarithmization. Modern mathematics does not have simple solutions implemented in polynomial time, but compared to decades of slow progress, the sharp activity in this area of ​​the last six months is very suspicious.

Limited discrete logarithmic algorithms were obtained. At the moment there are no known ways to use these developments in practical cryptography, but even these mathematical advances scare cryptographers. Researchers conducted analogies with attacks on SSL of the form BEAST , CRIME and BREACH . The features of asymmetric cryptography used for these attacks were similarly considered for many years as purely theoretical and not having practical use, but everything turned out differently.

The behavior of the programs and their developers after these attacks was also important. It turned out that a large part of the software is difficult and sometimes impossible to modify to support new cryptographic standards. Although there are more advanced cryptographic algorithms, their setup and implementation take much longer than they should.

It is worth remembering that not only SSL, but also other data encryption protocols: SSH, PGP, etc., can suffer from polynomial algorithms for the general use of factorization of integers and discrete logarithms. Updates with new cryptography methods for operating systems and application software: because software relies on digital signatures, fake update packages will quickly appear. Although this catastrophe may not happen soon, or maybe it will never happen at all, since it will be proved that it is impossible to solve the corresponding mathematical problems in polynomial time, we should protect ourselves by deploying alternative cryptography methods, the researchers believe.

As a solution to all problems, cryptography based on an elliptic curve over finite fields is proposed. The elliptic cryptography methods are similar to the methods of other asymmetric algorithms: there is an assumption about the complexity of a mathematical problem, in this case - discrete logarithmization in groups of points of elliptic curves. Unlike mutually similar problems of factorization of integers and discrete logarithm, the positive results in one of them do not threaten elliptic cryptography.

Support for elliptical cryptography has its own problems. Most of the technology is patented by BlackBerry, and patent problems have led some manufacturers to abandon technology support. Using elliptical cryptography protocols (for example, the latest implementation of the SSL technology - TLS 1.2) is not yet widely supported. The certification centers, which so far almost do not provide elliptical cryptographic certificates, are also guilty of this.

In general, researchers urge the information technology industry to begin supporting elliptical cryptography today, as well as to ensure the security of systems using cryptography: they should not rely on outdated algorithms and protocols. The software should be easily updated, allowing you to keep parity with the mathematical progress and technical achievements of the industry. Cryptoapocalypse may not happen, but readiness for it is required now.
Based on Ars Techica . Photo of user lyudagreen.