Searching (who am I kidding, crack) private keys using FPGA and mining chips

[OssyRozenberg]

Happy New Year at all!

On this forum have repeatedly discussed ways to crack wallets in the Bitcoin blockchain. Typical hacking methods are key enumeration (LBC https://lbc.cryptoguru.org/about) and dictionary attack / brain wallets (https://eli5.eu/brainwallet/).
It is believed that breaking a wallet takes millions of years, but let me disagree. These calculations were done for household PCs.
In fact, there are only two bottlenecks. This is the key generation speed and the key verification speed.

Today, the mining chips make 71 Gh/s (BM1387). Bitfury Clarke is already 120 Gh/s. BM1391 produces 170-200 Gh/s, 1397 - already 440-500 Gh/s (in S17+). Do not forget that this is the speed of a double SHA-256 (SHA-256).
If we take the standard algorithm for addresses calculating (https://gobittest.appspot.com/Address) it is not difficult to notice that most of the steps are the same SHA-256 and SHA-256 (SHA-256). One RIPEMD-160 stage and several bit shifts. Is it possible to use the mining chip as a coprocessor when generating keys? Yes, it is possible, but more on that later.

The second bottleneck is checking the balance at the address found. The system should turn to the blockchain and make sure that there are bitcoins on the addresses belonging to the key pair. Compared to hashing speed, it is very slow.
The situation changes if you know a wallet or a private key with a balance. In this case, you should only verify a few bytes.

Armed with this knowledge, I assembled the simplest device based on the S9 hashboard and Cyclone IV FPGA evaboard. This works correctly and I was able to crack test wallets with a simple (low order) key.

Findings:
1. A hashboard is poorly suited for simultaneous computing. It is necessary to connect the chips in parallel, but not in a daisy chain.
2. It is necessary to organize the instruction pipelining in the FPGA for acceleration of calculations.

Now a little about the economy. Why is all this necessary?
I do not want to steal user funds. This is not possible in my system if your wallet is not generally known.
However, there are a lot of forgotten wallets in the blockchain. Some wallets contain thousands of bitcoins. And these wallets remain motionless for many years. You can consider this as a treasure, which has the right to change the owner, imho.

Take for example the Antminer S17e (64Th), whose current profitability is 0.5 btc/year.
The device contains 144 BM1397 chips with approximately 440 Gh at each.
We’ll make the calculation for a wallet protected by seed phrase with a 12-word. The English BIP39 dictionary contains 2048 words. With high probability the old wallet is encrypted in English (or Hex, lol).
((2048 ^ 12) / (144 * (440^9))) / (86400 * 365) = 1939618 years it will take one ASIC to search for all the combinations.
However, if we’ll track 10,000 wallets, then 1939618/10000 = 194 years to search for at least one match. And even if we have 100 ASICs, it turns out 2 years to search for at least one match (based on average luck).
These calculations are very simplified, but they show the order of numbers.

For 2 years, these same 100 ASICs will get 2*100*0.5 = 100 bitcoins. Provided there are no changes in the network’s hashrate and the power of ASICs (no).

At the same time, the difficulty of the seeds of abandoned wallets will never change.
And finding at least one wallet like 1FeexV6bAHb8ybZjqQMjJrcCrHGW9sb6uF can pay for the mining of 100 ASICs for 1600 years. Their name is Legion 12ib7dApVFvg82TXKycWBNpN8kFyiAN1dr, 12tkqA9xSoowkzoERHMWNKsTey55YEBqkv, 1PeizMg76Cf96nUQrYg8xuoZWLQozU5zGW etc.

Thus, mining abandoned addresses is more profitable than mining new coins. Over time, the situation will change in this direction IMHO.

WBR, Ossy.

Update. 6 march 2020.
Pic1 - Structure
Pic2 - Algorithm
1. Defined prototype architecture.
2. The distribution of tasks is determined.
3. Alpha version of bitstream is tested.

Tasks are shared between mining chips and FPGA. In current configuration the prototype is capable to generate (and compare) up to 1500G keys (addresses) per second.
The current prototype is contains only 20 mining chips. After improving the technology computing power will be multiplied.

[pooya87]

you are too confused about how things work!
first of all a bitcoin mining machine (ASIC) is computing an entirely different hash algorithm than the hash algorithm used in creating an address. just because you see the words "SHA" doesn't mean they are the same. one is SHA256(SHA256) and the other is RIPEMD160(SHA256). you can never use an ASIC to find HASH160 hashes.

secondly hash is not even the important part! the real "bottleneck" is elliptic curve point multiplication and the fact that the number of private keys is unimaginably high that even if you could build a dedicated machine to compute them and then have millions of them working day and night you still have to spend millions of years to cover a small portion of it.

by the way those two projects you named have nothing to do with hacking. LBC is mostly a scam project that has infected its users in the past and not to mention that is is designed to "solve a puzzle" that was created by someone intentionally for them to solve. and brainwallet is just taking advantage of the fact that some people in the past never listened to those warning them not to try and create their own private key with a weak self created entropy.

[OssyRozenberg]

Hello pooya87!
Pls explain what you mean "doesn't mean they are the same"? The SHA algorithm is defined at the standard level.
RIPEMD160 is just one of the key generation steps. For this I use FPGA. And for the curves too. I never suggested using a mining chip only. It just a co-processor.
As for deterministic keys (did you mean this?) "the number of private keys is unimaginably high". But most number of a real ancient wallets are P2PK
I did not know that LBC are scam. However, this is theoretically possible, as are brain wallets too. This is based on the finiteness of the dictionary.

[pooya87]

i am talking about the numbers you are posting here which are irrelevant. they are the number of double SHA256 hashes that miners can compute not the number of HASH160 that a chip can compute.
not to mention that your final number is way off the mark when you are talking about the combination of words in a 12 word seed. because it is not just about hashing, it is about converting that seed phrase to a BIP32 entropy which requires PBKDF2 (ie. a bunch of HMACSHA512 among other things) then performing the BIP32 steps which consists of first choosing a derivation path which is unknown to you and then performing a bunch of point multiplication and HMACSHA512 among other things to get the child private keys. then another point multiplication to get the public key and then hashing. you are simply ignoring all these very time consuming steps and focusing on one small hash.

As for deterministic keys (did you mean this?) "the number of private keys is unimaginably high". But most number of a real ancient wallets are P2PK

using P2PK doesn't change anything. the protection of these outputs is based on the fact that converting a private key to public key is still an irreversible function with the current technology and will remain that way for at least another decade.

I did not know that LBC are scam. However, this is theoretically possible, as are brain wallets too. This is based on the finiteness of the dictionary.

it has nothing to do with the dictionary being finite, it is all about people who chose a weak set of words for their brain wallet that were too common and could be guessed easily. something like choosing "123", "qwerty" or "password" as your password.

[OssyRozenberg]

I have MVP on my desk but you keep explaining to me how it works

SHA256 is the basic function of bitcoin used at all stages of its work. Mining chip is not a panacea but acceleration of this function speeds up the whole process. Of course this requires some algorithmic tricks. like a diagnostic codes for a one-time hash generation, adjustment of target to issuing each result, etc.

FPGAs can optimize computations very well. For example, it is known that SHA-512 is faster than SHA-256 on 64 bit machines. HMACSHA512 is not identical, but the optimization paths are the same. I do not ignore this stage - I do not see a problem on this stage.

Why did you decide that it is impossible to count HMACSHA512 as fast as a SHA256? FPGA counts only two stages out of many. I talked about the instruction pipelining in the first post in this sense. This eliminates downtime for the chips. Using a mining chip reduces the power and cost of equipment. This problem can be solved completely on the FPGA but it will be more expensive.

P2PK is changes everything This is a bit more combinations, but it also eliminates half of the heavy functions from the algorithm
Of course the same exhaustion method can be applied to P2PKH too.

Brain wallets are a classic example of a limited dictionary. The dictionary is limited to typical passwords from the list or simple words and phrases. Most brain wallets are encrypted with a combination of no more than three words, usually one. https://eli5.eu/brainwallet/detail/1PzYwVuTotg15ridCGNnAo8u3dr6bE2Yxy.html
English contains a little more than one million words. My device will complete enumerate them in a few weeks.

You say the right things such as "MD5 is safe", "cryptonight is ASICs resistant", etc. But from my point of view, you never programmed on verilog. It is not the same with .NET or PHP cryptography implementations The bitcoin algorithm is well protected from reverse decryption. But against from exhaustive algorithm it is poorly protected. I repeat, security calculations are outdated and do not include the power of ASICs and FPGAs. Direct evidence now flashing LEDs to my eye

[OssyRozenberg]

Updated by new data.

[OssyRozenberg]

A small calculation of effectiveness of using mining chips in bruteforce. Mining chips can greatly reduce the cost compared to FPGA-only solution.
S9 is capable of 14 TH/s (average). The main obstacle for bruteforce of HD wallets is 100.000 hashes. The chip does two hashes by default. In addition, it can load new data during hashing. Using cross-loading, this eliminates the load time losses. Thus, only 50.000 hashes need to be done without load time losses. How many wallets can hash this device? 280 M.wallets/s. S17 Pro can hash 1120 M.w/s.

In reality, the speed will be slightly lower because the hashboard is not designed to high speed communication (for maximum efficiency it is necessary to design ad hoc device). However, in just a few weeks many popular ASICs (T9/S9 etc) will become scrap. These are millions of free SHA-256 co-processors. Design a control board that can turn them into "seedpick" seems like a good idea.
ASIC's consumption will be halved (approximately) plus cascading to a pool. If you had a S9 farm this can be a powerful treasure hunt tool.

Let me remind I do not design a cracker. It will not be able to crack modern wallets. This is a forced restriction that I have programmed. If you have savings on old wallets (created until mid 2012 or started from "1"), just transfer BTC to modern ones and be safe. But abandoned wallets must be opened! As of January, out of the 18.14 million BTC that existed at that time, almost 60% had never moved.

After halving with the current price of Bitcoin treasure hunting becomes more profitable than mining. A rainbow table is valuable too, even if an address with a balance was not found.
Both in mining and in hunting, luck is at the basis. Finding a block using one ASIC is also difficult like finding a treasure with my device. But by combining the power we can do more. The pool is effective in both cases. Consider this factor when trying to calculate how long it will take to find the first treasure

I would like to know the opinion of the community, will such a control board for the resurrection of bitmain scrap be interesting for ASIC's owners? https://ibb.co/pwPgTpG

[OssyRozenberg]

A bit update. The final version of PCBs are ready and sent to me. Hopefully it arrives before christmas...
FPGAs are already received  https://ibb.co/k8BQcph
This year viscous as jelly broke all plans and schedules... 

[NotATether]

Did you test this setup yet? Also, are you only planning to use the ASIC chips to compute one SHA256? Because according to this https://bitcoin.stackexchange.com/questions/84616/how-specific-are-asics-design-can-they-single-hash-sha256 the way they are designed let's them only take a "fragment" of a double hash as input so they are unsuitable for computing single hashes.

So there's a lot of SHA256d hardware scrap lying around in the world but you need to wire logic gates and circuit boards together to create an ASIC that's designed for RIPEMD160(SHA256) and another kind for HMACSHA512. Unfortunately I don't think the ASICs used in bitcoin miners can handle those computations (keeping in mind the word ASIC is a generic term for hardware with logic gates optimized to do one function).

But I'd love to see benchmarks of SHA256 on your FPGA vs. a CPU and GPU. And also those of SHA512 and their HMACs while you're at it.

[Somras]

I can only see this as a thread attempting to find someone greedy enough to PM OP and get scammed hard.

[OssyRozenberg]

Several photos of the current stage: https://photos.google.com/share/AF1QipP2SmhUfXw6m5VmpXNChounStt32iGRhqHsPBErKKVNhSu50osefdQrReEZ4vk1ZQ?key=TGtZM2VvcGFjaG0xYTZzT2JCR2FLYlR5aVl1Mk1R
 

[OssyRozenberg]

Also, are you only planning to use the ASIC chips to compute one SHA256?

I said earlier: the data must be prepared. For example, shifted by nonce (4-byte) and some other operations. The nonce should be loaded as well (is now a part of data). A golden nonce in Bitcoin mining is a nonce which results in a hash value lower than the target. What happens if the target == 0xFFFF....FF? Right: any result will be returned.
There are several ways to generate keys. In some, you have to complete 100k SHA256 hashes (or 50k double hashes). This way allows to reduce the enumeration range, by the way.
Finally, which ASIC do you mean? There are many chips: https://en.bitcoin.it/wiki/List_of_Bitcoin_mining_ASICs
Only Bitmain has four actual chips right now. All chips are different, have different OCD paths, "some ASIC chip" does not exist.

[minkpump]

How was the progress of this? I have two farms with more than 6 thousand s9's.

[OssyRozenberg]

How was the progress of this? I have two farms with more than 6 thousand s9's.

This is being tested now. Some T9's do not want to work with our motherboard. This is a rare problem, but we want to understand why.
Don't throw your s9's, they might come in handy later 



We also ordered a special SHA-256 chip (ACIC) for a personal device. It will be much more effective in a small volume. Additionally, we are losing our dependence on Bitmain chips.
Of course, if you have an Bitmain ASIC you have the chips by default. This problem does not concern you. But for making our own devices, it is difficult to buy new chips in large quantities...

[OssyRozenberg]

One note about the "random" in generation of old wallets (until the middle of 2012).
The entire cluster below belonged to one owner. The entire cluster was generated at about the same time (two months). Just look at the wallets and answer me - is this random or not? 

12Rf4ep2H2eLBbzsqex4G4ajAvpy1HARPn
13KKUHYT2MPTdDkA6XAhFFxDQGDb1GgiFm
16hqbeAuVSmQxaEPA14q9qV3RhhdUYSAQX
16qxewbNQwHYdjQHx9HjEtxXaac9gvituH
16yevHBZG3LSEgMBnEJLhzhSVCd2j7nUXS
179s1AHXYrmzzchdLPaMYVX3qh8SvnhD3n
19Ghp4E3AMgbN62qN8osioaxCENGZWQeoU
19M9bCvvq7ndRs9qV4yuZMycwUYytNB2Xq
1Ad9fAZjGAH1vfL88LhJBSB7h9Dq68BWCu
1BS4NfZ3LtirYp9bJrihQn7QgAyixU3nJL
1BhRJqyS62Yzx4AXwGuN9UZnvp9JorVdfn
1DziNMP2JXwWcxNdqJ2BLy6QjmdmFYbxjx
1E6UhG329LfJ3SxEW7oetPnpq5NyW4pP2m
1HMZUnetUmjavpCUVaLUhyMqfJRciAw3jt
1HUthdvt7ipCrxaFn4KBbAdhAN26CQt3dm
1HW8E6q52wBiMgKWxJpqCa2yGhuydyU1UF
1HcDMPfBVJynh8am1hkyWKfk9bXnS5T3Nz
1LTL4AeuxUFoT5Q2USG6j4KR5ZQTWu5KdJ
1MJFFMaZriohY3udf1buUqAHcdP1totNo5
1MPMsap53sW1c3GLycySHGNC8unWHpQKNL

[NotATether]

How was the progress of this? I have two farms with more than 6 thousand s9's.

This is being tested now. Some T9's do not want to work with our motherboard. This is a rare problem, but we want to understand why.
Don't throw your s9's, they might come in handy later 

What is the keys/second that you're getting from this setup, if you recorded this metric during testing?

[OssyRozenberg]

Note 2.
"It takes a million years to iterate over all combinations of private keys and get the first luck!"
1EHNa6Q4Jz2uvNExL497mE43ikXhwF6kZm has a private key 0000000000000000000000000000000000000000000000000000000000000001  

[OssyRozenberg]

What is the keys/second that you're getting from this setup, if you recorded this metric during testing?

Very much. About 3 orders of magnitude higher than the known solutions.
Additionally, we have developed our own chip. It should be much more efficient and fast. Or more efficient only  

[stilichovandal]

One note about the "random" in generation of old wallets (until the middle of 2012).
The entire cluster below belonged to one owner. The entire cluster was generated at about the same time (two months). Just look at the wallets and answer me - is this random or not? 

12Rf4ep2H2eLBbzsqex4G4ajAvpy1HARPn
13KKUHYT2MPTdDkA6XAhFFxDQGDb1GgiFm
16hqbeAuVSmQxaEPA14q9qV3RhhdUYSAQX
16qxewbNQwHYdjQHx9HjEtxXaac9gvituH
16yevHBZG3LSEgMBnEJLhzhSVCd2j7nUXS
179s1AHXYrmzzchdLPaMYVX3qh8SvnhD3n
19Ghp4E3AMgbN62qN8osioaxCENGZWQeoU
19M9bCvvq7ndRs9qV4yuZMycwUYytNB2Xq
1Ad9fAZjGAH1vfL88LhJBSB7h9Dq68BWCu
1BS4NfZ3LtirYp9bJrihQn7QgAyixU3nJL
1BhRJqyS62Yzx4AXwGuN9UZnvp9JorVdfn
1DziNMP2JXwWcxNdqJ2BLy6QjmdmFYbxjx
1E6UhG329LfJ3SxEW7oetPnpq5NyW4pP2m
1HMZUnetUmjavpCUVaLUhyMqfJRciAw3jt
1HUthdvt7ipCrxaFn4KBbAdhAN26CQt3dm
1HW8E6q52wBiMgKWxJpqCa2yGhuydyU1UF
1HcDMPfBVJynh8am1hkyWKfk9bXnS5T3Nz
1LTL4AeuxUFoT5Q2USG6j4KR5ZQTWu5KdJ
1MJFFMaZriohY3udf1buUqAHcdP1totNo5
1MPMsap53sW1c3GLycySHGNC8unWHpQKNL

You found the treasure.

[hskun]

bro，have any good news?