Reflections on Trusting Hardware Wallet Manufacturers

Recently, the hardware wallet manufacturer Ledger announced a new feature that would allow users to back up their seed words with some cloud providers. The seed would be split up and encrypted, such that no cloud provider on his own could get access to any funds. Nevertheless, this was received with considerable criticism by some parts of the wider community. They regarded it as a problem to have that kind of functionality embedded in the device. For some, it came as a surprise that such a thing was possible at all, and that the relevant secrets were not protected by some kind of hardware guarantee. For many users, this was the first realisation that the device firmware, and updates to this firmware, require complete trust in the manufacturer.

In this post we will demonstrate that the need for this kind of trust is unavoidable. To this end, we will see how the completely normal activity of signing transactions can be maliciously misused to leak a complete private key. Therefore, even if you could convince yourself that the only thing that ever leaves the hardware wallet are signatures (which is the whole purpose of the device!), this would still not be sufficient to reduce the need for trust. The idea is relatively simple: We will exploit the fact that, for a single message and private key, there exists a practically unlimited number of valid signatures. We will use this to leak a single bit of the private key for each signature the user requests.

The below sections will use Rust code to demonstrate the idea, but those are not necessary to understand the bigger picture.

Demonstration

We start with a malicious signer that will leak its private key one bit at a time:

1
struct Signer(secp256k1::SecretKey);

As mentioned above, the idea is to leak a random bit of the private key with every signature. As Bitcoin private keys have 256 bits, we let the first signature byte indicate the location of the bit that will be leaked. The very next bit in the serialisation will then say what that bit of the private key is. This leads to the following check whether we have successfully leaked a bit with a signature:

1
2
3
4
5
impl Signer {
  fn is_leaking_sig(&self, sig_bytes: &[u8]) -> bool {
    extract_bit(&self.0.secret_bytes(), sig_bytes[0]) == sig_bytes[1] >> 7 & 1
  }
}

Every time the user asks for a signature, the signer will leak a random bit of the private key. For each signing attempt, this means a 50% chance that the signature will leak information, which means we will need two attempts on average:

1
2
3
4
5
6
7
8
9
10
impl Signer {
  fn sign_message(&self, msg: &[u8]) -> secp256k1::ecdsa::Signature {
    loop {
      let sig = self.generate_sig(msg);
      if self.is_leaking_sig(&sig.serialize_compact()) {
        return sig;
      }
    }
  }
}

The signature collector can simply watch the blockchain for transactions sending coins from a particular address, and keep track of which bits have been leaked:

1
2
3
struct SigCollector {
  privkey_bits: std::collections::HashMap<u8, u8>,
}

Every time a new signature comes in, he updates his list of leaked bits:

1
2
3
4
5
6
impl SigCollector {
  fn receive_sig(&mut self, sig: secp256k1::ecdsa::Signature) {
    let ser = sig.serialize_compact();
    self.privkey_bits.insert(ser[0], ser[1] >> 7 & 1);
  }
}

The collector doesn't need to wait until all 256 bits have been leaked. The last 40 to 50 bits can easily be brute-forced, since the collector knows which public key the private key should map to. Once he has either collected or brute-forced all bits, the private key can be simply reconstructed as:

1
2
3
4
5
6
7
8
9
impl SigCollector {
  fn extract_privkey(&self) -> secp256k1::SecretKey {
    let mut extracted_privkey = [0; 32];
    for (bit_pos, bit) in &self.privkey_bits {
      extracted_privkey[(bit_pos / 8) as usize] |= bit << (bit_pos % 8);
    }
    secp256k1::SecretKey::from_slice(&extracted_privkey).unwrap()
  }
}

The complete code can be found here. 

Conclusion

We have seen how, using only completely normal signatures, a hardware wallet can exfiltrate a user's private key, given the address gets reused enough times. This demonstrates the need for trust in the hardware manufacturer. Importantly, this need for trust can be mitigated and distributed over more entities: Software and hardware specifications can be open-sourced, and firmware builds be made deterministic. In addition, some hardware manufacturers also employ measures to ensure that the hardware wallet on its own cannot fully choose the signature by itself, thus avoiding the above attack if only the hardware wallet is compromised.