website-public/_posts/2024-05-19-research-update-9.md

layout	title	author	date
post	Update #9 - Cake Wallet Technical Writeup	Christian Reitter	2024-05-19 22:00:00 +0000

In this post, we're disclosing new technical information on the Cake Wallet flaw from 2020/2021 that led to the generation and use of very insecure Bitcoin wallets.

Table of Contents

* placeholder {:toc}

Urgent Warning

If you’re a Cake Wallet user or know someone who is, we urgently recommend checking if you -> still use a vulnerable old wallet software version -> still use an old and weak Bitcoin Electrum mnemonic seed generated with a vulnerable version

Affected wallets are at risk of immediate and complete loss of all Bitcoin funds, and this research update will show why.

Introduction

Please see [research update #6]({% link _posts/2024-02-13-research-update-6.md %}) for some general context of the Cake Wallet PRNG vulnerability.

To summarize, the Cake Wallet software used a weak Pseudo Random Number Generator (PRNG) to generate Bitcoin wallets. The software vendor publicly disclosed this vulnerability in May 2021, released a patched software version and asked users to urgently transfer their affected funds to different wallets.

We first came became aware of the public Cake Wallet PRNG vulnerability in July 2023 while researching the Milk Sad vulnerability. Since it was one of the most relevant publicly acknowledged vulnerabilities in Open Source wallet software, we included [a short section]({% link disclosure.md %}#not-the-first-hack-weak-entropy-in-cake-wallet) on the issue in our main writeup for flaws in libbitcoin-explorer, but only looked briefly into the technical details at the time due to a different research focus on Mersenne Twister based wallet keys.

This research update is meant for technical readers with a background in security and programming.

Technical Deepdive

The Cake Wallet Footgun: randomBytes()

The Cake Wallet software is written in the Dart programming language. The vulnerable version used a custom PRNG wrapper function called randomBytes() to fill Uint8List objects (roughly similar to byte vectors) with random data, taken from either the Dart Random.secure() or Random() PRNG APIs.

Combining two cryptographically secure and insecure code paths in one function is a bad practice, as is defaulting to the insecure method. In combination with a robust-sounding function name, this created what's known to programmers as a "footgun" - a feature you're likely to shoot yourself in the foot with. 🦶 ⬅️ 🔫

Code bitcoin_mnemonic.dart:

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 footgun went off in the important generateMnemonic() function that generates Bitcoin wallets. Here, randomBytes(byteCount); does not set the second function parameter to secure == true and consequently uses the known-insecure PRNG as the only entropy source for the master wallet private key. 🎯☠️

Code bitcoin_mnemonic.dart:

String generateMnemonic({int strength = 132, String prefix = segwit}) {
  final wordBitlen = logBase(wordlist.length, 2).ceil();
  final wordCount = strength / wordBitlen;
  final byteCount = ((wordCount * wordBitlen).ceil() / 8).ceil();
  var result = '';

  do {
    final bytes = randomBytes(byteCount);
    maskBytes(bytes, strength);
    result = encode(bytes);
  } while (!prefixMatches(result, [prefix]).first);

  return result;
}

When the vulnerability was first disclosed on Reddit, this technical source of the bug was quickly spotted and pointed out by users in the space of a few hours.

Analyzing Dart Random(), Part 1

Ok, so the vulnerable key generation function used the insecure variant of Dart's Random() API:

The default implementation supplies a stream of pseudo-random bits that are not suitable for cryptographic purposes.

Use the Random.secure constructor for cryptographic purposes.

Everyone agrees that this is bad. But how bad exactly?

Random() is not meant to be a Cryptographically Secure Pseudo Random Number Generator (CSPRNG), and so the code is generally allowed to return very weak and easily guessable results. One example for this can be found in its seeding function, which initializes itself via the current system time under some conditions:

Code random.cc:

Random::Random() {
  uint64_t seed = FLAG_random_seed;
  [...] // OMITTED MAIN SEED CALCULATION CODE
  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);
}

This fallback mechanism is a well-known weakness pattern, see CWE-337: Predictable Seed in Pseudo-Random Number Generator (PRNG) and CWE-335: Incorrect Usage of Seeds in Pseudo-Random Number Generator (PRNG). The exploitation difficulty depends mostly on the used resolution of the system clock and the potential time range an attacker wants to try out via brute-force (minutes, days, years?).

However, let's focus on the default case where this special fallback is not used to pick the PRNG seed, for reasons that will become clear later.

While investigating the Cake Wallet behavior, we searched for prior work in the form of existing security analysis writeups for the Dart Random() PRNG in general, or the Cake Wallet vulnerability specifically, that would tell us about its practical properties. Reviewing and reversing cryptographic mechanisms is usually very time consuming, so we hoped that other researchers had written about this before, but no luck - we seem to be the first to do so. (In case there was something out there that we missed, [let us know]({% link index.md %}#contact) so that we can add it as a reference).

Our primary research question: how weak, exactly, are the generated wallets to brute-force attacks? In other words, is it realistic to generate all weak wallet candidates and scan them for usage on the blockchain, as we did with Mersenne Twister-based weak wallets?

For this, the amount of actual (not-otherwise-guessable) entropy supplied by Random() is an essential factor, so let's look more closely into that.

Right from the start, the initial signs were not at all encouraging for our research goal of practical scans.

Code random.cc:

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;
      }
    }
  }
  [...] // OMITTED FALLBACK SEED CALCULATION CODE
  Initialize(seed);
}

