New vulnerability 2023!!! 32 bits of entropy and $170,000

09.02.2024
New vulnerability 2023!!! 32 bits of entropy and 0,000

This story begins on Friday, July 21, 2023. When trying to use a well-protected cryptocurrency wallet, its owner discovered that all the funds stored in the wallet had simply disappeared. This was not an accident – he was the victim of a rather sophisticated theft. The funds were sent to the attackers’ addresses on July 12, while the hardware wallet was not used for several days. (Details below)

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

  • Generated on a laptop in an isolated network ( air-gapped ) on Linux OS with self-compiling software
  • BIP39 24-word mnemonic phrase used
  • Mnemonic introduced securely into Ledger and Trezor hardware wallets
  • Good PIN coding and physical protection of hardware wallets are available
  • The mnemonic seed has never touched computers outside the isolated network
  • The backup copy of the mnemonic phrase was well protected.

Well done. Everything was done beautifully :). Did not help.

Where is my friend’s crypto?

The victim turned to his friends with similar key generation and management protocols, and a second victim was found! The second victim also had the contents of his cryptocurrency wallet stolen during the same period of time – both victims’ Bitcoin (BTC) was stolen at the same minute on-chain. The victims realized that this was not an accident. They were victims of some kind of hacking.

The victims discovered that not only bitcoins (BTC) were stolen. The attackers also stole Ethereum and other cryptocurrencies from the same wallets. The victims realized that this could only happen as a result of the leakage of the private keys of their main wallets. Forcing hardware wallets to authorize incorrect transfers or hacking individual sub-account private keys would have a more limited impact.

A theft like this, affecting two people at once, despite all precautions, should be very unlikely. What’s even worse is that these two weren’t the only victims. The public Bitcoin transactions associated with the theft drained funds from many different wallets, likely from around a thousand different wallet holders in Bitcoin alone.

So what’s going on? Did someone find a vulnerability in a hardware wallet that could be exploited remotely, exploit it on a large scale, and wait several months before collectively executing on-chain drain transactions? Worse, perhaps one of the basic cryptographic primitives is vulnerable? Maybe the magic of quantum computing is at work here? 😱

Tensions grew, and a search began for the source of compromise.

Our crypt is missing, but how?!

As a result of the conversation, both victims realized that their affected wallets were generated on a similar airgap setup, albeit with a difference of several years. At that time, the problem seemed difficult to define and could point to various sources. The victims decided to start from the very beginning – from the steps to create a wallet, from the first commands used, and then progressively.

The original tool involved in the creation of both wallets was Libbitcoin Explorer in version 3.x and its binary command bx. The open source Libbitcoin project has been around for a very long time (since 2011!), and bxcontains everything you need to create a standalone wallet in one standalone binary.

Despite the fact that bxit is a specialized tool that most wallet users have not even heard of, it enjoys some popularity and a small section is dedicated to it in the appendix of the book “Mastering Bitcoin”. In other words, it seems to be a perfectly adequate tool to use.

A short example of the process of creating a wallet in the 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 assigned to victims’ wallets. This private key is the basis of all wallet security.

Could the problem be related to the binary command bxthat the victims were using? They made sure that the /dev/randomRandom Number Generator (RNG) subsystem in Linux laptops had enough entropy, but perhaps this was not enough? Could this be a serious system configuration problem or a virus?

At this point, we called several friends with experience in the field of information security to help us understand the situation and study the appropriate paths for the wallet generation code 🕵️‍♂️.

As more and more people looked at the case, the first signs of a serious problem emerged.

The more eyes, the more bugs?

The team decided that it would be logical to start their search by looking at the source code bxof the command bx seed.

Execution bx seedcalls a function new_seed(size_t bit_length)in libbitcoin-explorer src/utility.cpp , which calls a function pseudo_random_fill(data_chunk& out)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 ones ? Okay, a pseudo-random number generator (PRNG) isn’t necessarily that bad if it is a Cryptographically Secure Pseudo Random Number Generator (CSPRNG ). It may be okay, 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 minute. mt19937twister— is PRNG Mersenne Twister used here ? 🤔 At this moment, the first alarm bells are ringing. Mersenne’s PRNG is not a CSPRNG, i.e. cryptographically secure, so it should not be in any code that generates secrets. One of the vulnerabilities of the Mersenne vortex is that its internal state can be reversed by an attacker who knows several hundred results, which compromises the secrecy of the remaining results of the same stream, which are unknown to the attacker (to put it simply).

