BitCrack - A tool for brute-forcing private keys

[Driltan]

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...  

[digitalcitizen]

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 ?



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...  

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.

[almightyruler]

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'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.

[digitalcitizen]

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'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.

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:

Code:

james@research:~/BitCrack/bin$ ./cuBitCrack -s 0x1000000000 -r 0x1FFFFFFFFF -o ~/testcase.txt -d 1 14iXhn8bGajVWegZHJ18vJLHhntcpL4dex
[2018-11-24.08:24:46] [Info] Compression: compressed
[2018-11-24.08:24:46] [Info] Starting at: 0000000000000000000000000000000000000000000000000000001000000000
[2018-11-24.08:24:46] [Info] Initializing 
[2018-11-24.08:24:46] [Info] Generating 262,144 starting points (10.0MB)
[2018-11-24.08:24:46] [Info] 10.0%
[2018-11-24.08:24:46] [Info] 20.0%
[2018-11-24.08:24:46] [Info] 30.0%
[2018-11-24.08:24:46] [Info] 40.0%
[2018-11-24.08:24:46] [Info] 50.0%
[2018-11-24.08:24:47] [Info] 60.0%
[2018-11-24.08:24:47] [Info] 70.0%
[2018-11-24.08:24:47] [Info] 80.0%
[2018-11-24.08:24:47] [Info] 90.0%
[2018-11-24.08:24:47] [Info] 100.0%
[2018-11-24.08:24:47] [Info] Done
Tesla V100-SXM2- 446/16130MB | 1 target 219.93 MKey/s (31,273,254,912 total) [00:02:22][2018-11-24.08:27:12] [Info] Found key for address '14iXhn8bGajVWegZHJ18vJLHhntcpL4dex'. Written to '/home/james/testcase.txt'

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.

[Driltan]

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 

[almightyruler]

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  

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.

[PietCoin97]

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

and what are the best settings for GTX 1070?

[gembitz]

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  

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.

so who found the first coins? hehe

[digitalcitizen]

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  

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.

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.

[btc-room101]

Hi all,

I've been working on a tool for brute-forcing Bitcoin private keys. The main purpose of this tool is to contribute to the effort of solving the Bitcoin puzzle transactions: https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

Screenshot:



It is open-source under the MIT licence and requires no external dependencies other than the CUDA toolkit. It builds on Windows using Visual Studio 2015, and Linux using Make (you might have to edit the Makefile and point it towards your CUDA toolkit directory).

It can search for compressed/uncompressed keys or both.

The performance is good, but can likely be improved. On my hardware (GeForce GT 640) it gets 9.4 million keys per second compressed, 7.3 million uncompressed.

Note:
-Currently it is CUDA only.
-It can only search one target key at a time


Features I would like to add if there is enough interest for the project:

-Support for searching multiple target keys at one time Done
-OpenCL/AMD device support
-CPU with AVX/AVX2/SHA support
-Checkpoints/Stop and resume
-Vanity address generation


Source and Win32/Win64 binaries available here:
https://github.com/brichard19/BitCrack
https://github.com/brichard19/BitCrack/releases/tag/v0.0.6


Thoughts?


Thanks!

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

[almightyruler]

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,

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.

[vel12]

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,

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.

that's what he wants

[MoparMiningLLC]

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.

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?

[digitalcitizen]

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.

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?

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.

[almightyruler]

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.

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?

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.

[MoparMiningLLC]

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.

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?

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.

ok got it - you are not brute forcing an unknown person's account but one specifically set up for this challenge.

[timisis]

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.

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?

Why is solving cryptographic problems as a miner not stealing, while it is stealing as a key cracker exactly? Because you say so?

[PietCoin97]

Hi all,

I've been working on a tool for brute-forcing Bitcoin private keys. The main purpose of this tool is to contribute to the effort of solving the Bitcoin puzzle transactions: https://blockchain.info/tx/08389f34c98c606322740c0be6a7125d9860bb8d5cb182c02f98461e5fa6cd15

Screenshot:



It is open-source under the MIT licence and requires no external dependencies other than the CUDA toolkit. It builds on Windows using Visual Studio 2015, and Linux using Make (you might have to edit the Makefile and point it towards your CUDA toolkit directory).

It can search for compressed/uncompressed keys or both.

The performance is good, but can likely be improved. On my hardware (GeForce GT 640) it gets 9.4 million keys per second compressed, 7.3 million uncompressed.

Note:
-Currently it is CUDA only.
-It can only search one target key at a time


Features I would like to add if there is enough interest for the project:

-Support for searching multiple target keys at one time Done
-OpenCL/AMD device support
-CPU with AVX/AVX2/SHA support
-Checkpoints/Stop and resume
-Vanity address generation


Source and Win32/Win64 binaries available here:
https://github.com/brichard19/BitCrack
https://github.com/brichard19/BitCrack/releases/tag/v0.0.6


Thoughts?


Thanks!

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

do you have an open source software ?

can you find the bounty transactions mabey faster with your strategy ?

[almightyruler]

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.

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?

Why is solving cryptographic problems as a miner not stealing, while it is stealing as a key cracker exactly? Because you say so?

Mining a block is essentially the same as solving a puzzle challenge: the winner is expected to claim the funds.

Cracking arbitrary addresses - funds that belong to other people - is completely different. IMHO.

[almightyruler]

do you have an open source software ?

can you find the bounty transactions mabey faster with your strategy ?

Note the earlier post suggesting that this person may not be entirely legit.