The code defines the local variable uint64_t seed, which can hold up to 64 bits of information, and calls DartUtils::EntropySource(uint8_t* buffer, intptr_t length) to fill it completely with random values.

Relevant code positions for the entropy source:

Code main_impl.cc:

init_params.entropy_source = DartUtils::EntropySource;

Code dart.cc:

set_entropy_source_callback(params->entropy_source);

The EntropySource() function seems to always use cryptographically secure entropy:

Code dartutils.cc:

bool DartUtils::EntropySource(uint8_t* buffer, intptr_t length) {
  return Crypto::GetRandomBytes(length, buffer);
}

The Crypto::GetRandomBytes(length, buffer) implementation depends on the operating system, but generally fetches random bytes directly from strong sources like /dev/urandom.

The PRNG state variable is also large enough to hold this complexity between PRNG iterations:

Code random.h:

 private:
  uint64_t NextState();
  void Initialize(uint64_t seed);

  std::atomic<uint64_t> _state;

The uint64_t _state is sufficiently large to keep the intermediary PRNG states from being directly enumerable by us.

One PRNG function looked interesting:

Code random.h:

  // Returns a random number that's a valid JS integer.
  //
  // All IDs that can be returned over the service protocol should be
  // representable as JS integers and should be generated using this method.
  //
  // See https://github.com/dart-lang/sdk/issues/53081.
  uint64_t NextJSInt() {
    // Number.MAX_SAFE_INTEGER (2 ^ 53 - 1)
    const uint64_t kMaxJsInt = 0x1FFFFFFFFFFFFF;
    return NextUInt64() & kMaxJsInt;
  }

For context, Dart code can run in a Javascript environment. Since Javascript has the odd property to store integers as floating point numbers, integers in that environment are limited to 53 bits of complexity instead of the original 64 bits. At first, this seems like an interesting restriction that could bring down the overall complexity of this and other functions. The vulnerable Cake Wallet software doesn't run in a Dart Javascript context, though, so this is not directly relevant for our analyzed target.

To recap, a first review pass over the main implementation of the insecure Dart Random() PRNG class suggests it self-seeds with 64 bits of system-provided entropy under normal conditions. Cryptographic keys with this complexity level are still considered totally broken against resourceful adversaries. That said, the exponentially increased brute-force complexity between keys with 32 bits of entropy and keys with 64 bits of entropy means that they're much less feasible to break at scale in our self-funded research.

Weak but not easily exploitable - case closed! Right?

Analyzing Dart Random(), Part 2

Not exploitable for us? Not so fast! In security research, extra persistent digging can sometimes overcome seemingly impossible odds. There's always room for implementation issues in crucial functionality, or other "real world" problems which undermine the expected security of the theoretical model. A combination of hard work, patience and luck can lead you to previously hidden layers, and that's often where the new or interesting vulnerabilities are.

In the case of Dart Random(), the breakthrough came in finding math_patch.dart during further code review. This source code file contains not just math functions, but also special implementations of the Random class in pure Dart instead of C++.

In this previously hidden layer, the security situation looks quite different and much less solid than before.

Code math_patch.dart:

