CVE-2023-39910: Milk Sad: /full write-up

Technical write-up

This is the story of a wallet theft enabled by bad cryptography. It covers our research on problems with Libbitcoin Explorer 3.x (CVE-2023-39910), outlines how it is related to the Trust Wallet vulnerability (CVE-2023-31290), and shows some of the real-world impact that we were able to confirm. Additionally, it has some early research on problems with bx 2.x that we became aware of late in the disclosure process. If you’re looking for a less-technical summary, head over to the summary page and the FAQs.

Table of Contents

• Part I - Tracing the Issue to the Source
  • Dude, Where’s my Cryptocurrency?
  • Dude, Where’s my Friend’s Cryptocurrency?
  • Our Cryptocurrency is Gone, But How!?!?
• Part II - Context and Impact
  • Codename “Milk Sad”
  • Not the First Hack: Weak entropy in Cake Wallet
  • Not even the second Hack: Mersenne Twister use in Trust Wallet
  • Ongoing On-Chain Thefts - Some Facts
  • Searching for Wallets - Motivation and Limits
  • Searching for Wallets - Implementation
  • Other Confirmed Victims of this Theft
  • Basic Timeline of Thefts and Our Disclosure
  • Libbitcoin Team Response and Context
  • Suspected RNG Problems in Older bx Versions
• Part III - Summary and Outlook
  • Basic Lessons Learned
  • Summary
  • Future Work
  • Additional References
  • Commercial Work
  • Other Notes
• Credits

Part I - Tracing the Issue to the Source

Please note that throughout this article, minor details relating to the victims have been omitted or changed.

Dude, Where’s my Cryptocurrency?

Our story starts on Friday, 21 July 2023. Upon attempting to use a well-protected cryptocurrency wallet, the wallet owner realizes that all of their funds stored in their wallet are gone. This was no accident – they were the victim of a sophisticated theft. The funds were sent to the attacker’s addresses on July 12th, at a time when the hardware wallet wasn’t in use for several days. (Details below)

The generation and use of the affected wallet was unusually strict:

• Generated on an air-gapped Linux laptop with self-compiled software
• Use of BIP39 24 mnemonic word phrase
• Mnemonic securely entered into Ledger & Trezor hardware wallets
• Good PIN and physical security on the hardware wallets
• Mnemonic seed phrase never touched a non-air-gapped computer
• Mnemonic seed backup well-protected

Dude, Where’s my Friend’s Cryptocurrency?

The victim reached out to their network of friends with similar key generation and management protocols, and a second victim was identified! The second victim also had the contents of their cryptocurrency wallet stolen during the same period of time – both victims Bitcoin (BTC) was stolen in the same minute on-chain. The victims realized this was no accident. They had fallen victim to a some type of hack.

The victims discovered their Bitcoin (BTC) holdings were not the only things stolen. The attackers had also taken Ethereum and other distinct cryptocurrency types from the same wallets. The victims realized this could only happen with an underlying leak of their main wallet private keys. Tricking their hardware wallets into authorizing incorrect transfers or breaking individual private keys of sub-accounts would manifest with a more limited impact.

A theft like this affecting two people at once despite their thorough precautions should be very unlikely. Even worse, the two victims weren’t the only ones affected by this. The publicly visible Bitcoin transactions of the theft pull in funds from what looks like many different wallets, possibly by up to a thousand different wallet owners on Bitcoin alone.

So, what in the world is going on!? Had someone found a remotely exploitable hardware wallet vulnerability, used it on a wide scale, and waited for months before executing the on-chain sweeping transactions collectively? Even worse, could one of the underlying cryptographic primitives be broken? Could Quantum Computer magic be involved? 😱

Tensions were running high - thus began the search for the source of compromise.

Our Cryptocurrency is Gone, But How!?!?

After coordination and communication, the two victims realized that their affected wallets were generated on a similar airgap laptop setup – although the individual victims’ wallets were generated several years apart. At that point, the issue seemed hard to pin down and could have originated from many sources. Our victims decided to start at the beginning – their wallet generation steps, from the first commands used and working their way up from there.

An essential tool that was involved in the wallet creation in both cases was the Libbitcoin Explorer in a 3.x version, via its bx binary. The Libbitcoin project has been around for a very long time (2011 !), is Open Source, and bx brings everything needed for an offline wallet generation in one self-contained binary.

Despite being a specialized tool that most wallet users won’t have heard of, bx has some popularity and is dedicated an appendix section in the “Mastering Bitcoin” book. In other words, it appeared to be a reasonable tool to use.

Brief example of the wallet generation workflow used in a Linux shell:

# generate 256 bits of entropy, turn it into BIP39 mnemonics
bx seed -b 256 | bx mnemonic-new
<output of secret BIP39 mnemonic words>

