Quantum Threat, Today

Quantum computers are the new boogie-man everyone in tech is afraid of. But if such computers can potentially solve many of humanity’s hardest problems (like weather prediction), why are they such a scary thing? Well, it turns out, humanity has a few self-made “problems” that we’ve explicitly designed to be hard; and we really don’t like it, that quantum computers solve those too! Namely, cryptography.

The above video is a Ted talk. It’s a nice introduction for someone with no engineering background to feel the magnitude of the problem; but it raises more questions than it answers. We need a bit more nuance instead of saying that quantum computers will break all modern cryptography.

To do that, we need to dig deeper into what quantum computers actually do, and, at least approximately, how. The same way you don’t need to understand electrical engineering to reason about bits; you won’t need to know quantum physics to reason about qubits. That said, remember the first time ever you heard about a bit? Yeah, you’re starting from that level again.

And no, I’m not going to reinvent the wheel, rather will point you to this amazing lecture by Grant Sanderson. I’m 100% certain you will come out with way more questions than answers, but I promise you will have the answer to at least one: how does quantum computing impact modern cryptography?

The main takeaway from the above lecture, is that quantum computers are not going to magically break (all of) cryptography. Without special algorithms that can exploit structural mathematical concepts, the speedup of a quantum computer versus a classical one, through Grover’s brute-force search algo¹, is “merely” a quadratic improvement.

Whilst, that is admittedly a significant speedup, modern cryptography isn’t for the faint of heart either. The numbers are astronomical, which a square root will not bring into the realm of feasibility that easily. Why then are people talking like it’s the end of the world?

Turns out Yoda was right: there is another (algorithm)! In 1994, Peter Shor devised a mechanism² that is only feasible on quantum computers, but solves both the integer factorization problem, and the discrete logarithm problem in polynomial time. Whereas most of modern cryptography is only speeded up quadratically in the quantum realm, anything backed by int factorization or discrete logs is essentially broken. Which pretty much covers the entirety of public key cryptography.

But if Shor’s algorithm is over 30 years old, why wasn’t there any urgency in these past 30 years, and why is there one now?

Race for qubits

Both Grover’s and Shor’s algorithm were devised purely in theory, at a time when quantum computers were only theorized to be possible. The first actual computer with 2-3 qubits appeared around 5 years later and the first run of Shor’s algorithm to factor the number 15 (with 7 qubits) was done in 2001³.

Simply put, there were not enough qubits to go around and do any meaningful work on. To break RSA 2048 or ECC, naturally a proportional number of bits are needed. This led to an initially slow, then gradually speeding up race to who gets to build the first chip with enough stable bits.

That race is heating up. With current top contenders being IBM’s Condor at 1121 (unstable) qubits and Google’s Willow at 105 (stable-r) qubits. They are optimizing for different aspects, but the result is that both quantity and quality of qubits is rising fast.

The above images are courtesy of the New York Times, the IBM⁴ and Google⁵ rigs respectively. Fancy! Interestingly, the actual chips are the exact size of usual CPUs, the rest is overhead.

On the upside, neither 1121 unstable bits, nor 105 stable bits are enough to crack open modern cryptography. On the downside, if we follow the trend, we have 5 years if we’re optimists; and 3 years if we’re pessimists. Either way, RSA and ECC is going down… very soon.

What is and isn’t breaking

The issue around quantum computers and cryptography is mostly the hysteria, people writing apocalyptic articles about everything breaking (blame AI for destroying the world, not quantum computers). The world’s not ending due to Shor’s algorithm, but we need to be aware what is.

In cryptography, you have a few large classes of “problems” for a lack of a better word: encryption, digital signatures, key derivation, key exchange and hashing. Of these, the impact of quantum computers is wildly different:

• Hashing is a mechanism through which you can create a tiny checksum of some potentially gigantic input data. The use case is to verify that a large piece of data you obtained from an untrusted source really does contain what the source claims (or for a less malicious use case, just to check that there was no corruption mid-flight). This is mostly not impacted by quantum computers. The main hash algos nowadays are SHA2⁶, SHA3⁷ and maybe BLAKE2⁸. Whilst their internal construction differs a bit, from a security perspective they can only be brute forced. Grover gives us a quadratic speedup, but there’s still enough room to spare.
• Key derivation is a mechanism through which you can take a small piece of random data (either a root key or a user password) and generate one or more “subkeys” out of it. This allows safeguarding only a small bit of secret, and recovering everything else from it. This is mostly not impacted by quantum computers. The main algorithms for deriving keys are HKDF⁹ and Argon2¹⁰. Only Grover’s brute forcing can be used against HKDF, so whilst it reduces the security quadratically, the enormity of the original difficulty keeps it protected enough. Argon2 is even more protected, as that algorithm is also memory-hard, so it would need not only KBs of qubits, but tens/hundreds of megabytes.
• Digital signing is a mechanism where you create a key-pair: a private part you keep and a public part you distribute. The secret part can be used to create a signature over some data, that anyone with the public piece can verify to be originating from the person holding the private part. Digital signatures are based on asymmetric-key cryptography and are totally broken by quantum computers. The popular constructions are RSA¹¹ and EdDSA¹², both solvable (breakable) with Shor’s algorithm.
• Encryption is the mechanism through which you encode a piece of clear- text data in a way, that only the intended recipient can decipher; to all external observers, the encoded data is incomprehensible. This is achieved by creating a small, random, symmetric encryption key; using this key to encrypt the large data; and sharing the tiny key with the intended recipient out-of-bounds (we’ll get back to this). Encrypting the data with this tiny key is not impacted by quantum computers. The industry standard algorithms are AES¹³ and ChaCha20-Poly1305¹⁴, which only get the usual Grover quadratic speedup. The problem is that tiny key we said needs to be sent out-of-bounds.
• Key exchange is the mechanism through which two entities can negotiate a shared secret key, without it having to be verbatim transmitted. The goal is that once the key is negotiated, data can be encrypted between the two parties safely. Key exchange protocols rely on asymmetric-key cryptography, which means - you guessed it - it gets totally broken by quantum computers. The popular constructions are DH¹⁵ and ECDH¹⁶, both solvable (breakable) with Shor’s algorithm mostly due to the math that supports them.

The TL;DR is, that hashing and key derivation are safe, even in a quantum computing world. Their security budget gets a haircut, but otherwise it’s fine. The low level encryption itself is safe, but you need to figure out how to agree on that little shared secret to encrypt with. The popular key exchange algorithms and digital signatures go out the window!

Fixing the cryptography

The root cause for the fallout is that Shor’s algorithm breaks the integer factorization; and the discrete logarithm problem. To rebuild a functional cryptography suite; we need “new math” that remains hard even on a quantum computer. Luckily, there is “new math” from 1996 based on lattices¹⁷, that seems to survive well in the quantum world.

The current leading proposals for post-quantum cryptography are ML-DSA¹⁸ for digital signatures and ML-KEM¹⁹ for key encapsulation (newer mechanism to agree on shared keys). These are the standards being implemented and rolled out by all major players in the world. So, why such a long article only to mention that it’s a solved problem?

Because the solution is kind of bleeding from multiple wounds. One, it’s a new cryptographic construction that barely has reference implementations. Existing code has not been battle-tested, so might contain bugs; and even the math itself might prove to be broken. Switching over to ML-DSA and ML- KEM right now - as base security - is reckless.

Unfortunately, we can’t wait either! Any encrypted data from the internet captured today, might be decryptable with a quantum computer in 3-5 years. Many things are not sensitive in the context of 5 years, but some can be, like your genome that stays the same throughout your life. You really don’t want to lose that.

There is an elegant solution to the underlying issue: composite signatures and hybrid key encapsulation. When digitally signing something, we can use both EdDSA and ML-DSA, essentially attaching two signatures; the other side verifying both at the same time before accepting as valid. The advantage is that we can immediately roll this out: if ML-DSA gets proven broken before quantum computers arrive, we still retain the EdDSA security.

Similarly for key exchange, we can encapsulate the symmetric key with both X25519 and ML-KEM, essentially double encrypting everything. The other side needs to be able to open both encryption, one after the other, to read the data. The advantage is again the same, we can immediately roll this out: if ML-KEM gets broken before quantum-computers, we still retain ECC security.

Both being standardized in Composite ML-DSA²⁰ and Hybrid ML-KEM / X-Wing²¹.

Dark Bio cryptography suite

Since all the post-quantum cryptography is new and is being actively worked on all fronts, it’s quite hard to integrate everything together. Parameters need to be selected to attain the same security budget; specs scattered in a number of DRAFT RFCs need to be followed; reference libraries are missing most dev-ex features since the emphasis is on getting the crypto right, not on usability.

We’ve been ourselves struggling with transitioning our code to post-quantum cryptography for the reasons above and ended up shipping the grunt work in a handful of small wrapper libraries. The goal was to take the cryptography work that all the implementers are doing individually, and create a unified API surface above all of them; implementing the needed developer experience features to make using post-quantum cryptography easy.

The suite is implemented in two languages and fuzzed against each other:

• Rust: https://github.com/dark-bio/crypto-rs (darkbio-crypto)
• Go: https://github.com/dark-bio/crypto-go

FFI bindings and WASM wrappers also exist for two more languages:

• Flutter: https://github.com/dark-bio/crypto-fl (darkbio_crypto)
• TypeScript: https://github.com/dark-bio/crypto-ts (@darkbio/crypto)

Besides the post-quantum cryptography, the libraries also contain helpers implementing secure crypto-systems, like COSE serialization, strict CBOR encoding and basic post-quantum-signed certificate support. Some might be limited in the scope to the features we’ve found useful ourselves.

Challenges remaining

We’re in a good place. Quantum computers are still a bit out, and libraries are popping up here and there to help do the transition. Not everything is rosy. We haven’t talked about the cost of post-quantum cryptography.

An elliptic curve Ed25519 private key is 32 bytes. A public key is also 32 bytes. A signature is 64 bytes. These are almost insignificant sizes. They fit anywhere, in any protocol.

A composite ML-DSA private key is 64 bytes (because we have key derivation that is quantum-safe). A public key is 1984 bytes, and a signature is 3373 bytes! Those are two orders of magnitude increases.

An X-Wing ML-KEM private key is 32 bytes. A public key is 1216 bytes and an encapsulated key is 1120 bytes. But X-Wing cannot authenticate, so also including an extra composite ML-DSA layer around it, it bubbles up to 4493 bytes boilerplate before sending the 1st data byte.

So what? What is 2-4KB compared to even a tiny .jpg? Why do we even care? The problem is not the raw byte size, the problem is that for the past 14 years, every infrastructure on the internet was built around tiny numbers when it comes to cryptography (ECC). E.g:

• Cloudflare permits an env var to be max 4KB, ASCII.
• Cloudflare database keys are capped to 512 bytes.
• Cloudflare Websocket tags can be max 256 bytes.
• URLs accepted by browsers are max 2000 bytes.
• QR codes can contain a maximum 3KB of data.

Up until now, the “identity” of a key was its public key. There wasn’t any reason to use anything else for most systems. Now that optimization breaks, so everyone who relied on it globally, needs to introduce a new indirection across their entire infra. It’s going to be a nightmare. The 32B->2KB bump.

Verification time of an ML-DSA signature also jumps up ~4x, but that’s less of a breaking problem and more of an annoyance for very large providers and the occasional software that needs to validate huge swath of signatures.

This challenge is not going away. Whereas you might consider waiting until the cryptography libraries catch up with devex; they will not catch up with the old signature sizes; and there is no time to invent new math before the quantum computers arrive.

Epilogue

Quantum-computers are not yet powerful enough to access your sensitive data live, today. But they are advancing fast enough to make it feasible storing all your data transmissions, and decrypting it in 3-5 years. For your and your users’ sake, start transitioning to quantum-secure infrastructure now. Consider anything you send today with pre-quantum cryptography broken. The quantum threat is already here, it’s just not yet very evenly distributed.