In this blog, we explore these FAQs, and many more. For quick answers, scroll down to the end of the blog. 

• Are quantum computers an immediate threat to my data?
• How do I find quantum hardware to run a post-quantum algorithm?
• Do post-quantum algorithms help in decrypting ransomware encrypted files?
• My data-at-rest is protected by symmetric encryption. Surely there's no reason to worry, correct?

Ciphers: the heart of secure communication 

Secure communication is paramount in today's highly interconnected world. It ensures the confidentiality, integrity, and availability of information exchanged between individuals, safeguards against cyber threats, ultimately contributing to a safer and more cyber-resilient digital landscape. The pacemakers behind securing communication are ciphers — they convert plain text into unreadable formats (or, cipher text) to protect sensitive information, allowing only authorized parties with the correct (private) key to decrypt the data and retrieve the original message.

An analogy for trapdoor functions: spilling ink on the carpet is easy - taking it out is much harder. Image generated using Adobe Firefly.

Cipher algorithms, in turn, utilize trapdoor functions —  those that allow easy computation in one direction, and are extremely hard the other way.

For e.g., consider the multiplication of two prime numbers 149 x 761 = 113389, which is the easy problem. The problem inverse of multiplication is factorization: given 113389, finding its prime factors is considerably harder. RSA utilizes this mathematical hardness to securely transmit information between parties who have never met by using a public key for encryption and a private key for decryption (asymmetric cipher), as shown below. 

Bob (left) generates a pair of numbers P and Q, and a pair of public (e) and private (d) keys. N = P*Q and e are shared to Alice (right). Alice uses these to encrypt her document, which can subsequently be decrypted by Bob by using his private key. For an eavesdropper to steal the information, they need to be able to factorize N into P and Q to deduce the private key d.

While RSA-2048 (which uses 617-digit keys) has never been factorized, it is becoming increasingly clear that this may not be so for long. On the one hand, this does not seem like uncharted territory — in the past, encryption algorithms have been repeatedly broken by an increase in computational resources and smarter counter-algorithms. On the other hand, this time may be different as the adversary that will potentially break RSA is not an intelligent piece of code or more compute power — it will be a machine that obeys entirely different laws of physics.

Quantum-charged parallel compute

In 1995, Dr. Peter Shor showed (paper) that polynomial-time "quantum" algorithms exist to solve the problem of factorization (among others). This is an exponential improvement over the best factorization algorithms of today, such as GNFS. Some order-of-magnitude estimates for comparison purposes are tabulated below.

Q: What are quantum algorithms?
A: Simply put, they are algorithms that can be run using circuitry on quantum-bits, or qubits. Qubits are more versatile than bits, because (unlike bits which can take the value 0 or 1) a qubit can coerced into a superposition of 0 and 1.  This ability to simultaneously be in two different states is a phenomena that defies our everyday experiences and unlocks incredible computational prowess. A slightly math-heavy example of using superposition to solve a search problem in one-shot is concocted below, but please feel free to skip ahead.

The key takeaway is that quantum computers leverage qubits in superposition to explore many possible states at once, enabling exponentially faster solutions to many problems. This massive parallel computation powers Shor's algorithm to efficiently factors large numbers, theoretically breaking RSA encryption, and posing a significant threat to current security protocols. So the question is: what's the Post-Quantum way out? 

Towards quantum-resistant cryptography

Graphical representation for the class of problems that are easy (like addition), quantum-easy (like factorization) and the rest that are quantum hard.

While Quantum Computers (QC) seem to spell doom on our cyber resiliency efforts, not all is lost, and not by a long shot. QC are only good at a select class of problems — while factorization N = P x Q is "quantum easy" (blue + gray disks above), there is a large class of problems that are "quantum hard". One example of a quantum hard problem is Regev's "learning with errors" (LWE paper), which was shown by Peikert  to have the trapdoor property, making it suitable for use in post-quantum public key crypto-systems. Subsequently, NIST's recently-concluded decade-long search for post-quantum crypto (PQC) algorithms declared Kyber (a key encapsulation algorithm) as a finalist, which relies precisely on modular LWE. 

Implementation of PQC 

One might intuit that an algorithm that protects against attacks by QCs would surely require more resources, larger keys, etc. However, this turns out not to be true. In the diagram below, we compare the TLS 1.3 handshake protocol using a classical asymmetric encryption algorithm (like RSA or ECC) with that using a PQ key-encapsulation algorithm like Kyber. We immediately notice that the number of keys required is smaller in the latter case — the server does not need to create two keys, but just a single shared session key.

TLS 1.3 handshakes with ECDH (a classical algorithm that relies on the discrete logarithm problem) and with Kyber.

Classical vs PQ: benchmarks

This supremacy of PQC algorithms continue into the performance as well. The Kyber benchmarks below were performed using the kyber-py library on Giacomo Pope's GitHub. Note that for Kyber, the encryption and decryption columns are for encapsulation and decapsulation respectively. The RSA benchmarks were obtained using openssl:

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:<keysize>

Apple M1 Max; 10 Cores; MacBookPro 18,2

Intel x86_64; VM on Intel(R) Xeon(R) Gold 6348 CPU @ 2.60GHz: as we tested on a VM with 4 vCPUs, the absolute numbers are not illuminating. However, the RSA:Kyber ratios for  both security levels are listed below.

Our key take-aways from the above analysis are:

1. Increasing the security from AES-128 to AES-192 is found to take about 1.5x round-trip time, a massive improvement over the 10x increase for RSA
2. The massive advantage stems from the key-generation step: finding two large semi-prime numbers and then computing the private/public keys takes considerably larger time than setting up the MLWE problem in Kyber.
3. If we use a hybrid protocol (like X25519Kyber768), we lose the time-advantage that Kyber provides, while hedging against any potential vulnerabilities that it might entail in the future. However, now that NIST has standardized it, we expect a secure openssl implementation soon.

FAQs

Q: Are QCs an immediate threat to my data?
A: Yes. Many threat actors are starting to use the harvest-now-decrypt-later strategy. Any data that may have a long shelf life (such as PIIs) are under threat of QCs. 

Mosca's theorem. Adapted fromRedHat Blog.

Concretely, we can utilize Mosca's theorem: If the sum of the time to migrate to the PQC algorithm (y) + shelf life of data (x) > time left before we have a quantum computer that can break RSA (z), then we need to worry!

Q: How do I find quantum hardware to run a PQC algorithm?
A: We don’t need any fancy quantum hardware to implement PQC algorithms – they work just fine on our regular computers. PQC algorithms are just math problems that are super-hard for even the smartest computers, whether they're regular or quantum.

Q: Do PQC algorithms help in decrypting ransomware encrypted files?
A: No, PQC algorithms can't help decrypt RW-encrypted files. They're designed to prevent future attacks, not to recover from past damage. If you were infected by a RW, utilize Veritas Recovery Workflow to recover from a recommended recovery point for a seamless experience.

Q: My data-at-rest is protected by symmetric encryption. Surely there's no reason to worry, correct?
A: While asymmetric encryption (for data in-transit) is a direct victim of Shor's algorithm, symmetric encryption (for data at-rest) with > 112 bits is considered secure against Grover's algorithm. However to perform backups, data needs to be moved using a TLS handshake between the primary backup server and the client, which is an asymmetric key exchange. This step is the weakest link in the chain, vulnerable to QCs via the harvest-now-decrypt-later strategy.

Source-to-Sink data path, where TLS handshake is using asymmetric PKE.