The above command produces a 24 word BIP39 mnemonic phrase comparable to those of the victims’ wallet. This private key is the foundation of all wallet related security.

Could the bx binary command the victims used have something to do with the problem? The victims ensured that their /dev/random Random Number Generator (RNG) subsystem of the Linux laptops had sufficient entropy, but perhaps that wasn’t sufficient after all …? Was there a major system configuration issue or virus?

At this point in time, a handful of friends with Information Security backgrounds were called in to help review the situation and the relevant wallet generation code paths 🕵️‍♂️.

As more eyes settle on the situation, the first signs of a major problem emerge.

Given Enough Eyes, All Bugs are Shallow?

The team decided that source code review of bx of the bx seed command is the logical place to start looking.

Running bx seed calls the new_seed(size_t bit_length) function in libbitcoin-explorer src/utility.cpp, which calls a pseudo_random_fill(data_chunk& out) function in the libbitcoin-system library:

console_result seed::invoke(std::ostream& output, std::ostream& error)
{
    const auto bit_length = get_bit_length_option();

    // These are soft requirements for security and rationality.
    // We use bit vs. byte length input as the more familiar convention.
    if (bit_length < minimum_seed_size * byte_bits ||
        bit_length % byte_bits != 0)
    {
        error << BX_SEED_BIT_LENGTH_UNSUPPORTED << std::endl;
        return console_result::failure;
    }

    const auto seed = new_seed(bit_length);
    ...
}


data_chunk new_seed(size_t bit_length)
{
    size_t fill_seed_size = bit_length / byte_bits;
    data_chunk seed(fill_seed_size);
    pseudo_random_fill(seed);
    return seed;
}

Only pseudo-random? Alright, a pseudo-random number generator (PRNG) doesn’t have to be bad if it’s a Cryptographically Secure Pseudo Random Number Generator (CSPRNG). Perhaps everything is fine, but let’s take a closer look.

We follow the call path: pseudo_random::fill(data_chunk& out) -> pseudo_random::next() -> pseudo_random::next(uint8_t begin, uint8_t end) -> std::mt19937& pseudo_random::get_twister()

Wait a moment. mt19937, twister - this uses the Mersenne Twister PRNG? 🤔 At this point, the first alarm bells are going off. Mersenne Twister is not a CSPRNG, so it shouldn’t be in any code path that generates secrets. One alarming property of the Mersenne Twister is that its internal state can be reversed by an attacker who knows a few hundred outputs, endangering the secrecy of the other outputs of the same stream that the attacker doesn’t know (in simplified terms).

However, if the PRNG is re-seeded before every wallet generation, only one output is fetched, and the single result is kept secret, would the weak construction of MT19937 be fatal enough for a remote theft if everything else is done well?

The search within this the pseudo_random.cpp code file continues, and we don’t have to go much further into the pseudo_random::get_twister() details to learn the actual problem.

// Use the clock for seeding.
const auto get_clock_seed = []() NOEXCEPT
{
    const auto now = high_resolution_clock::now();
    return static_cast<uint32_t>(now.time_since_epoch().count());
};

// This is thread safe because the instance is thread static.
if (twister.get() == nullptr)
{
    // Seed with high resolution clock.
    twister.reset(new std::mt19937(get_clock_seed()));
}

What the hell !? A bad PRNG algorithm, seeded with only 32 bit of system time, used to generate long-lived wallet private keys that store cryptocurrency? 😧

The group of investigators had to perform a ‘double-take’ here – surely bx couldn’t use this to generate private keys.

The team investigating the compromise could not believe this to be the case, and setup a simple experiment to validate the hypothesis. Like all good experiments, environmental variables were under the control of the experimenters, in this case – it was the variable time itself that was most relevant in studying the issue at hand. Using the official bx version 3.2.0 release binary in combination with the libfaketime library to test our theory, and run separate executions under exactly identical clock conditions:

$ wget https://github.com/libbitcoin/libbitcoin-explorer/releases/download/v3.2.0/bx-linux-x64-qrcode -O ~/.local/bin/bx
$ chmod +x ~/.local/bin/bx
$ sudo apt install libfaketime
$ export LD_PRELOAD=/usr/lib/x86_64-linux-gnu/faketime/libfaketime.so.1 FAKETIME_FMT=%s FAKETIME=0

$ bx seed -b 256 | bx mnemonic-new
milk sad wage cup reward umbrella raven visa give list decorate bulb gold raise twenty fly manual stand float super gentle climb fold park

$ bx seed -b 256 | bx mnemonic-new
milk sad wage cup reward umbrella raven visa give list decorate bulb gold raise twenty fly manual stand float super gentle climb fold park

💥 Same time - same “random” wallet! Unbelievable.

