Three months have passed since discovering the explanation for the observed thefts and our intense sprint towards the initial publication of the Milk Sad vulnerability in the blockchain-explorer bx wallet software. By quickly publishing, we fulfilled our primary goal of telling the world about the issue - providing an explanation for affected victims, and hopefully sparing some future users from the same fate. The disclosure also raised the public profile of the weak Pseudorandom Number Generators (PRNGs) vulnerability class and underlined the catastrophic impacts it can have in the cryptocurrency world.
After the dust settled and things got back to normal, most of our team members have now turned their focus back to their day jobs and other projects.
Curiosity is a powerful motivation, though, and so a few members of the group keep digging into more details of the fallout of weak bx keys, similar vulnerabilities involving weak private keys, and related security research that interests us.
Going forward, we will make use of individual blogposts to share new details, discoveries, and other topics we see as notable.
Table of Contents
Summary of Weak BIP39 Private Keys for bx 3.x
In the original publication, we listed some aggregated statistics of the discovered Bitcoin wallet private keys in the BIP39 range associated with bx 3.x, the main CVE-2023-39910 impact, that we had found at the time.
Our updated current statistics on discovered wallets and path usage are as follows:
| BIP39 entropy bit length mnemonic length |
128 bit 12 words |
160 bit 15 words |
192 bit 18 words |
224 bit 21 words |
256 bit 24 words |
|---|---|---|---|---|---|
m/44'/0'/0'/0/0 path, compressed, P2PKH |
8 | 0 | 2 | 0 | 14 |
m/44'/0'/0'/0/0 path, uncompressed, P2PKH |
0 | - | 0 | - | 1 |
m/49'/0'/0'/0/0 path |
1 | 0 | 1 | 0 | 2634 |
m/84'/0'/0'/0/0 path |
0 | 0 | 1 | 0 | 9 |
| sum of unique wallet private keys | 9 | 0 | 4 | 0 | 2655 |
In the 256 bit range, there are two wallets which used multiple paths. Ranges marked with - were not tested.
The total number of known weak BIP39 private keys with Bitcoin Mainnet usage (on the analyzed paths and address formats) in this range is therefore 2668.
Additional notes:
- Our search doesn’t detect wallets used exclusively with an additional BIP39 user passphrase, non-standard path use or multisig wallets.
- We scanned the 15 word (160 bit) and 21 word (224 bit) BIP39 seed ranges, but found them empty, at least on the common paths. While
bx mnemonic-newcan create those variants of the BIP39 standard, they are not so common. This result is therefore plausible to us. - In the original writeup, we outlined that many of the
3-prefix BIP49 wallets in the 256 bit range likely belong to the same entity. One of the earliest transactions for this seems to be 3931b570..4f501910 on 2018-10-03, and many similar transfers to weak wallets in this range happen within the next few days, some with identical transaction amounts.
Breaking Weak bx 3.x ec-new Private Keys
During the initial research sprint towards understanding and reproducing the bx PRNG weakness, we focused on code paths and usage variants that run weak bx seed entropy through bx mnemonic-new to generate BIP39 mnemonics. BIP39 is the de facto standard for interoperability with other hardware and software wallets for many years now, and was the mechanism used by the affected wallet owners who kicked off our research, which is why we saw this as the most relevant and important variant.
After the public disclosure, we continued our search into another mechanism that bx has for wallet generation: the bx ec-new mode (documentation).
Unlike bx mnemonic-new, this is more of a legacy mode and somewhat limited in flexibility. Under the hood, it is based on BIP32, but not BIP39. Despite following the well-defined “hierarchical deterministic” wallet scheme of BIP32, the ec-new logic is hardcoded to only use the topmost derivation path (m/) in combination with the older P2PKH address format (1-prefix addresses, BIP44).
It took us a bit of time to figure out the details from the bx source code, particularly due to the unexpected path usage. Once we knew what we were looking for, the actual wallet private key searches progressed multiple times faster than for the BIP39 variants 😎.
The core reasons for this are:
- No need to compute the 2048 rounds of PBKDF2-HMAC with SHA512 that BIP39 requires.
- Use of a single derivation path for the receive address derivation, which doesn’t need separate receive address searches.
- Cheaper address path derivation calculations, since the path is short and doesn’t traverse through multiple sub-keys.
To put this into perspective, brute-forcing and checking all possible Bitcoin private keys of a particular bx seed | bx ec-new input length range for 2^32 wallet candidates requires only about 70 minutes of wall-time on a modern Ryzen 7950X3D desktop processor according to our experiments, without the need for GPUs or other accelerators. In other words, this is a very practical attack!
We found the following new Bitcoin wallets:
| entropy bit length | 128 bit | 192 bit | 256 bit | 512 bit |
|---|---|---|---|---|
number of wallets, m/ path, compressed, P2PKH |
2 | 54 | 12 | 1 |
number of wallets, m/ path, uncompressed, P2PKH |
0 | 12 | 0 | 0 |
Overall, we discovered 81 such new wallets in total.
Additionally, we did not find any wallets in the following bit length range variations: 64 bit, 160 bit, 224 bit, 384 bit, 768 bit, 1024 bit, 2048 bit, 3072 bit, 8192 bit while searching for compressed public key P2PKH wallets on the base path.
A noteworthy detail here is the apparent trend towards 192 bit wallets, which is the default bit length of bx seed. It appears that users of bx ec-new had less reason or motivation to override the default settings, which is different from the BIP39 keys where 24-word (256 bit) and 12-word (128 bit) mnemonics were more popular. One possible explanation is that users were less concerned with compatibility of the generated private key by other software, since it’s not widely used elsewhere.
Some relevant facts about the discovered wallets from ec-new:
- Earliest use on 2016-12-15, likely with a pre-release version of
bx3.0.0. All other usages are after the official release date. - Overall, a total cumulative volume of 112.86 BTC has moved across the weak wallets of this type (estimate based on known address history).
- The last large outgoing transaction from this set of wallets is 3a5b1c78..f54fe376 with 1.13 BTC, which happened on 2023-03-31 18:58. It is unclear to us if this is theft or a legitimate movement.
- The attacker behind the 2023-07-12 main theft found and used at least one of these private keys, as proven by stealing from 1JUdUgFm7B9GZihtf4jtryCmt4YcRMaJGx via one of the three main theft transactions. The stolen amount was small: 0.0015 BTC, less than $50 at the time.
- In August 2023, several small outgoing transactions moved other remaining funds, which individually were worth a few dollars. We think these were intentionally skipped by the main attacker due to the their low value considering the transfer fee overhead, and are now slowly swept by other opportunistic thieves. The primary destination address for this is bc1q0yxd9avwy2wnj7lpj35v5d5n5ejfn79mk37xgd.
To summarize, the bx ec-new type of wallets generated with the weak bx seed PRNG were indeed used over multiple years and held sizeable funds. Based on our current understanding, the wallet owners were lucky enough that the PRNG issue was not exploited until some point 2023. Only one minor loss from this range can clearly be attributed to the 2023-07-12 thief.
2023-07-12 On-Chain Theft - Ethereum Addresses
In our initial analysis, we listed several Bitcoin transactions that transferred money away from bx wallets with weak private keys.
On Ethereum, we regard 0xaa8b55e2..854e9125 as the main address used by the primary thief to steal coins and related assets in the Ethereum ecosystem from weak bx wallets. The vast majority of these transactions also happened on 2023-07-12 within hours of the Bitcoin theft transactions, strongly suggesting this Ethereum account was used by the same person or group.
According to a Reddit post, at least one apparent victim used a weak Trust Wallet private key, and not a weak bx private key. We have not confirmed this ourselves yet, but it sounds very plausible to us given the overall timeline and similarity between the Trust Wallet and bx PRNG implementation issues that the attacker stole from a pool of Trust Wallet- and bx users, plus potentially other weak wallets they were tracking.
Observations:
- The funds collected and forwarded by this address within a week of the time of the main theft exceeds 1350 ETH, plus many additional ERC20 assets which are valuable on their own.
- Unlike the Bitcoin theft destination addresses,
0xaa8b55e2..854e9125account stayed active for several days in July 2023. - The account has some brief activity again in August 2023.
Counting just the identified amount of Ethereum that went through this account, this adds over $2.5M USD to the overall theft volume (@ $1,868.50 USD / 1 ETH on 2023-07-12), if all of was gained by illegitimate means. We’ll go further into this in a future blog post.
Milk Sad Lookup Server - End of Service
We’re shutting down the lookup service for weak BIP39 mnemonics. Despite the challenges involved, it was important to us to give potentially affected wallet owners a way to verify if they are using a known weak wallet, and the lookup service filled that gap.
Internally, we intended this to be a time-limited service from the start, and now the moment has come to spin it down. We hope the service has been useful for some of you.
New Git Repositories
We’ve published some of the underlying source code and configuration behind the lookup server here. This does not allow a direct 1:1 replication of the service since the underlying search data isn’t included, but could still be useful as a reference. It also includes the Rust source code for generating a fast bloom filter and searching entries against it, which we’ve used in a similar role for the main research as well.
The source code and content for this milksad.info website you’re reading is now also available in a public repository. If you’re interested in how the Jekyll static website generation is configured and which changes we’re making to the published content over time, go check it out!
Outlook
Our research has led us deeper into the Mersenne-Twister rabbit hole, and we have new results to share about weak Trust Wallet private keys, and more. We’ve now got a new RSS feed for updates, if you don’t want to miss the next post.
Stay tuned!
Page updates
This post was updated with newer statistics.