Update #17 - PHPCoinAddress Wallets - Part 1

Research into the vulnerable PHPCoinAddress wallet software and different generations of PHP random number generation.

PHPCoinAddress

Background and History

Over the past several years of Milk Sad research, we extensively searched for weak cryptocurrency wallets with keys derived from non-cryptographic pseudo-random number generators (PRNGs). Among the many different PRNG algorithms, we most heavily analyzed the 32-bit version of Mersenne Twister (MT19937-32), which is especially susceptible to brute-force attacks through its restricted seeding range (among other bad security properties). Since Mersenne Twister was bundled with many different programming languages and environments, it saw a diverse range of accidental or negligent usage for key generation, such as the vulnerability that prompted the initial Milk Sad research.

I recently came across old open-source code of PHPCoinAddress, a wallet generation software library that uses Mersenne Twister in a way we hadn’t seen or analyzed before. This intrigued me to take a closer look!
As the name implies, PHPCoinAddress is a wallet generation and handling software written in PHP. It was first released in early 2013 and announced in May of 2013 on bitcointalk.org:

PHPCoinAddress is a PHP Object that creates public/private key pairs for Bitcoin and many other cryptocoins.

PHPCoinAddress is intended to be easy to integrate into other PHP projects. More info: https://github.com/zamgo/PHPCoinAddress […]

Unlike most software wallets, PHPCoinAddress was apparently designed for use on a webserver instead of a personal computer or smartphone. Its primary purpose seems to have been to frequently generate new wallets as destination addresses for purchases in online shops that accept cryptocurrencies. It focused on Bitcoin, Litecoin, and other “early” cryptocurrencies that were common in 2013, and it predates Ethereum.

Within a few months of introduction, the severe security vulnerability through use of Mersenne Twister for the wallet generation was called out by bitcointalk.org user Abdussamad on December 13th 2013:

The private keys generated by this script are not safe. You can see on line 240 of phpcoinaddress.php that mt_rand is used to generate the private key. That function is not safe for cryptographic use: […]

Despite this public disclosure, usage of PHPCoinAddress has clearly continued far beyond December 2013, even though the original developer apparently abandoned the project as early as 2014.

Today, the original repository github.com/zamgo/PHPCoinAddress is unavailable, but other unsafe forks of it like coinhelper/PHPCoinAddress remain. There is at least one fork at FuzzyBearBTC/PHPCoinAddress where the problematic random generation function has been replaced, but it’s still marked as insecure by its author.

The coinables/Bitcoin-NoAPI-Shopping-Cart project used the insecure PHPCoinAddress library for its key generation. I suspect it’s one of the sources for the Bitcoin wallets found in the wild, and its README.md now acknowledges that it was vulnerable and led to thefts:

# Users have lost funds using the # PHPCoinAddress library

This was discussed publicly in 2017, several years since the underlying vulnerability had been made public.

The Problematic Code

The insecure PRNG usage happens right at the beginning of create_key_pair(), calling PHP’s mt_rand() API:

public static function create_key_pair() {

    $privBin = '';
    for ($i = 0; $i < 32; $i++) { $privBin .= chr(mt_rand(0, $i ? 0xff : 0xfe)); }
    $point = Point::mul(bcmath_Utils::bin2bc("\x00" . $privBin), self::$secp256k1_G);
[...]

Source on GitHub, more on this below.

Key Generation Behavior

What makes the PHPCoinAddress wallets different from other MT19937 usage we investigated in the past is the combination of multiple factors:

1. Raw generation of secp256k1 keys directly from PRNG outputs (= no usage of BIP32 or BIP39 key derivation standards)
2. Usage of PHP’s mt_rand() -> version dependent behavior
3. PHP’s mt_rand() integer range handling -> version dependent behavior
4. Special PHPCoinAddress PRNG request pattern for the first private key byte
5. Use of PRNG output stream offsets (= no forced PRNG reseeding)

To find the generated wallets, we need to understand and re-implement all of those steps. The next sections give an overview for some of them.

PHP mt_rand() behavior

To my surprise, it turns out that PHP has substantially changed the underlying PRNG behavior of their mt_rand() function at least three times over the last two decades, in part to fix coding mistakes in their original implementation:

The PHP code calling mt_rand() will generate different keys depending on the local PHP engine version’s implementation, settings and state. This means that there are effectively three distinct ways that weak wallets can be generated by the same PHP code. According to my research, only the two newer variants are practically relevant for the PHPCoinAddress vulnerability, likely because the older PHP versions before 5.2.1 were no longer in use on any of the relevant servers once the vulnerable PHPCoinAddress software was released.

Additionally, the code within mt_rand() that truncates the 32-bit integer output of each PRNG result into the requested integer number range is also defined on the engine side and changed substantially between some of these versions. I’ll describe some implications of this later.

Special First Byte Handling

Take a look at this particular core section in the key generation code:

$privBin = '';
for ($i = 0; $i < 32; $i++) { $privBin .= chr(mt_rand(0, $i ? 0xff : 0xfe)); }

This code is designed to fill a variable with 32 byte of pseudorandom data by incrementally appending an extra byte at a time. The intended use of privBin is to serve as the 256 bit key material of a secp256k1 elliptic curve key later in the function.

An important detail of the generation code is $i ? 0xff : 0xfe for the second mt_rand(int $min, int $max) parameter, which behaves differently for $i == 0 than all other loop iteration counts where $i != 0. In other words, for the first byte of the generated private key, instead of requesting a random integer in the interval 0 to 255 (0xff), it only requests a number in the interval 0 to 254 (0xfe).

I suspect the code author intended this as a (primitive) way to ensure the generated private key would never exceed the secp256k1 key curve order and create an invalid key, since that can only happen if the first byte is 0xff, though this is a very blunt way of solving this problem that also avoids a lot of valid keys.

This mt_rand() calling detail is important since depending on the mt_rand() implementation, requesting different integer intervals can lead to very different outputs, and hence different private key “ranges”.

Results

This article is split in multiple parts. Search results will be presented in part two. Stay tuned for more!