A secure and reliable utility would not derive the same mnemonic seed phrase under these circumstances. This was the first hard evidence that the bx seed secret generation code in an official release uses the broken time-based pseudorandom function for wallet entropy.

Digging deeper, the team confirmed that the code uses the standard MT19937 Mersenne Twister PRNG variant which only operates on 32 bits of initial seeding input by design, and not the MT19937-64 extended variant with 64 bits of seeding. So the PRNG can at most have 2^32 starting positions as an upper bound, regardless if it’s seeded by /dev/random or time.

To put this in different words: when running bx seed -b 256 to request 256 bits of non-guessable entropy, the result is 32 bits of high-precision clock time that was put through a blender (or rather: twister 🌪️) and expanded to 256 bit without adding new information. The number of possible key variations would grow exponentially with the size if this were real entropy data, so the difference from the safe expected result (256 bits) and the actual result (32 bits) is of astronomical proportions.

Anyone can re-compute and find a victim’s originally used entropy after a maximum of about 4.29 billion attempts if they have specific characteristics to look for to see if they successfully found a cryptocurrency wallet. In this case, by checking derived wallet addresses that were seen receiving funds on a public blockchain in the past. To put this number into perspective: brute-forcing this key space takes a few days of computation on the average gaming PC, at most. And unfortunately, anyone with sufficient programming skills could do it.

In terms of cryptocurrency wallet security, this is a pretty catastrophic situation.

Friday 21 July ends with a handful people who know that everything just got very complicated. Not only did some friends irrevocably lose complete control over their wallet private keys and funds - the ad-hoc group also has a serious disclosure problem on their hands.

Given that the theft was first identified in the US, early team members wanted to avoid failing to report a crime and get appropriate tax loss reporting for victims, and so an early disclosure of our findings to the FBI was made. We also saw this could be helpful in quickly limiting the fund movements of attackers on major exchanges, if that became necessary.

Part II - Context and Impact

For this section, we’ll switch to a non-chronological presentation for readability.

Codename “Milk Sad”

Faced with the unexpected task of handling an urgent disclosure, we were in need of a project name that was relevant yet told outsiders nothing about the technical issue. The suggestion was made to use the first two words of first BIP39 mnemonic secret generated by bx on time zero - milk sad wage cup reward […] -> Milk Sad. We found our project name.

Not the First Hack: Weak entropy in Cake Wallet

Very early in our evaluation of the possible flaws that could lead to an issue like this, one of our team members recalled a weak entropy situation in Cake Wallet.

While no CVE was filed for Cake Wallet as far as we can tell, in May 2021 the Cake wallet team announced a weak entropy vulnerability in their wallets requiring all users to rotate their mnemonic phrases.

Some further investigation into this situation by Reddit user Pure-Cricket7485 revealed the glaring flaws in Cake Wallet’s entropy sourcing strategy.

Notably: Cake Wallet Used Dart’s non-secure Random() to generate wallet seeds:

Uint8List randomBytes(int length, {bool secure = false}) {
  assert(length > 0);
  final random = secure ? Random.secure() : Random();
  final ret = Uint8List(length);
  for (var i = 0; i < length; i++) {
    ret[i] = random.nextInt(256);
  }
  return ret;
}

This can be a real problem considering Dart’s Random() can fall back to 0 or system time

Random::Random() {
  uint64_t seed = FLAG_random_seed;
  if (seed == 0) {
    Dart_EntropySource callback = Dart::entropy_source_callback();
    if (callback != nullptr) {
      if (!callback(reinterpret_cast<uint8_t*>(&seed), sizeof(seed))) {
        // Callback failed. Reset the seed to 0.
        seed = 0;
      }
    }
  }
  if (seed == 0) {
    // We did not get a seed so far. As a fallback we do use the current time.
    seed = OS::GetCurrentTimeMicros();
  }
  Initialize(seed);
}

One Reddit user compared this approach to Mersenne Twister, which got us considering if bx had a similar flaw.

Not even the second Hack: Mersenne Twister use in Trust Wallet

A few days into our disclosure process, we learned of the Trust Wallet vulnerability that Trust Wallet published in late April 2023. After reading Ledger Donjon’s excellent write-up on the discovery and research of CVE-2023-31290, we’re somewhat shocked: this is so close to the vulnerability in bx. And the Trust Wallet publication confirms that attacks on their user’s wallets go back as far as December 2022. Why did it take until mid-2023 for money to disappear from bx-generated wallets?

There’s a lot to unpack here, so let’s start with the vulnerability details.

The vulnerable Trust Wallet version and bx share the same basic, fatal flaw of generating wallet entropy from the unsuited MT19937 Mersenne Twister algorithm. bx additionally uses some clock information to seed MT19937, but this doesn’t make a big difference to practical offline brute-force attacks by remote attackers. It’s still the same limited 32 bits of key space that attackers can comb through completely.

