The Quantum Computing Threat - Part 1

Part 2 of this series was published in May 2024. Read here now.

Introduction

The quantum computing threat refers to the potential risk posed by the advent of quantum computers to current cryptographic systems. Unlike classical computers, quantum computers have the ability to solve certain mathematical problems exponentially faster, which could potentially allow them to break commonly used encryption algorithms. This could pose a significant threat to information security, as encrypted data, such as financial and personal information, could become vulnerable to attack. The transition to post-quantum cryptography, which is resistant to attacks from quantum computers, is underway to mitigate this threat.

Both the civilian (banking, online, payment, cryptocurrency, etc.) and government sectors are at a tipping point of a looming encryption threat. Why are industries and entire governments investigating new cipher suites in response to the advent of quantum computing? Are today's encryption schemes - RSA, Diffie Hellman, Elliptical Curve Cryptography, AES - all going to be useless tomorrow? The answers all lie in the mathematical fields of Modern Cryptography and Quantum Computing. Are some cipher suites safe? 

The Scope

We have been living in a world that has changed and evolved from physical security to more electronic security. To provide security, you must use digital keys and certificates. These "keys" are then used to encrypt and secure your data and identity within the digital world. As we become more "any connection from anywhere" the means of secure transactions becomes even more critical. The threat from quantum computing is really aimed at a few ubiquitous cipher algorithms that derive their security from the same underlying mathematical concept: the Hidden Subgroup Problem. The impact of some entity discovering your password in minutes is profound.

For decades, mathematical cryptographers believed that some asymmetric algorithms like RSA and DH were "exponentially" secure – with sufficiently long keys, classical computing would never be able to break them, requiring hundreds or even thousands of years. In 1994, when the concept of a quantum computer was little more than an intellectual curiosity, Peter Shor proved that a quantum computer, satisfying the axioms of quantum computing, could factor large numbers in polynomial time. This became known as Shor's Algorithm. Shor and other researchers were able to show that, given a sufficiently powerful quantum computer, these vulnerable cipher suites could be 'broken' within minutes.

While this is not a threat today, it could be a real threat soon. Most experts believe that a quantum computer capable of breaking "strong" instances of RSA or DH will be available in five to ten years. Is it something we keenly need to be aware of – YES! Most organizations adhere to a policy of protecting sensitive data for ten years, making it vulnerable to a future quantum computer. We will cover data shelf life in a latter article. For now, data that is safe today, may not be safe tomorrow.

Moore's Law, Shor's Algorithm, Quantum Computing, Oh My!

Gordon Moore, an early CEO of Intel, observed that the speed and power of computing doubles roughly every two years (and gets cheaper), an observation that has held true for decades and has become known as "Moore's Law." This is not the problem here, not the threat against modern cryptographic algorithms. These algorithms are built and analyzed with Moore's Law in mind. Security standards are set to withstand attacks from classical computing for centuries assuming Moore's Law holds.

The new threat from quantum computing follows from truly remarkable results in quantum mechanics. The fundamental magic that drives the power of a quantum computer is the ability to perform a nearly infinite number of computations simultaneously, leading to a mind-boggling amount of parallelism. Hence Shor's Algorithm works, from a very high level, by trying all solutions at once and then grabbing the correct answer from the pile by virtue of it being the "best" (most probable) answer. Magic, indeed!

To recap, with the advent of quantum computing, you are now able to take advantage of Shor's Algorithm to break a few extremely important cipher algorithms: specifically, the following asymmetric algorithms used in key exchange protocols to derive a shared secret key:

• RSA
• Diffie Hellman over a large Prime Number group
• Diffie Hellman over an Elliptical Curve group

NIST Final Release

NIST called for a competition of sorts on selecting the next cipher suite to provide a solution against the imminent threat of quantum's power of resolving keys to our most secure cipher suites. This is referred to as the hunt for secure "Post Quantum Cryptography", or PQC. The NIST PQC competition is like the very successful NIST AES competition, which ended in 2000 with the selection of Rijndael. Interestingly, most of the algorithms proposed during the PQC competition have been based on hard problems related to integer lattices.

Although the NIST PQC competition is continuing into another round (final release of standards is 2024), on July 2022, NIST announced four interim recommended algorithms ("winners"). Those winnersand categories are:

Key Exchange: General Encryption:

• CRYSTALS-Kyber (Smaller keys and fast)

Digital Signatures:

• CRYSTALS-Dilithium (Recommended/primary algorithm)
• FALCON (Smaller signatures than Dilithium)
• SPHINCS+ (Larger and slower than the other two but different math used – great for backup)

In the future, we could see more of these cipher suites making their way to commercial solutions like firewalls, VPNs, and application gateways. The world of security is always evolving, this is worth a look and staying ahead of.