Quantum resistant blockchain and cryptocurrency, the full analysis in seven parts. Part 6.
By QR Collector on ALTCOIN MAGAZINE
Part 1 here, part 2 here, part 3 here, part 4 here and part 5 here
Why BTC is vulnerable for quantum attacks sooner than todays estimates.
Small recap: Blockchain transactions are secured by public-private key cryptography. The keypairs used today will be at risk when quantum computers reach a certain critical level: Quantum computers can, at a certain point of development, derive private keys from public keys. See for more sourced info on this subject in part 3. So if a public key can be obtained by an attacker, he can then use a quantum computer to find the private key. And as he has both the public key and the private key, he can control and send the funds to an address he owns.
Just to make sure there will be no misconceptions: When public-private key cryptography such as ECDSA and RSA can be broken by a quantum computer will be an issue for all blockchains who don’t use quantum resistant signature schemes. The reason this article is about BTC, is because I take this paper as a reference point. In that paper the authors have calculated an estimate when BTC will be at risk, while taking the BTC blocktime as the window of opportunity.
The BTC misconception: “If you don’t reuse addresses, BTC is quantum resistant.”
In pretty much every discussion I’ve read on the subject, I notice that people are under the impression that BTC is quantum resistant as long as you use your address only once. BTC uses a hashed version of the public key as a send-to address. Therefore the full original public key, is not made public untill you make a transaction. So in theory, all funds are registered on the chain on hashed public keys instead of on the full, original public keys, which means that the original public key is (again in theory) not public. Even a quantum computer can’t derive the original public key from a hashed public key, therefore there would be no risk that a quantum computer can derive the private key from the public key. If you make a transaction, however, the public key of the address you sent your funds from will be published in full form on the blockchain. So if you were to only send part of your funds, leaving the rest on the old address, your remaining funds would be on a published public key, and therefore vulnerable to quantum attacks. So the workaround would be to transfer the remaining funds, within the same transaction, to a new address. In that way, your funds would be once again registered on the blockchain on a hashed public key instead of a full, original public key.
If you feel lost already because you are not very familiar with the tech behind blockchain, I will try to explain the above in a more familiar way:
You control your funds through your public- private key pair. Your funds are registered on your public key. You can create transactions, which you need to sign to be valid. You can only create a signature and sign your transaction if you have your private key. See it as your e-mail address (public key) and your password (Private key). Many people got your email address, but only you have your password. So the analogy is, that if you got your address and your password, then you can access your mail and send emails (Transactions). If the right quantum computer would be available, people could use that to calculate your password (private key), if they have your email address (public key).
Now, because BTC doesn’t show your full public key anywhere until you make a transaction. That sounds pretty safe. It means that your public key is private until you make a transaction. The only thing related to your public key that is public, is the hash of your public key. In part 2 you can read a more extensive explanation of hashing. But here is a short explanation of what a hash is: a hash is an outcome of an equation. Usually one-way hash functions are used, where you can not derive the original input from the output.(Due to the nature of the math, not even with a quantum computer) Every time you use the same hash function on the same original input (For example IFUHE8392ISHF), you will always get the same output (For example G). That way you can have your coins on public key “IFUHE8392ISHF”, while on the chain, they are registered on “G”.
So your funds are registered on the blockchain on the “Hash” of the public key. The Hash of the public key is also your “email address” in this case. So you give “G” as your address to send BTC to.
As said before: since it is, even for a quantum computer, impossible to derive a public key from the Hash of a public key, your coins are safe for as long as the public key is only registered in hashed form. The obvious safe method would be, never to reuse an address, and always make sure that when you make a payment, you send your remaining funds to a fresh new address. (There are wallets that can do this for you.) In theory, this would make BTC quantum resistant, if used correctly. This, in reality, is not correct. Even if you only use your address once, your public key will be exposed long enough for quantum computer hacks.
Already exposed public keys.
But before we get to that, there is another point that is often overlooked: Not only is the security of your personal BTC is important, but also the security of funds of other users. If others get hacked, the news of the hack itself and the reaction of the market to that news, would influence the market price. Or, if a big account like the Satoshi account were to be hacked and dumped, the dump itself, combined with the news of the hack, could be even worse. An individual does not have the control of other people’s actions. So even though one might make sure his public key is only registered in hashed form, others might not do so, or you might not even know their public key is exposed in certain cases, even though you never made transactions from your address.
Lately, Pieter Wuille, BTC dev, acknowledged this on twitter, here and here.
This is also acknowledged by Andrew Poelstra in this interview. (40:00 and further) He even goes as far as explaining how public keys are exposed in several other ways besides sending transactions to such an extent that “basically all the public keys are exposed.” “If everybody else bitcoins are lost, then […] you have retained all these tokens that are worthless.” Which is an acknowledgment of the risk of value decline due to hacks of the percentage of BTC that is not on addresses with hashed public keys?
44:00 “It was never intended as quantum protection. It doesn’t function as quantum protection. There’s sort of this idea out there that it does, but it doesn’t. And even if it did, by the way, it’s very unclear how you would spend your coins again, because you have to reveal the public key to spend the coins.”
There are several reasons why a substantial amount of addresses actually have exposed full public keys:
- Only unused addresses are quantum secure, but in reality, there are a lot of people, who reuse addresses. (To clarify: with unused I mean an address that has only been used to deposit funds on, and not used to make transactions from. Because if you make a deposit, or if others transfer funds to your address as payments, your public key stays hidden, but if you make a transaction from that address to another address, your public key will be revealed. See for a detailed explanation, part 2.)
- Bitcoin transactions with P2PK UTXOs: these are the older addresses from the period that public keys were not hashed, but published in full. (about 1.77 million BTC fall into this category) (https://eprint.iacr.org/2018/213.pdfp. 7) This includes the Satoshi funds.
- Bitcoin users publishing their public key on a Bitcoin fork, e.g. Bitcoin Cash or Bitcoin Gold. (https://eprint.iacr.org/2018/213.pdf p. 7)
- Any other revealing of public keys, such as part of signed messages to ensure integrity, in forums, or in payment channels (e.g. Lightning Network [51]). (https://eprint.iacr.org/2018/213.pdf p. 7)
In total, about 36% of all BTC are on addresses with exposed public keys. About 20% of all BTC is on lost addresses see also here. This includes the Satoshi coins. See part 5 for an explanation about lost addresses and why these will never be secure against quantum hacks.
Hijacking transactions.
But even if you consider the above an acceptable risk, just because you yourself will make sure you never reuse an address, then still, the fact that only the hashed public key is published until you make a transaction is a false sense of security. It only works, if you never make a transaction, so if you never spend your funds. Why? Public keys are revealed while making a transaction, so transactions can be hijacked from the moment you send them from your device.
It is important to fully understand two things:
1.) How is a transaction sent?
The owner has the private key and the public key and uses that to log into the secured environment, the wallet. This can be online or offline. Once he is in his wallet, he states how much he wants to send and to what address.
When he sends the transaction, it will be broadcasted to the blockchain network. But before the actual transaction will be sent, it is formed into a package, created by the wallet. This happens out of sight of the sender.
That package ends up carrying roughly the following info: the public key to point to the address where the funds will be coming from, the amount that will be transferred, the address the funds will be transferred to (depending on the blockchain this could be the hashed public key, or the original public key of the address the funds will be transferred to). This package also carries the most important thing: a signature, created by the wallet, derived from the private- public key combination. This signature proves to the miners that you are the rightful owner and you can send funds from that public key.
Then this package is sent out of the secure wallet environment to multiple nodes. The nodes don’t need to trust the sender or establish the sender’s “identity”, because the sender proofs he is the rightful owner by adding the signature that corresponds with the public key. And because the transaction is signed and contains no confidential information, private keys, or credentials, it can be publicly broadcast using any underlying network transport that is convenient. As long as the transaction can reach a node that will propagate it into the network, it doesn’t matter how it is transported to the first node.
2.) How is a transaction confirmed/ fulfilled and registered on the blockchain?
After the transaction is sent to the network, it is ready to be processed. The transaction waits to be added to a block. Transactions will not be added to a block immediately. It depends on the fee that is added to the transaction and to the amounts of transactions that need to be added. At rush hours, it can take longer then usual. The nodes will bundle transactions to verify and register on the next block. The verifying is done during a period called the block time. In the case of BTC that is 10 minutes.
If we process the information written above, we will see that there are two moments where you can actually see the public key, while the transaction is not fulfilled and registered on the blockchain yet. So:
1: During the time the transaction is sent from the sender to the nodes
2: During the time the nodes verify the transaction. (The blocktime)
An attack during moment number 2: Hijacks during blocktime
This paper describes how you could hijack a transaction and make a new transaction of your own, using someone else’s address and send his coins to an address you own during moment number 2: During blocktime, the time the nodes verify the transaction:
“(Unprocessed transactions) After a transaction has been broadcast to the network, but before it is placed on the blockchain it is at risk from a quantum attack. If the secret key can be derived from the broadcast public key before the transaction is placed on the blockchain, then an attacker could use this secret key to broadcast a new transaction from the same address to his own address. If the attacker then ensures that this new transaction is placed on the blockchain first, then he can effectively steal all the bitcoin behind the original address.” (Page 8, point 3.)
So this means that BTC obviously is not a quantum secure blockchain. Because as soon as you will touch your funds and use them for payment, or send them to another address, you will have to make a transaction and you risk a quantum attack.
An attack during moment number 2: Hijacks pre-blocktime.
The story doesn’t end here. The paper doesn’t describe the possibility of a pre-blocktime hijack.
So back to the paper. As explained: while making a transaction, your public key is exposed for at least the blocktime. For BTC this blocktime is 10 minutes. That is the period where your public key is visible and where, as described in the paper, a transaction can be hijacked, and by using quantum computers, a forged transaction can be made. So the critical point is determined to be the moment where quantum computers can derive private keys from public keys within 10 minutes. Based on that 10 minute period, they calculate (estimate) within how many years QC’s start forming a threat to BTC. (“ By our most optimistic estimates, as early as 2027 a quantum computer could exist that can break the elliptic curve signature scheme in less than 10 minutes, the block time used in Bitcoin.” This is also shown in figure 4 on page 10 of the paper and later more in depth calculated in appendix C, where the pessimistic estimate is around 2037.)
But before a miner selects a transaction and starts to work on a block, the transaction is added to the mining pool and waits there to be selected. This selection isn’t instant, and thus another window of opportunity to start working with the public key arises. Now in rush hours, transactions can be stuck in the pool for a while simply because transactions are piling up and the network can’t handle the amount of transactions fast enough. So at these times the window of opportunity could increase quite seriously and the time the public key is exposed is extended.
But you could also artificially extend that 10 minutes through network based attacks like DDoS, BGP routing attacks, NSA Quantum Insert, Eclipse attacks, or anything like that. (And I don’t mean you extend the block time by using a network based attack, but you extend the time you have access to the public key before the transaction is confirmed.) Bitcoin would be earlier at risk than calculated in this paper.
Also other Blockchains that hash their public keys, and which have way shorter block times, imagine themselves safe for a longer period than BTC. But with this extension of the timeframe within which you can derive the private key, they too will be vulnerable way sooner.
Not so long ago an eclipse attack demonstrated it could have done the trick. Here a paper on the eclipse attack. Causing the blockchain to work over max capacity, means the transactions will be waiting to be added to a block for a longer time. This time needs to be added on the blocktime, expanding the period one would have time to derive the private key from the public key.
That seems to be fixed now, but it shows there are always new attacks possible and when the incentive is right (Like a few billion $ kind of right) these could be specifically designed for certain blockchains.
An attack during moment number 1: MITM attacks
An MITM attack could find the public key in the first moment the public key is exposed. (During the time the transaction is sent from the sender to the nodes.) As explained, these transactions that are sent to the network, contain public keys that you could intercept. That means that if you intercept transactions (and with that the public keys) and simultaneously delay their arrival to the blockchain network, you create extra time to derive the private key from the public key using a quantum computer. When you done that, you send a transaction of your own before the original transaction has arrived and is confirmed. That way you send funds from the stolen address to an address of your choosing. The result would be that you have an extra 10, 20, 30 minutes (or however long you can delay the original transactions), to derive the public key. Therefore, slower quantum computers form a threat. Meaning that earlier models of quantum computers, can form a threat to cryptocurrency than is assumed now. This can be done without ever needing to mess with a blockchain network, because the attack happens outside the network.
When MITM attacks and the other mentioned ways of hijacking transactions will form a threat to BTC, other blockchains will be vulnerable to the same attacks.
At this point of time, the public key would be useless to an attacker due to the fact there is no quantum computer available now. Once a quantum computer of the right size is available, it becomes a problem. For quantum resistant blockchains this is different. MITM attacks and hijacking is useless to quantum resistant blockchains like QRL because they use quantum resistant keys.
You can continue reading here: part 7