From what we know, Trust Wallet only creates 12 word BIP39 mnemonic based wallets, which fixes the entropy requirements (and therefore PRNG usage) to 128 bit. bx more is flexible and generates 128 bit, 192 bit, 256 bit outputs (and others). More variations means more search space, but do the wallets generated with bx seed -b 128 overlap with the ones created by Trust wallet?

As it turns out, they do not - due to a nuance in the PRNG usage. The MT19937 Mersenne Twister algorithm used by Trust Wallet and bx is the same, but the output is consumed slightly differently.

When filling the entropy array with PRNG data, Trust Wallet consumes one MT19937 output of 32 bits, takes the least significant 8 bits of this output to fill the array, and throws away the other 24 bits via the & 0x000000ff bitwise-and in wasm/src/Random.cpp:

// Copyright © 2017-2022 Trust Wallet.
//

[...]

void random_buffer(uint8_t* buf, size_t len) {
    std::mt19937 rng(std::random_device{}());
    std::generate_n(buf, len, [&rng]() -> uint8_t { return rng() & 0x000000ff; });
    return;
}

Due to the C++ mechanisms used in libbitcoin-system for pseudo_random::fill(), its code performs the same 32 bits -> 8 bits truncation, but exactly the other way around - taking the 8 most-significant bits from the PRNG instead.

As a result, all generated bx seed outputs are - to our knowledge - in a completely different key space than what the Trust Wallet code would generate, which means the BIP39 mnemonics are also different.

To confirm this, here’s a quick experiment. The Ledger Donjon write-up contains a specific example wallet that they describe as follows:

[...]
RNG seed: 0x8ec170a8
Mnemonic:
sorry slush already pass garden decade grid drip machine cradle call put
[...]

If we re-compute RNG seed 0x8ec170a8 with the bx code for a 12 word BIP39 mnemonic, it comes out as the following instead:

local chef load churn future essence type leave program weird ancient owner

This confirms that the the wallet generation process is indeed different.

In Ledger Donjon’s write-up, they close with the following line, which reads a lot like foreshadowing to us:

During our investigations, we also noticed that a few addresses were vulnerable while they had been generated a long time before the Trust Wallet release. That probably means this vulnerability exists in some other wallet implementations which is concerning…

However, we suspect the other wallets seen by Ledger Donjon weren’t wallets generated by bx 3.x versions, unless Ledger Donjon experimented a lot with the PRNG outputs and hit this other usage pattern. The presence of more affected wallets in the 12-word Trust Wallet range suggests there are yet other affected wallet generation tools out there which use MT19937, though. Due to time constraints, we did not investigate this further for the time being.

When comparing our disclosure task on bx with that of Ledger on Trust Wallet, it’s notable that their disclosure was to a single, commercial, evidently well-funded wallet vendor. Based on their publications, Trust Wallet had direct communication paths to individual users that they could leverage to selectively inform them of vulnerabilities related to their wallet. Additionally, their wallet was only vulnerable for a limited amount of time, and the issue was discovered relatively quickly, with many users still regularly using the app.

In their post-mortem, the Trust Wallet team lists the total lost funds as $170,000 USD:

Despite our best efforts, two exploits occurred, resulting in a total loss of approximately $170,000 USD at the time of the attack.

As we understand, Trust Wallet decided to financially incentivize users to move their funds to safety, as well as reimbursing lost funds for users affected by the theft. Additionally, they paid a significant $100,000 USD bug bounty to Ledger Donjon for the coordinated disclosure.

In our case, unfortunately, most of these factors did not apply. Given the Libbitcoin project’s noncommercial nature, lack of direct communication channels to end users, multiple years of affected wallets and likely widely imported/exported keys and BIP39 mnemonics, the situation was much more difficult on the security researcher side.

With the Trust Wallet & Ledger Donjon write-ups out there, all bx seed private keys compromised, and active on-chain exploitation for bx wallets ongoing, it was clear to us that a long coordinated disclosure was not beneficial. If we wanted to give affected bx wallet owners the chance to recover their funds, we would have to aim for a publication in days, not months. In this situation, time is on the side of the attackers rather than the victims.

Well-established security programs like Google Project Zero have a similar policy for actively exploited vulnerabilities:

[…] if Project Zero finds evidence that a vulnerability is being actively exploited against real users “in the wild”, a 7-day disclosure policy replaces the 90-day policy. […]

Ongoing On-Chain Thefts - Some Facts

