The Quantum Computing Threat to Blockchain

Blockchain and Quantum computing are two technologies awaiting a impactful collision. Cryptography is an essential component of both quantum computing and blockchain. It is predicted that the blockchain systems we have today will be outdated once quantum computers are commercially available on the market and become mainstream.

The data on the internet that is stored in servers and databases and is secured by current security mechanisms is vulnerable to cyber attacks. This threat becomes imminent as quantum computers are gaining traction. Information interchange on the internet as it exists in its current form uses the Rivest–Shamir–Adleman (RSA) algorithm and Elliptic-Curve Cryptography (ECC). These algorithms are used to encrypt and decrypt information transmitted over the internet. These algorithms fall inside a class of public-key cryptography or asymmetric cryptography generation of such key pairs are based on mathematical problems termed one-way functions.

The incapacity of a computer, or a supercomputer, or even a network of hundreds of supercomputers, to solve these math problems provides much of currently confided-on cryptography its defensive competence.

The capabilities of a Quantum computer

The problems and solutions created by cryptologists require far more effort than exponential time. Time scale solutions like polynomial, square root, quadratic, and factorial are all huge improvements on exponential time and are known as superexponential time scale solutions. Any computing agent that delivers these types of time advancements are a threat to algorithms which provide defense to underlying assets by banking on exponential time defenses. Any cryptanalytic attack that exceeds exponential time is a threat to cryptographic solutions that relies on exponential time protection. Qubits and quantum algorithms give superexponential problems and solutions.

The advent of quantum computing represents a epitomic shift in which digital technologies will encounter both challenges and opportunities. The capabilities of quantum computers are getting better at a very fast pace.

• In 2012, a 4-qubit quantum computer was demonstrated to factor the number 143.

• In 2014, a quantum computer could factor the number 56,153.

• In 2019, Google and KTH Royal Institute of Technology published a paper titled "How to factor 2,048-bit RSA integers in 8 hours using 20 million qubits".

With each passing year, fewer and fewer qubits are needed for computation making error correction more efficient and quantum computers more practical.

The Security holes in Blockchain

Blockchain implements an open, distributed, cryptographically signed digital ledger that is secure against tamper and verifiable by the stakeholders. To prevent bulk rewriting of an entire sequence of blocks from some point in the past as well as attacks to deny service or grow the chain faster than legitimate sources can, a work requirement is added to make rewriting long chains prohibitive. For our purposes here, the relevant structure amounts to the following description: It is worth exploring the conjunction of blockchain technology and quantum computing in the following four areas.

Communication over the blockchain network Inter-node communication relies on protocols such as HTTP. The security of the communication happens in HTTPS within the SSL/TLS protocol stack. TLS supports one-time key generation (which is not quantum safe) with AES for symmetric encryption and several non-quantum-safe algorithms for exchange and authentication, such as RSA, DH, ECDH, ECDSA, and DSA. This means that all internet communications, including transactions and messages sent between applications and nodes in a blockchain, will not be quantum safe when robust quantum computers become fully operational.

The use of Pseudo Random Numbers (PRN) The blockchain consists of a sequence of blocks that are stored on and copied between publicly accessible servers. Each block consists of four fundamental elements: a) the hash of the preceding block b) the data content of the block (i.e. the ledger entries) c) the nonce that is used to give a particular form to the hash d) the hash of the block All processes mentioned above require random numbers as inputs, which in the case of blockchains currently present, are obtained from pseudorandom number generator (PRNG). PRNG is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values).

Digital signatures Digital signatures are one of the most essential components of blockchain technology. Bitcoin and Ethereum use elliptic curve cryptography (ECC), particularly the ECDSA signature schemes on curve secp256k1. Others, such as EOSIO, use the NIST standard secp256r1 curve. NIST recommends that ECDSA and RSA signature schemes be replaced due to the impact of Shor’s algorithm on these schemes.

