Chasing Cyber - #20 - No Free Lunch

Shor's Algorithm and Symmetric Keys

Welcome to the 20th edition! This week I wanted to share a great article I spotted, plus pour a little pessimism on symmetric key distribution.

---

Quanta Article on Shor’s Algorithm

In September ‘23, a new paper demonstrated how to vastly reduce the gate count required for running Shor’s Algorithm.

The paper, by Oded Regev, reduced the gate count from about 4 million to 100k for a 2048-bit RSA key. This came at the cost of requiring many more qubits.

I reported this news at the time, but I somehow missed this fantastic write-up in Quanta Magazine that followed up in October. Bruce Schnier just posted a link to this in his excellent blog.

If you want a deeper understanding of how Shor’s Algorithm works, and why there are usually trade-offs between gate counts and memory use, this is a great read.

Link to article: https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/

Link to the paper: https://arxiv.org/abs/2308.06572

---

Symmetric Keys != Free Lunch

There are no free lunches in cryptography. Remember this as we witness a surge of symmetric key distribution systems.

Interest in symmetric systems is peaking due to the quantum threat. Symmetric algorithms are largely safe from quantum attacks, and thus a system based on symmetric keys is intuitively more quantum-safe.

Symmetric systems are often touted as superior to public key infrastructure (PKI) and promise to eliminate the inconveniences of managing certificates.

However, while PKI is awkward, so are symmetric systems. Key distribution is a fundamentally awkward process.

A big challenge with symmetric systems is bootstrapping. To share a key using symmetric cryptography, both parties need a copy of the same transport key (which will encrypt the key during transit). Said another way: to share keys using symmetric crypto, you already need the capacity to securely share symmetric keys.

This challenge is solved by sharing transport keys manually. Much like bank ATMs, or spy novels from the 1970s, this may involve people carrying suitcases, or fragments of keys, to be assembled in the destination device.

A related challenge is scalability. In a distributed system, participants need unique keys to communicate with all other parties. This scales badly as the system grows. Imagine how many suitcase carriers are needed in a 10,000-node network.

One “solution” to this is having a centralised symmetric key distribution platform, which delivers keys on-demand to network participants. However, this brings back many of the same challenges as a PKI. The central system needs to manage user lifecycles, including revocation. And, worse, it becomes a single point of failure (i.e. a place where all the keys live).

I’m confident there are use cases where symmetric key distribution makes sense. But I share these thoughts to highlight the lack of free lunch. You must make a careful decision on the trade-offs you are making if you adopt such a system.

Equally, don’t assume PKI is always the right answer!