We decided to focus on Bitcoin as the main coin network for a limited analysis considering our time constraints. Due to the flexibility of bx seed output, funds on every BIP39 mnemonic (or even just BIP32 seed) compatible coin under the sun could be affected. With regular day jobs to take care of and limited time & compute resources, doing various steps 100x times wasn’t an option. This overview is therefore narrowly focused on Bitcoin, and only presents a partial view of the overall theft actions. Consider the presented figures a lower bound for the overall affected monetary value.

For Bitcoin, there are two main clusters of transactions that we think were malicious:

1.) The big 2023-07-12 theft:

date

transaction

destination address

moved value

note

2023-07-12 10:41

593e11588a2529ed…

3GMQRwh8Yz1WVftL…

~5.0538

14 inputs

2023-07-12 10:41

81cfe97cc16a4939…

3LwDzjA1xH8amCHu…

~9.744 BTC

> 300 inputs

2023-07-12 10:41

a22b33a9a4ca0de2…

3D2mKf28exn26v7B…

~14.847 BTC

> 1200 inputs

We attribute these to one well-prepared actor, who stole around ~29.65 BTC worth upwards of $850,000 USD in Bitcoin alone (8/2023 exchange rate). We think it’s likely this actor also carried out theft of other coins in the same day. At the time of writing, these funds have not moved away from their new location.

2.) There is a second, earlier pattern of fund movements that we suspect are also thefts:

This behavior started May 3rd 2023 and consisted of multiple smaller wallet sweeps which continued until July 15th. In total, we think this sweeping sums up to about 0.33 BTC. The funds have been moved again to further addresses, which differentiates this actor pattern from the first we outlined.

We have not seen any reports of stolen funds for these addresses. Theoretically, this special actor may be legitimately moving his funds from many distinct wallets (see further analysis) or he is a malicious actor. The addresses reported below are linked by being spent in the same transaction, which indicates that this a single actor or group.

Suspected Attacker Addresses:

• bc1qdmpx2th8h7l4j0z93sxnrlpuaxfvkkfxlv7n2c (0.1382 BTC)
• bc1qpnq4q7dcgvpuz8z9dy3d3jp4vuumw0hte4d32n (0.0700 BTC)
• bc1qf9q85mt73sr0vzlqkvy75pyal3g5w2ca7zx3cv (0.0045 BTC)
• bc1q5rcm7gcl3n50q93xcwwz5una7xy89unlqhy075 (0.1147 BTC)

Here’s a list with some known coins with confirmed thefts (before the publication of this disclosure):

• Bitcoin (BTC)
• Ethereum (ETH)
• Ripple (XRP)
• Dogecoin (DOGE)
• Solana (SOL)
• Litecoin (LTC)
• Bitcoin Cash (BCH)
• Zcash (ZEC)

There are likely many more coin types involved, as the additional cost to execute this attack on other coins for the affected wallets is limited to the R&D time required for identification and funds withdrawal. We hope that attackers have some increased risk of getting caught via coin-specific tracing of their identities and methods, but do not have anything to report there.

Overall, our estimation is that over $900,000 USD worth of cryptocurrency assets were moved as part of the overall theft actions (@exchange rate 8/2023), although some of the drained wallets may have been taken over via other vulnerabilities.

Searching for Wallets - Motivation and Limits

The primary reason for rapidly searching for affected Bitcoin wallets was to assess the overall damage in terms of magnitude of stolen & remaining funds, as well as to provide technical confirmation that the vulnerability was real and the sole explanation for the initially analyzed theft. We had some hope that if we came across any substantial remaining funds, there would be a small but non-zero chance to somehow inform the rightful owner so that they could save their funds. In the planning phase, we were considering options to relay a warning message to the wallet owner via a centralized cryptocurrency exchange used for direct deposits, finding wallet owners with publicly listed addresses, or discovering some other back channels. At the very least, we could extend the disclosure time scheduled in that case while searching for options.

Ultimately we did not identify any substantial remaining funds above a threshold of $5000 on the Bitcoin network in the analyzed ranges related to wallets generated with bx 3.x versions, as of the disclosure publication date. It’s plausible that larger sums of funds remain on similarly affected wallets of one sort of another, with slightly different derivation paths, but we did not find them with our analysis steps so far. It is also possible that some wallet owners use additional BIP39 passphrases, which provide moderate to strong protections depending on passphrase strength and other factors and make discovery much harder.

We want to be very clear on the scope of our research-related actions:

1. The two originally described victims managed to recover a small portion of their own wallet contents that had not yet been stolen, using their regular wallet setup they had before the theft.
2. We did not move any funds on any of the unknown victim wallets, on any coin.
3. We do not know or are in any way associated with the attacker(s) that stole the funds.

In summary, none of the group members moved any funds that they were not the legal owner of, or knows the identities of the thiefs.

