2022 - The year of Post Quantum Cryptography

The discussion on when quantum computers (QC) will ever become a reality - or if it will become practically useful - is far from settled. What is clear is that several large enterprises and nations are prepared to invest in developing quantum computers.

Due to how quantum computers would work, they would pose a threat to the cryptographic algorithms used to secure businesses and societies around the world.

In this blog post we consider the implications of a working quantum computer on the most common cryptographic algorithms and ciphers, and show that quantum computing will have a far bigger impact on the asymmetric, public key algorithms that we today use for key exchange and authentication.

Quantum computing impact on symmetric ciphers

For symmetric algorithms such as the block cipher AES, the quantum search algorithm Grover's algorithm will reduce the time to find a key to the square root of N (sqrt(N)), and thus reduce the strength of the cipher. Basically, AES with a 256 bit key will only provide the security of AES with a 128 bit key. This is a big impact, but still far from a full breakdown of the security provided by symmetric algorithms with good margins. Algorithms such as AES-256, ChaCha, BLAKE2, SHA-3, SHA-512 are all widely deployed and all have good security margins. Extending these algorithms is also fairly straightforward, and will not require huge research or major changes to protocols and libraries.

Quantum computing impact on asymmetric ciphers

Algorithms such as Diffie-Hellman, RSA and Elliptic curve are either directly based on - or are related to - the Discrete Logarithm Problem (DLP). For these algorithms Shor's algorithm will pose an existential threat. This algorithm reduces the complexity of DLP to log(N). With such a low scalability, just increasing the key lengths would not work as a mitigation.

For this reason, in 2016, NIST started the Post Quantum Cryptography (PQC) project and contest. In the request for algorithms, NIST stated a need for public key algorithms based on alternative principles and underlying problems other than DLP. In July of 2020, after four years of evaluations, NIST announced seven finalists. Out of these, four are for Public Key Exchange (PKE), and three are for signatures (authentication). Most of the finalists are either based on Lattice-based cryptography or code-based cryptography (pdf with a good presentation on code-based cryptography).

The exact dates for when the PQC will be completed has not yet been announced, but given the cadence so far, 2022 is a good guess. But recent news shows that organisations wants to move forward and start deploying the new algorithms even before the PQC has completed.

IBM presents a mainframe with PQC finalists implemented

Note: Assured is not affiliated with nor endorsed by IBM.

Last week, IBM presented the latest version in their Z-series of mainframes, the z16. And one of the new features is that it is a quantum safe system. What this means is that the new Crypto Express S8 implements the PQC finalists. In the announcement of the z16, IBM highlights Lattice-based algorithms as being supported.

(If you want to see what the IBM z16 looks like, Linus Tech Tips recently posted a video on YT where he tries to break a z16 mainframe.)

OpenSSH 9.0 provides quantum computing safe key exchange

On 2022-04-08, OpenSSH 9.0 was released. With this new release OpenSSH changes the default key exchange to a hybrid NTRU Prime + x25519 key exchange method. This means that the non QC safe x25519 key exchange is augmented with the Lattice-based, QC safe NTRU Prime algorithm. So, just by upgrading to the new version (and unless having a specific key exchange configuration), OpenSSH users will start using quantum computing safe key exchange.

Conclusions

These releases shows how quantum computing safe algorithms can and are starting to be deployed. The world is starting to respond to the potential security impact of quantum computers. What worries me however is not deploying new algorithms, but phasing out the old algorithms. Considering how long it has taken to phase out DES and MD5 (which is still not completed), phasing out RSA and Diffie-Hellman will probably take decades.

Image(s) used under license. Costex/Shutterstock.com