class _Random implements Random {
  // Internal state of the random number generator.
  @pragma("vm:entry-point")
  final Uint32List _state;
  static const _kSTATE_LO = 0;
  static const _kSTATE_HI = 1; // Unused in Dart code.

Instead of a single uint64_t _state of the C++ implementation, here the PRNG state is expressed as two 32 bit elements - low (LO) and high (HI) - with an ominous code comment describing that the high element is unused. Does this mean the PRNG operates on a total of 32 bits of state alone in practice? 🤔

Yes, it does!

Code math_patch.dart:

  static int _nextSeed() {
    // Trigger the PRNG once to change the internal state.
    _prng._nextState();
    return _prng._state[_kSTATE_LO];
  }

As you can see, the seed handling throws away the higher 32 bits by only return the lower 32 bits. 🔥

More fundamentally, it becomes clear that Dart is actually using two nested PRNGs. The outer one (in pure C++, shown before) has 64 bits of state and is seeded with 64 bits of entropy, but the inner one (in Dart & some C++, shown here) has only 32 bits of effective state and is seeded with a truncated 32 bits of output from the outer PRNG.

This is somewhat bizarre, and clearly really lucky for us on the researcher side - but bad for any real world users who are caught in some insecure usage. We can only speculate why this particular design was chosen, but we expect it had something to do with the Dart virtual machine boundaries, the desire to write as much fundamental code in Dart as possible, and the previously discussed Javascript runtime environment restrictions.

Code math_patch.dart:

  // This is a native to prevent 64-bit operations in Dart, which
  // fail with --throw_on_javascript_int_overflow.
  // TODO(regis): Implement here in Dart and remove native in math.cc.
  static Uint32List _setupSeed(int seed) native "Random_setupSeed";
  // Get a seed from the VM's random number provider.
  static Uint32List _initialSeed() native "Random_initialSeed";

Brute-Forcing Dart Random()

Regardless of the reasons for Dart's dual-stage PRNG design, we can now effectively break most of the remaining defensive characteristics by peeling off the outer PRNG layer that is more difficult to attack. Whatever the outer layer does, the inner PRNG only uses it for an initial 32 bit request for seeding data. Instead of trying to exactly simulate the outer PRNG to determine what value that was, we can treat the inner PRNG's smaller seeding state space as coming from a perfect but limited RNG source and directly brute-force through all combinations!

To spell this out, instead of trying 18446744073709551616 iterations of the outer PRNG, we only have to try 4294967296 of the inner PRNG, which is clearly a lot less work.

In our hands-on research, we re-implemented the relevant components of the inner Dart PRNG in Rust to avoid any runtime dependency on Dart, to experiment with the behavior and to ensure fast computation.

This involved some intermediary computation details that aren't important for understanding the general vulnerability, such as

• The extra four rounds of "cranking" during PRNG seeding
• The mix64() function to spread 32 bits into the 64 bit range
• The nextInt() "fast case" used by Cake Wallet via random.nextInt(256)

The main takeaway message is that the non-secure Random() variant in Dart on Android, as used by the vulnerable Cake Wallet app, can be brute-forced in practice on a single machine in short order since it has only 2^32 potential starting states.

Reconstructing Cake Wallet Keys

Now that we know the algorithm to generate the 2^32 different raw byte chunks that make up all possible PRNG outputs Cake Wallet can ever get during the key generation, it's time to focus back on the Cake Wallet code.

Code bitcoin_mnemonic.dart:

String generateMnemonic({int strength = 132, String prefix = segwit}) {
  final wordBitlen = logBase(wordlist.length, 2).ceil();
  final wordCount = strength / wordBitlen;
  final byteCount = ((wordCount * wordBitlen).ceil() / 8).ceil();
  var result = '';

  do {
    final bytes = randomBytes(byteCount);
    maskBytes(bytes, strength);
    result = encode(bytes);
  } while (!prefixMatches(result, [prefix]).first);

  return result;
}

Some explanations are in order. Most wallet software uses the BIP39 standard to standardize, encode and checksum the master private key of a cryptocurrency wallet into the form of a human readable passphrase, the so-called "mnemonic" or "seed phrase". Cake Wallet uses the Electrum seed phrase, a different standard that is derived from BIP39 but intentionally incompatible with it.

We won't go into all the details and differences between the two, but one important design aspect of the Electrum seed phrase in this context is how it implements checksums over the seed phrase.

Where BIP39 reserves some bits in the raw encoded data purely for checksums and computes them based on the selected key (12 word mnemonics: 128 key bits + 4 checksum bits = 132 bits total), the Electrum seed format uses all available bits for the key (12 word mnemonics: 132 key bits total) and then applies certain restrictions on which keys are considered valid, depending on the intended Bitcoin usage.

The vulnerable Cake Wallet version used a hardcoded mnemonic length of 12 words = 132 bits for this, see int strength = 132. Since 132 bits aren't directly on a byte boundary, some extra masking via maskBytes(bytes, strength) is required after fetching 136 bits of output from the PRNG to cut off the extra bits.

Consider prefixMatches(), which is called with the single string prefix target const segwit = '100';

Code:

List<bool> prefixMatches(String source, List<String> prefixes) {
  final hmacSha512 = Hmac(sha512, utf8.encode('Seed version'));
  final digest = hmacSha512.convert(utf8.encode(normalizeText(source)));
  final hx = digest.toString();

  return prefixes.map((prefix) => hx.startsWith(prefix.toLowerCase())).toList();
}

In effect, this is a complex way of asking "if I HMAC-hash the private key I just generated, does the resulting hash value start with these specific bits I'm interested in, which serve as a checksum?" Assuming that the HMAC-SHA512 hash result values are effectively random, and since we're asking for the exact hex prefix of 0x100 (0001 0000 0000 in binary notation) with a length of 12 bits, only 1 in 2^12 results will - on average - satisfy this requirement.

In other words, the wallet generation code loop will - on average - instantiate a new Random() PRNG for 4096 times, rejecting the first 4095 of them because the generated key doesn't have the right hash properties.

Here is the loop code again:

Code bitcoin_mnemonic.dart