As far as we’re aware, even under ideal hypothetical circumstances, moving other people’s funds to avoid theft by bad actors can become a legal nightmare. Even in the most ideal scenario – where there is a single victim, clear ownership proofs, well-established identities on both sides, single jurisdiction and reliable private communication options - this carries a lot of risk.

In our situation, the circumstances were substantially worse than the ideal case in most ways we could think of. Therefore, we saw any scenario that involved us moving anything of any value, which we didn’t own before the disclosure, as opening the floodgates of legal problems. (Remember that we’re not lawyers, and this is not legal advice; We’re also not finance folks, so this is also NOT financial advice)

For the adventurous reader, who would consider going ahead anyway as a “white knight” in this case, please consider the following dilemma: any attacker can recompute the owner’s private keys, which nullifies the value of any cryptographic signatures with those keys. In any scenario that involves moving a wallet owners’s funds away to a wallet you control, how do you know the person showing up in your inbox (or on your doorstep) asking to get back “their” funds is the legal owner? Particularly if there is no centralized entity, such as a big cryptocurrency exchange, that backs the claim and can provide circumstantial evidence?

That’s a tough situation! And this dilemma doesn’t even touch other problems such as complying with anti-money-laundering (AML) laws, tax declarations, and a host of other aspects.

In case you are one of the affected victims of the theft: no, we definitely do not have your funds or know of a way to get them back. We’re sorry.

If it’s any consolation, we’ve worked hard to give our affected friends and all other victims at least some explanation and closure on why any funds could be stolen in the first place, and help them to avoid getting burned again by the same vulnerability.

You may use the lookup service to check if your wallet was impacted.

Searching for Wallets - Implementation

Please note that we’re intentionally vague on some non-trivial technical details, since we need to make an ethical trade-off between sharing the technical details that are needed to shine a light on this problem, and giving bad actors an unnecessary technical advantage on day 1. Additionally, while we are big fans of Open Source, we will not release custom code we wrote for parts of the on-chain analysis at this time for similar reasons.

For our exploratory research, we focused on the BIP44, BIP49 and BIP84 standard address formats and derivation paths. Our primary focus was on finding both formerly used as well as currently used Bitcoin wallets generated by bx seed | bx mnemonic-new on bx 3.x versions with common BIP39 mnemonic word phrase lengths and settings.

Specifically, this covers:

• 128 bits = 12 words, bx seed -b 128
• 192 bits = 18 words, bx seed -b 192 (default)
• 256 bits = 24 words, bx seed -b 256

We used a publicly available list of all Bitcoin addresses historically seen by the Bitcoin network and constructed a bloom filter with a very low false positive rate on the data set. Using this filter, we were able to do quick address lookups to query and discard many unused wallet candidates, for which the relevant derived accounts were never seen by the network, without doing costly lookups to a Bitcoin full node.

We only consider wallets where the first address was used. The standard mandates to scan the first 20 addresses, but computing addresses is a bottle-neck in our search. We also only consider wallets using the standard derivation paths specified by BIP44, BIP49, and BIP84. In total, we discovered over 2600 distinct and actively used Bitcoin cryptocurrency wallets that are based on the bad bx seed entropy.

The majority of these wallets, a group of over 2550, has an oddly similar usage pattern with small deposits around the same dates in 2018. We think this is the result of some automatic tool use of bx, and that these wallets may actually share the same owner. We’re not sure what this experiment was about, but they’re all in the 256 bit seed output range and have a BIP49 address type (‘3’ prefix), which helps distinguishing them a bit from other addresses.

Excluding this large number of special wallets, we’ve identified less than 50 wallets with more individual usage patterns that we associate with likely use by human wallet owners. Those are distributed across the mentioned ranges and address types. We know this survey to be incomplete, as we have not discovered all wallets involved in the sweeps we observed on the blockchain.

Within this set of wallets, we were able to find and identify both of the initial victim’s wallets. This gives us confidence that our research into the the explanation for the theft is correct.

A decent portion of the discovered individually used wallets did not have any BTC funds on them since before 2023, so no money could be moved away from them by the attackers. However, we still consider them fully affected for two reasons:

1. Any new deposits to them are at risk of immediate, automated theft (as outlined in the Ledger Donjon article).
2. Access to the underlying wallet private keys allows reconstructing all derived addresses on all coins, linking the wallet owner’s previous actions on all of them, a significant privacy impact.

Other Confirmed Victims of this Theft

Within a few days after the large theft of July 12th 2023, a victim of the theft came forward on Reddit:

1. https://www.reddit.com/r/Bitcoin/comments/158nyuo/mass_hacking_of_over_1000_bitcoin_accounts/

The Reddit user u/0n0t0le provides an interesting data point, since he lost ~0.25BTC but was able to move away and recover over 1.05 BTC that the attackers didn’t find or take at that point.

