What do you need to know about algorithm decay?

It is probably now a widely known fact that encryption algorithms are becoming out-of-date and crackable due to technological advances. This is true for cryptographic algorithms used almost imperceptibly in electronic signatures or encryption, but also for all other applications. Contrary to popular belief, these algorithms are not unbreakable. All the algorithms are crackable! This fact was already known when the algorithms were created.

So why do we trust these algorithms? Why do we use them?

The answer may be obvious since the time needed to crack them is measured in millennial. None of any attacker can wait that long. This means thousands of years, taking in consideration the current calculation power of the computers.

Why are algorithms secure?

The most widely used encryption algorithm, which is also used in the technical background of electronic signatures, is RSA. RSA uses key pairs, a public key, and a secret key. The advantage of public-key encryption is that the sender and receiver do not need to exchange any secret passwords or keys to communicate securely. In addition, the secret key must not be known to anyone other than the signatory. Its protection is based on a mathematical problem. To simplify, two large prime numbers are multiplied together.

The problem is that, knowing the multiplication, you must be able to determine the two prime numbers used for the multiplication. If the attacker succeeds, he will know the prime numbers and with these the secret key as well. In mathematics, breaking a complex number into prime factors is called prime factorization. In theory, prime factorization can be done in all cases, but for large numbers there is no efficient way to do it, so it requires a lot of calculation, time, and energy. Thereby, the RSA and ECC algorithms currently in use are adequate for security control purposes.

So why are the algorithms becoming obsolete? Why is the key size important?

With technological developments, we need to be informed year by year about security solutions. However, technological innovation is creating faster computers, which means that the millennial needed as mentioned above to crack algorithms will become a few thousand years by the time, then a few hundreds of years, and finally hours and minutes. After a while (measured in years, decades) all algorithms are destined to become antiquated. Fortunately, in order not to cause significant problems with this obsolescence process, there is a possibility to increase the size of the key used in the encryption process. The larger the key size used for an algorithm, will result a larger digit in the prime numbers that the attacker needs to be able to determine. As we increase the key size, the computational power required for decryption increases exponentially with it. Thus, increasing the key size is also a way to protect against expiry.

How do we know when our algorithm expires, and the current key size becomes risky?

Many experts and institutions internationally, including NIST, are working on the evaluation of this problem. As a result of their work, recommendations and standards are being produced. One of these standards is ETSI TS 119 312, which covers the algorithms used for qualified electronic signatures regulated by eIDAS.

The standard specifies that until the end of 2025 it is recommended to use the RSA algorithm with the 2048 bit key, which is currently widely used also by the NETLOCK system. As the use of 3-year certificates is widespread, it is advisable to increase the key size until the end of 2022. The standard recommends using at least a 3072-bit key size for RSA or the ECC algorithm. Based on the latest v1.5 release of the standard, encryption based on the RSA algorithm will be fully sufficient until 2029.

How long the increasement of the key size can extend the life of any algorithm?

It is not possible to increase the key size for either the RSA or the ECC algorithm for an indefinite period, as the storage of keys becomes uneconomical after a certain time. For RSA and ECC algorithms it is still possible to increase the key size in the future.

It appears that quantum computers will play the biggest role in the future in the obsolescence of these algorithms. The quantum era is not yet directly threatening us, but with the mass emergence of quantum computers, we can expect a big leap in the acceleration of prime factorization due to the huge parallel computing power.

How can we avoid the algorithms to become outdated?

We can prepare for the expected lapse in advance, as future algorithms will be designed to replace the most common encryption methods, such as RSA and ECC, which are the core of secure communications. The solutions currently used will be exposed to a high degree of vulnerability with the widespread emergence of quantum computers.

When they are released, the RSA and ECC algorithms will no longer be reliable enough, at which point it will be necessary for authentication providers such as NETLOCK to switch to the so-called Post-Quantum algorithm. While the Post-Quantum standard is under development (expected to be finalized by 2024), it would be premature to implement the algorithm as it may change before the standard is finalized.