PQC – The Quantum Threat

Traditionally, research and public perception of Computer Science follow a motto of the month. A couple of years ago, it was Cloud-Computing. Today, thanks to ChatGPT and familiar, it is Artificial Intelligence (or LLMs). Somewhere between those two were blockchain technologies (and Meta, depending on whom you ask). 

In this series of Blog posts, we at TACEO, want to highlight what we think may be the future motto of the month - namely, (Post)-Quantum Security, or PQC. However, this is only partially true, as PQC is already an essential topic for big players in the industry and academics below the surface of public perception. For now, awareness is lacking in contrast to, say, AI. Nevertheless, we think this will change in the next couple of years. Then you will read news articles not about ChatGPT but about how Quantum Computers will revolutionize our outdated computing model, which we have used since the 50s. Of course, like the topic of AI, one must be careful about “quantum hype” and look at it through a critical lens, however quantum computers will at least have one critical impact we would like to highlight in this post.  

Estimates for Quantum Computers 

At the time of writing, it is 2023, so we still have a couple of years before we get a CRQC. 

And - why should I care?

That is a fair question. What is the impact on you, your company, or the state you live in? Let's give an example. You came to this blog post via some link you clicked on (I assume). When you look next to your address bar in the browser, you can see that this page is protected with TLS (HTTPS). This means that before our server sends even one bit of content to your browser, the client (your machine) validates that taceo.io possesses a signing key (in our case RSA) bound to the domain in the certificate. We can inspect the certificate in a Linux terminal using openssl and see it does indeed use RSA.

openssl s_client -showcerts -servername taceo.io -connect taceo.io:443 <<< "Q" | openssl x509 -text
--- snip ---
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            04:05:a9:2e:9f:56:cb:78:51:af:51:a4:a4:ad:cc:1a:7f:59
        Signature Algorithm: sha256WithRSAEncryption
        Issuer: C = US, O = Let's Encrypt, CN = R3
        Validity
            Not Before: May  9 09:31:44 2023 GMT
            Not After : Aug  7 09:31:43 2023 GMT
        Subject: CN = taceo.io
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption 
                Public-Key: (4096 bit)
--- snip ---

Our machines then agree on a shared secret (some bits, most likely 128 bits long) using some variant of DH Key Agreement, which the devices then use to encrypt/decrypt the web page's content. During these steps, the server signs all messages with the previously validated key so that your browser is sure that no one in-between tempered with the messages. 

Imagine someone has access to a CRQC. This person could forge the signing key of taceo.io and act like they own the domain, thanks to Shor's Algorithm. Shor's algorithm can solve the Integer Factorization Problem (IFP) in polylogarithmic time. And if you can solve the IFP, you can break RSA, as its hardness assumption derives from the hardness assumption of the IFP. 

Since the attacker has access to a CRQC and performed Shor's algorithm, they retrieve the private key from our RSA public key. You would never know that you are talking to an imposter. They could sign every message, completely breaking Authenticity. Moreover, they could attack the Key Agreement, deriving our shared secret without us ever knowing, which breaks Confidentiality (they could also just visit the web page and read the blog post themselves, but for the sake of the example, imagine it is a secret post) with Shor’s Algorithm. If they compromised the Key Agreement, the attackers could also modify the page's content, encrypt it again, and send it to your browser. Suddenly, you do not read a blog post about PQC, but your browser shows you forms where you must put your credit card information. 

To be fair, breaking TLS on a blog post is not too scary. But it conveys specific attack vectors that are eligible for other websites. Imagine, instead of taceo.io, the attackers target your banking platform. Suddenly, they have access to your bank account. It would not be possible to trust and use things like e-Commerce, e-Government, and other similar sectors.  

It does not stop by attacking TLS. Every software, irrelevant if used to run, e.g., your car, or your phone, would not be able to trust other pieces of software it interacts with, and you also cannot trust the software itself. Authenticity and Non-Repudiation would break instantly.  

As already written above, a CRQC also breaks Confidentiality and Integrity when communicating between two (or more) parties. The open-source (and really good, you should check it out) instant-chat messenger Signal promises End-to-End encryption, meaning only the senders and receiver can read the messages sent. Not even Signal itself. Nevertheless, the Signal Protocol is also vulnerable to Quantum Attackers; meaning said attacker could read or modify every message someone sends. 

Also, most popular blockchains nowadays are vulnerable to CRQC. A Quantum Attacker would likely be able to steal millions of bitcoins, leading to distrust of the system and dropping its value to zero (or near zero).  

Ok, ok - but why should I care now?

This is also a fair question. The trivial answer is that you have to care about CRQC sooner or later. So, why not now? According to a famous saying: "The best time to plant a tree was 20 years ago. The second-best time is now." To our advantage, we are still in the "20 years ago" part of the saying. 

A more sophisticated reason is the so-called "harvest now, decrypt later" attack. As the name implies, an attacker may store encrypted documents or messages at this point. Even though the attacker does not have any means to decrypt the secret documents now, they will as soon as they have access to a CRQC. 

Indeed, some sectors are more “vulnerable” to this kind of attack. Vulnerable might be the wrong word in this case, as it has more to do with the specific value of the data. Of course, a Quantum Attacker is still able to read the Signal message I wrote to my colleagues this morning, enclosing to them the secret message that our coffee stash is empty, but is it worth storing Signal messages with their respective key exchanges from some developer in a team chat for multiple years? Most likely not.  

However, a nation state actor such as certain three-letter organizations might have attack targets where it could be quite feasible to store messages for ten to twenty years and still get value from them once a powerful enough quantum computer is built. Furthermore, this timeframe shrinks year by year, and it will become increasingly more attractive to store data for a few years to be able to decrypt it later. Other sectors such as the health industry also are dealing with highly sensitive and often long-term relevant data and should ensure that they are not hit unaware by advances in quantum computing. 

So, cryptography is dead no matter what? 

Luckily, it is not all doom and gloom for crypto. First, if you have read the post carefully, you may have noticed that I remained short of a description of a vulnerability in the actual encryption of the messages during our attack scenario on the blog post. I only wrote about attacks on the Signature/Authenticity and Key Agreement parts. The reason for this is that most symmetric cryptography (which is used to perform the actual encryption of data) is not vulnerable to Quantum Attackers. This is not strictly true because to have the same level of security, we must increase our key size (approximately doubling it). But to increase a 128-bit symmetric encryption key to a 196 or 256-bit key, using the same encryption algorithm is a trivial change by comparison. Only the Key Exchange/Agreement is vulnerable to Quantum Attackers. 

But what about Key Agreements and Digital Signatures? They still are integral building blocks of multiple protocols such as TLS and cannot be replaced with just symmetric cryptography. This means we need replacements for those primitives, and this is where the area of Post-Quantum Cryptography (PQC) comes into play. 

PQC are cryptographic primitives, algorithms that are not vulnerable to Quantum Attackers. As an important distinction, PQC algorithms do not require a quantum computer to execute and should run on our current devices. Another common name for these types of algorithms is “quantum-safe” or “quantum-resistant” algorithms. However, one major issue is that cryptographic algorithms are a very delicate building block and switching from our existing RSA- and DH-based algorithms to new ones requires an extraordinary amount of trust and confidence in the new PQC algorithms. 

For that reason, the US National Institute for Standards and Technology (NIST) kickstarted the PQC standardization project in 2016. Our next blog post will dive into this NIST competition, its outcomes, potential candidates to replace currently used algorithms such as RSA and what we can expect for the future of PQC. 

In the meantime, thanks for reading, and see you around!