Introduction
In this blog post, we tell a tale of how we discovered a novel attack against ECDSA and how we applied it to datasets we found in the wild, including the Bitcoin and Ethereum networks. Although we didn’t recover Satoshi’s private key (we’d be throwing a party instead of writing this blog post), we could see evidence that someone had previously attacked vulnerable wallets with a different exploit and drained them. We cover our journey, findings, and the rabbit holes we explored. We also provide an academic paper with the details of the attack and open-source code implementing it, so people building software and products using ECDSA can ensure they do not have this vulnerability in their systems.
The Novel Attack
Part of the Kudelski Security Research Team’s activities includes looking into new vulnerabilities and exploits. A few months ago, while researching ECDSA nonce attacks, a member of our team discovered a more general way to exploit complex relations between nonces to retrieve the signing key. A review of existing literature seemed to confirm that this was indeed a novel insight, so we started digging into it. If you are interested in the math and details surrounding the attack, here is a link to the paper.
In a nutshell, the attack looks at the fact that you can always define a recurrence relation among nonces used in different ECDSA signatures as a polynomial of arbitrarily high degree, with unknown coefficients, modulo the order of the curve’s generator point. If you have a set of N ECDSA signatures (for the same private key) and this recurrence relation is of degree D, then (under some caveats we will talk about later) you can use the ECDSA signature equation to re-write the polynomial in terms of the private key and the recurrence unknown coefficients. We have found that the unknown coefficients can be eliminated from the polynomial, which always has the signer’s private key among its roots. So, if D is low and you have enough such correlated signatures (N ≥ D+3), then you can perform a key recovery attack by simply finding roots of a polynomial with known coefficients over a finite field, which is an easy task on a computer! To run the attack in practice, the following is required: A minimum of 4 signatures generated by the same private key, the associated public key, and the message hash associated with each signature. If the nonces obey the recurrence relation, we retrieve the private key used to generate the vulnerable signatures. The more signatures are used in the attack, the slower it gets, but the more likely it is to succeed: If you attack N signatures and their N nonces follow a recurrence relation of degree at most N-3, then you can perform a key recovery attack on ECDSA!
We tested the attack on a specially crafted set of signatures to verify that it works. You can find the proof-of-concept code here.
How Bad Is It?
In simpler words, what our attack means is that every time an ECDSA signature is generated, the signature itself gives us a relation between the nonce and the private key. If the nonces are truly randomly generated, this should never be a problem because the chance that a number of nonces picked at random fit on a low-degree polynomial recurrence relation is negligibly small.
But there is a catch: nonces are usually output by a pseudorandom number generator (PRNG) rather than being really random, and PRNGs are deterministic algorithms with relatively low complexity. In the best scenario, the PRNG used is complex enough and cryptographically secure, meaning (among other things) that any polynomial correlation between its outputs will have such an astronomically large degree that you can safely consider it indistinguishable from truly random. But weak PRNGs are basically everywhere. Take, for example, the simple case of a linear congruential generator (LCG), which is the typical textbook introduction to PRNG implementations. LCGs are to PRNG what ROT13 is to encryption and “1234” is to secure passwords. Despite that, due to their simplicity and popularity, they are the default choice for many non-critically secure applications, and it is totally possible that a “placeholder” LCG implementation slips into production code without being replaced by a more secure one.
Even more worryingly, let’s look at the recent criticism on the NIST SP 800-22 document. This publication contains in Appendix D a list of “reference random number generators” that are clearly not adequate for cryptographic purposes, including LCGs and other more or less weak generators that rely on simple quadratic or cubic recurrences and which could be affected by our attack if defined modulo the curve’s generator point order. To exploit this weakness for our attack, though, we need to have a batch of ECDSA signatures that are consecutive (meaning that the nonces are consecutive outputs from the same PRNG) and ordered (meaning that you know the order in which these signatures have been generated).
SP 800-22 also includes a list of tests that clearly fail to detect simple biases that can be demonstrated by relatively easy cryptanalysis. Because of this, NIST decided to revise this publication, but how many implementations still follow the old guidelines? And, even if the guidelines are revised, researchers have clearly shown that past and present usage of PRNGs in the wild doesn’t often follow best practices; examples include RSA keys with common factors, non-uniformly generated prime numbers and keys, small-value nonces and keys used for ECDSA in signing Bitcoin transactions, nonces with common prefixes, and others. So, summing up, we think it is reasonable to expect that our attack may affect certain implementations, but for the attack to work, we need consecutive and ordered ECDSA signatures. Where can we find a lot of these?
Bitcoin!
The Bitcoin blockchain is basically a large, public mine of ECDSA signatures. In fact, ECDSA has been used as the default signature algorithm since Bitcoin’s creation in 2009. We know that, in principle, most ECDSA signatures in the Bitcoin network are ephemeral, in the sense that the generating secret key is only used once, but we also know that this practice is not always in place, especially for the older transactions, and also Bitcoin has the advantage that the blocks follow a temporal history, which puts a certain degree of order on the signature generation time (only approximately, because there is no way to determine the order in which signatures in the same block were generated, since the timestamp is only recorded for a block, not for each signature).
The problem is that these are mainly our speculations, and we have no clue how accurate all these speculations are. So, it’s time to verify.
We downloaded and installed Bitcoin Core, the official Bitcoin client, and let it synchronize the whole chain. The sync process took about a day on a fast fiber connection, and the total blockchain size was about 430 GB, up to block 752’759 on September 5, 2022. We forked rusty-blockparser and added code to dump the ECDSA signatures and original messages that were signed for all the P2PKH transactions. There are other types of Bitcoin transactions, such as P2WPKH, but for the sake of simplicity, we only focused on these. One difficulty in dumping the required data is computing the correct original message that was signed. This message is never included in the transaction itself. Bitcoin clients are expected to re-compute the message based on bits of information stored in the chain. To be even more precise, each input in a transaction is signed, so there may be multiple signatures per transaction. To build this message, one must use information from previous transactions. To ensure we were building the message correctly, we verified all the signatures using the message we built as we were about to dump them. If a signature didn’t verify successfully, we would immediately know that something was wrong. Our source code, which builds the correct original message, is available here.
Another reason why this task is non-trivial is the lack of proper documentation about building the right message. The Bitcoin wiki contains a page with a diagram. Upon clicking this diagram, a preview is shown with a comment underneath that mentions that the diagram contains two errors! Thanks to a detailed StackExchange answer and lots of trial and error, we obtained the right message, and the signatures would validate.
Correctly dumping all the signatures and original messages from the raw blockchain data took 24 hours. The resulting output file size was 271 GB and contained 763’020’390 unique signatures. This file contained, on each line, the following information: output_address, ECDSA signature R and S values, public key, transaction ID, original message, and block timestamp. We grouped the signatures by public key and then, within each group, sorted signatures by timestamp to have more chances of picking consecutive ones. At this point, we had a dataset ready to run the attack on. But first, here are some statistics about the dataset.
These signatures were produced by private keys associated with 424’549’744 unique public keys. Of those 424 million public keys, 390 million, or about 92%, produced only 1 signature. There were 34 million public keys with at least 2 signatures, 18 million with at least 3 signatures, 12 million with at least 4 signatures, 9.6 million with at least 5 signatures, and 7.8 million with at least 6 signatures. There was a considerable number of public keys with over 200k signatures. The public key associated with the most signatures had 3.4 million signatures. This is illustrated in the chart below. Note that the y-axis uses a logarithmic scale.
The attack is generic and can be run with at least N=4 signatures (linear case) but can also be run with more signatures, for example, 5 signatures for the quadratic case and 6 signatures for the cubic case, or even more signatures. The linear case will also detect repeated nonces but is more general because it can exploit any linear recurrence relation. However, we wanted to go even further and run the quadratic case (N=5) because we thought it might give more interesting results. We considered the cost/benefit ratio of performing cubic or higher attacks to not be worthwhile, so we stopped at the quadratic case, meaning batches of 5 signatures. Since we sometimes have more than 5 signatures associated with a given public key, we decided to perform a sliding window over the signatures sorted by timestamp and run the attack on each window of size N.
So, how did it go?
We ran the sliding window attack with N=5 on a 128-core VM, and it was completed in 2 days and 19 hours. The estimated cost of the attack was about 285 USD. We broke 762 unique wallets. All of these had a zero balance. Interestingly enough, we could break all these wallets, not because of a linear or quadratic recurrence but because there was at least one repeated nonce in the signatures. So, it looks like the common mishap of ECDSA implementations using a repeated nonce was the cause of trouble.
Since we only ran the attack using a window of size 5 so far, we may have missed a few vulnerable wallets that would only have been found for public keys that had exactly 4 signatures. So, we re-ran the attack with N=4 on only the signatures from wallets with exactly 4 signatures. We were able to break 11 new wallets with a zero balance and at least one repeated nonce, thus increasing the total amount of broken wallets to 773.
We suspect (and in some cases have evidence, as we will discuss later) that all these wallets have zero balance because they have already been hacked in the past due to the repeated nonce vulnerability. We also estimated the total theoretical amount of tokens that may have been stolen from these 773 wallets to be 484 BTC, a value of approximately 31 million USD at Bitcoin’s peak.
Compromised Bitcoin Wallets And 1idiot
One question we had was, where did the money go? Who stole the tokens? To answer this question, we obtained the list of the latest transactions performed by each broken wallet address. We went through those transactions in reverse chronological order. As soon as we found a transaction that was actually sending tokens out, we assumed this was the transaction that emptied the attacked wallet. We assumed that once a wallet was cracked and tokens were stolen from it, that victim didn’t use their wallet anymore after that. This may not be completely accurate, but we think it’s a reasonable assumption. One safeguard we accounted for was to discard any transaction that happened after September 5, 2022, since this was the time until which we dumped transactions from the chain, so our dataset was already that old.
Looking at the list of destination Bitcoin addresses of broken wallets, we saw a few addresses with human-readable words, likely Bitcoin vanity addresses. For example, one address started with “1idiot”. This immediately caught our attention. Here is an excerpt from the list of destination addresses sorted by the total amount of Bitcoin that was sent there from vulnerable wallets, and an approximate USD equivalent amount, using Bitcoin’s peak rate of 65’000 USD/BTC.
| Rank | Address/public key | BTC received | USD received |
|---|---|---|---|
| 1 | 1HSqyCH5mF6jbRc… | 75.00 | 4’875’000.00 |
| 2 | 1EDLS29FrUDBDUo… | 40.55 | 2’635’750.00 |
| 3 | 14o4Miuvfed3RTW… | 16.98 | 1’103’700.00 |
| 4 | 1Ht6dp7Kxn9htAc… | 4.61 | 299’650.00 |
| 5 | 1LC8y73rshNWupD… | 3.57 | 232’050.00 |
| 6 | 18y4Vc58sBoZMns… | 1.65 | 107’250.00 |
| 7 | 2103db3c3977c51… | 0.53 | 34’450.00 |
| 8 | 1FCpHq81nNLPkpp… | 0.24 | 15’600.00 |
| 9 | 1F1vpdhbxPrqAau… | 0.24 | 15’600.00 |
| 10 | 1GoK8AAGRcKBSk3… | 0.09 | 5’850.00 |
| 11 | 2103bec42e5d718… | 0.05 | 3’250.00 |
| 12 | 1idiott6U6jsgYg… | 0.04 | 2’600.00 |
| 13 | 1my451PNkeEGfz8… | 0.02 | 1’300.00 |
| 14 | 1CujFmDMm22pKGn… | 0.02 | 1’300.00 |
| 15 | 1Gk94K6oxfAET2J… | 0.02 | 1’300.00 |
| … | … | … | … |
| 464 | 3879zijnf1QpzVo… | 0.00 | 0.35 |
| 465 | 1MPUBTT2jjDqDsi… | 0.00 | 0.35 |
| 466 | bc1q8742wwqvxhf… | 0.00 | 0.21 |
We have identified 466 different addresses or public keys the tokens that were sent to. The top address apparently received as much as 75 BTC, while the less well-ranked addresses sometimes only received a few satoshis. In total, we counted that 144 BTC (or 9.4 million USD at the above USD/BTC rate) were stolen, which is less than the total theoretical amount of 484 BTC we mentioned earlier, which sounds reasonable to us.
In the above top 15, there are 2 non-address type destinations, the ones ranked 7th and 11th. These are public keys. This means the funds were not sent to an address but to a public key (P2PK transaction type). It’s a bit more challenging to find out where the funds went for this type of transaction because we would have to index the whole chain again and see if there was a transaction that reused that output as input later. The various public bitcoin blockchain explorers we have tried did not provide that information, or it did not appear to be reliable. We didn’t go any further with tracking these public keys.
In that same list, we noticed these addresses that appeared to be vanity addresses:
- Rank #12: 1idiott6U6jsgYg…
- Rank #31: 1eouxuruZ7Qz64Y…
- Rank #63: 1KgiftfVXuKffFZY…
- Rank #93: 1dust8J4MJjfn6F…
- Rank #157: 1HackfRHUGxpDAX…
Notice the appearance of words such as “idiot,” “gift,” “dust,” or “Hack” in these Bitcoin addresses. Since Bitcoin addresses are generally anonymous, unless someone can prove that they own a specific address, it is extremely difficult to determine who moved these funds without proper chain-analysis technology. Nevertheless, we investigated these addresses a bit deeper and gathered the following information.
1idiot
The address is involved in 26 transactions. Funds were sent to this address in 2017, which would seem to indicate that the money was stolen at that time. This address now has a zero balance and has sent all its funds to another vanity address called “1andreas” (1andreas3batLhQ…) on 2018-01-22. The 1andreas address has a balance of 0.036 BTC at the time of writing. Note that this address happens to be owned by Andreas Antonopoulos, who apparently received unsolicited donations of over 100 BTC in late 2017. This means that the unknown owner of the 1idiot wallet may have decided to donate the tokens they had collected from vulnerable wallets.
A total of 0.04 BTC was received by the 1idiot address from the vulnerable wallets we identified.
1eouxuru
The address is involved in 17 transactions. Funds were sent to this address in 2014. All funds were sent to the 1EDLS address, which is surprisingly ranked 2nd in the above table. The funds were then further sent to a long chain of addresses, which makes it difficult to track. We believe that this address may be involved with some cryptocurrency exchange’s address because it moved a lot of funds.
A total of 0.01 BTC was received by this address from the vulnerable wallets we identified.
1Kgift
The address is involved in only 2 transactions, which happened in 2015. It looks like the long chain of addresses formed when following this address leads to some cryptocurrency exchange (3BT57Z3DXs5Tbeaqe31EZLUbc4fDDrYGHm). This may suggest that the attacker cashed out at some point or sent the tokens further.
A total of 0.006 BTC was received by this address from the vulnerable wallets we identified.
1dust
This address is involved in a large number of transactions, 5872, to be precise. The latest transaction happened in 2015. Due to a large number of transactions, we didn’t investigate this further.
A total of 0.0039 BTC was received by this address from the vulnerable wallets we identified.
1Hack
The address is involved in 10 transactions. The first transactions happened in 2014. All funds were sent to the 1idiot address in 2017.
A total of 0.00028 BTC was received by this address from the vulnerable wallets we identified.
In addition to these vanity addresses, we also had a better look at the top 3 ranked addresses from the above table and gathered the following information.
Addresses with most received tokens from identified vulnerable wallets
The top address received 75 BTC in total. The first transaction happened in 2018. After that, some funds were regularly sent to various other addresses. Interestingly, the amount of each transaction was often 0.5 or 1 BTC. At the time of writing, this address still has a balance of 63.5 BTC, and the latest transaction happened on 2022-07-06. The addresses ranked 2nd and 3rd have received 40 BTC and 16 BTC, respectively. The address ranked 2nd appears to be linked to the 1eouxuru vanity address. Its latest transaction dates to 2014. The 3rd address’ latest transaction happened in 2015.
Public talk about these attacks
We found out that some people were openly talking about how they collected some funds from vulnerable addresses because of signatures with a repeated nonce on the bitcointalk.org forum. One example of that is this thread, where forum member “johoe” wrote on April 10, 2016, that, so far, he had collected about 7 BTC by performing a nonce reuse attack. In 2014, the same forum member participated in another thread about reused nonces. We didn’t track how many funds were openly reported to be moved using that technique on that public forum.
We wondered what the next data source to investigate would be and thought that the Ethereum blockchain would be the best candidate because of its size and popularity. That would be where we would have the greatest chances of finding vulnerable signatures in the wild.
Ethereum
Ethereum transactions are also signed with an ECDSA key. To obtain the transactions, we installed geth and lighthouse and let them synchronize. Indeed, since The Merge, it appears that two clients are necessary to obtain the whole chain: an execution client, such as geth, and a consensus client, such as lighthouse. We synchronized the chain from the genesis block up to block 15’844’545, on October 28, 2022, which is about a month after “The Merge”. The total size of the chain on disk was 1.6 TB and it took 21 days to synchronize. Also, about 120 GB of additional space was necessary for lighthouse.
We wrote a program in Python that queries our fully synchronized local geth node’s JSON-RPC API for data. We specifically use the “eth_getBlockByNumber” endpoint to obtain blocks by their number. In each block, we go through each transaction and dump the signatures and corresponding original message. The hardest part in implementing this was clearly to reconstruct the correct original message, which is not included in the transaction itself. Indeed, similarly to the Bitcoin case, Ethereum clients must recompute that message themselves to verify signatures.
In Ethereum, the format of a message to be signed changed over time, based on the number of a block. For example, in Ethereum version “Spurious Dragon” (blocks 2’675’000 to 4’369’999 included) the message is computed in a specific way. However, in Ethereum version “Berlin” (blocks 12’244’000 to 12’964’999 included), the message is computed in another way. Each version of the Ethereum protocol has its way to compute that message. Since the original message is required to verify a signature, we had to implement the construction of the message for all the 13 different Ethereum protocol versions that existed between block 0 and 15’844’545. The Ethereum yellow paper and the geth source code were of great help to build the right message for each Ethereum protocol version.
To make sure that we didn’t make any mistakes, we computed the message and checked that the signature in each transaction was valid according to that message for each transaction as we dumped the data. That way, we knew that our dataset was correct. The source code of our parser is available here.
Dumping all the signatures and messages from the start of the chain until October 28, 2022 (block 15’844’545) took 3 days and 4 hours. The output file size was 628 GB and contained 1’759’432’087 signatures. This file contained, on each line, the following information: source_address, ECDSA signature R and S values, public key, transaction ID, original message, and block time.
We grouped the signatures by public key and then, within each group, sorted the signatures by timestamp. Finally, we started running the quadratic sliding window attack (N=5) on this dataset. After about 48 hours, we had 5 successful attacks on 2 unique wallets. Both had repeated nonces, and both had a zero balance. At that point, we had processed about 22% of the input file. Since the number of successful attacks was so small and the cost of the attack was significant, we decided to stop the attack.
We couldn’t find any real-world case of recurrence nonces in the Ethereum dataset either, but we tried one more thing.
TLS
TLS is a widely used protocol to secure communications over the internet. For example, it is used in HTTPS. If a website has a TLS certificate that contains an ECDSA key, then a signature can be collected every time an initial TLS connection is established to that website.
We started by obtaining the Cisco Umbrella 1 Million domain names list. This list contains domain names ordered by the amount of traffic they receive. For the attack to work, we would need to obtain signatures that were sequentially generated using the same PRNG. To maximize the chances of this happening, we would need to be the only client establishing at least 4 TLS connections sequentially, and nobody else would need to make connections simultaneously. We thought that using domains near the bottom of that list would maximize these chances because of the lower traffic to these domains.
We wrote a program in Python that uses OpenSSL to perform a TLS handshake on each target. While the program ran, we captured the network traffic and saved it to a PCAP file. We wrote another Python program to read the PCAP file and extract the signatures and original messages. As expected, producing the correct message was a challenge. To validate that our attack was working correctly end-to-end, we set up a TLS server using a self-signed certificate for which we had previously generated the private key and used that server as a target. Then, since we had the private key, we were later able to sign the original message again but with a fixed nonce that we would reuse every time. Upon running the attack, we could successfully verify that the private key could be retrieved because of the nonce re-use. At the same time, we took the opportunity to verify the signature as we computed the message. Our code is available on Github here.
In late 2022, we ran 3 scans with different parameters. For the first scan, we used a sample of 1000 domains from some part of the list, made 10 consecutive TLS handshakes for each domain, and waited 0.2 seconds between each handshake in order not to be banned or temporarily blocked from these domains. For the second scan, we used a sample of 2000 domains from the list, performed 6 handshakes per target, and waited 0.3 seconds between each handshake. For the third and last scan, we used a sample of 10’000 domains from the list, performed 6 handshakes per target, and performed the handshakes as fast as possible.
As a result, we collected 467 unique signatures during the first scan, which took less than an hour to perform. The second scan lasted 1.5 hours, and we were able to collect 1083 unique signatures from that one. The third scan took less than a day and yielded 4505 unique signatures.
For each dataset, we sorted the signatures by public key, and then, within each group, by timestamp. Since the datasets were small, we ran the sliding window attack with N=4, 5 and 6 on a 4-core laptop. Each run was completed in a few seconds. We had zero successful attacks but only ran this on a very small sample of potential cases.
Conclusions
So, since we aren’t sipping Mojitos on a beach in some exotic location, you can tell we didn’t gain access to Satoshi’s wallet, but we recovered the private key of some Bitcoin wallets showing that the attack works. We only scratched the surface by looking at Bitcoin, Ethereum, and some TLS connections. With this initial look, we wanted to ensure that an attacker couldn’t cause financial damage before releasing the details. But there are many other locations where ECDSA is used, such as additional blockchains, batches of PGP signatures, other TLS connections, and embedded devices, just to name a few. We release this information along with code so that people and organizations can proactively ensure they are secure against these attacks and create more robust systems. We hope you find this useful.
The code for the attacks is available on Github here.
Special Thanks
Special thanks to my colleagues Marco Macchetti, for the original attack proof-of-concept and idea and Tommaso Gagliardoni for contributing to this blog post and fruitful discussions.
Kudelski Security Research 