However, if the PRNG is re-sat before each wallet generation, only one result is retrieved, and that result is kept secret, would the weak design of MT19937 be fatal enough, i.e. susceptible to remote theft if everything else is done well?

The combing of the code file pseudo_random.cppcontinued, and we did not have to go into detail pseudo_random::get_twister()to understand the essence of the 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 weak PRNG algorithm that uses only 32 bits of system time is used to generate long-term private keys for wallets that store cryptocurrency? 😧

Our investigative team even went through it twice—couldn’t it be possible bxto use THIS to generate private keys?

The team looking for the vulnerability couldn’t believe this was the case, so they set up a simple experiment to test this hypothesis. As with all good experiments, the environmental variables were under the control of the experimenters, and in this case it was the variable that timewas most relevant to understanding the problem at hand. To test our theory, we used the bxofficial version binary 3.2.0in combination with the library libfaketime, running separate executions under absolutely identical clock synchronization 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

💥 At the same time, the same “random” wallet was obtained! Incredible!

A safe and reliable utility would not print the same mnemonic seed phrase under such circumstances. This was the first conclusive evidence that the secret generation code bx seedin the official release uses a broken time-based pseudo-random function for wallet entropy.

Digging deeper, the team was convinced that the code used the standard version of the Mersenne Twister MT19937 PRNG, which by design only works with 32 bits of initial seeding input, and not the extended version MT19937-64 with 64 bits of seeding. So this PRNG can have at most 2^32 starting positions as its upper bound, regardless of whether it is seated /dev/randomor timed.

In other words, when executing bx seed -b 256256 bits of unguessable entropy for a request, the result is 32 bits of high-precision clock time, passed through a blender (more precisely: a twister, aka a vortex 🌪️) and expanded to 256 bits without adding new information. If this were real entropy data, then the number of possible key variations would grow exponentially with size, so the difference between the safe expected result (256 bits) and the actual result (32 bits) is astronomical!

Anyone can recalculate and find the victim’s original used entropy after a maximum of about 4.29 billion attempts, as long as they know certain characteristics that can be used to determine the successful detection of a cryptocurrency wallet. In this case, it is checking derived wallet addresses that have been seen receiving funds on the public blockchain in the past. To put this figure into perspective, bragging through this key space takes a few days at most on the average gaming PC. And, unfortunately, anyone with sufficient programming skills can do this.

In terms of the security of cryptocurrency wallets, this is a rather catastrophic situation.

Friday July 21st ended with the realization that things had become very difficult. Not only did several friends permanently lose full control of keys and funds from their wallets, but our group also had a serious problem with information disclosure.

Not the first hack: weak entropy in the Cake wallet

Early in our assessment of possible vulnerabilities that could lead to a similar issue, one of our team members remembered the weak entropy situation in the Cake Wallet.

As far as we know, in May 2021, the Cake Wallet development team announced that there was a vulnerability in the entropy of their wallets , which required all users to change their mnemonic phrases.

Further investigation into this situation by Reddit user Pure-Cricket7485 revealed tangible flaws in the Cake Wallet’s entropy source strategy.

In particular: Cake Wallet used the unsafe Dart’s Random() function 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 is 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 the Mersenne Twister, which made us wonder if it had a bxsimilar flaw.

Not even a second hack: Using Mersenne Twister in Trust Wallet

A few days after the disclosure process began, we learned of a vulnerability in Trust Wallet , published at the end of April 2023. After reading Ledger Donjon’s excellent report on the discovery and research of CVE-2023-31290 , we were somewhat shocked at how close this vulnerability is to the vulnerability in bx! And the Trust Wallet publication confirms that attacks on the wallets of their users occurred as early as December 2022. Why did money from wallets generated by bx, begin to disappear only in mid-2023?

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

