Large Bitcoin Collider Is Generating Trillions of Keys and Breaking into Wallets | Hacker News Reader

Large Bitcoin Collider Is Generating Trillions of Keys and Breaking into Wallets

motherboard.vice.com

116 pointsjonbaer62 comments

About 10% of Bitcoins were created early, before 2012, and have never been traded. If somebody ever finds the key of the early lost Bitcoins, they'll have a huge payoff, over a billion dollars. Speculation is that either "Satoshi Nakamoto", whoever he is, is holding onto them for a big payoff, or somebody lost the private key for all those early Bitcoins. As the years go on, the second explanation seems more likely.

Or he didn't loose it and isn't motivated by money. Which seems also likely since he had the skills and decided not to cash in on the fame either.

Or Satoshi died, which has been another theory.

E.g. Hal Finney https://en.wikipedia.org/wiki/Hal_Finney_(computer_scientist...

I imagine he would have planned for such an eventuality.

(Although, "let the coins vanish" is as valid a plan as any.)

Gaining access to the early wallets and bringing those Bitcoins into circulation will lead to a crash in Bitcoin value due to both increasing the supply (as in https://en.m.wikipedia.org/wiki/Spanish_Price_Revolution?wpr...) and decreasing confidence of other Bitcoin holders in the security of their wallets. You could extract some portion of the value if you do it slowly and pretend that Nakamoto is using his wallets, but you will not be able to extract their current market value.

While agree the increase in supply would drop the price I don't think the Spanish Price Revolution is analogous . . I think that's more analogous to what cryptocurrencies are doing to the Dollar.

In what way? Cryptocurrencies can be treated as just another asset.

Assets than can be created ex nihilo which will drive inflation.

How would you sell that many coins to guarantee maximum payoff? Surely getting access and attempting to sell Satoshi's stash would trigger a massive panic in the market?

Not sure their what their heuristics are for narrowing the search space, but there certainly are some good ones. For instance, early versions of blockchain.info's wallet generated private keys by reading an ARC4 stream that had been seeded with Math.random() calls xor'd with timestamps. Quite the circus!

If collisions exist in the hashing algorithm, how you derive the seed for a random number generator is pointless

Every hashing algorithm has collisions, for good cryptographic ones there's just no practical way of finding them.

There is no practical way of finding a collision for a specific key. Finding collisions to one of the created keys non-specifically is a much smaller search space.

They're just doing a naive sequential search.

I believe there was a time when blockchain.info's Android wallet generated keys from Apache's 301 redirect HTML fetched over HTTP[1].

I think there's also a lesson about idiot-proofing APIs. With the benefit of this in hindsight, I might instead return an invalid, non-HTTP response that blows up every major HTTP client internally, so that it's impossible for the API consumer code to happily truck along interpreting a non-200 response body as if it's valid random data.

[1] https://www.reddit.com/r/Bitcoin/comments/37nlg1/i_was_the_g...

http://directory.io/ seems relevant here.

You could utilise google's cache with this one.

It seems suspicious. Bitcoin cryptography isn't broken, AFAIK, so chance to randomly break into any real wallet should be almost non-existent. I think, they either lying or exploit something different, like RNG weakness.

This explains the approach in more detail: https://lbc.cryptoguru.org/man/theory

This is confusing to me. The link describes narrowing the search space to ~136.17bit, but that is still far too large to be tractable. Do they get an additional birthday bound on that somehow? 68 bits would not be insane, but I don't really understand what's going on here.

I highly doubt they found a collision with a probability of 2^-136, unless they exploited some kind of bad RNG bug (in which case the probability is much higher, of course).

No birthday bound. The keyspace reduction is based on the number of addresses with a balance.

They're cracking a challenge with intentionally weak keys.

They're not cracking addresses generated by normal wallets.

For example, here's a challenge that gets increasingly hard that you can use to see how efficient crackers are: https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9...

If this kind of attack is feasible, then maybe one should have several wallets and spread one's Bitcoin funds among these wallets, to dilute the risk. Maybe one wallet could be used just for receiving external transactions, but its funds could be immediately transferred to other wallets. Or maybe there are also weaknesses to this approach...

I'm not currently a Bitcoin user, and ambivalent about Bitcoin's virtue, but still hope that this kind of attack turns out to be fruitless and impractical.

>then maybe one should have several wallets and spread one's Bitcoin funds among these wallets, to dilute the risk

Sounds like Bitcoin is ready for the mainstream!

To be fair, aren't bank accounts only insured by the government for up to $250,000 per account?

To make matters worse, they're only insured to 250k in the event of a bank failure (running out of money)

having your account or identity hacked, on the other hand, you are on your own to make sure the bank replenishes your account ^.^

That is not true. The law obligates the bank to make you whole (subject to certain limits if you delay reporting until well after you knew of the theft).

The first tier is 3 days. Additionally, you need to spend money to be made whole, which you can of course sue for legal costs afterwards.

These are non-trivial steps and there are not many banks waiting out there to just give you your money back without some prodding

Three days from when you become aware does not seem unreasonable to me. Further losses are preventable and if you choose not to prevent them, it makes sense to me that you should bear some responsibility.

I'm not sure what you mean when you say you have to spend money to be made whole. I'm not aware of the banks having any right to charge you in order to get them to comply with the law. Would you please explain?

You would need to sue them in a court of law if they don't comply, which involves hiring a lawyer, which of course is needlessly expensive.

A bank that follows the law after your money has gone poof is the /best/ situation you can hope for, and probably isn't the /average/ or /median/ situation.

I don't check my many bank accounts every day and I prefer to spend days out in the wild with little internet. I will not be a happy camper on the day I'm hacked and my bank tries to explain why it's my fault that they can't pay me :)

