Quantum risk to the Ethereum blockchain - a bump in the road or a brick wall?

The main focus of this article will be to answer the following questions:

1. What is the impact of quantum computing on cryptocurrencies?
   
2. How do storage and transit attacks differ?
3. When is this going to become a problem?

Cryptographic methods in cryptocurrencies

The goal of cryptocurrencies is to enable the exchange of value without relying on a central authority. Instead, cryptographic algorithms are implemented to achieve consensus, create and process transactions, ensure the integrity of data, and more. Hashing algorithms and public-key cryptography¹ form the basis of cryptocurrency security, and these algorithms are believed to be secure against any attack with currently available computing power. However, quantum computing promises new capabilities in processing power. This is most likely going to have a significant impact on cryptocurrencies.

Grover’s algorithm, developed in 1996 by Lov Grover, is expected to reduce the security of hashing algorithms by 50%. Even more significant, Shor’s algorithm, developed by Peter Shor in 1994, is believed to completely break public-key cryptography which is used for generating digital signatures in practically all cryptocurrencies. In this blog we will mainly focus on the impact on public-key cryptography.

Addresses and transactions

Understanding and quantifying the impact of quantum computers on the Ethereum blockchain requires a better understanding of the address and transaction structure.

Address structure
Cryptocurrency funds are associated with a specific address, just like in traditional banking where money is stored under an account number. To access the funds in your bank account you need credentials to authenticate. In cryptocurrencies this authentication is performed using cryptography. A mathematical relationship exists between a user’s credential (private key) and the corresponding account number (cryptocurrency address). The specifics of this relationship between the private key, the public key and the address is depicted in Figure 1. The security of the address structure is based on the fact that the relationship between private keys and addresses is one-way. Someone with the credentials can access the account (and perform transactions) but knowing the account number does not provide any information about the credentials.

Quantum threat to Ethereum

As described above, the security of Ethereum (and many other cryptocurrencies) is based on the one-way relation between the private key and the address. A quantum computer using Shor’s algorithm is expected to break the one-way relation between the private and the public keys. This is the first step in Figure 1, The relation between the public key and the address is only partially impacted³. This means that a quantum computer can only derive the private key associated with a specific address if the public key is already known. This is only the case if the address has been used before to send funds.

We define quantum-exposed funds as coins residing in addresses where the public key is already published in the blockchain (through a transaction). Funds in addresses where the public key is not known (if funds have never been transferred out of the address) are not exposed, and are safe against currently known quantum attacks.

The unique way cryptography is used in cryptocurrencies (public keys are not always public) results in two distinct types of attacks: the storage attack and the transit attack.

Storage attack
In this attack, a malicious actor will search for funds that are stored in quantum-exposed addresses. They will then use a quantum computer to derive the private key associated with the vulnerable address, which will allow them to transfer the funds to a new address that is not vulnerable to a quantum attack.

Finding quantum-exposed funds is particularly easy in the Ethereum blockchain. Each node in the network keeps a balance sheet, called the world state, with all addresses that have ever been used and a counter that shows how many times they were used to transfer funds from. An attacker can simply look for all addresses in the world state where the counter is larger than 0. From the resulting list, the attacker picks a target address with plenty of funds. Next, they scan the blockchain for a transaction sent by this specific address and use it to obtain the corresponding public key. As explained before, after having obtained the public key, the attacker can now use a quantum computer to derive the private key and steal the funds from the targeted address.

We performed an analysis on the Ethereum blockchain to find out how many coins would be vulnerable to this type of attack. For the purpose of this analysis, we are focusing solely on Ethereum’s native token, Ether, and ignore other third party tokens implemented on Ethereum. Despite being ignored in this analysis, tokens implemented using the ERC20 standard that are stored in quantum-exposed addresses, would also be vulnerable to the storage attack.

In Figure 2 we see the result of the analysis, showing the total number of Ether in circulation over time, distinguishing between those in quantum-exposed addresses and those in non quantum-exposed addresses. From the data, it is clear that currently over 65% of all Ether are vulnerable to a quantum attack, and this number has been continuously increasing. This is a significantly larger percentage than the 25% we found for the Bitcoin blockchain in a previous analysis¹.

The difference between Ethereum and Bitcoin is primarily caused by the fact that the Bitcoin architecture is based on generating a new address for each transaction (known as the “UTXO model”). Ethereum’s architecture is based on reusing the same address unless forced to do otherwise (known as the “account model”). The account model was intentionally chosen for Ethereum in order to facilitate the implementation and usage of smart contracts. However, it causes the funds within the network to, on average, be more vulnerable to quantum attacks.

Transit attack
As discussed above, users performing a cryptocurrency transaction need to publish the public key associated with the sender’s address. The transaction is broadcast to the network to be incorporated into a new block. The time between broadcasting the transaction (revealing the public key) and the transaction being incorporated in a block opens a window of opportunity for an attack. A malicious actor could listen to broadcasted transaction, quickly derive the private key and send a competing transaction of the same funds to the attacker’s address.

