5

I've read the article from Unciphered about it, multiple times, and still fail to understand it.

It basically says that wallets generated by the BitcoinJS front-end library from 2011 to 2015 are vulnerable because of poor randomness generation. (Especially those generated between May 4, 2011 to March 2012.)

But it's really vague on explaining what the actual exploit is. It could be just summarized as: it used Math.random() for randomness before March 2014, and it is a bad function

Let's look at the initial commit from March 4, 2011 : eckey.js is used for generating the private key, while rng.js and prng4.js in the jsbn folder are used for harvesting randomness.

rng.js

If rng_pool is not already initialized, it is filled with random values from Math.random()

while(rng_pptr < rng_psize) {  // extract some randomness from Math.random()
    t = Math.floor(65536 * Math.random());
    rng_pool[rng_pptr++] = t >>> 8;
    rng_pool[rng_pptr++] = t & 255;
  }

Math.random() according to the article has a cycle of 2^60 values before they repeat. The article also mentions that it fails modern benchmark tests, but I'm not sure about them.

Is Math.random() the whole weakness of the story? What is the weakness actually about?

Later, the time in milliseconds is seeded to the pool

function rng_seed_time() {
  rng_seed_int(new Date().getTime());
}

And later for

SecureRandom.prototype.nextBytes = rng_get_bytes;

we initialize the state, and pass the pool as the key into the RC4 cipher

rng_state = prng_newstate();
rng_state.init(rng_pool);

from prng4.js

prng4.js

which creates a 256 value array

this.S = new Array();

and fills it with the loop

for(i = 0; i < 256; ++i) {
    j = (j + this.S[i] + key[i % key.length]) & 255;
    t = this.S[i];
    this.S[i] = this.S[j];
    this.S[j] = t;
  }

eckey.js

eckey.js uses SecureRandom() and creates our private key

var rng = new SecureRandom();
....
this.priv = ECDSA.getBigRandom(n);

But again, this tells us next to nothing about the actual vulnerability and what attacks might be used. Unciphered's article suggests that if we have GUID or IV (I guess that's a public key?), then we can do the work with just 2^32 to 2^64 values (2^48 most commonly).

Also, not sure about the clicks being added in the entropy pool, apart from:

<body onClick='rng_seed_time();' onKeyPress='rng_seed_time();'> comment.

In what way, other things are added into entropy pool apart from the initial timestamp seed?

Edit July 23, 2024:

Sorry, I forgot that ecdsa.js also has its own context

ecdsa.js

Basically, getBigRandom() method is realized in this file with rng = new SecureRandom();

