By Andrew Poelstra and Jonas Nick

New cryptographic tech to protect users from leaking keys through hardware wallet attacks

Introduction

In the wake of our recent launch of Blockstream Jade, we’d like to talk about a feature we’ve developed to eliminate the possibility of a certain hypothetical undetectable attack that a hardware wallet could engage in against its owner.

While this idea has been around for many years, we were the first to implement production-ready code. Shift Crypto (who helped contribute to the implementation) have already added the feature in BitBox, and it will be deployed to Blockstream Jade in the coming weeks.

The premise of this attack is straightforward: a hardware wallet can leak the user’s secret key by carefully constructing its signatures. Since the compromise happens during signature generation rather than key generation, even if the user verifies that her keys were produced from strong randomness, e.g., by generating her seed words by rolling dice and then importing them into multiple wallets to ensure they produce the same addresses, it is still possible to execute the attack.

While all hardware wallets are potentially vulnerable to such an attack, this is an unusual threat model in that we assume the host computer is trustworthy while the hardware wallet is compromised. And while we assume a compromised hardware wallet, we still assume that the secret keys themselves are neither compromised nor backdoored.

The way the attack works is that the hardware wallet generates a nonce, a unique single-use number that constitutes half of an ECDSA (or Schnorr) signature, in a way that appears to be uniformly random but actually is not. There are many ways to do this: the hardware wallet could produce nonces which are completely known to an attacker, letting him solve for the secret key used in every signature; it could grind a byte or two of the user’s master seed into every nonce, letting him solve for every secret key given a few hundred signatures, even from different keys; it could subtly bias each nonce (even by as little as a single bit) such that keys could be recovered using the hidden number problem. Regardless of the technique, such malicious signatures can be made impossible to detect.

Contrary to popular belief, using RFC6979 deterministic nonces cannot protect against biased-nonce attacks. While RFC6979 does ensure that nonces are uniformly random, it is impossible for a user to verify that it was actually used, so it cannot protect against a malicious wallet.

There are a number of known ways to prevent or detect such an attack:

• Users could re-derive their keys on trusted hardware, compute signatures using RFC6979, and determine whether or not the hardware device did the same. This is dangerous and impractical.
• The hardware wallet could provide a zero-knowledge proof that it produced its nonces correctly. This is complex and computationally intensive.
• The hardware wallet could do a multisignature between its own key and a user’s key, which is derived from a password and does not need to be particularly secure. This would be an effective defense but complicates backup and recovery of coins, as wallets would then need to implement the same protocol to recognize each others’ coins, and loss of the password would mean loss of funds.
• The user could do a multisignature between multiple hardware wallets from different vendors. This would require extra steps for the user when generating keys and signing, and we recommend it in general, but in this post, we’d like to describe something that requires no work from the user.
• The hardware could use our anti-exfiltration scheme, which has similar implementation complexity to a multisignature but can use an ordinary workflow with unmodified BIP32 keys.

The latter solution, which we call anti-exfil, is what we have implemented.

Design Challenges

The core idea behind anti-exfil is very simple: use sign-to-contract to ask the hardware wallet to commit, using its signature nonce, to some random data provided by the host computer. The commitment re-randomizes the nonce, eliminating any information that might’ve been contained therein, and the host computer throws away the random data to ensure that nobody can derandomize the result again. However, ensuring that the covert channel was entirely eliminated, and that the host computer was unable to use the protocol to extract secret keys, proved non-trivial.

The full protocol is as follows:

1. The host computer chooses uniformly random data b which it wants the hardware wallet to commit to, and sends a hash of this data to the hardware wallet.
2. The hardware wallet computes its nonce as it normally would; if it is using deterministic randomness, it ensures that the host’s hashed data is part of its randomization. It sends this nonce R to the host.
3. The host then replies with the unhashed random data b that it wants a commitment to.
4. The hardware wallet computes R + H(R||b)G and signs the transaction using this as its nonce.

This protocol is the sixth and final scheme described in this mailing list post . While it is a bit more complicated than the obvious “host sends randomness, hardware wallet uses sign-to-contract” scheme, each step has an immediate justification:

• The hardware wallet must send its nonce R to the host before learning the random data b, or else it could choose R after-the-fact such that the final nonce is biased. (The sign-to-contract commitment structure prevents the wallet from choosing the final nonce arbitrarily, but with a bit of grinding it can still effect a bias.)
• However, the host computer needs to send a commitment to b to the hardware wallet before it reveals R, or else the host could trick the wallet into creating three signatures using the same R but different b. The host could then algebraically solve for the secret key using these three signatures.

Design Challenges 2: Selective Aborts

As mentioned in the above mailing list post, even this protocol does not entirely block the ability of the hardware wallet to bias nonces: it can still create a bias in the final nonces simply by refusing to produce signatures when the would-be nonce does not match its preferred bias.

If the user’s wallet software responds by restarting the protocol with a fresh random blob b, the result will be a successful attack. So it is essential that the wallet software does not do this, and instead bubbles up the failure to sign to the user. (If the wallet restarts with the same b, this is fine, and will be sufficient to deal with e.g. USB connection failures).

The user would see this as the signature failing, and may attempt to simply retry with a slightly different transaction; or they may replace their wallet with one that makes different signatures; or they may even try replacing the hardware wallet with a new one using the same keys. In fact, none of these mitigations can prevent this form of nonce bias.

Fortunately, even in principle, no attack of this form can successfully leak keys without more than 40 or so user-visible failures. Our recommendation to wallet developers is to ensure that any such failure results in a scary user-visible message, which recommends that the user sweep their coins to an entirely new wallet (with fresh keys) if they see this message more than a few times in their lifetime, and consider alerting other users of the device in public.

Summary

We have described an attack that a malicious hardware wallet could perform against the ECDSA (and Schnorr, post-Taproot) signatures used in Bitcoin, in which signatures are generated in undetectably faulty ways that leak key material. In order to execute such an attack, a malicious party would need to compromise the signature generation code on a hardware device, which cannot be done without cooperation from the hardware vendor (or an incredibly serious security breach).

However, because such an attack is undetectable, mitigating it is important for users who are storing coins for long periods of time, if only so that they can have peace of mind.

In recent weeks, we have implemented a mitigation called anti-exfil, which is split between our general-purpose wallet library and the high-performance cryptography library which underpins it. We are planning to release anti-exfil very soon in Blockstream Jade.

Note: This blog was originally posted at https://medium.com/blockstream/anti-exfil-stopping-key-exfiltration-589f02facc2e