News for hackers. Stuff that matters.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by Bedon292 on Saturday April 15, 2017 @12:22PM (#14121409)
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.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by SomeStupidPoint on Saturday April 15, 2017 @01:26PM (#14121716)
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.)

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by csomar on Saturday April 15, 2017 @01:50PM (#14121837)
> 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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by SomeStupidPoint on Saturday April 15, 2017 @02:15PM (#14121968)
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?

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by ryan-c on Saturday April 15, 2017 @03:32PM (#14122403)
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).
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by ryan-c on Saturday April 15, 2017 @03:26PM (#14122375)
The wallets they've found most likely were made with weak keys on purpose.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by xseven on Saturday April 15, 2017 @01:45PM (#14121807)
Multi-sig is the cure :)
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by ryan-c on Saturday April 15, 2017 @03:25PM (#14122368)
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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by m-j-fox on Saturday April 15, 2017 @03:26PM (#14122373)
Oh hi bitgo.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by josst on Saturday April 15, 2017 @12:39PM (#14121479)
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.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by kordless on Sunday April 16, 2017 @12:25AM (#14124316)
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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by gogeek on Sunday April 23, 2017 @06:36PM (#14180819)
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.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by xseven on Saturday April 15, 2017 @01:37PM (#14121770)
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
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by sanswork on Saturday April 15, 2017 @04:18PM (#14122620)
No coins to provide transaction fees if they are all lost though which is what the person you were replying to was saying.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by lern_too_spel on Saturday April 15, 2017 @05:04PM (#14122853)
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.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by api on Saturday April 15, 2017 @12:45PM (#14121514)
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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by lern_too_spel on Saturday April 15, 2017 @05:12PM (#14122891)
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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by panarky on Saturday April 15, 2017 @02:47PM (#14122140)
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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by TheDong on Saturday April 15, 2017 @03:09PM (#14122271)
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.

Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by billions on Saturday April 15, 2017 @05:19PM (#14122920)
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.
Re:Large Bitcoin Collider Is Generating Trillions of Keys an... by andy_ppp on Saturday April 15, 2017 @01:21PM (#14121695)
This assumes an end to speculation which IMO will always exist.