Quantum-Safe Protocols Part 1: Quantum Risks to Modern Cryptographic Protocols

TLDR: This is part 1 of 3 in a series of posts about the considerations involved in assessing the threats to cryptographic protocols in a post-quantum environment, analyzing how protocols can be modified to maintain their resilience in the face of quantum-capable adversaries, using the Signal protocol as context.

To many, the term quantum mechanics conjures images of “spooky actions at a distance” ¹, with terms such as entanglement, superposition and collapsing states being thrown into the mix. Such perceptions are understandable, as these concepts mostly lie outside our everyday intuition, and popular science coverage doesn’t always help.

Despite its obscurity, these concepts have been demonstrated by researchers to enable quantum computation. Quantum computers can be understood as devices which read information, process them and output results while leveraging quantum mechanics and its associated properties ².

In the realm of cybersecurity, the risks posed by quantum computation deserves attention. We’re unlikely to see a general-purpose quantum computer anytime soon ^{3 4}, but that has not stopped researchers from proving a real threat, that techniques leveraging quantum computation can undermine the security guarantees many of today’s systems depend on.

The first post in this series aims to unpack what quantum computers are and how certain techniques enabled by quantum computation can threaten the security of cryptography.

What are Quantum Computers?

As this is not meant to be a deep dive into quantum mechanics and its inner workings, most concepts here will be introduced on a surface level. *If you’re interested in delving deeper, I highly recommend checking out Quantum Country by Andy Matuschak and Michael Nielsen ⁵.

I think a helpful way to approach quantum computation for those new to the concept would be to compare aspects of it to classical computation - on the basis of inputs, information processing and outputs.

Classical computers store and process information as bits, something that exists in a binary state of either 0 or 1 at any moment. Quantum computers on the other hand use quantum bits, or qubits. They leverage principles of quantum mechanics to exist in a state of superposition ⁶. One way to understand this is that instead of bits which are deterministic representation of either binary value, qubits are represented as a linear combination of both states, which convey the probability of the qubit existing in either binary state when measured.

Manipulation of information in classical computers is done with logic gates, such as AND, OR and NOT gates. They take one or more bits as input, and produce a deterministic output. Quantum gates on the other hand work with qubits, meaning that instead of working on discrete value of bits, they instead operate on a linear combination of binary states - meaning that it is an evolution of probabilities instead of a process on discrete binary values ⁶.

Crucially, feeding classical information into logic gates yields consistent and observable results, but working on qubits with quantum gates does not. Outputs of operations involving quantum gates are probabilistic; a system of qubits has to undergo measurement to extract information in classical forms from a quantum state ⁶. Quantum measurement techniques produce a probabilistic output of information.

Quantum computation introduces several unique possibilities. For instance, the Hadamard gate enables creation of a superposition, by taking a qubit of a definite state and placing it into a combination of either binary states ⁶. Quantum operations thus operate on a foundation of probability, instead of operating on discrete states, they work to manipulate the probability of the qubits within a system. This enables new ways to approach calculations and computations.

Risks to Current Cryptographic Protocols

We are yet to reach a stage where we can realise what a general-purpose quantum computer would look like and its capabilities. Despite this, researchers have demonstrated that quantum computation theoretically enables novel techniques to perform certain operations. These techniques have been shown to affect modern cryptographic protocols.

Cryptographic Protocols and Primitives

To security practitioners, one concern of quantum computation are the risks that it poses to the cryptographic protocols that are widely used today. Cryptography can be defined as techniques to secure communications under the presence of an adversary. Cryptographic protocols are the specific steps to “mangle” and “unmangle” information such that only intended recipients can read them ⁷. They come in all shapes and sizes, differing in characteristics such as how encryption and decryption is performed, how keys are used in both processes, and how keys can be generated and distributed. Cryptographic protocols can be found in systems we interact with everyday, examples including Transport Layer Security (TLS) which forms the backbone of a secure internet, and end-to-end encryption in messaging platforms.

Analysis of cryptographic protocols can be daunting, as they often involve several elements, processes and terminology. A particularly useful way to better understand these protocols is by identifying the cryptographic primitives involved in the protocol ⁸. They are essentially lower-level mathematical algorithms that transform information from an input to an output to achieve a particular security goal. The security provided by primitives are predicated on a mathematical characteristic, that certain problems or operations are difficult enough such that no computer can solve them within a realistic period of time ⁸.

Consider the example of symmetric-key algorithms. They consist of:

