The transition to quantum computer-resistant algorithms

The only constant feature of the world is change. Even in cryptography, after a period of apparent calm, paradigm shifts occur, bringing a new perspective and sending previous technologies to the dustbin of history. This can result in a replacement of technologies as such, usually meaning classical development. Or an earthquake caused by a complete replacement with no chance of a gradual generational replacement, in which case it is necessary to simply start over.

Why is this transition necessary?

Currently, so-called quantum computers are coming on the scene. Current cryptography has problems with them. The reason is simple. Previously theoretical procedures, requiring the energy output of the entire galaxy to break current algorithms, or time far beyond the lifetime of the universe, have been incredibly reduced by quantum computers. The new approach means power in the tens to hundreds of kW over a period in the orders of units up to tens of days. Moreover, today it is possible to capture existing secrets, which can be broken only after a few years. And their impact can be devastating for a given organization.
Thanks to these procedures, it is possible to break current algorithms, which ensure confidence in data protection by means of methods such as digital signature, key material exchange, or key agreement. With symmetric algorithms, the situation is similar, though not as urgent. Here, too, a change will be necessary, most often consisting in increasing the length of the key (and eventually in increasing the length of the block). Both these directions are thus awaiting a change, built on new concepts of the approach. Currently, these procedures are called PQC (Post-Quntum Cryptography), or post-quantum cryptography. In addition to this name, it is possible to occasionally encounter QRC (Quantum Resistant Cryptography), a quantum-resistant cryptography, in which case it is probably meant quantum computing or quantum computers.

What does the transition involve?

