In the news a few days ago, the revelation that Luke Dashjr, a core Bitcoin developer, had his wallet compromised, and lost 200 BTC. A small fortune, and something of a shock. I’m guessing that someone with that expertise would not have left his private key lying around, so as a cryptocurrency non-enthusiast I’m left curious as to how the attackers might have done it. So I phoned a few friends who do walk those paths for an explanation, and the result was a fascinating conversation or two. The most probable answer is still that someone broke into his computer and copied the keys — straight-up computer theft. But there’s another possible avenue that doesn’t involve stealing anything, and is surprisingly simple.
I’m guessing that most Hackaday readers will know something about how a blockchain works, and also how public-key cryptography works. Public-key cryptography is key to the security of a cryptocurrency like Bitcoin, with the key that unlocks all your wealth for you being your private key and the key which allows transactions to be made with you by other people being your public key.
If you want to send some cryptocurrency to someone else, you encrypt the transaction using their public key which is as its name suggests, public, and your private key which is known only to you. Thus it’s important that your private key is kept really private, because if someone finds it they control your stash of cryptocurrency. So to steal all those bitcoins someone had his private key, an eventuality that should never have happened. We can safely assume that his protection of the key was as good as it gets, so further assuming that nobody physically stole his hardware wallet or whatever he kept it on, his key was compromised by other means.
The true security of public-key cryptography lies in it being extremely difficult to guess an individual’s private key. A brute-force algorithm to guess Luke Dashjr’s private key would require unimaginable computing power over a geological-level timespan, thus it’s also safe to assume that nobody set their computer to guessing his key alone. At this point, it’s helpful to stop thinking like an engineer, and start thinking like a gambler. An engineer calculates the time required to brute force Luke Dashjr’s private key, but a gambler throws the dice and sees if the throw generates any money.
Thinking from a gambler’s perspective, what are the dice, and how likely is a throw to win? If you roll the dice by guessing a private key at random and try it against Luke Dashjr’s stash of Bitcoin alone, then you’re in the same area as the engineer waiting geological time for your computer to crack it. But if you’re a gambler, you don’t care about Luke Dashjr or anyone else, you’re simply interested in the keys to any wallet with some Bitcoin in it. At this point the odds against you come down enormously, because instead of one chance with Luke Dashjr, you have a whole blockchain’s worth of possibilities for a match.
So here’s how it works. The blockchain contains the public keys of all its participants, everyone who has, or has had, Bitcoin. You collect that list, which is quite large, and hold onto it. Then you roll the dice, by generating a random private key. From that private key you generate the corresponding public key, and check whether it’s in the list of public keys on the blockchain. If it matches, you empty the wallet connected with it; if not, you repeat the process by generating another key. By not focusing on a particular individual account, you’ve reduced the time you’ll have to wait to crack any account from a geological aeon to a much more manageable figure. My friends suggested that it might be possible to find something in the order of months if they had enough resources.
As the title says then, it’s a surprisingly simple way to steal cryptocurrency. But simple doesn’t mean that the attack makes economic sense. Guessing key pairs requires significant resources and time, and you have to weigh this against the chances of finding a whale with boatloads of Bitcoin versus the chance of finding an account with a couple bucks left in it, which would sting after having invested millions into computer time. Doing this seriously is a gamble, and thankfully for the integrity of Bitcoin, probably a bad bet. But who knows? People do play the lottery.
If you want to roll the bones yourself, there is even a handy proof of concept in the form of keys.lol, the product of Sjors Ottjes, a Dutch web developer. This site displays a range of keys and queries the Bticoin and Ethereum blockchains to see if they match anything. You’ll soon see the scale of the task as you load random pages, and it’s safe to say that the chances of loading a page with a valid key on it are very small indeed.
If you hold Bitcoin, you should at least think about the brute force attack. But it doesn’t concern us — our wealth is held in unobtainable semiconductor devices stashed in a safety deposit box.
Header image: Ralf Roletschek, CC BY-SA 3.0.
Sorry but this is nonsense, the likelihood of an address collision is not just kind of low so that with enough compute power you would practically have a chance to find one, it’s ridiculously low, impossible with a pure brute force attack. In the order of < 1 / (2 ^ 100) low.
The compute power it would take to find a collision even in 100 years is several orders of magnitude higher than the compute power to just overtake Bitcoin with a 51% attack.
So you’re telling me there’s a chance?
Yeah!
Ridiculously low is not even marginally close to impossible. Further, this is statistical, not static numbers. A brute force attack takes an average amount of time over an arbitrarily large number of attempts. Any individual brute force attack could be successful on the very first attempt or try 100% of the options and only succeed on the very last attempt (or in this case, exhaust all of the invalid options before hitting the first valid one). Sure, the odds are absurdly low that either of these will actually happen, but that is still infinitely higher odds than literally impossible.
That said, I’m pretty sure you are right that the computing power required to do this with good odds even given 100 years is far higher than a 51% attack.
That’s the nature of gambling though, isn’t it? Your odds of becoming a millionaire by getting a good education and working hard are far higher than your odds of spending the same money and effort on the lottery and winning millions of dollars, yet so many people choose to play the lottery instead, and despite the astronomically small odds, some do still win. You can’t rely on stupid people to choose the rational path, and if the odds are non-zero there’s always a chance one of them will eventually win despite the odds. And no, “It would take a million years on average” doesn’t mean some won’t win the first time they play.
The bitcoin private key is 256 bits. Even if there are 4 billion valid wallets, that means you still have 256-32 = 224 bits left to guess.
It may be a ‘simple’ way to guess addresses, but it doens’t actually work out in practice. Even if you assumed every possible bitcoin address (i.e. all possible bitcoins spread out so ever address contains the smallest possible denomination of a 10^-8 of one bitcoin) you would need to take over the entire has power of the entire worldwide bitcoin network, and use it purely for bruteforcing addresses for 16,500 years, you may find a valid address (and steal yourself 0.015 US cents). If you do not assume such a broad distribution of addresses, it’s even worse.: https://medium.com/coinmonks/how-likely-is-it-that-someone-could-guess-your-bitcoin-private-key-6c0edd56fa1f
Basic cryptography can confirm it is far more likely his private key was stolen than that it was subject to an untargeted bruteforce attack.
No you wouldn’t. You would just need to get lucky and guess a good one in a much shorter time than average.
Odds are probabilistic, not guarantees. People win at slots and the lottery, occasionally the first time they play. Just because the odds are one in a million, and it would take more than a lifetime of playing to reach a million attempts, or even half that, doesn’t mean that it’s impossible to win. It just means the vast majority of players will never win. Some still do though. Brute forcing doesn’t take the average time. That 16,500 years is an average, not the exact time required for each attempt to win. A very long average doesn’t mean it is impossible to win on the first attempt, in the first year, or in the first decade. It just means the probability is extremely low. That’s still infinitely higher than impossible though, and incredibly low probability events happen all the time in nature. Bad odds is not the same as impossible, and a very long average time doesn’t mean it can’t or won’t happen in a much shorter time.
You are correct, however, that the odds that his key was stolen are many orders of magnitude higher than the odds that it was randomly discovered through gambling. No security is perfect. A 256 bit key has 256 bits of security. An 8 character password with capital and lower case letters, numbers, and special characters only has 52 bits of security. Even a 16 to 20 character password falls barely above 100 bits of security. A good password is ~2^156 times easier to crack than a Bitcoin private key. And that’s not considering even simpler attacks like social engineering, that even security professionals aren’t 100% immune from. Statistically speaking, it’s far far more likely someone broke through his security, even if it is incredibly good.
Do you need to type in or otherwise provide your private key when doing transactions?
I’m thinking about the birthday paradox, where you only need 23 people to have more than 50% odds that two of them will share the same birthday.
23 50.7%
30 70.6%
40 89.1%
50 97.0%
60 99.4%
70 99.9%
Does that change if your birthday is Feb 29?
There is a tiny difference, but it is close enough.
23: 50.68650%
(ref: http://www.efgh.com/math/birthday.htm )
This assumes that all the private keys are perfectly random and there isn’t a flaw in their generation, which is the kinda thing that’s happened before.
Reading this article, I was anticipating the punchline being a flaw with the private key generation algorithm of a particular software tool. I was disappointed with this article’s suggestions.
Reading through the link, the story being told is his private key was stored on the computer with his hot wallet (a wallet connected to the internet), so that his computer may have been compromised remotely.
There’s also other comments questioning this guy’s integrity based on his previous actions along with suggestions that this could be part of a plot to evade taxes.
I doubt we could ever be sure what actually happened.
It’s so much easier and less stressful being poor.
Where live there is a serious offence called “stealing by finding”, if you knew it wasn’t yours it is viewewd as no less of a criminal offence.
Please be kind and respectful to help make the comments section excellent. (Comment Policy)
This site uses Akismet to reduce spam. Learn how your comment data is processed.
By using our website and services, you expressly agree to the placement of our performance, functionality and advertising cookies. Learn more
Author
Administraroot
