Topic: BitCrack - A tool for brute-forcing private keys - page 93. (Read 76881 times)

The whole point of a puzzle transaction is that someone will solve it. The person who created the puzzle has donated those funds, and intends for the winner to claim them. Kind of like hiding a wad of bank notes in a local park, and publicly announcing clues on how to locate them.

Yes, my understanding is that you are supposed to try and brute-force an N-bit key for a reward of BTC.  So, if you found a 50-bit key, you'd get 0.05BTC.

It's now getting so difficult that I don't think keys 58 and up (until the larger claimed ones) are going to be found soon, unless it's just pure luck.  The search space is massive.  I can crack a single DES key (I search the entire 64-bit space) in less than a day, but there are additional more expensive steps to finding a valid private key.  So just keys/s is not really enough; other optimisations need to be done.  The distribution of rewards according to work with the LBC was a good idea.

So, essentially my understanding is that while you don't own the key, a) it's been made deliberately findable (at least for smaller keys!), b) there's a hint on where to search for a key for the BTC reward, and c) the transaction was created in a curious manner indicating this wasn't just any type of funds transfer.

I think we can make a reasonable inference that this is a puzzle, and if you get lucky and do some real work to find a key, you get some BTC.

please clarify - how is finding/taking funds (essentially stealing) found to have no moral dilemma? and why would stealing be a reward?

or am I misunderstanding and there is no stealing being done and these are just free funds floating out there?

that's what he wants

Wasn't LBC created to solve the puzzle transactions? Just like BitCrack was? Up to this point it has been a relatively small search space, so not impossible to brute force.

Cracking an arbitrary, 100% random private key is a different matter, of course.

One advantage of focusing on puzzle transactions is that finding (and taking) those funds presents no moral dilemma. It's meant to be a reward.

I wrote a package last year called 'inflection', its detailed on www.inflection.top, but I have been working on this problem since 2012, and I was an early miner, but I always found BTC-HACKING, e.g. solving the 'discrete log problem' more interesting than accumulating btc.

All the things you have asked for have been done,

But I might add that 'brute force' hunting is not the way to go about this problem, like the other guy 'LBC' linear collider, its stupid to search 1-N, where N is 2**256, as that is counting all the atoms in the universe, many times over. It can't be done, unless you have an infinite time-frame to solve the problem,

The way to go about this is INTELLIGENT selection of the seed for searching the frames ECDSA, also using SAGE and MSEIVE ( most powerful factoring tool on earth ), you can factor public-keys, and develop a good band for your search, also using FFT, and RNN-LSTM you can generate favorable regions for searching,

My software that supports all GPU HW, currently does 150M/sec calcs per 1060 class card, so on a typically GPU rig for mining, I can do over a Billion calc's per second, but that is still just 10***9, where our scope is say 10**77, and there are 10**71 atoms in the universe.

Also I don't think its possible to find a particular key for a particular address, the way to go about this problem, is I have 200 million addresses with value, and 100k with high-value, I use a four layer hierarchical bloom-filter that starts at 2*32, and goes up to 2**40, everytime I find a priv-key that matches my list, there is 0.0000001% chance of false-positive, that one in 10 million, but I'm doing a billion a second, so I'm geting a lot of false positive hits, so as candidates are found, they past to the next heirarchy of bloom filters, so I can kick out up to one in a billion false-positives, I usually dial this stuff in so I can about 100 candidates a day, then its easy to use the database online to check if the key found has a 'current value', if > 0, then I log, I have found lots of 0.001 BTC, but the odd's of finding > 0.01 BTC are low, as we're talking 2*22 in a space of 2**128

So in reality here I'm looking for 200 million keys at once, not looking for one, and I'm using best estimates of likelyness to search in spaces

I think the most progress will be made in the area of sage/msieve using the published papers on discrete-log problem solving, if you want to find a particular key for a particular public address. Right now I have it down to 2**42, which is still to long to search, but with 2**24 at once, my search space is only 2**22, which is no problem

I was reading somewhere that Bitcoin Core developers, and others (mathematicians, cryptologists, etc) were trying to make the case that 160 bits is not going to be enough at some point.  Eventually they convinced Gavin Andressen that 160 bits gives them the heebie jeebies.  I'm not sure what the result of that was, I'll have to look it up.  Maybe it can be found on Gavin's blog.  I don't recall the details off the top of my head, but I found it fascinating.

so who found the first coins? hehe

Hello how can i use the --continue commmand please can someone describe me that ?

and what are the best settings for GTX 1070?