I know several people who have had their bank accounts stolen at one point or another, and it's never required a lawsuit to be made whole. This is because almost all the transactions by which you can lose money through your bank are reversible, except for cash withdrawals.

In the EU usually only up to EU100.000 per account.

It appears that they are finding the private keys for transactions that already occurred. Reusing an address is not part of Bitcoin's design and it was never intended for people to do that. By not reusing addresses (not reusing private keys) I think one would be immune to this attack. The article doesn't seem to have much detail; anyone have more detail on this?

Edit: The details are in the URL posted by alphydan; it looks like address reuse does not matter with their method.

Even more important, by reusing addresses you are making more signatures using the same private key. This has proven to be a vulnerability where one can deduce the private key from these signatures (though limited to a bad implementation) but it's worth considering.

Very interesting work. 3 Quintillion keys generated, 3 private keys with coin in them. I have to wonder what processing power is being put into it, and if that power would be more effective at just mining coin, if someone were just after the money. At least in the short term. I think in the long term attacks like this might become more and more prevalent. Because at some point it may be easier to do this than mine new bitcoin.

Bitcoin is finite and one would expect the supply to become smaller over time thanks to keys being lost or owners dying and their accounts being inaccessible. In the long term guessing keys may be the only way to obtain new coins.

The new mining...

This would basically make Bitcoin Keynesian, since coin stored in wallets would now decay with a given probability. So you would have to invest it at least a little to beat the decay (shrinkage) rate.

This assumes an end to speculation which IMO will always exist.

Bitcoin becomes unspendable and worthless when the private keys are lost.

But when you have the private keys, your Bitcoin doesn't "decay". On the contrary, it becomes more scarce, and therefore more valuable.

You missed the point.

Once the primary way of gaining bitcoins is hacking wallets, the longer a bitcoin is behind the same private key, the longer that given wallet is a target.

IMO, the most vulnerable wallets are going to be the ones actively in use and stored insecurely, for example, on Windows machines subject to the recent NSA bug.

You're mixing up Keynesianism with money supply increases due to changes to the reserve ratio, discount rate, and printed currency. These happen to central bank controlled fiat money regardless of whether the people controlling the money supply are Keynesian.

Then you conflated losing some percentage of your cash assets due to inflation, which can happen even if the money supply does not change, to losing all of your cash assets with some probability. The former encourages investment, while the latter encourages not holding cash at all.

Not true. Mining at later stages will provide miners with transaction fees which will be significantly high enough for them to focus on keeping the network secure rather trying to find colliding keys

No coins to provide transaction fees if they are all lost though which is what the person you were replying to was saying.

Unless you have a hidden advantage, the cost of mining and the reward for collecting transaction fees will converge. The capital required to become a miner is very small, and the amount that a user can offer for fees is easy to change, allowing the market to be very efficient.

This is a common irrational argument (meaning it requires more work to determine truth) regarding the exhaustion of "supply". A "coin" is simply a numeric value in a wallet of a whole amount. Fractional amounts can, and will, continue to be "created" using subdivision of existing coin. There is, with future code changes, no limit to the precision of the values stored there, so even a sub fraction of a bitcoin will still do to serve the entire network, if the network is still operating, of course.

