Bitcoin developer John Cantrell checked over a trillion combinations of words to unlock the Bitcoin address and take the money. Here’s how.
John Cantrell, the developer of Lightning Network messaging protocol Juggernaut, broke open a Bitcoin address yesterday and took the $9,300-worth of coins for himself. But this wasn’t theft, it was part of a game that he won. Now he has revealed how he did it.
As Decrypt reported yesterday, Alistair Milne, CIO of the Altana Digital Currency Fund, orchestrated a challenge on Twitter where the winner would get an entire Bitcoin. Starting in May, he periodically published hints to a 12-word seed phrase for a wallet address that contained one Bitcoin. Whoever picked up all the clues could use the phrase to unlock the Bitcoin wallet and take the Bitcoin inside.
I just published an article on how I checked over 1 trillion mnemonics in 30 hours to win @alistairmilne‘s 1 Bitcoin giveaway. I hope to pay-it-forward with a contest of my own that can’t be won by software, details to come soon! https://t.co/5TNu1Z8CpL
— John Cantrell (@JohnCantrell97) June 18, 2020
However, Milne planned to post the last three or four words in one go. This was an attempt to prevent someone from brute-forcing the address open (by continuously guessing words until a combination worked). But his plan failed. With just eight words, Cantrell was able to guess the remaining words, find the right combination and unlock the wallet.
Hacking the Bitcoin address
Before the eighth word was published, Cantrell started preparing. He wrote in his Medium post that, with eight words, there would be “roughly 1.1 trillion possible mnemonics,” that needed to be checked.
A mnemonic is a 12 or 24-word seed phrase for a Bitcoin private key that grants full access to the funds that are kept on it. There is a limited list of 2048 words such phrases could contain—but that doesn’t make hacking a Bitcoin wallet much easier.
To test a single phrase, Cantrell needed to generate a seed from the mnemonic, master private key from the seed and an address from the master private key. After writing a special program and running a few benchmarks, it turned out that the hardware he had at the time was not up to the task.
Cantrell’s laptop was only able to check around 1,250 mnemonics per second, totalling 108 million per day. “This means it would take my CPU about 25 years to generate and check the 1 trillion possibilities needed to brute force the mnemonic while only knowing 8 of the words,” he noted. And that’s if only four words are missing.
To iterate all possible 12 word seeds using the same setup would take about 309,485,009,821,345,068,724,781,056 days.
— John Cantrell (@JohnCantrell97) June 18, 2020
To solve the problem, Cantrell looked to cloud computing. He rented several dozen graphics cards on a GPU marketplace and Microsoft’s cloud computing service Azure and wrote software that would distribute the work in batches across each graphics card.
Halving through the testing of this system, the eighth word was published and the game was on. He started up the machines.
“At the peak I was testing about 40 billion mnemonics per hour. This means it should have taken around 25 hours to test the 1 trillion mnemonics. I knew that on average it should only take 50% of the time,” Cantrell said.
But he was incredibly unlucky. After testing 85% of the combinations, he had no luck. And he realized there may have been a fundamental flaw. His plan depended on the words being in the right order—which wasn’t guaranteed. If this wasn’t the case, “there would have been 8! (factorial) more possibilities,” making it impossible to crack.
Over a day of intense computations later, Cantrell “had largely given up hope that it would work” and “literally almost turned it off.”
“I couldn’t get myself to actually stop it at that point as I had come so far so I just let it continue. To my surprise a little while later that evening (at 91%) and after almost 30 hours and exactly 1 trillion checks (1,000,710,602,752) it had found a solution!” Cantrell said.
Took the ‘hacker’ just 44 hours to brute force. They paid a huge miner fee (0.01BTC!) so were worried about others doing the same and felt under pressure
— Alistair Milne (@alistairmilne) June 17, 2020
He then paid an excessively high fee of 0.01 Bitcoin ($94) to transfer the money to his own wallet—in case anyone else had guessed it (he wanted the Bitcoin miners to give preference to his transaction).
Milne confirmed that it had been taken. “I knew I was against the clock but most people thought it would take a few weeks to brute force 4 seed words,” he tweeted.
Now, Cantell plans to “pay-it-forward” with a contest of his own—that “can’t be won by software,” of course.
GIPHY App Key not set. Please check settings