We were able to confirm for case 1) that the user had their funds in a vulnerable wallet in the bx seed ranges.

Please note that BIP39 mnemonic secrets as well as other wallet private keys typically do not contain any clear indication on the software used to generate them. As a format designed to be exportable and importable between different wallet software, it is therefore possible that users do not clearly or correctly recall where a given wallet was created. This can lead to a lot of confusing information on potentially affected other wallet software, and makes fact-finding harder.

In the interest of correctness, we’re currently not listing other open leads that we’re following up on, but may update this section at a later point in time.

Basic Timeline of Thefts and Our Disclosure

Date

Event

2022-11-17

Ledger Donjon discloses Trust Wallet vulnerability to Binance

2022-11-21

Trust Wallet code patch on GitHub publicly removes Mersenne Twister usage

2022-11-21+

Trust Wallet selectively notifies affected users of the vulnerability

2022-12-?

Vulnerable Trust Wallet wallets exploited on-chain (according to vendor)

2023-03-?

Vulnerable Trust Wallet wallets exploited on-chain again (according to vendor)

2023-04-22

Trust Wallet publicly discloses Trust Wallet vulnerability

2023-04-25

Ledger Donjon publishes their Trust Wallet vulnerability write-up

2023-05-03

First potential exploitation of bx 3.x wallets

2023-07-12

Main exploitation of bx wallets

2023-07-21

We discover the bx vulnerability during incident response analysis

2023-07-22

We send initial email to establish communications with the Libbitcoin team

2023-07-25

First Libbitcoin team response, indicating team is too busy for contact

2023-07-25

We send context information without vulnerability details to the Libbitcoin team, asking for followup

2023-08-03

We send technical vulnerability details and detailed disclosure context to the Libbitcoin team

2023-08-03

Libbitcoin team response, indicating they do not feel this is a bug

2023-08-04

We request a CVE for the bx seed vulnerability in versions 3.x from MITRE

2023-08-05

Libbitcoin team response, further detailing they do not feel this is a bug

2023-08-07

MITRE assigns CVE for the bx 3.x issue

2023-08-08

Publication of this article

Please note that this timeline focuses on the main events and is not exhaustive.

Libbitcoin Team Response and Context

During our accelerated coordinated disclosure to the Libbitcoin team, the Libbitcoin team quickly disputed the relevancy of our findings and the CVE assignment. By our understanding, they consider bx seed a command that should never be used productively by any bx user since it is sufficiently documented as unsuited for safe wallet generation.

We do not agree with this assessment.

Please consider the following timeline and linked resources:

Date

Information

2013-07-21

Libbitcoin Explorer predecessor tool adds a newseed command for entropy generation

2014-10-16

First Libbitcoin Explorer wiki documentation page for bx seed

2014-12-14

First Libbitcoin Explorer (bx) release starting with version 2.0.0

2015-12-21

Libbitcoin Explorer (bx) release 2.2.0

2017-02-10

Libbitcoin Explorer (bx) release 2.3.0

2015-01-19

A Libbitcoin team member adds and updates bx seed usage suggestions to “Mastering Bitcoin” (described below)

2016-10-21

The Libbitcoin team changes the seed generation to Mersenne Twister via PR#559, commit

2017-03-08

Libbitcoin Explorer (bx) 3.0.0, includes PR#559

2019-08-29

Libbitcoin Explorer (bx) 3.6.0, currently latest official release

2021-05-02

bx seed command gets renamed to bx entropy on GitHub branch, still based on Mersenne Twister, PR#628, 1, 2

We’re aware of a single warning note in the bx seed documentation page in the wiki:

WARNING: Pseudorandom seeding can introduce cryptographic weakness into your keys. This command is provided as a convenience.

The wording “can introduce” is quite weak and a user may not be aware that this produces a seed that is completely insecure and should not be used to store anything of value.

When adding bx seed related workflows to the “Mastering Bitcoin” book appendix, Libbitcoin team members described it as follows:

Generate a random “seed” value using the seed command, which uses the operating system’s random number generator. Pass the seed to the ec-new command […] $ bx seed | bx ec-new > private_key […]

Similarly, in “Mastering Bitcoin” Chapter 4:

You can also use the Bitcoin Explorer command-line tool (see [appdx_bx]) to generate and display private keys with the commands seed, ec-new, and ec-to-wif: $ bx seed | bx ec-new | bx ec-to-wif […]

Neither Chapter 4 nor the Appendix contain the warning that bx seed does not produce secure random numbers. The examples do not warn the user that wallets created like this are insecure.

We informed the authors of “Mastering Bitcoin” and they will revise the text.

The following Libbitcoin documentation includes bx seed:

