Wallets with Randomness Issues

This article has three layers:

1. Layer 1: The Intuition: A 256-bit lock, using only a 32-bit key
2. Layer 2: Real-World Use: Brain Wallets, Android randomness vulnerability, Profanity, Milk Sad, Trust Wallet
3. Layer 3: Entropy, CSPRNG, how to test randomness, and nonce in signatures

Layer 1: The Intuition

1.1 A 256-bit lock, a 32-bit key

An Ethereum private key is a 256-bit number, with approximately $10^{77}$ possible values—more than the number of atoms in the observable universe. Guessing it is impossible.

But what if the program generating the private key does this:

1. Takes the current time (or a 32-bit number) as a "seed";
2. Uses a standard pseudo-random number generator to calculate a 256-bit private key from that seed.

Then, while the private key looks like it has 256 bits, it actually only has $2^{32} \approx 43$ hundred million possibilities. A single graphics card could try them all in a few hours.

The security of a private key depends on its entropy (the number of truly unpredictable bits), not its length.

1.2 Three common mistakes

Layer 2: Real-World Use

The Profanity incident is particularly noteworthy: "Vanity addresses" are themselves a red flag. To obtain an address starting with 0x0000, the tool needs to generate a massive number of private keys very quickly, causing the developer to sacrifice randomness for speed.

Layer 3: Principles and Engineering

3.1 Entropy and CSPRNG

• Entropy: A measure of unpredictability. A fair coin flip provides 1 bit of entropy; a 32-bit seed provides at most 32 bits of entropy, and no amount of "shuffling" afterwards will increase it.
• CSPRNG (Cryptographically Secure Pseudo-Random Number Generator): After being provided with sufficient initial entropy, the output is indistinguishable from true randomness, and seeing previous outputs does not allow one to predict future outputs.

3.2 Why Mersenne Twister is insufficient

Mersenne Twister (MT19937) is an excellent statistical pseudo-random number generator, suitable for simulations and games. However, it is linear (based on linear recurrence over $\mathbb{F}_2$, the same class as LFSRs and stream ciphers): by observing 624 consecutive 32-bit outputs, one can reconstruct its entire internal state and predict all subsequent outputs. Even if the seed is long enough, it cannot be used for cryptography.

3.3 How to test

Randomness issues are almost impossible to detect just by looking at the output: a generator with only 32 bits of entropy will still produce output that looks random and passes statistical tests. Therefore, the focus of testing must be on code review:

1. Identify all locations where private keys, recovery phrases, nonces, or session tokens are generated;
2. Confirm that every instance directly calls the OS or the language standard library's CSPRNG;
3. Confirm that no time, PID, or counters are used as seeds, and no seeds are fixed "for reproducibility";
4. Be extra cautious in environments where "entropy might be insufficient," such as WebAssembly, embedded devices, or immediately after a virtual machine boots.

3.4 Randomness during signing

Not only does private key generation require randomness, but ECDSA also requires a random nonce $k$ for every signature; if it is repeated or predictable, the private key will be leaked. The modern approach is RFC 6979: generating $k$ deterministically using the private key and the message hash, completely removing reliance on the quality of a random number generator. Ed25519 and BLS signatures are inherently deterministic (see "Schnorr Signatures," Bilinear Pairings, and BLS Signatures).

3.5 Advice for users

• Only use well-known wallets and hardware wallets to generate recovery phrases;
• Do not use any "vanity address generators" unless they are open-source, audited, and use a CSPRNG;
• If an old wallet was generated using an unverified tool, transfer your assets to a newly generated wallet.

Summary