Researchers at Kudelski Security have managed to break Bitcoin and Ethereum wallets using a novel attack against one of the most popular asymmetric key algorithms of modern cryptography. Although Satoshi Nakamoto’s wallet was not among the 764 wallets they were able to break, it is quite worrying to see that a software issue can make such a modern cryptographic algorithm like ECDSA vulnerable. Analysis of data that comes purely from open sources could reveal a practical weakness of an algorithm that is the fundamental basis of secure internet communication, public key infrastructures, and cryptocurrency transactions.
Software Issue Behind the Scenes
As with many other times in the history of attacks against cryptographic algorithms, the cause of a successful attack is not a vulnerability in the algorithm itself, but the fact that poor-quality software used an algorithm with insufficient care. It is crucial to obtain “high-quality” random numbers during the calculation of many cryptographic operations. Such operations store passwords using salted hashes, the generation of cryptographic keys used to authenticate web servers on the internet, or an employee before access is given to the company’s private network using a virtual private network (VPN) service. The generation of digital signatures – which is necessary for the verification of the transactions – also requires a cryptographically strong random value. In the absence of strong random values, there would be a relation between the random and the private part of the signing key. This property could be exploited, and the private key can be acquired by an attacker. In the possession of the private key, any transaction related to the key can be verified, meaning that the balance of the wallet can be transferred.
Not a New Idea, but a New Method
Though the attack itself is novel, the idea behind the attack is not so new. The lack of high-quality random numbers has caused serious vulnerabilities in the past. In 2002, a researcher found an issue in the version of the OpenSSL distributed with Debian Linux and its derivatives that reduced the entropy of generated random values. The issue caused SSH, VPN, and X.509 keys generated by the affected versions of OpenSSL to become vulnerable. Services still used a key generated by the affected version of the code which meant they remained vulnerable until the regeneration of the key. In 2010, a group called _fail0verflow _compromised an ECDSA key Sony used to sign software for the PlayStation 3 game console. The root cause of the attack was almost the same as it is now, namely Sony did not use different random numbers when digitally signing different software. The novelty of the current attack is that it exploits the high-degree relationships among the random values (nonces) used to generate digital signatures. It means if the nonce was not generated by a cryptographically secure random number generator but using a weak pseudo-random number generator (PRNG), it would allow the attacker to retrieve the private part of the key used to generate the signatures.
Special Kind of Open-source Intelligence
Three prerequisites must be met to successfully retrieve the signer’s private key from signatures. The first one is that the random value used to generate the signature should come from a weak PRNG. The second one is to have a batch of consecutive digital signatures generated by using the same PRNG. The third one is that the signatures can be ordered, meaning that we know which signatures have been generated after which one. It could be assumed that there are implementations that use weak PRNGs as it is not basic knowledge whether random number generators are adequate for cryptographic purposes and some legacy software may follow older guidelines. The question is: where can an attacker find a consecutive and ordered list of signatures? The answer is: in several places. Digital signatures are part of each cryptographic protocol, so they can be collected from open sources. The best examples are cryptocurrencies, where the transfers are validated by digital signatures. These digital signatures must be published to allow each party to validate the transactions. Basically, cryptocurrency blockchains are huge collections of the necessary signatures. For instance, researchers could collect 763 million unique signatures from the Bitcoin blockchain which were generated by 424 million unique public keys. Most of the time a key was used to generate only a few signatures, but millions of keys generated at least four signatures, which is the minimum requirement of the attack.
Someone Got Ahead of the Researchers
Researchers ran their attack for two days and 19 hours with an estimated cost of USD 265, resulting in 762 unique broken wallets, but someone may have gotten ahead of them, as all the wallets had zero balance. The researchers suspect that these wallets have already been hacked in the past. If they had not been hacked, 484 BTC could have been stolen from these wallets, which means almost 12 million USD. However, 484 BTC was worth 31 million USD at Bitcoin’s peak. The question arises, where did the money go? The researchers obtained that the recipients were addressed by the latest transactions of the broken wallets. They identified 466 different recipient addresses, where the top 1 received 75 BTC, and the top 5 received 140 BTC, meaning more than USD 1.5 million, and almost USD 3 million, respectively. They counted 144 BTC in total, which is far from the theoretical 484 BTC, but it still sounds like a profitable business, worth the aforementioned USD 265 cost of the investigation. After the first transaction to the top address in 2018, several transactions were initiated from that address to several recipients for 0.5 or 1 BTC, although the account still had a balance of 63.5 BTC. Researchers also found public conversations about accounts that were swept exploiting repeated nonces. A forum member called johoe claimed that he had collected 135 addresses that can be compromised using that technique, and 82 had been compromised already at the time of his post. He also stated that he collected 7 BTC from the broken accounts. He was willing to send the funds back to the owner after proving ownership. The researchers repeated their attack against Ethereum after collecting more than 1.7 billion ECDSA signatures. They managed to break 2 unique wallets processing 22% of their signature collection. They decided to stop the attack, considering that the cost-benefit ratio was too low.
Is This Still a Real Issue Now?
Considering only the results related to the Bitcoin wallets, I would say this might not be an issue anymore. The exploitable signatures were generated several years ago, perhaps with the same software that had a serious flaw, which may have already been fixed. The signatures were exploitable not because they used a pseudo-random generator during signature generation, but due to repeated nonce values. At the same time, given that digital signatures are used in so many cases, such as during a cryptographic handshake, this may still be a significant issue. Exploiting the vulnerability indeed requires getting consecutive signatures from a potentially affected server, which is not a trivial problem in the case of a busy server, as many other clients connect to a server between our consecutive connections. Even so, if an attacker manages to exploit a server, the server certificate is compromised without any sign on the server. For as much as the certificate revocation is one of the weakest points of X.509, it is troubling that such a simple flow in an implementation can cause certificate compromise. The case would be even more worrying if there were a similar flow in certificate issuance, as this would compromise a CA, which could result in unpredictable consequences.
Originally published at https://www.balasys.eu.
Licensed under a Creative Commons Attribution-ShareAlike 4.0 International (CC-BY-SA 4.0) License.
Photo by Jievani Weerasinghe on Unsplash
Top comments (0)