Hash functions Hashing functions take an element from a set of infinitely many elements and gives an output from a finite set of 2256 elements in the case of the SHA-256 function that is used by most of the blockchain networks today. Thus, from a hash value stored in the blockchain, it is statistically impossible to obtain the element that resulted in that value. This property, known as irreversibility or pre-image resistance, guarantees the security of these operations even in the presence of quantum computers.

Additionally, hash functions are continually evolving for increased security. For example, if quantum computers evolve to the point of posing a threat to SHA-2, then SHA-3 is already standardized as an alternative that offers a higher level of security in NIST standard FIPS202.

Block mining Blockchain networks that use proof-of-work as the consensus mechanism rely on finding nonces. Quantum computers will be able to find these nonces quadratically faster using Grover’s algorithm. However, this does not pose a major threat to the security of blockchain networks because the solution will be as easy as quadratically increasing the difficulty to compensate for the quantum advantage. In networks with consensus protocols that do not promote competition between nodes, such as the proof-of-authority used in the LACChain Blockchain, this threat will not exist.

Quantum Computing Threats to Blockchain

The computational data structure known as a blockchain provides an open, public, distributed ledger that has many interesting applications, including digital currencies. The security of this ledger depends on the difficulty of solving certain cryptographic problems which are undermined by the potential of quantum computation. Specifically, hashes as used in signing the blocks of the ledger can be compromised, as can any public/private key system which relies on the so called hidden subgroup problem.

Blockchains are at greater potential risk from quantum computing than other technologies because they are heavily dependent upon cryptography. The very premise of blockchain protocols is the computational infeasibility of inverting certain one-way hash functions, but these may be broken with quantum computers. At the same time, blockchains also stand to potentially benefit the most from the innovations developed in quantum cryptography.

• Grover’s algorithm can dramatically speed up function inversion. This allows the generation of a modified pre-image from a given hash (a hash collision) allowing a signed data block to be modified. This voids guarantees of authenticity of the ledger entries undermining the entire blockchain. The speed-up due to Grover’s algorithm is a factor of the square root of the number of possible hashes, meaning that a hash subjected to quantum attack would only be as secure as one with half as many bits subjected to classical attack. Grover’s algorithm is specifically a solution to the problem of finding a pre-image of a value of a function that is difficult to invert. If we are given a signature that is the hash value of some data 𝑠=𝐻(𝑑), and the function 𝐻(𝑑)can be implemented on a quantum computer, then Grover’s algorithm allows us to find 𝑑 for a given 𝑠in time of order 𝑂(√𝑛) where 𝑛 is the size of the space of valid hashes. In other words, it allows us to generate hash collisions more efficiently than brute force search, which would be 𝑂(𝑛). For a hash of length 𝑘 bits this means that we have a significant speedup by a factor of 2𝑘/2. This can be very large even for small values of 𝑘.

• Shor’s algorithm applies to any aspect of blockchain that relies on asymmetric key cryptography. The most commonly referenced problem is that of breaking RSA encryption. RSA relies on the ease of multiplying prime numbers in contrast to the difficulty of factoring large numbers into prime factors. Shor’s algorithm speeds-up this process exponentially, effectively breaking RSA encryption. Variants of Shor’s algorithm do the same for other asymmetric key cryptosystems. It helps to find the two prime factors of a composite integer used as a public key in an algorithm like RSA. Being able to factor the integer, which is computationally challenging on classical computers, yields to the attacker the private key of the public/private pair. That makes it possible for the attacker to forge messages, signatures, etc.

• Risk of quantum attack in mining Mining is the consensus process that validates new transactions and keeps the blockchain secure. One way would be to attack the hashing algorithm by which the mining operation is conducted. In Bitcoin, the hash function, though, is quite strong, and possibly more quantum-resistant than other cryptographic algorithms used in blockchain operations. Bitcoin’s Hashcash proof-of-work consensus algorithm uses a double SHA hash function, meaning two sequential applications of SHA-256; a SHA-256 of SHA-256 (a composite function of SHA-256(SHA-256(x))) (Kelly et al., 2018; Aggarwal et al., 2018).

