8 ms·
Large Bitcoin Collider Is Generating Trillions of Keys and Breaking into Wallets
- Bedon292 10y agoVery 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.
- josst 10y agoBitcoin 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.
- api 10y agoThe 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.
- andy_ppp 10y agoThis assumes an end to speculation which IMO will always exist.
- panarky 10y agoBitcoin 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.
- TheDong 10y agoYou 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.
- billions 10y agoIMO, 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.
- lern_too_spel 10y agoYou'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.
- xseven 10y agoNot 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
- sanswork 10y agoNo coins to provide transaction fees if they are all lost though which is what the person you were replying to was saying.
- lern_too_spel 10y agoUnless 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.
- kordless 10y agoThis 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.
- gogeek 10y agoGuessing 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.
- SomeStupidPoint 10y agoSmall 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.)
- xseven 10y agoMulti-sig is the cure :)
- ryan-c 10y agoP2SH 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.
- notamy 10y agohttp://directory.io/ http://directory.io/ seems relevant here.
- dzhiurgis 10y agoYou could utilise google's cache with this one.
- hrehhf 10y agoIt 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.
- TheDong 10y agoTo receive anything, you must have an address (the public key). All coins (UTXO) are associated with addresses which must have private keys. It's impossible to only have a public/private keypair for the instant a transaction is being made because the UXTOs must be owned spendable by some public/private keypair while a transaction containing them is not immediately happening. You clearly don't understand what you're talking about.
- hrehhf 10y agoYou have ignored the difference between an address with has never spent anything and an address which is being reused. Since you know everything, why not address this directly? edit: Though unrelated to this article, here is a case where address reuse (and software bugs) led to vulnerable wallets: http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-private-keys.html http://www.nilsschneider.net/2013/01/28/recovering-bitcoin-p...
- TheDong 10y agoAn address which never spent anything can still be the recipient of a transaction. Those are the addresses which are being attacked here.
- homero 10y agoThere's actually a public key that isn't the address and it's revealed when spending
- 10y ago
- vbezhenar 10y agoIt 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.
- alphydan 10y agoThis explains the approach in more detail: https://lbc.cryptoguru.org/man/theory https://lbc.cryptoguru.org/man/theory
- awirth 10y agoThis 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).
- ryan-c 10y agoNo birthday bound. The keyspace reduction is based on the number of addresses with a balance.
- always_good 10y agoThey'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/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15 https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9...
- chejazi 10y agoNot 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!
- mankash666 10y agoIf collisions exist in the hashing algorithm, how you derive the seed for a random number generator is pointless
- Ded7xSEoPKYNsDd 10y agoEvery hashing algorithm has collisions, for good cryptographic ones there's just no practical way of finding them.
- estro 10y agoThere 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.
- ryan-c 10y agoThey're just doing a naive sequential search.
- scintill76 10y agoI 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_guy_who_lost_6_btc_using_blockchaininfo/crokzk8/?context=10000 https://www.reddit.com/r/Bitcoin/comments/37nlg1/i_was_the_g...
- domador 10y agoIf 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.
- bigtimeidiot 10y ago>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!
- pavel_lishin 10y agoTo be fair, aren't bank accounts only insured by the government for up to $250,000 per account?
- salesguy222 10y agoTo 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 ^.^
- obstinate 10y agoThat 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).
- salesguy222 10y agoThe 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
- arcaster 10y agoMaybe 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.
- Animats 10y agoAbout 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.
- ZirconCode 10y agoOr 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.
- joobus 10y agoOr Satoshi died, which has been another theory.
- acjohnson55 10y agoE.g. Hal Finney https://en.wikipedia.org/wiki/Hal_Finney_(computer_scientist) https://en.wikipedia.org/wiki/Hal_Finney_(computer_scientist...
- pavel_lishin 10y agoI imagine he would have planned for such an eventuality. (Although, "let the coins vanish" is as valid a plan as any.)
- lern_too_spel 10y agoGaining 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?wprov=sfla1 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.
- ge96 10y agoCollide her? I just met her haha