A Challenge in Verifying Hardware Wallet Security

Bitcoin, Ethereum, and other blockchains use the ECDSA algorithm for transaction signatures. A crucial aspect of ECDSA’s security is the use of a random number in each signature it generates. However, if this number isn’t genuinely random — for instance, if it’s repeated or if attackers can predict it due to poor random number generation — it can expose the user’s private key. Today, we’re discussing a particularly insidious security threat: the impossibility to confirm if a hardware wallet is gradually leaking our private keys.

Kleptography in Wallets

Kleptography, a term first coined by Young and Yung in 1996, involves secretly substituting a secure algorithm with a compromised one. This compromised algorithm, while appearing to function normally, subtly leaks the user’s confidential information to an attacker.

Attackers can reveal bits of information and avoid detection in a black-box setting, where an observer can only see the inputs to and outputs from the system but not the internal workings.

This stealthy form of attack has also been referred to as Algorithm-Substitution Attacks (ASA) and subversion attacks. No matter the name, the threat remains the same: a cryptographic system that, to all outward appearances, is working perfectly but is, in reality, betraying its user’s confidential information to an adversary.

A secure crypto wallet implementation keeps private keys securely stored within the device and never exposes them during the signing process.

However, attackers with access to the ECDSA implementation could subtly alter it to leak information about these private keys. For instance, they might modify the generation of numbers used in the signature process, encoding information about the secret key within the signatures. This information is encoded within the signatures and leaves the signing device as part of a crypto transaction.

To an outside observer, the signatures produced by such a backdoored device appear entirely normal, passing all standard validity checks. However, an attacker who knows about the backdoor could collect these signatures and, through careful analysis, slowly reconstruct the private key. Once the private key is compromised, the attackers can sign transactions as if they were the legitimate owner, leading to the theft of the user’s crypto assets.

RFC 6979 is the Solution?

To mitigate this risk, deterministic ECDSA was introduced (as defined in RFC 6979). Instead of relying on a new random number for each signature, deterministic ECDSA generates this number deterministically using the private key and the message hash. This method ensures that the same message signed multiple times with the same key will always produce the same signature, removing the risk of private key exposure due to random number reuse or predictability.

The Challenge

However, a new problem arises: How can we verify that a device, such as a hardware cryptocurrency wallet, uses deterministic ECDSA as it claims to be?

The issue here is that we need the private key to determine whether a wallet created a transaction signature using random or deterministic ECDSA. But hardware wallets are designed to keep the user’s private key secure and never reveal it. So how can we confirm a device implements deterministic ECDSA correctly without access to the private key and without trusting a third party?

This is a complex question with no straightforward answer. So let’s first explore how an attacker might implement a kleptographic attack.

Leaking the seed with Trial-and-error filtering

As demonstrated by real-life incidents and research papers, it is possible to reveal an ECDSA secret key with only two signatures. However, attackers capable of compromising a hardware wallet manufacturing process would target the secret seed for higher ROI. With a wallet master key or seed, attackers can take all the assets from all the accounts in all the blockchains used by the victim. A second requirement for the attacker’s algorithm is that only they can retrieve the seed from the blockchain transactions. The backdoor needs a lock; otherwise, it would not a be “backdoor.” Next, we’ll describe an algorithm to achieve this.

The attacker begins by tinkering with the process of creating the signature. This process involves a deterministic or randomly chosen number: r. This number r plays a crucial role in ensuring the security of the signature. The signature data, the output of the ECDSA algorithm, includes the point R on the curve derived from the number r.

However, the attacker’s algorithm doesn’t choose r entirely at random. Instead, they use a particular function (PRF) that takes a curve point as input and gives a pair of values as output.
Now, this function is like a lock — it requires a password to produce the same output for the same input. In this case, the attackers chose the password they wanted. They use this password and the x-coordinate of the point R on the curve (derived from the number r) as the input to this function. The output is a pair of values (INDEX, BIT), like a map coordinate.
Here comes the trick. The attacker repeats the above process until the bit at the position INDEX of the secret seed equals BIT (0 or 1). Hence, the number r is not entirely random because the malicious code selected it to reveal a bit of secret information in each signature to those who know the password.

Recovering the Secret

The attackers monitor public blockchains, and once they’ve collected enough transaction signatures, they can start piecing together the secret seed. For each signature, they use the function with their secret password and the x-coordinate from the signature to get a pair of values (INDEX,BIT). Then, they store each BIT at INDEX in an array, like a jigsaw puzzle.
After going through all the signatures produced by the victim, the array will contain the leaked secret.

This is a very simplified explanation of how a kleptographic attack works — a stealthy way of leaking secret information from a process that’s supposed to be secure.

References

How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys https://arxiv.org/abs/1501.00447

Uncontrolled Randomness in Blockchains: Covert Bulletin Board for Illicit Activity https://eprints.lancs.ac.uk/id/eprint/150101/1/main.pdf