The vulnerable version of Trust Wallet both bxhave the same basic fatal flaw of generating wallet entropy based on the unusable MT19937 Mersenne Twister algorithm. bxAdditionally, the MT19937 seed uses some clock information, but in practice this is not of much importance for a remote offline brute force attack. These are still the same limited 32 bits of key space that attackers can comb up and down.

To the best of our knowledge, Trust Wallet only creates 12-word wallets based on the BIP39 mnemonic, which fixes the entropy requirements (and therefore PRNG usage) at 128 bits. bxmore flexible and generates 128-, 192-, 256-bit outputs (and others). More options mean more room to search, but do wallets generated with .com overlap bx seed -b 128with wallets created by Trust wallet?

It turns out not – due to a nuance in the use of PRNG. 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 32-bit MT19937 output, takes the low-order 8 bits of this output to fill the array and throws out the remaining 24 bits through & 0x000000ffwasm /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 libbitcoin-systemC++ mechanisms used for pseudo_random::fill(), its code performs the same truncation 32 bits -> 8 bits, but exactly the opposite – taking the 8 most significant bits from the PRNG.

As a result, all outputs bx seed, as far as we know, are in a completely different key space than the one that the Trust Wallet code generates, and therefore the BIP39 mnemonics are also different.

To confirm this, let’s conduct a small experiment. The Ledger Donjon report provides a specific example of a wallet that is described as follows:
[…]
RNG seed: 0x8ec170a8
Mnemonic:
sorry slush already pass garden decade grid drip machine cradle call put
[…]

If you recalculate the RNG seed 0x8ec170a8using the code bxfor the 12-word BIP39 mnemonic, you get the following:

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

This confirms that the wallet generation process is indeed different.

At the end of Ledger Donjon gives the following line, which, in our opinion, can be considered a foreshadowing:

“During our investigation, we also noticed that among the vulnerable addresses there are several that were generated long before the release of Trust Wallet. This likely means that this vulnerability exists in other wallet implementations, which is cause for concern…”

However, we suspect that these other wallets spotted by Ledger Donjon were not generated by versions of bx 3.x, unless Ledger Donjon experimented with PRNG outputs and came across a different usage pattern. The presence of other affected wallets in the Trust Wallet 12-word range suggests that there are other wallet generation tools using MT19937. Due to time constraints, we have not yet conducted further research.

When comparing our disclosure challenge to bxLedger’s Trust Wallet challenge, the disclosure was to a single commercial and apparently well-funded wallet manufacturer. Based on the posts, Trust Wallet had direct communication channels with individual users that it could use to selectively inform them of vulnerabilities associated with their wallets. Additionally, their wallets were only vulnerable for a limited time and the problem was discovered relatively quickly, with many users continuing to use the app as normal.

In their report , the Trust Wallet team puts the total amount of lost funds at $170,000:

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

As we understand, Trust Wallet decided to financially incentivize users to transfer their funds to a safe place, as well as reimburse lost funds to victims of theft. In addition, they paid Ledger Donjon a significant reward of $100,000 for their coordinated disclosure.

Unfortunately, most of these factors are not applicable to our case. Given the non-commercial nature of the Libbitcoin project, the lack of direct communication channels with end users, the long history of the existence of affected wallets, and the likely widespread availability of imported/exported BIP39 keys and mnemonics, the situation for security research and troubleshooting is much more difficult.

Taking into account the already published Trust Wallet and Ledger Donjon reports, the compromise of all private keys bx seedand the ongoing active exploitation of wallets bx, it became clear to us that long-term agreed upon disclosure of information will not help anyone. If we want to give affected bxwallet owners a chance to keep their funds, then we need to aim for publication to take days rather than months. In this situation, time is on the side of the attackers, not the victims.

Well-established security programs such as Google Project Zero have a similar policy regarding actively exploited vulnerabilities:

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

New vulnerability 2023!!! 32 bits of entropy and 0,000

Current thefts in different blockchains – some facts

Due to time constraints, we decided to focus on Bitcoin as the main network. Due to the flexibility of the withdrawal bx seed, funds in all coins compatible with the BIP39 mnemonic (or even just the BIP32 seed) may be affected. Given the main job and limited time and computing resources, it was not possible to perform the sequence of steps 100 times. Therefore, this review focuses only on Bitcoin and provides only a partial understanding of the theft activities. The given figures can be considered as the lower limit of the total volume of the affected money supply.

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