  do {
    final bytes = randomBytes(byteCount);
    maskBytes(bytes, strength);
    result = encode(bytes);
  } while (!prefixMatches(result, [prefix]).first);

Extra observant readers may have already spotted the implications of this checksum-and-reject mechanism, combined with picking a newly-seeded PRNG after each rejection. Since the checksum mechanism is necessarily deterministic and will always reject the same inputs, and since the Dart PRNG is deterministic with regards to a certain seed, this acts as a giant filter on top of the already very-limited Random() PRNG state space. While there are 2^32 potential private keys that randomBytes(byteCount); can return, the vast majority of them will not get accepted by prefixMatches(result, [prefix]).first, leading to another roll of the (loaded) PRNG dice - a behavior that is the same across all vulnerable Cake Wallet instances.

In effect, this reduces the number of possible weak Cake Wallet private keys to about 2^32 / 2^12 = 2^20 keys. We counted 1049308, to be exact.

This is extremely bad. 💥💥

Let that number sink in for a moment - you're asking a security software to generate a private key with over 120 bits of non-guessable entropy, and you're getting .. 20 bits. 😱

Real World Implications

This is already a very long post, so the observations on historical usage, a timeline and other details will follow in a future research update.

We're sad to say that there are still some users of this range of extremely weak Bitcoin wallets who are acutely at risk.

Finding weak wallets with remaining balances is a real ethical dilemma. As mentioned before, this vulnerability has now been widely public for three years after the vendor disclosed it (long before we were involved). We made a number of efforts to try and reduce the impact on remaining vulnerable wallet owners, including

• Confidential discussions with the vendor, including on how to inform affected users
• Helping the vendor to roll out a special app update to detect and warn most victims where still possible
• Publishing the generic [research update #6]({% link _posts/2024-02-13-research-update-6.md %}) to raise awareness of the issue without directly revealing technical details
• Delaying disclosure of this issue for many months to give victims additional time

Unfortunately, we've now exhausted our options and decided it's finally time to publish.

As with our previous work on Milk Sad, we did not move any funds in this range that we didn't legally own. We therefore cannot help with getting any funds back that were moved illegitimately by others.

Summary & Outlook

In this research update, we've shown a broad range of technical details on the Cake Wallet PRNG vulnerability, including security information that has not been public before. We hope this helps to improve the public understanding of the known-insecure Dart Random() PRNG and provides another useful case study on the catastrophic impacts of badly chosen PRNG mechanisms during cryptographic key generation.

We will discuss other details of this work in a future research update iteration.

If you would like to see more articles with tech-heavy focus on our work or have something interesting to share, [let us know]({% link index.md %}#contact)!