Open-Source Tool Identifies Weak Bitcoin Wallet Signatures

UPDATE (17th October 15:00 BST): A previous version of this article stated that Valsorda "pinned the blame for the vulnerability on developers", however he has since denied this.

The developer behind a program that checks for the Heartbleed vulnerability, Filippo Valsorda, has created a new tool that he says tracks down poorly secured bitcoin transactions.

Insecure transactions can leak private keys, increasing the risk that a users' bitcoin could be stolen, and Valsorda's Blockchainr tool is designed to weed them out.

According to research by Valsorda, known flaws found in some implementations of the Elliptic Curve Digital Signature Algorithm (ECDSA), which provides cryptographic protection for bitcoin transactions, render certain wallets and transactions vulnerable to attack.

While the risk to funds held in wallets is very low, Valsorda claims that certain well-known bitcoin clients may be weaker than others due to the way random numbers are generated.

"I applied a known attack to the real world and showed how you could use ECDSA in a safe way that doesn't need random numbers so that it would not fail scanning the block chain," Valsorda told Vulture South at The Register.

His research findings were presented at the Hack In The Box 2014 event in Malaysia yesterday.

Valsorda argues that, if poorly implemented, the ECDSA can result in weak signatures lacking randomness. If an attacker can find such transactions in the block chain, the weakness can be exploited to reveal the private keys involved in the transaction.

A poor random number generator (RNG) can create the same 'random' number ('k' in the formula above) on more than one occasion. When the transaction is hashed, this number is multiplied by the same generator point (ie: same random number) as the public key.

Since one unknown has been removed from the equation, the private key can be revealed by effectively reversing the hash through additional mathematical operations.

The chance of even a bad RNG producing an identical number twice is very low, but it still poses a small risk.

While researching the vulnerability, Valsorda believes, he found evidence of bitcoin thefts exploiting the vulnerability dating back to 2013.

According to The Register, Valsorda said he identified one attacker who stole 59 BTC in August 2013.

He added:

Valsorda has designed his Blockchainr tool to scan the block chain for vulnerable transactions.

While some might fear such information could be misused, Valsorda did not manage to find any wallets that could be raided. However, he said, this may be because they have been raided already.

In addition to testing old transactions, Valsorda also examined the ECDSA implementation in a number of popular wallets.

He claims that some providers like Electrun, MultiBit/Bitcoinj, Bitrated/Bitcoinjs-lib and Trezor used a safer, deterministic model of signature generation. Bitcoin Core, Blockchain and Armory were found to be less safe.

The use of an RNG within the browser was, in some cases, linked to reduced transaction safety. The chance of duplicate signature generation even on those wallets deemed less safe is still less than 1%, said Valsorda.

Not everyone agrees with the conclusions, however. Armory's CEO and founder Alan C Reiner told CoinDesk:

"The fact that people are moving to 'deterministic signing' is really an enhancement, to protect against weak random number generators," he said. "But Armory doesn't run on any platforms with weak RNGs, so our 'unsafe' rating should be 0%."

Reiner further said that Armory follows the NIST-approved specification for ECDSA, which has been in place for 10 years, "the same way it is used in other secure systems throughout the Internet".

CoinDesk also spoke to Blockchain about Valsorda's claims. A spokesperson said:

"This issue first came to our engineering team’s attention in August 2013. We took steps then to patch the vulnerability created by a small minority of users relying on old out-of-date web browser versions.

Blockchain's My-Wallet tool relies on, not one, but three sources of entropy to generate ECDSA signing keys: the browser-based RNG, mouse movement & keyboard interaction, and a server-side RNG. This protects users from out-of-date browsers with weak RNGs while maintaining the ability run a fully client-side, non-custodial wallet that is easy to use across your desktop and mobile devices."

Blockchain, the firm said, remains vigilant about potential security issues and continues to actively monitor potential threat vectors generated by common software such as web browsers.

Blockchain encouraged all users to make sure they are running the most up to date software to ensure better security.

Valsorda has made his code freely available to other developers by posting it on GitHub and has called on fellow developers to address the issue, taking care in their choice of random number generators.