The Perfect “Harvest Now – Decrypt Later” Attack 

In my previous article, I described how Quantum Computers threaten the foundation of current cryptographic algorithms, but critics might say that a Quantum Computer is not yet available and won’t be for a while, so by then we will surely have new algorithms.

Well, let’s look at one particular problem with this approach. Suppose you have documents you want to keep safe, so you encrypt them and store them in a database (like classified documents, financial and medical records, trade secrets or anything really). If anyone gets hold of this document, nothing would happen because it’s encrypted, right?

Nothing wrong so far, but what if that document gets stolen now and then decrypted in 10 years time when Quantum Computers are powerful enough. There is nothing you can do about it. Even if you deploy the greatest Post-Quantum-Algorithm in the world, the content of this document will be known to your adversaries.

Well, who cares about some 10 year old document really?

How about some bitcoins?

There are over 1m bitcoins (1,148,800 BTC to be exact) that are believed to be owned by Satoshi, the famous unknown creator of Bitcoin. These bitcoins remain unspent. Unlike a fiat currency like USD where you can physically own the currency, nobody “owns” a bitcoin. All you “own” is a private key that belongs to this bitcoin’s public key.

Problem is, the public key for all these bitcoins is stored in plain text visible to anyone on the blockchain. If I have a Quantum Computer that can break Elliptic-Curve-Cryptography (ECC), all these bitcoins belong to me and I will be a multi-billionaire (at current market rates, these BTC’s are worth around 10 billion USD).

So I think there is enough economic incentive (actually, 10 billion reasons) to develop a quantum computer.

Surely a fix is easy, right?

Well, it’s not that simple. Bitcoin can easily replace the vulnerable ECC signature algorithm with a quantum-safe alternative (not that we have one right now) and from that point forward all bitcoin transactions will be secure.

To protect the existing bitcoins that are stored on the blockchain, they would have to be moved to these new quantum-safe addresses. But in order to move them, their private key would be needed. If I have a Quantum Computer, I will be able to produce a valid private key to all of Satoshi’s coins. Who decides now who is the real owner of these bitcoins?

That is a perfect “harvest now, decrypt later” attack. I can harvest these public keys now and derive the private key once Quantum Computers become available.

So how do we fix this?

The Bitcoin community doesn’t seem to worry about this threat too much, which is understandable from the standpoint that a) a quantum-safe ECC signature algorithm replacement is not yet available and b) the vast majority of bitcoin transactions doesn’t actually reveal the public key. They only reveal the hash of a public key (P2PKH) and without the public key itself, even a Quantum Computer can’t break a key it doesn’t know.

However, this seems to neglect the fact that some unspent bitcoin transactions from the past do contain the public keys on the blockchain (P2PK) – including all of Satoshi’s 1m Bitcoins. That alone is worth 10 billion USD at current market rates, which is a massive economic incentive for anyone to build a quantum computer. This alone is so massive that it cannot be neglected.

Summary

The situation with Satoshi’s bitcoins represent the perfect “harvest now, decrypt later” attack scenario (it is even easier as nobody needs to harvest anything as the Bitcoin blockchain is public and in many places 😉

It will be interesting to see what will be done to reconcile this situation as it is certainly non-trivial. It surely can’t be that whoever moves the coins first to a quantum-safe address is the legitimate owner… Otherwise time is of the essence as major advancements are being made to break RSA encryption even for current noisy Quantum Computers (see https://arxiv.org/abs/1905.09749). More on that in a future blog post.

Everything is electronic these days. Everything is encrypted. But the nitty-gritty details actually do matter, so let’s use this mess as an example of where you don’t want to be. Start your Quantum-Safe Initiatives right now to make sure you are protected.

Andreas Baumhof, Vice President of Quantum Technologies