1.) Grand theft 2023-07-12:

datetransactionaddress of the recipientapproximate volumenoticed
2023-07-12 10:41593e11588a2529ed..3GMQRwh8Yz1WVftL..~5.053814 addresses
2023-07-12 10:4181cfe97cc16a4939..3LwDzjA1xH8amCHu..~9.744> 300 addresses
2023-07-12 10:41a22b33a9a4ca0de2..3D2mKf28exn26v7B..~9.744> 1200 addresses

We attribute them to one well-trained thief who stole approximately ~29.65 BTC worth up to $850,000 USD, and that’s in Bitcoin only (as of 8/2023). We believe that this burglar most likely stole other coins on the same day. At the time of writing, these funds have not moved anywhere from this new location.

  1. There is a second, earlier model for the movement of funds, which we believe is also theft:

This behavior began on May 3, 2023, and consisted of many small wallet stripping operations that continued until July 15. In total, we estimate that the amount of these sweeps amounted to about 0.33 BTC. The funds were once again moved to other addresses, which distinguishes this pattern of behavior from the one described above.

We have not seen any reports of funds being stolen from these addresses. In theory, this particular user could have legitimately moved his funds from many different wallets (see further analysis), or he could also be an attacker. The addresses below are related in that they were marked in the same transaction, indicating that they are the same entity or group.

Addresses of the alleged attacker:

Here is a list of some known coins with confirmed cases of theft (prior to the publication of this investigation):

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

It is likely that we are talking about many more coins, since the additional cost of carrying out this attack on other coins in the affected wallets is limited by the R&D time required to identify and withdraw funds. We hope that there is a chance to catch the attackers by tracking specific coins for their identification and operating methods, but we have nothing to report on this yet.

Overall, we estimate that over $900,000 worth of cryptocurrency assets (at 8/2023 exchange rates) were moved in this hack, although some of the affected wallets may have been emptied through other vulnerabilities.

New vulnerability 2023!!! 32 bits of entropy and 0,000

Finding wallets – motivation and limitations

The main reason for the rapid search for affected Bitcoin wallets was to assess the overall damage in terms of the volume of stolen and remaining funds, as well as technical confirmation that the vulnerability was real and the only explanation for the initial theft. We had the hope that if we discovered significant balances of funds, there would be a small but non-zero chance of somehow informing the rightful owner so that he could salvage them. During the planning stage, we considered options for sending an alert to the wallet owner through a centralized exchange used for direct deposits, finding wallet owners with public addresses, or detecting other feedback channels. As a last resort, we could extend the scheduled disclosure time while we search for options.

Ultimately, as of the date of publication of the investigation, we did not find significant balances of funds in the analyzed ranges of the Bitcoin network exceeding the $5,000 threshold associated with wallets generated on versions of bx3.x. It is quite possible that larger amounts of funds remain in similar wallets of one type or another with slightly different creation methods, but during the analysis we have not yet discovered them. It is also possible that some wallet owners are using additional BIP39 passwords, which provide moderate to strong protection depending on password strength and other factors, making detection much more difficult.

We would like to be clear about our actions in the investigation:

  1. The two initially described victims managed to recover a small part of the contents of their own wallet, which was not stolen, using their usual wallet setup that they had before the theft.
  2. We did not move any funds in any of the unknown victims’ wallets, not even a single coin.
  3. We do not know or are in any way associated with the attacker(s) who stole these funds.

In general, none of the members of our group moved funds of which he was not the legal owner, and does not know the identities of the thieves.

As far as we know, even under ideal hypothetical circumstances, moving someone else’s funds to avoid theft by criminals can turn into a legal nightmare. Even in the most ideal scenario – where there is one victim, clear evidence of ownership, well-established identities on both sides, a single jurisdiction and reliable communication channels – this involves a lot of risk.