It will be interesting to see what happens to Satoshis Millions (and any other funds which haven't moved for years) when/if technology advances sufficiently that Bitcoin has to switch to a different hashing algorithm to properly secure funds. In that case, funds MUST be moved (via the new algorithm) to protect them; any historical unspent outputs would remain susceptible to cracking. Perhaps at some point that will become the new form of mining.

Thanks for those explanations.
I wish I were good at maths.
Maybe in 20 years we would have the technology. But the security will be strong enough to prevent a crack I think 

I believe you are correct, yes.

I verified the result with 1x GPU at 200m k/s. Trying to find the 37th private key, using the above calculations, 687 seconds/~11 minutes at 200m k/s.  So the search space is 137,438,953,471 decimal.

Result:


Of course, searching the entire keyspace here won't be necessary, so there will always be a result faster than the maximum time expected, at least for these puzzles.

Maybe adjust your calculations for e.g. 10 trillion keys/sec to see how safe it might be from a well-funded adversary?  50 trillion? 100 trillion?

I think you are correct, and either way, 10 trillion or 50 trillion or more, a collision or a match for 160-bit output of RIPEMD160 is going to be (probably) impossible for years to come.

I'm not able to verify your math, but to extrapolate: if breaking a 40 bit key takes 91 minutes, then I think finding a collision (not necessarily the original private key) for the 160 bit output of RIPEMD160 will take a maximum of 91 x 2^120 minutes?

Or more simply, 2^160 / 200,000,000 = 7.3075081866545145910184241635814e+39

Which I believe is 7,307,508,186,654,514,591,018,424,163,581,400,000,000 seconds, or 231,719,564,518,471,416,508,701,933,142,000 years.

Even if my answer is off by a few orders of magnitude, or someone manages to crack concurrently over a million GPUs, the chances of finding a collision (or match) are still close enough to nil to call it impossible.

You might be able to get a rough estimate with your keys/s knowing how many bits of key you need in the private key you're looking for.

Bear in mind I'm no expert either, but using 8 GPUs similar to yours, you'd need to search through at least 4 quadrillion, hundreds of trillions, ... private keys from the first valid 58 bit key (if you're looking for key 58 in the puzzles).  That's 4 or 5 solid days of searching with 8 start points and a range -r of about 500 trillion, I think.

I could be wrong!  I can't try that, so I can't verify.

You're still looking at oodles of keys, so have a look at your keys/sec, call it S, and the range of valid N bit keys, call it R, and roughly speaking R/S.  Adjust R and S for units and then look at the result in minutes, hours, days, weeks, years...

So, as an example, if you were looking at a private key of 40 bits, the first one with a 1 bit is 0x8000000000 (549,755,813,888‬ decimal) your search space is up to the first 41 bit key (double the first 40-bit key, so up to 0x10000000000 (1,099,511,627,776 decimal). Minus 1.  So your R is 0xFFFFFFFFFF  (1,099,511,627,775 decimal).

If you can do 200 million keys/s, then you can expect to find the 40-bit key within 5,497 seconds. 91 minutes.

I might try to verify this with smaller numbers of keys/s, with e.g. 32 bit key.  I think that's correct, you could get lucky and find the key within half that search space of course.

Hi everybody !
Currently testing OP's tool but I'm bad at maths.
How many thousand of years remaining until I could find the actual private key from the address I'm searching for ?

https://i.imgur.com/ac7NLBV.jpg

It's actually a 1080Ti not a 1080.
I don't trust the LBC code at all so I stay far from it but I'm surprised by the numbers I get here.
If only this project : https://github.com/Isaacdelly/Plutus was coded with CUDA...  

Can someone "donate" the address at some seed, eg the 0000.. seed? Since I could not compile, I could not extract with my own mod to the code.

Haha! Yeah, I have tried very manual methods.  It's super hard now even when you have the "chainstate" i.e. addresses with balances, guaranteed at that point in time.  So you have to be quick.  It would be pure luck starting at some point and trying for a year and wrecking some GPUs to find a key I think.

Good grief, Bitcoin is plummeting right now.  Just checked my balance.  Oh well.  I hope it goes back up later... back to topic.


It's coming (sort of).  It will be slow, so it will queue up a few to check over a few hours, a long time after brute-forcing, but only until some code to keep up with the chainstate is there.  It will still be slow, but it will work a lot better than thumping on a non-local API to get a balance.

And that entirely depends on a pull request later...

From the https://github.com/bitcoin/bips/blob/71586487532d832ae4a3b0deae797d86ddebe3fc/bip-0039.mediawikiBIP39 github


It is indeed 6 words not 7.  Also, if any other information can be recovered on the additional 6 words, 1 letter, approximate length, etc. the 2048 list becomes much much smaller very quickly.  For example, if we know a word is 3 letters it goes to 100 options.  If we know it is 4-5 letters it turns into 1000 options. If we know it has a "w" it turns into 166. Therefore, the partial information should also be accounted for when calculating the difficulty.

Oops, it is 7 unknown, not 6.

I agree that even when knowing the majority of the words, the chance of brute forcing the remaining bits to recover the complete key is infinitesimal.

Assuming 11 bits per word (2^11=2048), 17 known words means you have 187 bits of a 256 bit key already. That leaves 69 bits (2^69) to brute force.

If you were able to test 2^32 keys per second (an incredibly optimistic rate which assumes massive scale) it would still take 2^37 seconds to cover the entire search space... which is about 4358 years.

Things would be more complicated if you didn't know the positions of the words, as you would have to try the known 17 binary sequences in various locations, as well as brute forcing the remaining bits.

And if there's any key stretching involved the time taken to test each key, and therefore search the whole space, goes up by a significant amount.

Kind of cool that even if you know nearly 75% of a 256 bit private key, the chances of cracking it are still virtually zero.

Yes probably you are right but it's still highly doubtful the puzzle maker would do such transactions.