The Journey
Several months ago I encountered an internet stranger who sought information on how to test thousands of private keys automatically to see if they match a certain bitcoin address. The task sounded simple enough, so I started asking questions to familiarize myself with the problem.
Eljef Azo had generated a bitcoin address and private key using an online generator WalletGenerator.net. The address was 1GsAFeF3S5Bt1JU6CjjAzNtfgnzoXkyUnh
I was able to see that he had received 4 transactions of about 300k each.
I inspected the javascript on WalletGenerator.net which forwards to .com and found that I can test if a private matches with the target address via the following snippet
var test = ”5K2Jsi3DivvamoQfp2LUvk1TGxyL8CdfmXAW7j7C1TV4XkXk4Pj”; try{ testKeyObj = new Bitcoin.ECKey(test); }catch(er){ // invalid private key } if (testKeyObj){ var testAddr = testKeyObj.getBitcoinAddress(false); if (testApproxEquality(testAddr,targetAddr)) { console.log("found matching key\n" + test + "\nat_index: " + at_index); } }
To simplify the process I decided to run the tests directly within the web site’s environment.
Fatefully, I cached a local copy of the site early in the process.
Early signs
When the code I sent Mr. Azo yielded no matches, I dug deeper and found that WalletGenerator.net can give up to 60 different addresses for each private key.
// yields a different result every time var testAddr = testKeyObj.getBitcoinAddress(false);
This did not raise suspicions because I was thinking along the lines of standard derivative address schemes. I imagined that this website is serving the first n addresses from a randomly chosen starting point.
In hindsight, this is erroneous thinking because this site does not communicate in terms of any standard derivation schemes.
Reinforcing my suspicion, I learned that the addresses begin wrapping after the 60th one. So a small code modification will be able to account for their "derivation scheme" as follows:
// check the next 60 addresses; since they loop, we have full coverage. for (var ano = 0; ano < 60; ano++){ var testAddr = testKeyObj.getBitcoinAddress(false); if (testApproxEquality(testAddr,targetAddr)) { console.log("found matching key\n" + test + "\nat_index: " + at_index); } } }
This did not yield any results either.
Fanning out
So I offered a more thorough approach which will test every given key plus every possible single typo
function testWithSingleError(t){ for (var i = 1; i < t.length; i++){ baseKeyTest(t); var partA = t.substr(0, i); var partB = t.substr(i+1); for (var c = 0; c < 58; c++){ var alt = partA + chars[c] + partB; baseKeyTest(alt); } } }
This turned every test into 2900 different tests.
When it yielded nothing, I tried a method which checks for every possible combination of two typos
function testWithDualErrors(t){ for (var i = 1; i < t.length; i++){ var partA = t.substr(0, i); var partB = t.substr(i+1); for (var c = 0; c < 58; c++){ // chars.length = 58 var test = partA + chars[c] + partB; for (var i2 = i+1; i2 < t.length; i2++){ var partA2 = test.substr(0, i2); var partB2 = test.substr(i2+1); for (var c2 = 0; c2 < 58; c2++){ // chars.length = 58 var test2 = partA2 + chars[c2] + partB2; if (test2 == t) continue; baseKeyTest(test2); } } } } }
This turned every test into 8.4 million tests. Running the code against the list of potential keys was a slow process.
I spread the work across multiple browser tabs for lazy man's multi-threading but it was still projected to take half a year
Trusted Status
At this point Mr. Azo decided he trusts me enough (or he's had enough) and he would send me the key material he had so I can work on it at my own pace.
FASCINATING
I was concerned about having his key material because in the event of someone else recovering and stealing the sats, I could be implicated as a suspect. Dear reader, be aware of the problem here.
Here is where I realized that the address itself could be a typo, and explains why I'm using a partial matching test
function testApproxEquality(a,b){ // allows for up to half the characters to be typos var diffs = 0; for (var i = 0; i < 34; i++){ if (a[i] != b[i]) diffs++; if (diffs > 12) break; } return (diffs < 13); }
I slogged through the search, allowing my PC to churn away at the task whenever I wasn't using it, periodically sending an update to Mr. Azo.
Getting Performant
The performance bottleneck was the sha256 hash inside the following call, which checks if a key is valid inside the website source.
new Bitcoin.ECKey(test);
Once I passed 40% progress mark, I began dreaming of implementing the code in a native language an running the hashes on my GPU.
By the time I reached 70% progress, I was already compiling native code for running on a GPU.
Hello World
Now I need to get hashes pumping through here by the millions. But first I need to get to the bottom of that pesky key derivation process...As I was digging into the source, along with the associated GitHub project, I discovered a potential issue. I decided to bookmark it and share with Mr. Azo.
Before I had a chance though, I received the following from him:
Have you found it? The address is empty
Investigation
A look at the draining transaction shows that the address was swept along with many others for a total of .41482171 BTC then rapidly consolidated through several addresses. I am not equipped to do blockchain analysis to any meaningful extent. I just know this attacker controls more bitcoin than I could ever dream of acquiring.
As for walletgenerator.net forwards to .com
I realized after wasting much time, that my cached version of the site generates the same list of 60 addresses over and over.
The output addresses of the following snippet should never repeat in a thousand years.
// WARNING: may take a few moments of processing var s = ""; for ( var i = 0 ; i <500; i++){ ninja.wallets.singlewallet.generateNewAddressAndKey(); s += "\n" + document.getElementById("btcaddress").innerHTML; }console.log (s);
You can test it by visiting the oft-mentioned web site, hit F12 or open dev tools your way, and copy the snippet into the console. hit enter and wait. Maybe copy the list into a spreadsheet and sort it, or copy one address and search for a repeat.
At the time of this writing, I checked the walletgenerator.net forwards to .com site and noticed that it no longer emits a repeating sequence of 60 addresses.
The version of the site that I have cached DOES repeat.
Avoiding this disaster
-
If you must use a website-based key generator, use it offline and verify that the addresses given match with your private key material by testing several given addresses using known-good apps.
-
Use a seed phrase based scheme to eliminate case sensitive key storage
-
Etch or stamp your private key material into steel
-
Find a way to ensure that you can sign a valid spend transaction of a UTXO where you are accumulating significant amounts
Final Notes
Disclosure: Mr. Azo gave me permission to keep a significant portion of the stack if I find the address, for this reason the sats zapped to this article are split 50% with him. Eljef Azo is down by over 1.34 million sats and from what I gathered, he wasn’t exactly swimming in cash so if you find the grace to pitch him some sats, please. If for whatever reason, you want me out of the equation, you can exclude me by sending them directly to @Longtermwizard
I do not fear being implicated in this scam because I feel certain that the key material given does not correspond with Mr. Azo’s address by design.
I believe the scammer rotated out the scamming web site code periodically because, of the 60 addresses that repeat, none of them match Mr. Azo’s address.
If you are interested in the site I have cached or more of the test code, let me know.