Facebook finally unveiled the long-rumored crypto-currency and associated blockchain Libra.
While there are plenty of things to unravel (like Libra not actually being a blockchain), I wanted to have a bit of a deep dive on which cryptographic algorithms they use and its status on quantum-safety.
SHA3 & Edwards curve Digital Signature
So let’s look at the cryptographic operations and the design choices have been pretty wise upon the first look. They use SHA3-256 as the hash algorithm and EdDSA signature scheme using the edwards25519 elliptic curve.
SHA-3 is the successor to SHA-2 and it is certainly a good choice for a new cryptocurrency (Bitcoin uses SHA2, while Ethereum also uses a SHA-3 variant).
To spend money in any crypto-currency, you need to create a transaction and digitally sign this transaction (your wallet will take care of all the nitty-gritty details). The digital signature takes your private key to sign this transaction so that you can prove to the world that you are in possession of the private key and that the transaction is authentic.
EdDSA is the Edwards-curve-Digital-Signature-Algorithm. Like ECDSA (Elliptic-Curve-Digital-Signature-Algorithm) is is based on Elliptic-Curve-Cryptography, but it differs slightly and has many benefits over EDCDA. These benefits include
However EdDSA is still a discrete-log-based signature scheme (just like ECDSA which is used in Bitcoin/Ethereum) and the security properties of EdDSA still rely on the fact that computing discreet logarithms are really,really hard.
That is certainly the case for classical computers, however it is not the case for Quantum Computers and we have an algorithm since 1984 that can efficiently break this.
So what does this all mean?
While we probably won’t have a Quantum Computer powerful enough to attack this in the next 5, 10 or 15 years, doesn’t mean we don’t have to worry.
Well, for the next 5 or 10 or 15 years, it means nothing[1]. No Quantum Computer will be powerful enough to attack this, but that doesn’t mean you shouldn’t worry.
As a reminder, a Quantum Computer can just take a public key and derive the private key from it directly within seconds. There are algorithms for Universal Quantum Computers (such as IBM Q System One, IonQ, Google Bristlecone) as well as Quantum Annealers (such as D-Wave’s Quantum Computer)
Because every Libra transaction will contain the Sender’s public key (see section 3.2 of the Libra Blockchain whitepaper), every single account is at risk today.
Yes, you heard that right. Someone with bad intentions can just simply record all public keys today and store them (harvesting phase). Once a Quantum-Computer is powerful enough in the future, they can use them to derive the corresponding private key to it and all money is stolen.
It’s called a “Harvest Now – Decrypt Later” attack and Libra is not the only one vulnerable to it. Bitcoin is vulnerable too and in one of my last posts, I dug deeper into this topic. (https://www.linkedin.com/pulse/perfect-harvest-now-decrypt-later-attack-how-steal-10-baumhof/) For Bitcoin this is already a massive problem as there are over 1 million Bitcoins with an exposed public key that are worth over $10 billion USD right now.
So what needs to happen to make Libra Quantum-Safe?
That’s where it get interesting. Your Libra address is actually just a hash of your public key. Your public key is simply a point on the edwards25519 elliptic curve. To make Libra Quantum-Safe, we need to move away from Elliptic Curves, but that means that your Libra Address and your private and public key will need to change.
Now the problem is that your money is already in your current Libra address, so to make it Quantum-Safe, you’d have to actively move the funds to a Quantum-Safe address. Every single user need to do this for every single address. There is no way around that. Even if all users still have the private key, this will be a nightmare, but obviously this isn’t possible for users who lost their private key. The $10 billion USD in Bitcoin are then just up for grabs and nobody can do anything about it. The perfect crime.
And obviously this has to happen before a Quantum Computer exist, which nobody knows when it is, but it will happen and when it happens, then all your money is lost… Not really a perfect value proposition for long term storage of funds.
The Libra network will have to undergo a fork to implement these new algorithms, which in Libra’s case should be much simpler as it is a “closed” group of Validators and not a public, permissionless blockchain such as Bitcoin or Ethereum.
Could Facebook have designed Libra differently to make it quantum-safe?
Absolutely and they should have.
The problem is non-trivial though as there are no officially approved quantum-safe alternatives for the digital-signature-algorithm. NIST is running a competition to find one (or a few), but this competition still runs for a few years, so the choice of EdDSA is generally a good one.
However, Facebook could have done plenty of things differently and I just want to highlight two things:
I want to summarize this and make it relevant to all software applications: “Design it in a way where you can change out the internal cryptographic algorithms without any impact to the user“.
Facebook’s Libra blockchain will have to address these issues in the future, potentially at the expense of all its users. Designing a brand new system gives you the chance to do things right without inconveniencing everybody later and unfortunately this looks like an opportunity missed.
Footnote:
To complete the crypto protocol part of Libra, I’d like to mention that the Validators in the Libra network communicate via the Noise protocol framework (http://www.noiseprotocol.org/noise.html). It is a nice framework that includes Key Exchange, Symmetric Encryption and Hashing into one overarching protocol. Everything is configurable and e.g. the choice of ciphers for the encryption can be negotiated.
However it has to be mentioned that the Noise protocol uses the Diffie-Hellman Key exchange (DH), which unfortunately can be efficiently attacked with quantum computers. The purpose of the Key exchange is for both parties to negotiate a common encryption key, so if an adversary gains knowledge of the encryption key, it doesn’t matter anymore what type of encryption is used as if you have the key, you can trivially encrypt or decrypt everything anyways.
[1] I won’t get into an argument about timeframes and nobody can predict the future, but keep Neven’s law in mind. It states that quantum computers improve at a “doubly exponential” rate. Neven himself says:
“With double exponential growth, it looks like nothing is happening, nothing is happening, and then whoops, suddenly you’re in a different world. That’s what we’re experiencing here.”
I hope we won’t be experiencing the same here… For a related problem (factorization integers), researchers reduced the numbers of qubits required from over 1bn to 20m in the space of just 7 years. 20million is still a huge number, but the trajectory is still mindblowing.
Andreas Baumhof, Vice President of Quantum Technologies