The deflation issue is what is really addressed here, where no new coins will be introduced at a given point. Whether new coin arrives or not, is really not an issue. An analogy would be the use of pennies if all the paper money went missing.

Guessing keys should never be an option, otherwise Bitcoin needs to upgrade its cryptographic functions. The supply will be shrinking in the sense of the asset/currency becoming deflationary at some point, as soon as 'lost Bitcoins > mining reward'. The limit of 21 million is arbitrary. Actually the current maximum in terms of units is 2,100 trillion, as you can divide every Bitcoin in 10^8 units. As a hard fork can update this denomination, there is nothing that limits Bitcoin to be adopted by a large audience.

Small note, but 3,000 trillion is 3 quadrillion, not 3 quintillion. Which is their total, over a significant amount of time.

The bitcoin network does over 3 quintillion (>3,000,000 trillion) hashes a second. So even if they were doing a significantly harder to compute hash -- they're still only a very small part of the computational power the bitcoin network is using.

So it's probably already more effective to attack wallets than join a mining pool.

Ed: Estimate of numbers --

Assuming that their hashrate was over 3 months (article says nearly a year, but they're also scaling), they had about 300 million hashes per second. Bitcoin had 3 million trillion hashes per second over the same period. So you're talking 1 to 10 billion in raw hashrate, and even with a generous challenge factor, bitcoin is using millions of times more compute power.

There were about 150 thousand bitcoins mined over that period, so 1 in 10 billion of that is 0.000015BTC.

Since they hit 3 in use accounts with the same compute effort, they almost certainly made more BTC attacking wallets with collisions.

Ed2: How much parasitic hashing --

If you figure the average active wallet has between 1 and 5 BTC (very high variance), and the wallet hash takes about 100x as long (over estimate), they made 3-15BTC vs 0.015BTC by attacking the network versus mining, or about 200-1000x as much.

Since colliders are themselves unlikely to collide (and thus competition doesn't starve out colliders), the system will only stabilize if 99%+ of miners drop out of the pool or the difficulty in finding a collision raises 1000x.

Given the sunk costs in dedicated mining rigs and that new hashes would be breaking, it seems like parasitic hashing will continue to be an issue.

On the plus side, only a one-in-a-million chance it wipes one of your accounts.

(Of course, a fluke collision with a high value account might create other problems.)

Multi-sig is the cure :)

P2SH addresses can be brute forced several orders of magnitude faster than P2PKH. The attacker needs to generate 1-of-2 multisig scripts in the following form:

OP_1 [compressed pubkey] [0x02, 29 random bytes, 3 byte counter] OP_2 OP_CHECKMULTISIG

A new compressed pubkey must be generated every 2^24 iterations.

You compute a sha256 midstate from the first 64 bytes, then restore and compute over the rest of the script for each subsequent iteration, then ripemd160 the output. Very easy to GPU accelerate.

The slowest part of address generation is the elliptic curve math, and this avoids it entirely for most iterations, only needing to to refresh the public key when the counter rolls over.

Oh hi bitgo.

> So it's probably already more effective to attack wallets than join a mining pool.

That's not how you make the calculations. The reason the idea was called stupid is because the math doesn't add up. My guess is that these 3 private keys had weaknesses in them. Even the probability that they were found by "luck" is way far off.

Given merge mining is possible, I'd assume with some tweaking side-colliding + mining is possible. So if it was profitable miners would already be doing it.

I'm sorry, I'm not sure I understand your point: are you saying my math is off, given the claims of the article (ie, hashes computed, time spent, and compromises), or that the article is wrong because it's not that easy to crack?

Google found a SHA-1 collision (160 bit hash, same size but different method) in 9 quintillion hashes (plus some crypto work). The article claims they found a collision against 3 of millions of targets in 3 quadrillion hashes (likely plus some crypto work). Given the birthday paradox, it's not a priori impossible.

Could you explain why you don't believe their attack is mere hash collisions?

They're running a brute force preimage attack against all bitcoin addresses which currently have a balance. The reason they say "collision" is that if they found a key that hadn't been made weak on purpose, it would probably be a different key from the original (bitcoin addresses do not map 1-to-1 with keys).

The wallets they've found most likely were made with weak keys on purpose.

Maybe this is what the future of "treasure hunting" looks like?

Myself and a friend ran a wallet recovery service a while back, brings back memories haha. Very cool work, even as someone who works in the blockchain space.

Collide her? I just met her haha

Reply on news.ycombinator.com