Page

Command Excerpt

Last changed

wiki landing page

bx seed | bx ec-new | bx ec-to-public | bx ec-to-address

7/2018

bx mnemonic-new documentation

bx seed -b 128 | bx mnemonic-new

4/2017

bx hd-new documentation

bx seed | bx hd-new

4/2022

Random Numbers

bx seed -b 256

7/2018

All these examples do not contain any warning that the created wallets are insecure.

Other notable characteristics:

• The bx seed -b parameter cannot be configured to output less than 128 bits of binary output size. Related code comments on this limit include The minimum safe length of a seed in bits and These are soft requirements for security and rationality… It seems strange that the design explicitly prevents the user from creating a seed that is too short, but does not prevent him from creating a seed that has not enough randomness.

General notes:

• Dates regarding releases and commits are taken from Git/GitHub timestamp information. This may deviate from the actual dates in some cases.

Suspected RNG Problems in Older bx Versions

For the main part of our short and busy disclosure, we focused on the Mersenne Twister related issues in bx versions released after March 2017.

However, we recently observed some behavior on older bx versions before 3.0.0 that indicate other weak random number generator behavior of bx seed, in part depending on the system environment bx is executed on. Specifically, the std::random_device entropy source in combination with std::default_random_engine may not behave securely enough if the random engine uses insufficient seeding and acts as a non-CSPRNG similar to Mersenne Twister.

Tool

Version

Release

Status

Details

sx

1.x ?

2014

🔍 likely affected (some systems)

std::random_device + std::default_random_engine

bx

2.0.0 - 2.1.0

2014 - 2015

🔍 likely affected (some systems)

std::random_device + std::default_random_engine

bx

2.2.0 - 2.3.0

2015 - 2017

❔ unclear, improved behavior

std::random_device + std::uniform_int_distribution

bx

3.0.0 - 3.6.0

2017 - now

🔥 confirmed exploitable

get_clock_seed() + std::mt19937 Mersenne Twister

Please regard this as preliminary indications of potential problems. It is possible that some of the public thefts exploit random number generator issues in versions before bx 3.0.0, but we have not confirmed this yet.

We plan to follow up on this with additional research.

Part III - Summary and Outlook****Basic Lessons Learned

• Use BIP39 passphrases for your wallets, ideally with a complex passphrase based on entropy from a separate source.
• Trust only heavily audited software to be in your wallet generation path.
• Document every wallet generation setup for your future self, this may be very important.

Summary

In this article, we presented technical information of a weak entropy generation function in Libbitcoin Explorer, confirmed the practical use of the weak function for over 2600 cryptocurrency wallets on the Bitcoin Mainnet, and connected it to a recent large theft of cryptocurrency funds on multiple popular blockchains that amounts to an estimated $900k of damages. Additionally, we described the close similarities with another actively exploited vulnerability in Trust Wallet, and provided some background on the Libbitcoin Explorer context and overall timeline.

Future Work

• We plan further security research into bx 2.x RNG behavior.
• We may update this page in the next days as more information becomes available.

Additional References

• Security bug - Mersenne Twister MT19937 usage in Intel cryptography library

Commercial Work

We have not received any reward for this research and are not accepting donations.

If you like our work, check out the following commercial services offered by different team members and organizations:

• Distrust, LLC
  • Infosec firm focusing on high risk clients
  • Pentesting, threat modeling, hands-on security engineering
  • Full stack security evaluations and advisory retainer contracts
  • Covers: Shane Engelman, Anton Livaja, Ryan Heywood, and Lance Vick
• Christian Reitter
  • Freelance InfoSec Consultant
  • Pentesting, Code Audits, Security Research, Fuzzing
• Heiko Schaefer
  • Focus on OpenPGP: OpenPGP CA, Sequoia PGP, OpenPGP on HSM devices (OpenPGP card, PKCS #11, PIV)

Other Notes

• Included Libbitcoin code snippets are licensed under AGPLv3.
• For other code snippets, see the included copyright notice.

Credits

• Core Team
  • Distrust
    • Anton Livaja - [email protected]
    • Lance R. Vick - [email protected], https://lance.dev
    • Ryan Heywood - [email protected], https://ryansquared.pub
    • Shane Engelman - [email protected]
  • Independent
    • Christian Reitter - https://inhq.net
    • Daniel Grove - [email protected]
    • Dustin Johnson - [email protected]
    • Heiko Schaefer - [email protected]
    • James Callahan - [email protected]
    • Jochen Hoenicke - https://jhoenicke.de
    • John Naulty - [email protected]
    • Matthew Brooks - *@logicwax.com
• Special Thanks
  • Jack Kearney - Turnkey
  • Several trusted advisors that wish to remain uncredited. You know who you are.