• Interception, decryption and tamper of data communications Any encrypted communications used in the infrastructure upon which a blockchain is constructed are vulnerable to an attacker who can break the cryptographic security of the communications.

The general threat of quantum computation is that such algorithms become unviable because the premise of asymmetric effort of computation is invalidated. Quantum computing provides potential attacks on many cryptographic systems and algorithms.

The Urgency of the Threat

The operational consequence of the rise of Quantum computing is that whoever gets quantum computational capacity first has an advantage, but only until the defending parties develop the capacity themselves.

Estimates vary as to when quantum computing will be a threat to the current cryptographic infrastructure, blockchain-related and otherwise.

• An estimate from NIST, drawing from industry experts, suggests that quantum computers powerful enough to break the current 2048-bit RSA standard might be available by 2030 (Chen et al., 2016).

• Others predict that the elliptic curve signature scheme currently used by Bitcoin (ECDSA) is at even greater risk, and could be broken by quantum computing as early as 2027 (Aggarwal et al., 2018).

Current Threats

Previously, exploits such as Anyswap hack have happened because the random number required for signatures have been reused. The exploit used these signatures to reverse engineer the private key controlling AnySwap’s cross-chain MPC account and steal the funds. In this case, the transaction was generated by a hardware bitcoin wallet using a pseudo-random number generator that was returning the same random number every time. The ECDSA signature algorithm requires the generation of a per-message secret nonce. If this nonce is not generated uniformly at random, an attacker can potentially exploit this bias to compute the long-term signing key.

To summarize, many of the vulnerabilities arise because of deterministic seeding for generating random numbers that are in turn used to generate private keys. Apart from side-channel attacks, this weak seeding methodology also opens doors for decrypting harvested data.

Future threats

Algorithms vulnerable to quantum computing

Quantum computers in the near future can break any cipher algorithm whose security relies on the integer factorization problem, the discrete logarithm problem, the elliptic-curve discrete logarithm problem. The following algorithms and ciphers are vulnerable.

• RSA (Rivest–Shamir–Adleman)

• Diffie-Hellman key exchange

• Digital Signature Algorithm (DSA), also known as Finite Field Cryptography

• Elliptic Curve Cryptography like ECDSA (Elliptic Curve Digital Signature Algorithm)

• Schnorr and El-Gamal signature schemes

• Public Key Infrastructure (PKI)

• HTTPS/TLS which relies on PKI, thus breaking the entire web.

• Most VPNs, as they use HTTPS and PKI

• Hardware Security Modules (HSMs)

• Smart cards

• Blockchains and Cryptocurrencies

• Most two-factor authentication that relies on digital certificates, like Google security keys

• Pseudo random number generators (PRNGs)

Quantum Resistance

Algorithms resistant to quantum computing

Cryptographic algorithms that are secure against a cryptanalytic attack by a quantum computer are referred to as post-quantum cryptography or quantum-safe or quantum-resistant. The following algorithms fall within this category.

• Symmetric ciphers like AES.

• Newer integrity hashes, like SHA-2, SHA-3 when used with safe hash sizes

• SHAKE, a stream cipher

• Quantum key distribution (QKD), such as BB84, BBM, B92, COW, DPS, E91, and SARG04

• SNOW 3G, a word-based synchronous stream cipher

• Supersingular isogeny Diffie–Hellman key exchange (SIDH)

• Lattice-based cryptography

• Multivariate-based cryptography

• Code-based cryptography

• Some forms of zero-knowledge proof cryptography

• Quantum random number generators (QRNG)

• Quantum-based ciphers

Today, there are hundreds of billions of dollars worth cryptocurrencies that use distributed ledger technology (DLT) provided by blockchains. The crypto-assets locked in these ledgers need the guarantee of quantum resistance to safeguard the integrity of data and assets, which can be provided only by adopting quantum security technologies in their suite.