Bitcoin.ECDSA = (function () {
var ecparams = getSECCurveByName("secp256k1");
var rng = new SecureRandom();
....
var ECDSA = {
getBigRandom: function (limit) {
return new BigInteger(limit.bitLength(), rng)
.mod(limit.subtract(BigInteger.ONE))
.add(BigInteger.ONE)
;
},

.

Improve this question

2 Answers 2

Reset to default
11

The TL;DR answer: The problem is that due to a bug, the pseudo random number generator is only seeded with Math.random() and the current time. Both inputs can be guessed/recovered by an attacker. The generator itself is entirely deterministic, so once the seed is known, the attacker can calculate every possible pseudorandom number of the generator – and all keys derived from those numbers.

There are two types of pseudorandom number generators (PRNGs). In general, PRNGs are only designed to pass statistical randomness tests. They do not guarantee any properties beyond this, so it's perfectly possible that the internal state of the PRNG can be guessed, and that future values can be predicted based on the known state. In some use cases, this may be perfectly fine. But in security contexts where pseudorandom numbers are used to generate keys or other secrets, it's obviously crucial that the numbers cannot be predicted. This is why cryptographically secure random number generators (CSPRNGs) must be used in such cases. They're specifically designed to produce unpredictable numbers, e.g., by collecting entropy from different sources (like mouse movements) and using cryptographic algorithms like stream ciphers for the number calculations.

The authors of BitcoinJS did actually try to implement a CSPRNG. If you look at the source code of the vulnerable 0.1.3 version, they attempt to initialize an entropy pool with the window.crypto.random function (which is a CSPRNG), and then they use the stream cipher RC4 to calculate pseudorandom numbers.

However, the problem is that window.crypto.random isn't implemented in all browsers (and wasn't back then either). In this case, the library falls back to initializing the pool with Math.random and the current time. Both are completely unsuitable for security purposes. The current time can be guessed, and Math.random is a simple non-secure PRNG like Xorshift128 where the internal state can be recovered with a constraint solver and then used to simply calculate any past or future pseudorandom number.

Improve this answer
7
  • Let me get this straight. In rng.js , rng_pool is only seeded with Math.random() in the while(rng_pptr < rng_psize) loop and with Date().getTime() in rng_seed_time() function i.e. these are the only sources of entropy. Then we initialize the state with that pool rng_state.init(rng_pool); and all of this in order to create SecureRandom() {} class which will eventually be used to generate the private key like this.priv = ECDSA.getBigRandom(n) in eckey.js. What's the difference between the pool and the state (rng_pool and rng_state)?
    – Maltoon Yezi
    Commented Jul 23 at 16:51
  • @MaltoonYezi: Your understanding is correct. rng_state is a very poor name for the actual PRNG. It’s initialized with prng_newstate(), and this function creates the PRNG object (see prng4.js, for example). A far better named would have been just rng. And rng_pool is the seed for the PRNG. It’s only used once when the PRNG is created; after this it gets zeroed (see line 53 in rng.js).
    – Ja1024
    Commented Jul 23 at 17:03
  • If we look at rng_state as the object of prng_newstate(); from prng4.js then what value(s) will it be eventually assigned? Is it the array of integers like in the line 32 from prng4.js -> return this.S[(t + this.S[this.i]) & 255]; ? Then in ecdsa.js it becomes just rng in the line 128 like: var rng = new SecureRandom(); and in the line 180 we construct an integer value from that array with BigInteger(...). After this, the integer is passed to eckey.js for generating the private key?
    – Maltoon Yezi
    Commented Jul 23 at 18:29
  • @MaltoonYezi: Conceptually, SecureRandom is an abstraction layer which provides a single method: rng_get_bytes(ba), where the result is an array of ba pseudo-random bytes. This method can be implemented with different algorithms – right now, the only implementation uses RC4 to generate the bytes. The SecureRandom constructor can then be called to create a PRNG and, for example, pass the resulting object to the BigInteger constructor. This allows each ` BigInteger` instance to internally call rng_get_bytes(ba) and derive random integers from the bytes.
    – Ja1024
    Commented Jul 23 at 19:54
  • Do the bytes have the data type of Uint8Array? Hmmmmm.... Would building like a brute forcer, or something else, be helpful in terms of understanding the given code? I am getting better at reading it, but still feeling like I don't have the intuition for it
    – Maltoon Yezi
    Commented Jul 24 at 17:44
3

Normally, a bitcoin private key should be a randomly generated value in a 256 bit space. This is because it is practically impossible for an attacker to use brute force to crack a random value in a 256-bit space.

But, because of the flaws in bitcoinjs library that the article highlights (stemming from the use of math.random()), private keys generated by this library (under certain conditions) are actually in a space that is much smaller than 256 bits.

So, as to:

But [the article] is really vague on explaining what the actual exploit is.

The exploit is that it may be feasible for an attacker to use brute force to crack private keys generated by this library.

Improve this answer
4
  • >*space that is much smaller than 256 bits*. Like How smaller? Like between 32 to 64 bits?
    – Maltoon Yezi
    Commented Jul 23 at 16:54
  • It’s not really a problem of a reduced key space. The issue is that the seed for the library’s custom PRNG can be recovered. With this knowledge, it’s possible to calculate the private keys rather than having to find them through a brute-force search.
    – Ja1024
    Commented Jul 23 at 17:35
  • @MaltoonYezi, According to the article by Unciphered, it depends on various conditions. But, see the email referenced in the article, where it reads 'In some known configurations this system has substantially less than 48 bits of entropy'. Also, see where it reads 'Unciphered has successfully performed recovery of wallets generated using BitcoinJS derived software. In such cases, we have typically had to perform 48 bits of work'.
    – mti2935
    Commented Jul 23 at 17:36
  • @mti2935 Ok, thank you!
    – Maltoon Yezi
    Commented Jul 23 at 18:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .