Randstorm: You Can’t Patch a House of Cards
For a less technical breakdown of Randstorm please visit: https://www.randstorm.com
“The best exploit chain is the supply chain” - TCrown
Over the last 22 months, Unciphered has been working on a vulnerability which affected BitcoinJS, a popular package for the browser based generation of cryptocurrency wallets, as well as products and projects built from this software. Over a period of years, this vulnerability caused the generation of a significant number of vulnerable cryptocurrency wallets.
The source of the vulnerability is the SecureRandom() function found in the JSBN javascript library, combined with weaknesses that existed in major browser implementations of Math.random(). The JSBN library was utilized by BitcoinJS until March of 2014. Other projects incorporated early versions of BitcoinJS for the generation of Bitcoin and other cryptocurrency wallets. As such, it is difficult to calculate the exact time frame for the vulnerability, but we have observed vulnerable wallets being generated from 2011-2015. We can confirm that this vulnerability is exploitable, however, the amount of work necessary to exploit wallets varies significantly and, in general, considerably increases over time. That is to say, as a rule, impacted wallets generated in 2014 are substantially more difficult to attack than impacted wallets generated in 2012.
We have been coordinating disclosure with multiple entities and, as a result, millions of users have been alerted. In the event that it is possible an individual has assets held in an affected wallet, they should be moved to a newly generated wallet created with trusted software.
Vulnerability
In January of 2022, Unciphered was performing work for a customer that was locked out of a Blockchain.com (previously Blockchain.info) Bitcoin wallet. While examining this wallet, and avenues for recovery, it led us to (re)discover a potential issue in wallets generated by BitcoinJS (and derivative projects) between 2011 - 2015. This potentially affects millions of cryptocurrency wallets that were generated in the 2011-2015 timeframe. The value of assets still in those wallets is sizable. Unciphered engaged affected parties and has been working for over a year on remediating the issue. We weren’t, however, the first ones to notice this.
BitcoinJS (or bitcoinjs-lib) is a javascript implementation of Bitcoin. The first block of the Bitcoin blockchain was minted in January of 2009. The first commit of BitcoinJS was a little over two years later in May of 2011.
You can view the 0.1.3 version here - https://cdnjs.cloudflare.com/ajax/libs/bitcoinjs-lib/0.1.3/bitcoinjs-min.js
Unfortunately, for an incredibly popular library, there was an issue in BitcoinJS.
On the 6th of April, 2018, an individual calling themselves “Ketamine” sent an email from <ketamine@national.shitposting.agency> to the bitcoin-dev mailing list titled, “Multiple vulnerabilities in SecureRandom(), numerous cryptocurrency products affected.” In this post, the user states:
“A significant number of past and current cryptocurrency products
contain a JavaScript class named SecureRandom(), containing both
entropy collection and a PRNG. The entropy collection and the RNG
itself are both deficient to the degree that key material can be
recovered by a third party with medium complexity.”
And goes on to say:
“The most common variations of the library attempts to collect entropy
from window.crypto's CSPRNG, but due to a type error in a comparison
this function is silently stepped over without failing. Entropy is
subsequently gathered from math.Random (a 48bit linear congruential
generator, seeded by the time in some browsers), and a single
execution of a medium resolution timer. In some known configurations
this system has substantially less than 48 bits of entropy.”
In the same mailing list thread, Mustafa Al-Bassam (also known as “tflow” from LulzSec) comments:
“In practice though, this doesn't really matter, because navigator.appVersion < "5" returns true anyway for old browsers. The real issue is that modern browsers don't have window.crypto.random defined, so Bitcoin wallets using a pre-2013 version of jsbn may not be using a CSPRNG, when run on a modern browser.”
He appears to be referencing the piece of code below:
from https://github.com/bitcoinjs/bitcoinjs-lib/releases/tag/0.1.3 in bitcoinjs-lib-0.1.3/build/bitcoinjs-min.js
The origin of this code is Tom Wu’s jsbn, “Javascript Big Number,” library which he describes as,
“a fast, portable implementation of large-number math in pure JavaScript, enabling public-key crypto and other applications on desktop and mobile browsers.”
Specifically, the SecureRandom function is found in rng.js, which he describes as a:
“rudimentary entropy collector and RNG interface, requires a PRNG backend to define prng_newstate().”
Tom Wu’s JSBN is included in the src directory of the bitcoinjs-lib-0.1.3.tar.gz. It appears that BitcoinJS stopped using JSBN in March of 2014, however, we have found other projects, which incorporated their code, continuing to use the vulnerable function into 2015. Due to the widespread adoption of early BitcoinJS code, we still see vulnerable wallets being generated into 2015.
As noted, in the original disclosure, an unfortunate issue in the JSBN code imported into BitcoinJS means that while there is an attempt to gather entropy from window.crypto.random, this property is not a standard part of the modern Web Cryptography API or JavaScript. In the 2009 paper, “Symmetric Cryptography in Javascript” by Emily Stark, Michael Hamburg, Dan Boneh they say:
“Consequently Math.random cannot be trusted as the only source of entropy for our library. An alternative is to use the dedicated cryptographic PRNG window.crypto.random, which first appeared in Netscape 4. If present, this function would supply all the entropy we need. Unfortunately, as of this writing, window.crypto.random is not implemented in any major browser.”
While window.crypto.random did exist in Netscape Navigator 4.x, by the time that BitcoinJS was being used, the window.crypto.random function did not exist in the browsers being used to generate cryptocurrency wallets. As such, this call in JSBN fails silently when used by early versions of BitcoinJS and entropy is subsequently gathered from Math.random(). While Math.random() should never be used to generate cryptographic key materials, in the 2011-2015 time window, Math.random(), on all major browsers, had problems.
On November 19th of 2015, Mike Malone published the blog post, “TIFU by using Math.random()” where he details issues with the Math.random() implementation in the V8 JavaScript engine (used by Chrome). His company was using Math.random() to generate API identifiers. Using a 22-character identifier, he expects a collision of 1 in 6 billion requests, but discovered instead that “there would be a 50% chance of collision after generating just 30,000 identifiers.” He also notes, in passing, that Mozilla’s use of LCG (linear congruential generator) is also problematic and they should change their algorithm. As a result of this post, Jan de Mooij from Mozilla looks into the issue and writes the blog posts “Math.random() and 32-bit precision” & “Testing Math.random(): Crushing the browser.” He describes the algorithm used by FireFox as, "imported from Java decades ago," and theorizes that, “Maybe Microsoft imported the same algorithm from somewhere?” He also writes, “Results confirm most browsers currently don't use very strong RNGs for Math.random().” He points out that Safari’s GameRand RNG is “extremely fast but very weak.” and “This means the result of the RNG is always one of about 4.2 billion different numbers, instead of 9007199 billion (2^53). In other words, it can generate 0.00005% of all numbers an ideal RNG can generate.”
He files a bug against WebKit in which he advises that they move to a “better RNG.”
from Bug 151641 - Use a better RNG for Math.random()
Subsequently, the major browsers changed their Math.random() algorithms to XorShift128+ by 2016. A summary of these issues can be found in the blog post, “Randomness in the Web Browser.”
Due to the silent failure while attempting to gather entropy from window.crypto.random, the BitcoinJS code (imported from JSBN) falls back on weak pseudo-random number generation. There is a recommendation in JSBN’s rng.js that additional entropy be gathered from keypresses and mouse clicks:
Some of the BitcoinJS dependent projects end up following this advice (more on that soon). This prevents the generated key material relying solely on entropy from Math.random() but, depending on the amount of entropy gathered, this may still have led to the generation of attackable keys.
It is worth noting that the original notification of the vulnerability on the Bitcoin-Dev mailing list does not explicitly mention the JSBN library, the BitcoinJS project, nor any of the subsequent projects (such as Blockchain.info, later blockchain.com) which utilize BitcoinJS.
The original post does, however, advise:
“Necessary action:
* identify and move all funds stored using SecureRandom()
* rotate all key material generated by, or has come into contact
with any piece of software using SecureRandom()
* do not write cryptographic tools in non-type safe languages
* don't take the output of a CSPRNG and pass it through RC4”
As such, we must view the first identification of the weak code and call for affected users to move their funds as having happened on Fri, 06 Apr 2018.
Impact
The description of BitcoinJS on yarnpkg is:
“The pure JavaScript Bitcoin library for node.js and browsers. A continued implementation of the original 0.1.3 version used by over a million wallet users; the backbone for almost all Bitcoin web wallets in production today.”
from bitcoinjs-lib-0.1.3/build/bitcoinjs-min.js
BitcoinJS was used by many projects in the early 2010s. Below is a non-exhaustive list of projects which used BitcoinJS and their current status:
This list of projects was derived from release notes in various BitcoinJS releases, https://www.npmjs.com/package/bitcoinjs-lib/v/3.0.2, and https://classic.yarnpkg.com/en/package/@tradle/bitcoinjs-lib.
Not all of the projects mentioned above are affected, and for those that are, the impact varies depending on how long they utilized the vulnerable code, what additional mitigations they put in place, and the size of the user base at the time. In addition to the projects in the table above, there are many Github projects during the affected time frame which incorporated BitcoinJS. In most of those cases, however, utilization is unclear.
Bitcoin private keys should be generated with 256-bits of entropy; unfortunately, affected keys generated with vulnerable BitcoinJS (or dependent projects) often used less entropy than required. It is difficult to estimate the impact of this vulnerability accurately. Not all wallets were affected equally and depending on parameters of when (and how) they were generated, this could cause the entropy to be low enough for an organized, funded attacker to exploit.
Typically, in order for this attack to be feasible, an attacker would need something which was generated from Math.random() at the time of wallet generation - this would typically be the wallet GUID or IV. This reduces the amount of necessary work anywhere from 32 to 64-bits. From the GUID or IV we are able to derive the RNG's state by exploiting weaknesses found in the RNGs used in nearly all browsers within this time period. In most cases, this allows us to generate all prior and future values generated by the RNG. This includes the initial entropy pool which is the basis for private key generation.
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. These are wallets generated prior to March of 2012. Over time, the difficulty of performing these attacks becomes harder as projects begin incorporating additional sources of entropy into their wallet generation. For instance, in March of 2012, Blockchain.info (now Blockchain.com) significantly increased the amount of entropy gathered from user input during key generation. Prior to March of 2012, up to 48 bits of additional entropy was gathered during the wallet generation from user input. After March of 2012, the attack becomes significantly harder as they begin to gather, on average, 6-12 bits of additional entropy per keystroke and mouse click. This entropy is gathered from the timestamp (in milliseconds) of the user input. Without knowing anything about the time the wallet was created, the initial timestamp that is added to the entropy pool adds around 32 bits. Then, the amount of variability that exists in the timing between keystrokes after the page is loaded determines how many timestamp possibilities need to be guessed to properly reconstruct the entropy pool which was used to generate the user's private key. For example, trying all possible timestamps between two keypresses with a variability range of 250ms requires trying 250 values (~8-bit) whereas exhausting a range of 16 seconds requires trying around 16k values (~14-bit) per keystroke. In 2014, Blockchain.info began adding additional entropy from mouse movements, which again makes the attack exponentially more difficult. Bitaddress.org, a website which uses BitcoinJS for the generation of Bitcoin wallets, has gathered entropy from keypresses, mouse clicks, and mouse movements since November of 2011.
Despite such measures, there are still situations where cryptographically weak wallets could be generated. In the scenario where passwords are copied and pasted (such as if a password generator was used), entropy would not be gathered from keystrokes and could lead to the generation of a cryptographically weak wallet.
In addition to Bitcoin, it seems probable that there are Dogecoin wallets which are also affected by this vulnerability, as well as possibly Litecoin and Zcash wallets. Dogechain.info is a popular Dogecoin explorer which offers wallet generation services, derived from BitcoinJS, starting from December of 2013. There are also forks of BitcoinJS on github for both Dogecoin and Zcash (although, it is worth noting that Zcash was first mined in late 2016). Bitpay, a cryptocurrency payment service provider founded in 2011, incorporated code from BitcoinJS (including rng.js from jsbn), into their bitcore package in release 0.1.6 in February of 2014 until release 0.9.5 in February of 2015 (release 0.9.4 does not include rng.js either, but was released on February 12, 2015 which, according to their github is after 0.9.5 which was released on February 4, 2015).
Conclusion
In context, this vulnerability is perhaps best described using the following image from XKCD:
Image from: https://xkcd.com/2347/
Almost all substantial software development projects rely on third party libraries. As articulated in the cartoon above, it is not uncommon for popular code to be reliant on projects which are under-staffed or even abandoned. BitcoinJS is currently aware of such issues. On their github page, they advise:
“We recommend every user of this library and the bitcoinjs ecosystem audit and verify any underlying code for its validity and suitability, including reviewing any and all of your project's dependencies.”
Your threat model should determine the rigor of your supply chain auditing. If you are securing financial assets, PII, or other sensitive information, then ensuring the integrity of the code you are building upon becomes critical. The issues with SecureRandom() in JSBN, Math.random() in major browsers, BitcoinJS, and subsequently an ecosystem of related projects, was not the first of this type of supply chain vulnerability.
In May of 2008, Debian announced that a patch in 2006 had broken the random number generation for OpenSSL on their platform. In the blog post, “Lessons from the Debian/OpenSSL Fiasco”, Russ Cox describes how:
“...the ssh-keygen program installed on recent Debian systems (and Debian-derived systems like Ubuntu) could only generate 32,767 different possible SSH keys of a given type and size, so there are a lot of people walking around with the same keys.”
This blog post came out 10 years before ketamine@national.shitposting.agency disclosed issues with SecureRandom() on the bitcoin-dev mailing list. That disclosure was more than 5 years ago. Unfortunately, cryptocurrency has some unique problems - you can’t patch a private key and moving assets without permission is a crime. In the event that software used to generate wallets is discovered to have created vulnerable wallets, the only solution is for the users to move the assets to new wallets, or have those users legally direct someone else to do it on their behalf. This is why we are still dealing with this vulnerability in 2023.
As detailed earlier in this post, there are multiple projects, and blockchains, that are affected. We have reached out to the vendors that we were able to identify in order to alert them to this issue. As a result of this, over a million users have received alerts advising them that their cryptocurrency wallets are potentially vulnerable and urging them to move their assets to more recently generated wallets.
At Unciphered, we can confirm that this vulnerability is exploitable. It bears repeating that not all impacted wallets were affected equally and recovery is dependent on parameters of when the wallet was generated. If you are an individual who has generated a self-custody wallet using a web browser before 2016, you should consider moving your funds to a more recently created wallet generated by trusted software.
At this time, we are not providing further details on exploitation of this vulnerability to avoid providing additional information to bad actors.
In the words of BitcoinJS, from their current github page:
“Don't use Math.random - in any way - don't.”
References:
Ketamine@national.shitposting.agency - Multiple vulnerabilities in SecureRandom(), numerous cryptocurrency products affected (2018) - https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015873.html
Nathan Willis - Randomness in the Web Browser (2015) - https://lwn.net/Articles/666407/
Mike Malone - TIFU by using Math.random() (2015) - https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d
Jan de Mooji - Math.random() and 32-bit precision (2015) - https://jandemooij.nl/blog/math-random-and-32-bit-precision/
Jan de Mooji - Testing Math.random(): Crushing the browser (2015) - https://jandemooij.nl/blog/testing-math-random-crushing-the-browser/
Russ Cox - Lessons from the Debian/OpenSSL Fiasco (2008) - https://research.swtch.com/openssl
