Chasing Cyber - #28 - Debt

Shor's Algorithm, careful coding, and cryptographic debt

Fewer Qubits for Shor

A new paper claims to reduce the qubits needed to run Shor’s Algorithm. The updated approach requires fewer than 1,700 logical qubits to break a 2048-bit RSA key.

Should we panic? Probably not.

As with most attempts to optimise Shor’s Algorithm, trade-offs are being made. In this case, the consequence of reducing logical qubits is a significant increase in gate count (by a factor of 1,000). So it’s hard to judge whether “Y2Q” has gotten closer as a result.

And yet, each paper like this is a reminder that science doesn’t stand still. On the one hand, quantum computers are becoming more error-resistant and powerful each day. On the other hand, algorithm specialists are continually trying to optimise Shor’s Algorithm with papers like this.

All the more reason to take the quantum threat seriously and start planning!

You can check out the paper here: https://eprint.iacr.org/2024/222.

---

Pop Quiz

Can you spot the cryptographic coding error in this picture?

Look carefully!

If you can’t spot it, you might want to read this excellent article about constant-time cryptography:

https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html

Constant-time algorithm implementation is critical for avoiding a whole bunch of nasty side-channel attacks in cryptography. And this article does a great job of introducing the topic to non-technical newcomers. Take a peek!

---

On Cryptographic Debt

Let’s talk about cryptographic debt, and how it spawned a presidential memo and a multi-billion dollar industry.

Cryptographic debt accumulates through years of bad security decisions taken in the interest of speed or as a result of ignorance. Much like technical debt, which plagues software development projects, cryptographic debt has to be repaid. And the longer you leave it, the more painful it becomes.

Examples of cryptographic debt include:

• Failing to implement key rotation.

• Hard-coding algorithm choices.

• Spattering crypto code throughout your project, instead of centralising it.

• Not following (or even having) a cryptographic policy.

• Losing track of where cryptography is being used.

A critical consequence of cryptographic debt is an inability to adapt quickly to changing circumstances.

And so here we are, in 2024, needing to change a lot of algorithms to tackle the quantum threat. And companies are finding it very tough indeed. They’ve lost track of what cryptography is in use, which data lives where, and changing anything requires rewriting software from scratch.

The result? A presidential memo urging federal departments to take action, and a multi-billion dollar industry supporting organisations through the pain that lies ahead.

All of this should have been easy, had we baked crypto agility into our systems when we had the chance.

It’s important to recognise we now have a wonderful opportunity to build a better future. The quantum threat is forcing us to change all of our cryptographic systems. This means we can solve some of these problems once and for all, and develop a more agile and future-proofed set of technologies underpinning our cybersecurity.

I fear it won’t happen because it requires spending more than the minimum possible money. However, I suspect we’ll need more algorithmic changes in the years ahead, so it would be a wise decision to eliminate cryptographic debt while we have the chance.