Although this does not seem to be a big problem, the transition to quantum-computer-resistant cryptography will mean significant changes in architecture, changes in system settings in terms of cryptography support, and large-scale investments. A very cursory look at these changes is not enough, it can lead to erroneous conclusions. At first glance, these are only changes to the encryption of the transport layer, known as SSL/TLS. Changing algorithms only means changing the encryption sets, everyone can do that. But outside of SSL/TLS, this also means changing other places. Another communication channel is SSH, it also uses encryption to protect transmission. These are VPN technologies based on the principles of SSL/TLS, IPSec, OpenVPN, WireGuard, but also SSTP as a replacement (better encapsulation) for PPTP. But it does not stop there.
Technologies such as SSL/TLS, IPSec, OpenVPN, SSTP and others require a change even at the level of certificates. These provide proof of verifiability, unfortunately they use obsolete algorithms. Again, from the PQC point of view, these mechanisms need to be changed. This means changing the whole structure of PKI (Public Key Infrastructure). Here we are already talking about significant costs, infrastructure change and other impacts. But this is just the beginning of the whole issue. Because both transport encryption and VPN networks and the structure of PKI depend on the secure structure of the Internet. This brings us to the basic services of the Internet and communication.
One of the basic protocols is provided by the Domain Name System service, otherwise also the service of name translation. This has long been criticized because of the minimal protection of transmitted data, and as a solution, the extension of DNSSEC has been offered for several years (I don't forgive noting here that this extension is still little used). This has the ability to provide proof of correctness again, this time in the form of a digitally signed response with name translation. Based on current knowledge, it is not possible to forge signatures and this guarantees confidence in the correctness of the answers. But there is a hitch again, the digital signatures are built on obsolete algorithms. And quantum computers can break them again. So even the basic structure of the Internet will require changes. Of the basic services, this applies to both DNS (more precisely DNSSEC) and Network Time Protocol (NTP). Without it, it is not possible to verify whether the certificate or proof of accuracy is still valid at this moment. In addition to these protocols, however, it is necessary to change the routing protocols, which provide information on how to get through the maze of the Internet to a particular system. Without appropriate verification, it is not possible to trust the exchange of information about a route change. This includes network surveillance services … and could be continued.
Is that all? No, we are still in the beginning. In addition to the above communication channels, there are the current wireless networks. What could possibly be wrong with an ordinary WiFi network? I would allow myself a small fix, not only on WiFi, but also Bluetooth uses weak cryptography. And not only those. This also applies to today's wireless networks for the industry of things, automated systems including building environment management and a large number of other systems. Here it is not possible to just change supported cryptography, it will probably be necessary to replace components. Again, this is a huge cost, and there are still no solutions available for some technologies. But it also applies to wireless networks for mobile communications. For the moment, let's forget about 2G/3G/4G networks. If we are talking about 5G networks and considered 6G networks, only a few algorithms can be considered as resilient, most of the others will have to be changed. For such large networks, it is again an economic nightmare. For all of the above systems, who will bear the burden of proof of the correct implementation? Who will be responsible for the correct implementation? How will it be shown that it is not just pages in the documentation, when the real implementation lags behind the above descriptions? The proof requires verification of the correct implementation and at the same time measurement of how the transfer is made. In the case of these communication channels, this is an extremely difficult measurement.
Unfortunately, if it is possible to change these technologies in a way that guarantees resilience, it is still not won. It is necessary to change the support at the level of the applications that use these networks and services. As an example, you can think of a digital signature (expression of will, proof of key ownership or other uses). If the currently accepted signature is using algorithms such as RSA or ECDSA, it will not be trusted in the future. Therefore, the application must be able to use up-to-date cryptographic algorithms. Examples are programs designed for managing the economy of organizations, systems for contract management, document exchange within the supply-customer chain, data protection… This also applies to relatively common issues such as protection by encrypting data storage in disk arrays, computers or mobile phones, or encrypting backups. Today, users do not only use data storage tools, but also have to communicate with each other. Therefore, such a generational change will also affect various messengers and collaborative tools, providing virtual meetings and document sharing. It will also affect the change in the protection of e-mail communication. It still does not stop there. In order to save time and costs, it is necessary to use knowledge in this area, which should be summarised in BIA (Business Impact Analysis) and risk analysis. The extent of the impact at the application level differs for each organization, of course.
Another significant impact will be on the financial sector. In banking, these are complete changes to payment systems, which include, for example, changing terminals and smart cards, provided by card associations. It will be necessary to change the connections between ATMs and banks. Some will be new technologies of card companies providing secure payments by card, other changes await us for payments over the internet and others, which again brings huge costs. Ideally, there will be a change that the user will not recognize. But this may not be true, after all, we will soon (hopefully) recognize it.
The last small step concerns the mechanisms that we overlook on a daily basis. This is the cornerstone of most security solutions. This cornerstone is known as authentication mechanisms. Most of them are two to three decades old and are not able to cope with this change. Further use of these mechanisms thus leads to an extreme increase in the risk to the operation of the company. The reason is simple. The attacker will be able to intercept, break and then falsify any communication as if it were not even protected, thanks to weak authentication mechanisms. If he acts under the name of an employee, the chances of detecting this attack until it is too late are extremely low. Currently, such attacks are being carried out and are known as Business Account Compromise (BAC). Only the technologies of quantum computers are not used, but the techniques of social engineering.
Areas of interest. Please note, this is only an indicative overview, it is not intended to provide an exhaustive analysis.

• Internet infrastructure: NTP, DNSSEC, RPKI, routing protocols and verification of their information ...
• Trust services: PKI (certificates and their infrastructure)
• Communications networks: WiFi, Bluetooth, 4G/5G/6G, other radio communications including industrial communications, Internet of Things, automation of operations (e.g. buildings) and other systems
• VPN networks: IPSec, MACSEC, OpenVPN, SSL/TLS VPN, SSTP, WireGuard …
• Payment and banking systems
• Electronic mail, various communicators (messengers), collaborative tool
• Backup systems
• Key economy management and management systems: tokens, chip cards and other HSMs, KMS
• Storage encryption systems: Computers, mobile phones, external drives, disk arrays
• Authentication mechanisms
• Supply chain data sharing applications, electronic payment applications, sensitive document management applications and others, not specified here

How to plan and when to make the transition?

If an organisation decides to make changes to cryptography, it must be approached with discretion. Rapid implementation is not a happy solution. Most libraries started development in 2015-2020, so test versions are now available. During 2025, the first versions, which are intended for production deployment, should start to appear. Thus, migration should not start until the end of 2025 until the beginning of 2026. On the other hand, there is a limit set by the upcoming standards, when migration of algorithms should be completed by certain deadlines. For example, for key negotiation by 2030. Digital signature algorithms could theoretically be available until 2035, but this situation may change. One alternative is to force migration for critical infrastructure by 2027, end support for obsolete algorithms by 2030, and similar deadlines. Therefore, it is necessary to start preparing and analyzing today and monitor not only the development of cryptography, but also standards.

Comparison of mechanisms, test method and test environment

A small flaw in the whole migration process is the lack of information. For a large part of the industry, not only is there no information about algorithms, but there is also no information about impacts on systems load. Current testing systems suffer from certain ailments, there are errors that could cause these systems to weaken or break. This is due to the rapid development, which sometimes comes up against the limits of human capabilities. This, of course, has an effect in trying to create a counterweight. An example is the effort to create library functions capable of proving the accuracy of implementation (the FORMOSA project). Anyway, any deployment of these technologies depends on knowledge of the architecture of the protocols, what the impact of the new algorithms will be on the operation, the latency of transmissions and other “details”. Therefore, it is necessary to perform stress tests and verify the system's ability to cope with this load. The good news is the possibility to make at least a basic comparison of the performance of the individual algorithms. For the above reasons, this comparison must be considered indicative, as it varies according to the platform used, the systems deployed and the libraries.
This comparison contains both obsolete mechanisms from today's point of view and new ones. These are two sets, where the first covers KEM (Key Exchange Mechanism) algorithms. These are algorithms providing key agreement (calculation of a shared key without having to transfer it) and key exchange (one side determines the key and provides it to the other side). The second set contains DSA (Digital Signature Algorithm) algorithms, i.e. digital signature algorithms. The actual testing was done on a configuration containing:

• 13th Gen Intel® Core™ i7-1365U × 12, 64GB RAM
• Ubuntu 24.04.1 LTS
• OpenSSL 3.0.13
• OpenSSL OQS Provider 0.8.1-dev
• liboqs 0.12.0 compiled with LMS and XMSS support

Algorithm Property Evaluation

This section describes the measured data. The graphs process similar type of algorithms and approximately identical security equivalents, the table below the graph shows specific values in the number of executed operations per second and the corresponding security equivalents for each algorithm.
The first set of graphs describes classical algorithms such as Diffie Hellman, Diffie Hellman over elliptic curves, RSA and Diffie Hellman over community elliptic curves. Here you can see the effectiveness of elliptic curves, which can only be competed to some extent by decryption in an RSA algorithm. On the other hand, I made my work with RSA much easier. Thanks to the similarity of the algorithm for encryption and signing (the difference for a signature is only in the encryption of the hash function output over a specific text), it is possible to use the same results with a slight degree of inaccuracy.

The next graph shows the result of PQC algorithms. For comparison, they are accompanied by results for agreement on X25519 and X448 keys, which do not belong to these algorithms. Depending on the result, at the same or higher security level, grid algorithms achieve roughly the same performance and outperform the RSA algorithm. The measured values can be found in the table.

Digital signature algorithms are presented in three separate graphs. The corresponding tables are assigned to them. The first are classical digital signature algorithms based on historical DSA, RSA and ECDSA/EdDSA.

The next graph shows the result of PQC algorithms. For comparison, they are accompanied by digital signature results based on Ed25519 and Ed448, which again do not belong to these algorithms. According to the result, they have slightly less power than elliptic curves, yet still outperform the RSA algorithm.

The last group are signatures based on XMSS and LMS technologies. These are mechanisms where signature creation takes significantly longer, but are effective in authentication.
• For LMS (Leighton-Micali Signature), the W value (Winternitz parameter) changes the overall efficiency of the algorithm. A higher value means shorter signatures, allows faster authentication, but also seems to increase the signing time. At the same time, shorter signatures could be vulnerable to some, now mainly theoretical, attacks.
• In the case of XMS, two basic tree types can be encountered. XMSS (single-level structure - eXtended Merkle Signature Scheme) and XMSSMT (multi-level structure - XMSS Merkle Tree). • The H value changes the tree height in the case of LMS and XMSS/XMSSMT, has a minor effect on performance. A higher depth here allows for more signatures to be created.

Precautionary principle

Despite all the advantages of new mechanisms, it is necessary not to rush the transition. It is necessary to implement it in a relatively short time, but on the other hand, it is advisable to consider the risks. Every new system, including cryptography, needs time to find possible errors. During previous development, errors were found in protocols or in the architecture, even after a decade. At present, we have significantly better tools for analyzing and detecting such errors, just as developments (that is, our knowledge) in this area have shifted. Nevertheless, I would recommend caution in the case of the deployment of quantum computer-resistant technologies. We have a short, almost gallows term here, when the implementation must be mastered. The operational view requires a bridging period, when new and old algorithms will be available in parallel. For the above reasons, therefore, it should be deployed first on systems that do not process sensitive data. Only after the functionality and correctness of deployment is verified is a gradual implementation possible for more sensitive environments. At the same time, it is necessary to prepare contingency procedures for vulnerability detection, where a conservative approach can be defined on the basis of such a procedure for a limited period of time. By this we mean older technologies.

Conclusion

The transition to the post-quantum era will certainly not be a walk in the park. Still, a significant advantage is the increase in speed for some of the quantum computer-resistant algorithms, which means lower computational performance requirements. Organisations with knowledge of their environment, the impacts of implementation and possible downtime will have an advantage. Equally, organisations that plan the transition in cooperation with their business partners will have an advantage. This change is necessary, and without information on the scope and impacts it can end up in a very unfortunate way. Hopefully, temporary unavailability will be the worst thing that can happen to such organisations.

Autor článku:

Jan Dušátko

Jan Dušátko has been working with computers and computer security for almost a quarter of a century. In the field of cryptography, he has cooperated with leading experts such as Vlastimil Klíma or Tomáš Rosa. Currently he works as a security consultant, his main focus is on topics related to cryptography, security, e-mail communication and Linux systems.