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.
Are You A Gambler, Or An Engineer?
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.
How To Steal 200 BTC By Brute Force
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!
You have a: 1 in 1,222,000 chance of death or injury from lightning in a given year. Now compare 1:2^20 to 1:2^100 and tell me how often lightning has struck you in your life.
I have used keys[.]lol and found only one chance to finding a key: Wrongfully implemented RNG to find a point on the elliptic curves. Most vulnerable addresses were either at the beginning or end of the entire keyspace. I suspect these were created by malicious wallets.
Giving the person on purpose a weak key that is easy to find. It is the equivalent of a thumb on the scale or a dice with a lead weight inside. Foul play. Your chance is near NIL, jsut because it isn’t zero doesn’t mean you see it in the blink of a human life of =<100 years.
The left side “1” in that equation is actually a much more bigger number, everybody in the blockchain….
even if every person in the world was in the blockchain, the number would be ~2^33 which is still much smaller than 2^100
The elliptic curve Bitcoin private keys use is Secp256k1, it works by doing math on a group with order `n = 2²⁵⁶ – 14551231950b75fc4402da1732fc9bebf`, that means there are more than `2²⁵⁵` valid curve points.
Any number can be used as a private key `s` if `1 < s < n`, and I think the only additional requirement is for `s` to be random. If so, there are `n – 1` valid private keys on the curve.
We can now compute the probability of any two keys matching: `P(A) = 1 – (n!/(n-k)!)(n^-k)`, where `n` is the number of valid private keys (he birthday paradox Wikipedia page.
Where n is the number of possible keys and k is the number of generated keys. I'll use Stirling's approximation (`ln(n!) = n(ln(n) – 1) + O(ln(n))`, the big O notation indicates the error scales with `ln(n)`, which should be tiny)
My code is
“`python
#!/usr/bin/env python3
import math
from decimal import Decimal, getcontext
def stirling(n):
return n * n.ln() – n
getcontext().prec = 500
n = Decimal(2**256 – int('14551231950b75fc4402da1732fc9bebf', 16) – 1)
for i in range(256):
k = Decimal(2**i)
pa = 1 – ((stirling(n) – stirling(n-k)) – k * n.ln()).exp()
print(i, round(100*pa, 2))
“`
Output:
“`
120 0.00
121 0.00
122 0.01
123 0.05
124 0.20
125 0.78
126 3.08
127 11.75
128 39.35
129 86.47
130 99.97
131 100.00
“`
`2¹²²` is an unfathomably large number. If you had a computer capable of that many operations, you'd probably be better served mining all cryptocurrencies, advancing scientific research, or simply enjoying life on the inside of the Dyson sphere needed to run it. It still wouldn't give you more than a 0.01% chance of duplicating a key pair (and that duplicate is overwhelmingly likely to be one of your own).
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.
You are assuming computers that generate keys are truly random.
There have been known cases where certain libaries used for key generation were biased.
How many real keys have been generated by such an algorithm?
If you also use such a biassed tool, your chances of finding a collision go up significantly.
If you have additional knowledge like that it’s not a pure brute force attack anymore.
The point is, the gambler’s algorithm doesn’t play for a specific match, it plays for any available match. Any match with any wallet that ever existed is a hit, and if the wallet still has funds attached, it’s a win.
And there are some things that can be done to reduce the computation, not technically rainbow tables, but conceptually not that different. With some optimization, the cost-of-search computation drops to less than the BTC mining cost-of-search, with a payout potentially as high as the number of BTC stored in the most-funded wallet, rather than being capped at 1 BTC. And, with some software development, any FPGA miner or hash accelerator could be updated to do the heavy lifting, although it would be more convenient to test the potential matches externally.
In other words, it has the potential to have much better payback than mining, and works equally well against non-mined currencies.
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.
So, 2 bits is $0.25 USD, a Private Key is 256 bits, so that makes it worth $32 (USD).
For that, I would rather get the shave and a haircut
True, but now it becomes a “birthday attack” problem.
The odds of 2 people NOT having the same birthday are 364/365. When you get to 23 people, the odds of sharing a birthday are over 50%
Wikipedia link: https://en.wikipedia.org/wiki/Birthday_problem
No, it’s not a birthday attack because number of wallets is fixed.
But, the denominator is in the range of 2^256 aka 100 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000
So, it doesn’t matter if your numerator is a trillion (which is way to high for the number of active Bitcoin accounts that have a reasonable amount of money in them).
It’s like taking a few hundred people across all history and asking if they were born on the same exact second. Even if the probability improves, it’s still improbable.
If you do the math, you only need to pick about 6,000 people to find at least two with the same birth-second.
You’d need about 2^122 Bitcoin keys to find at least two matching ones with a probability greater than 0.01%. Even if you generated that many, the chance of that duplicate being someone else’s is far below one in a trillion.
33 bits – 32 bits = 32 bits. You are not even close.
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?
You need to sign a transaction with your private key, but you can do that while disconnected from the internet.
It’s possible in the way that I might fart and destroy a skyscraper is possible.
Normally you would use expectations. If the expected run time is 16,500 years, then that is what you use in your decision making. There’s no point in hoping that you might get insanely lucky.
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 )
It’s not really like the Birthday problem because in that problem everyone is from the same set… it’s talking about how ANY two people from the set have the same birthday. In this case there is two sets: the set of keys in the blockchain and the set of keys generated by the attacker. Consider: Two matching keys in the blockchain don’t help the attacker, not does it help if the attacker has two matching keys.
If you do this math for Bitcoin private keys (see my other comment), it looks like
2^120 0.00%
2^121 0.00%
2^122 0.01%
2^123 0.05%
2^124 0.20%
2^125 0.78%
2^126 3.08%
2^127 11.75%
2^128 39.35%
2^129 86.47%
2^130 99.97%
2^131 100.00%
Also in this case you want to match a generated key against someone else’s public key, and if you’re generating >2^120 keys it’s very likely that you’ll just match your own.
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.
Yeah my money is on his own bad opsec and now he’s spinning this fisherman’s story about some kind of exotic and HYPER unlikely attack to save face.
It’s so much easier and less stressful being poor.
Poor people are generally happier.
That is not just wrong, but the complete opposite of reality: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7525587/
Complacent people are generally happier – and poorer.
Yes, you don’t know how easy and calming it is to struggle every day to be able to buy food and pay rent :)
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.
Losers weepers, finders jailbirds?
If I ‘find’ it, it’s mine.
Don’t put all your coins in a single basket :)
Here’s a secret…. convert bitcoin into gold, then put it in a safe.
Yeah, gonna go with tax fraud or insurance fraud being much more plausible.
That said, the whole thing of Bitcoin mining is attempting to invert one way functions by guessing, so at least it would be on theme 😉
You mean to say that secret passwords can be guessed at? Good heavens! Who would have thought? This is serious. Should I put my bug-out plan into action?
Not before posting your Bug Out Location here!
(We want to be sure that you arrive safely)
B^)
if you convinced several million compromised computers to join you would it be faster?
It would be (a lot) more effective to just mine new coins.
Imagine you have spent 100 years doing bruteforcing then people invent new currency and leaving crypto currency 😅
So … how does one go about getting a private key, anyway? You’re supposed to pick a random prime number several hundred bits long, right? Exactly how does that work, and aren’t you at the mercy of whatever “randomness” this process actually implements? Presumably, a flaw in the picker could lead to someone being able to pick “colliding” random primes much more easily.
The private key is just a random 256 bit number. It doesn’t use primes, but elliptic curve cryptography. On a modern machine, you would use the cryptographically secure random generator provided by your operating system.
If you don’t trust your OS, you could create your own by calculating a SHA-256 hash over some suitable source material, such as a digital photograph of some clouds, on an air-gapped machine.
Oh, yeah, lots of cryptography has been screwed over because the random generator or algorithm was flawed, infact, the US government has done this intentionally many times to compromise the security of cryptography.
However, it’s assumed that someone who was a core developer of Bitcoin would have made sure that their keys were not compromised in this way.
Is today the 1st april? because this reads like it is.
Not only is the chance ridiculously low as the keys are simply way too big there is also different algorithms at play so you not only have to generate trillions of key+addresses, you need to make it for every format that could have been used.
Then there is another problem. Generating a single key+address combination is extremely slow thanks to it being all with elliptic curve math which deals with really big numbers. There are papers about elliptic curve multiplication on GPUs, maybe you could also develop your own FPGA. But at that point your skills are worth way more money than actually maybe finding a single coin.
so good luck with your ‘brute force’ attempt, many people tried, none succeeded.
How would quantum computing affect the crypto-world?
It’ll affect a plethora of more traditional cryptographic systems before there is any substantial impact on things like Bitcoin. As is, Bitcoin does not appear to be easily attacked by quantum techniques and there should be ample time migrate to more resistant cryptographic systems should that change. IMHO the concerns about quantum cracking of Bitcoin is a bit of a nothing burger.
I don’t see the advantage of checking each key guess against a large number of encrypted samples. It still takes the same amount of time to make each test. So what difference does it make if you’re testing a million keys against one sample, or one key against a million samples?
Seriously. I don’t understand.
Lets setup an escape room in a bank vault full of safety deposit boxes.
there is an unbreakable unopenable jar full of keys with a slit just large enough to pull out one key at a time.
The key may open one safety deposit box, It may open the safety deposit box of 89 year old Edna Gertrude who keeps nothing of worth just papers, it may open Satoshis box granting you access to the genesis block, it may open the box that has the vault release concealed within or it may not open any box at all. No way to tell but to try.
Do you pick the closest box to the jar and try all the keys one at a time and give up assuming no joy? Or do you try the first key in EVERY lock, then move on to the next key in all the locks?wash rinse repeat
What if you had a list from the bank that showed which boxes were available for rental? Wouldnt it make sense to ONLY try the key in boxes that MIGHT have a prize?
Thats what this idiotic premise boils down to.
Make a list of “boxes in use” by watching the chain. Trying 1 random key in 1,000,000 locks, over and over, until one random key and one LESS THAN random lock matchup.
Good Luck with that nonsense
I think part of the assumption is that generating the key takes more effort than trying it. Modern physical keys are essentially digital (each lock pin can be one of a small set of heights, say 8). A better analogy might then be that you had to cut each key before using it. So it would be slightly faster to cut a key and try two boxes than cut two keys and try one box.
That all said, there’s nowhere near the efficiency gain to significantly improve the odds and as mentioned, you likely to get less benefit from an random box than if you can target the vault box.
It depends on which part is the time consuming part, and keys are generally designed to take a lot more time to generate than they take to check equality in a lookup table.
But if you are guessing keys they take no time at all to generate, just keep adding 1.
by keep adding 1 you only generate part of the key pairs. and it is the part you do not need.
you have 2 keys here – one private and one public. what the article says generate a random pair, and see if the public key has been used before. if it has, then you have the private key matching it. i dont know why there is so much fuss about brute force attacking – this is not brute force random collision lookout.
A bloom filter can cut down the time to check substantially, and you might be interested in looking up rainbow tables (useful when generating the ‘key’ is the expensive part, but checking if it matches is easy). In this case it doesn’t really matter, because even finding a match via the birthday paradox would require more computation than our civilization is capable of.
The space is just too big for a collision attack to be realistic. Perhaps deliberately weakened public keys might be able to reduce the effort to crack a private key.
This case is either a simple hack, or quite likely a tax write-off on the part of the owner. Let’s see where those funds end up, and maybe if Luke decides to take an indefinitely long, private vacation somewhere tropical.
+1 on tax fraud
OK, listen up people. Here’s a list of reasons why crypto currency is a really BAD thing, and we should all avoid it.
1. Crypto currency is a back door waiting to be kicked in. Example (this story).
2. It’s dead money. There’s no interest paid on the any money deposited in Crypto. The money just sits there, and looses value (inflation currently at 7.1%).
3. What can you do with crypto? Demand a ransom, hide money obtained through criminal activities. Avoide paying taxes. Move ill-gotten gains to other Nations. (Summary: NOTHING GOOD !).
4. What could happen in the future? Bad actors could move large sums of money into, or out of various Nations destabilizing their economies. We are on the verge of this now.
The Moral of this story is:
Crypto Currency exists as a way of funding criminal operations. Speculators are attempting to make money off these crimes indirectly. Investing in Crypto supports and advances criminal organizations.
crypto: jUST SAY NO. It’s a very bad idea.
You are just viewing the technology with the variables currently in place.
We can expect new data networks to be created to render tcp/ip(the Internet) obsolete, which may actually have an infrastructure to use any/all failed innovations on the global network.
I think your warning is don’t invest in a network with a population of est. 5.5 billion users in 2022.
Global networks are not where the innovation is happening. Its not an information superhighway any more. Its easier to make ISH 2.0 to 100.0 on much smaller networks. The ratios and odds are much better ;)
Crypto is estimated to have 5.5 billion users? 68% of the world’s population uses crypto currency? Assuming people over 65 or under 15 don’t participate significantly in crypto currency, that means ~100% of people age 15-65 participate in crypto… That seems a bit high to me.
Consider the alternative.
What we have now.
Every nation printing money as fast as possible. Using it to fund weapons and distort markets with burning currency.
Anybody want to start a betting pool on the first major currency to implode?
I’ve got the English pound!
No Turkish WTFs are not a ‘major currency’.
This is a million bitcoin idea.
Payoff in CBCoin (Currency Bet).
What? Someone already did this?
Ten years on drugs and Fing in the Bahamas.
Bastard stole my idea.
Here’s the difference: if you use government-printed money, that government is answerable, especially if it’s a government that has periodic elections. If you put your money into cryptocurrencies, it’s like putting it into commodities, only without there being any actual commodity you can keep an eye on. No thanks.
We need a downvote. The quality of this submission is so low it reflects on HaD. Public keys arent even generally exposed onchain until just before they are spent.
I contemplated the idea of writing a tool that could perform such attacks, not because I wanted to steal bitcoins but because I wanted to learn GPU technologies such as CUDA and OpenCL – and heat my house while doing so. I procrastinated (how surprising….) and haven’t done it yet but I checked the math at that time and i seemed pretty unlikely I would ever steal someone’s bitcoins using this way. One could increase the odds of finding a key by cracking several crypto currencies and testing more key pairs at the same time but the odds were still very low.
As it was mentioned in previous comments, I think the expensive part here is generating the key, not comparing it to other keys. Also I thing there are other transformation and the keys are not stored as such in the block chain
The schemes I’ve heard about for stealing bitcoins more often involved sim jacking and I think that if a hacker targeted someone with 200 bitcoins, it would be worth buying a $100,000 browser exploit and stealing the guy private key.
I did the math for people talking about the birthday paradox (which doesn’t apply here because you want someone else’s key) and the odds of a brute force succeeding even with every computer in existence working on it for a billion years are practically nonexistent.
When your buck is a bit, watch out for the bug…. code has errors, lots and lots and lots of errors, bugs, mistakes and backdoors…. its just how code is.
great
If this is such a huge hole, then why did LBC (a crowd-sourced bitcoin key attack) stop posting outcomes in 2017?
https://lbc.cryptoguru.org/about
“We can safely assume that his protection of the key was as good as it gets”
After reading his tweets on the matter, that seems like a very bad assumption. Keeping your private keys on an internet-connected server is a bad idea. The server got compromised and his keys stolen.
think what you’d like about Bitcoin. It is surely not impossible, with the right tools and information, hardware and experience to exploit p2pkh transactions. i could give you around 20 good reasons, and proof that, as of right now, it has the capability of being breached. this is been true for over 10 years, and soon most of these secrets will be covered up and patched. i myself ran testing with timing scripts along with ecdsa and der lattice implementation with several successes. the probability of being exploited, or an address being drained for the average user is very low, yes and the blockchain is becoming more and more secure. But, for those of you that want to preach about “chances of being struck by lightning are greater” or “never in a zillion years” and that it’s totally “impossible” haha keep thinking that. thats what you told yourself and what they want you to believe. how far along did you study mathematics would be a good question and did you reach the chapters on fast modular exponentiation.