In our situation, the circumstances were significantly worse than in the ideal case by most possible criteria. Therefore, any scenario involving the movement of anything of value that we did not own prior to the disclosure presented us with a flurry of legal problems. (Remember: we are not lawyers and this is not legal advice; we are also not financial professionals, so this is not financial advice either).

For those readers who are ready to take the plunge and play the role of a “white knight,” we invite you to consider the following dilemma: any attacker can calculate the owner’s private keys, which negates the value of any cryptographic signatures with these keys. In any scenario that involves transferring a wallet owner’s funds to another wallet that you control, how do you know that the person who shows up in your DMs (or on your doorstep) asking for “their” funds back is the rightful owner? Especially if there is no centralized structure, such as a large exchange, that would support this claim by providing at least some evidence?

This is such a difficult situation! And that doesn’t even touch on other issues like anti-money laundering (AML) compliance, tax reporting, and a host of other aspects.

If you are one of the victims of theft: no, we definitely do not have your funds and we do not know how to return them. Sorry!

If it’s any consolation, we have made every effort to give our affected friends and all other victims at least some explanation and understanding of why this was possible in the first place, and to help them avoid getting into trouble again due to the same vulnerability.

Finding wallets – implementation

128 bits = 12 words,bx seed -b 128192 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 that have historically been seen on the Bitcoin network and built a bloom filter on this dataset with a very low false positive rate. Using this filter, we were able to quickly comb through addresses, find and discard many unused wallets whose corresponding derivative accounts had never been seen on the network, without resorting to a costly search on a Bitcoin full node.

We only considered those wallets where the first address was used. The standard requires scanning the first 20 addresses, but computing addresses is the bottleneck in our search. We also only considered wallets using the standard derivation paths specified in BIP44, BIP49 and BIP84. In total, we discovered over 2,600 different actively used weak entropy-based Bitcoin wallets bx seed.

Most of these wallets, a group of more than 2,550, have an oddly similar usage pattern: small deposits around the same dates in 2018. We believe this is the result of an automated tool bxand that these wallets may have the same owner. We’re not sure what that experiment was about, but they are all in the 256-bit seed output range and have a BIP49 address type (prefix ‘3’), which makes them slightly different from other addresses.

By excluding this large number of specific wallets, we identified fewer than 50 wallets with more individual usage patterns, which we attribute to the owners being real people. They are distributed according to the specified ranges and types of addresses. We know that our research is incomplete because we did not find all of the wallets that were subject to the sweep that was observed on the blockchain.

In this set of wallets, we were able to find and identify both wallets of the original victim. This gives us confidence that our investigation into the cause of the theft is on the right track.

A significant portion of the individual wallets discovered did not contain BTC until 2023, so the attackers were unable to withdraw money from them. However, we still consider them victims for two reasons:

  1. Any new deposits into them are at risk of immediate automatic theft (as described in the Ledger Donjon article).
  2. Access to the private keys of wallets allows you to recover all derived addresses on all coins, linking them to the previous actions of the wallet owner, which significantly affects privacy.

Other confirmed victims of this theft

A few days after a major theft that occurred on July 12, 2023, information from one of the victims appeared on Reddit:

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

Reddit user u/0n0t0le provides an interesting example, as he lost ~0.25 BTC, but was able to move and store over 1.05 BTC, which the attackers had not found or taken at the time.

In this case, 1) we were able to confirm that the user was storing his funds in a vulnerable wallet in the range of bx seed.

Please note that BIP39 mnemonic secrets, like other wallet private keys, usually do not clearly indicate the software that generated them. Because the format is designed to be exported and imported between different wallet programs, users may not clearly or correctly remember where a particular wallet was created. This could lead to a lot of confusing information about other potentially affected wallet software and make it difficult to find the facts.

Please consider this as an early indication of possible problems. It is likely that some of the public thefts have already exploited the random number generator vulnerability in versions prior to bx 3.0.0, but we have not yet confirmed this.

We plan to conduct additional research.

Key Lessons

  • Use BIP39 passphrases for your wallets, ideally complex passwords based on entropy from a separate source.
  • Trust wallet generation only to carefully tested software.
  • Document every setup when generating a wallet, this may be very important for you in the future.


Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO




via the link:
https://t.me/ExploitDarlenePRO