• KGen() → k A function to generate a cryptographic key.
• Enc(m,k) → c An encryption function which “mangles” a plaintext message under a cryptographic key to produce a ciphertext.
• Dec(c,k) → m A decryption function which “un-mangles” a ciphertext under the same key to retrieve the original text.

This primitive provides the security guarantee that a ciphertext can only be converted back to the original plaintext with the correct key. This security is founded primarily on the difficulty of obtaining the key such that ciphertexts can be decrypted - adversaries must brute-force all possible keys, something which will take a computer extremely long periods of times. Implementations of symmetric-key algorithms include AES and DES.

Cryptographic protocols usually are formed of multiple cryptographic primitives, leveraging the combination of their individual security guarantees to achieve overarching security goals at the application-level. Protocols are usually designed with an adversary in mind, an attacker who seeks to undermine the security of information the protocol aims to protect. The protocols are built with defences against possible actions of any adversaries, guaranteeing the security of information under such scenarios.

Shor’s and Grover’s Algorithms

Shor’s and Grover’s seminal work are significant advancements to cryptography under the context of quantum computation. They outline quantum algorithms that significantly speeds up the process of solving mathematical problems that are traditionally considered too difficult to solve within reasonable time.

Grover’s Algorithm is a quantum approach to search through unsorted data in a quicker way. In the context of cryptography, it can be applied to achieve a speedup in the process of brute-forcing information such as a cryptographic key ⁹. To understand the impact of Grover’s Algorithm, consider symmetric-key algorithms, whose security is founded on the fact that testing all possible encryption keys takes an unrealistic amount of time. An adversary capable of running this algorithm can gain a quadratic speedup of this brute-force search from a time complexity of N to square root of N. While this does not completely solve the issue of having to test all possible keys, it effectively reduces the strength of primitives relying on the difficulty of this property, affecting the security of symmetric ciphers and hash functions such as AES and SHA ¹⁰.

Shor’s Algorithm outlines a quantum approach to a specific task, which is quickly factoring large numbers into their prime multiples ¹¹. Cryptographic primitives such as asymmetric encryption and key-exchange algorithms base their security properties off the fact that while it is easy to multiply two prime numbers to obtain the result, it is significantly more difficult to recover the two prime factors of a large number, a process that will take a computer unrealistic amounts of time. Shor’s algorithm breaks these algorithms by making these problems solvable in polynomial time, affecting algorithms such as RSA and elliptic curve cryptography ¹⁰.

Modelling Quantum-Capable Adversaries

Analysis of cryptographic protocols necessitates assessment of potential adversaries, in order to better understand how security guarantees of these protocols can be undermined ¹².

A useful model is to classify adversaries to cryptographic protocols as either active or passive. An active quantum adversary is a threat actor who possesses a quantum computer and is able to perform operations such as Shor’s Algorithm in real time. Such adversaries break the security guarantees of cryptographic protocols in real-time, as they would be able to forge digital signatures or decrypt information without keys ¹³. Any system reliant on modern infrastructure faces short-term risks to the information they handle.

A passive quantum adversary, on the other hand, does not have access to a quantum computer yet. In such scenarios, the short-term risk to protocols are unaffected, but adversaries could still realistically perform “harvest now, decrypt later” attacks, where they capture encrypted traffic today, and store them until quantum technology matures ¹⁴. While security of information is not under immediate threat, information in its current state is at risk in the medium to long-term.

Assessments of cryptographic protocols using an active adversary may under-estimate the current risks of quantum computation to cryptographic algorithms. However, prudent risk management should assume passive adversaries to ensure security guarantees provided by cryptographic protocols today are retained in a future where quantum computation is attainable.

Unpacking Post-Quantum Migrations

Modifying entire cryptographic systems or protocols to be secure in a post-quantum environment can be a daunting task due to their complexity. A more feasible way to approach this would be to focus on the primitives that systems and protocols rely on ⁸. This consideration forms the basis of the NIST approach towards post-quantum cryptography (PQC). The PQC Standardisation Program outlines cryptographic primitives designed to withstand attacks from quantum computers. It provides developers standardised tools for transitioning existing systems to address quantum threats ¹⁵.

The next couple of posts will introduce the Signal protocol as a way to contextualise the process of post-quantum migration of cryptographic protocols. Part two will unpack the Signal protocol and its primitives, highlighting how their security guarantees can be undermined by quantum computation. Part 3 exemplifies different modifications to the Signal protocol to retain its security guarantees in a post-quantum environment.

References