Research: Hackers Could Install Backdoor in Bitcoin Cold Storage

Even a bitcoin wallet in cold storage, widely thought to be the most secure way to hold the digital currency, could leak its private keys to an attacker, a security researcher has found.

An attacker could reverse-engineer a compromised wallet’s private keys from as little information as a single transaction issued by that wallet.

The attack is particularly worrying because it would be successful even if the victim maintained a wallet on an air-gapped machine without an Internet connection – or even in space, as wallet provider Xapo is attempting to do –  according to the paper by Stephan Verbücheln.

Verbücheln, a researcher at Humboldt University’s Institute for Computer Science in Berlin, said:

“The attacker only has to watch the blockchain until two [compromised] signatures appear … the affected signatures are not detectable by anyone other than the attacker.”

Conventional wisdom has it that coins in cold storage are safe from attacks because the private keys never come in contact with the Internet or any other network.

In general, this is true. Even if the cold storage device could be compromised by malware, stolen private keys would fail to be transmitted to a thief because it isn’t connected to the Internet.

How it works

Verbücheln’s paper, which is titled, How Perfect Offline Wallets Can Still Leak Bitcoin Private Keys, sets out an attack that centres on bitcoin’s cryptographic algorithm.

This mathematical formula, known as ECDSA or the Elliptic Curve Digital Signature Algorithm, is used in the bitcoin protocol to ensure funds can be only be spent by their rightful owners.

When a bitcoin transaction takes place, it contains one or more ECDSA signatures. The number of signatures in a transaction depends on the number of inputs that it contains and are used to prove the transactions were authorised by their rightful owners. The amount of bitcoin contained in a transaction consists of the sum of its inputs.

The attacker must first create a compromised version of ECDSA. This is achieved with a kleptographic ‘SETUP’, or ‘Secretly Embedded Trapdoor with Embedded Protection’, which was first described in a 1997 paper by Adam Young and Moti Yung. That paper described a similar attack on the Digital Signature Algorithm, on which ECDSA is based.

Each time a bitcoin transaction is signed, the signature is generated partly from a random number known as ‘k’. The compromised ECDSA uses a specific formula to select ‘k’, which is in turn used to compute a further value ‘k2’.

The attacker will now watch for consecutive signatures signed by the compromised ECDSA. Because he knows how ‘k2’ was computed in the first place, he will be able to calculate that value from two consecutive signatures. With ‘k2’ in hand, the attacker can work backwards to calculate ‘k’ and the private key to that address.

“After the attacker knows ‘k2’ for an ECDSA signature, it is easy for him to compute the private key,” Verbücheln said.

An observer of the blockchain – and even the attacker himself –  looking at signatures from this compromised elliptic curve would not be able to detect any faults. Unlike a general observer, however, the attacker would be running his extraction formula on every signature on the blockchain, hoping to find the ‘k2’ value from signatures generated by his malicious ECDSA.

Eventually, the attacker will hit on the signatures signed by his handiwork, allowing him to discover ‘k2′ and ultimately derive the addresses’ private key.

“He can now store the extracted private keys and watch the addresses’ balance. He can use them to steal money at any point in time,” Verbücheln said.

The good news

Verbücheln said his paper has not been submitted for publication yet, although he is giving a talk on the topic at a conference in Amsterdam next week.

While the scenario described by Verbücheln is frightening – private keys essentially leaked to the blockchain – the good news is that it’s a difficult attack to carry out on a large scale.

Ivan Pustogarov, a researcher at the University of Luxembourg’s cryptology research group, said an attempt to smuggle compromised ECDSA code into a popular open-source wallet, for example, would be discovered by the public.

“In open-source [software] on a large scale … The code will be analysed at some point in time and the malicious implementation detected,” he said.

Verbücheln largely shares this assessment, although he cautions that some pieces of open-source code are so large and complex that even a dedicated community of developers may not detect a malicious addition.

Both Verbücheln and Pustogarov say that the most likely way for such an attack to be mounted would be through dedicated wallet services running proprietary software. Devices designed specifically for secure cold-storage of coins, for example, would be prime candidates for this sort of attack.

“Even if the manufacturer claims that it runs open-source code, how do you tell whether it is actually running what you compiled?” Verbücheln said.

According to Pustogarov, the Verbücheln paper describes an attack that is related to the ‘repeated r-values’ flaw that white-hat hacker ‘Johoe’ famously exploited to grab more than 500 BTC from wallet provider Blockchain.

“These two issues are related. The [Verbücheln] paper describes a more general approach, and repeated r-values is a sub-case,” he said.

Verbücheln said he does not know if the attack he described has actually been carried out. Nevertheless, the possibility that one of the core cryptographic algorithms underpinning bitcoin could be cunningly compromised, allowing a thief to pick the lock of even the most secure addresses, presents a chilling scenario.

“This attack has been known for many years for related crypto systems, so you can’t know for sure,” he said.