For the Ethereum blockchain the average time it takes to create a new block is about 10 to 20 seconds. This is much shorter than the time expected for quantum computers to derive private keys. However, attackers could use various additional attack methods to prevent transactions from being processed quickly, buying the time to perform their quantum attack. Furthermore, during the peak activity period of the Ethereum the network can get congested and transactions can take hours or sometimes even days to process. This potentially gives attackers plenty of time to perform such an attack and get their transaction processed faster by offering a higher fee to the processing nodes than the original transaction.

How do storage and transit attacks differ?
The transit attack requires a quantum computer that can derive private keys quickly, whereas the storage attack is possible even if it takes weeks or months to derive a single private key (as long as the funds are not moved before the attack is completed). Therefore, if a quantum computer were available, the storage attack would be feasible sooner than the transit attack. On the other hand, the storage attack can only target funds stored in quantum exposed addresses, whereas the transit attack can target any coin in transit.

There are multiple mitigation strategies possible without changing the current protocol, for example avoiding address reuse in wallet implementations. However, such measures are often not in line with the platform’s original design principles and can cause unintended side effects. For instance, Ethereum is based on the so-called “account model” which actually encourages address reuse. To properly mitigate the quantum threat it is imperative to transition to cryptography algorithms with a mathematical complexity that is too great for any feasible computer, even for a quantum computer. Such an approach has both technical and governance consequences, as we will discuss in a later section.

When is this going to become a problem – the quantum computing timeline

Quantum computing technology is in its infancy and the currently available quantum computers are far from able to attack cryptocurrencies. Many breakthroughs need to be achieved before the quantum threat becomes reality. The number of qubits needs to increase dramatically (millions instead of the tens that we have today)⁴, as well as their quality. Furthermore, noise levels must be reduced by orders of magnitude, which is a nontrivial scientific and engineering challenge. It is very difficult to predict when the quantum threat is expected to materialise.

To gauge the opinion of quantum experts, the Risk Institute together with Professor Michele Mosca from the University of Waterloo in Canada, have conducted a recurring research⁵. The results show that the majority of experts believe that within 15 years the probability of quantum computers attacking public key cryptography is high.

The quantum timeline will probably remain uncertain for the foreseeable future. However, risk management is not about making exact predictions. It is about evaluating likelihood and impact to calculate risk, and to devise mitigation measures that are acceptable for the predefined risk tolerance. Due to the increasing utilization of cryptocurrencies (and blockchains in general) the impact of a future quantum attack can become so big that it requires attention sooner rather than later. The key point is that the problem does not start when quantum computers mature but when we realise that we do not have sufficient time to mitigate the risk.

Transition to quantum-safe cryptocurrencies

In spite of the unclear development timeline of quantum computers, it is generally accepted that cryptocurrencies will eventually have to migrate to quantum-secure algorithms. This transition has two main aspects. On the technical level, quantum-secure algorithms need to be developed, tested, and standardised before they can be implemented. NIST is currently running a standardisation process for quantum-secure algorithms and it is expected to provide more clarity in 2022⁶. Specifically for cryptocurrencies, the choice of algorithm is critical. All current candidates have significant drawbacks when compared to current algorithms, either in e.g. required processing time, key size, or signature size. Many cryptocurrency platforms are under scrutiny anyway and are facing scalability challenges. The performance hit from new quantum-secure algorithms can therefore be detrimental to the adoption of this technology.

An additional aspect of this transition is the decentralised governance model of cryptocurrencies, which requires broad consensus for any substantial change to the protocol. As cryptography is so deeply engrained in the cryptocurrency architecture, any migration to new cryptography algorithms will likely include extensive debates regarding specific design choices. In the past, such debates have sometimes resulted in hard forks which have a negative impact on the trust in the protocol. The transition to quantum secure cryptography will probably be the most significant upgrade cryptocurrencies have had so far, and it is difficult to anticipate how difficult it will be to achieve a consensus. It might turn out that the unique governance of cryptocurrencies ends up being a double-edged sword.

With both the technical and governance issues it is clear that a substantial amount of time is needed to make cryptocurrencies resistant to quantum attacks. Currently, very few cryptocurrencies have made the first steps towards becoming quantum-secure, and most cryptocurrencies do not even identify this problem in their roadmaps. To properly secure the future of cryptocurrencies we believe that core development teams should get informed about the risks, devise a migration plan, and incorporate it in their roadmap. Acting now will allow for adequate preparation and eventually a smooth transition. If we fail to act on time, rushing into solutions when the threat becomes more imminent, the chance of implementation errors increases which can have an undesired outcome.

References:
[1] https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html
[2] https://medium.com/brandlitic/cryptography-in-blockchain-explained-df11fe1bd0f7
[3] Grover’s algorithm impacts the security of hashing algorithms but does not significantly increase the viability of an attack involving the retrieval of an input (of byte size 32) from a hash digest.
[4] https://quantum-journal.org/papers/q-2021-04-15-433/
[5] https://globalriskinstitute.org/publications/quantum-threat-timeline-report-2020/
[6] https://www.nist.gov/news-events/news/2020/07/nists-post-quantum-cryptography-program-enters-selection-round