Bruteforcing Bitcoin - Feasibility of the "Impossible"

"Because everyone said it is impossible, no one had tried right."

The Large Bitcoin Collider (LBC) tries to crack Bitcoin addresses per Brute Force.
In the recent weeks, the project has shown first successes.
What does this mean for Bitcoins safety ?!

• Stats:
  https://lbc.cryptoguru.org/stats
• The LBC Server
  http://lbc.cryptoguru.org:5000/

Rico, the head behind the LBC, explained the details in an interview,
on https://bitcoinblog.de/

• (orginal/german source)
  https://bitcoinblog.de/2017/04/06/das-weiss-ja-keiner-einige-behaupten-das-weil-sie-die-alternative-aengstigt/#prettyPhoto

---

• [translated / summarized version]

---

"Who are you and why you choosed the domain cryptoguru.org?"

---

I am a computer scientist. I just liked the Domainname.
I rent the cryptoguru.org domain and some hardware for a small bitcoin amount annually.

---

"You are running the Large Bitcoin Collider (LBC), which is used to search for collisions of Bitcoin addresses.

How did you come up with this idea and what do you want to prove ?"

---

In July 2016 I discovered the website http://www.directory.io/, which allegedly lists all Private Keys !
The message was, meaningfully: "Are there also my Keys in it ?
Yes, but no one will ever find it. Because ... mathematics.
This reminded me of similar cases in computer science.
(for example, all the works of Shakespeare are encoded in the PI number).

I did some research and found on bitcointalk.org, that people actually have tried to scrape directory.io and look into the addresses for content. I thought that this should be done better.
At first it was just an idea, but when I thought about i realized that you don't have to look at the whole 256bit, but only 160 bits.
The collision idea was born.
Then I thought, "Let's see how that goes!"

I just want to prove that many people can sometimes be wrong, even if they claim that something is impossible.
Because everyone said it is impossible, no one tried it right !

---

"If I understand this right, the LBC is a Brute-Force-Attack on any bitcoin address.

Can you explain how LBC is operating?"

---

Let's start how a Bitcoin address is created: You take a private key (a random string of a given length). This is calculating a public key, using coordinates on an elliptic curve. This you hash with SHA256. If you calculate this result with a RIPEMD160 algorithm, you have a hash160 ! Which is actually the Bitcoin Address ! To be able to read them better, this is coded with Base58, which means we have the popular bitcoin addresses ("1something...").

The Large Bitcoin Collider (LBC) clients have all hash160 addresses with more than 0 BTCs. He simply counts the private keys - we are interested in 2¹⁶⁰ - and calculates from this hash160. He compares this with the addresses where Bitcoins are stored.

---

"How likely or unlikely is it to find an address that has already been used?"

---

Of yourse there are many extrapolations, but the more you deal with it, the more unknown variables can be recognized. At some point, this looks like the Drake equation, which wants to estimate how many intelligent civilizations there are in the Milky Way, and you have to conclude that you do not know exactly.

As an example: There is only a maximum of 2¹⁶⁰ possible addresses and not 2²⁵⁶ as many believe. The 2¹⁶⁰ also only if RIPEMD160 is surjective, and really include the entire range of possibilities. What we hope, but do not know ...
There are currently about 15 million addresses with a credit (2²³). If we assume that they are uniformly distributed over the search space, this means that of 2¹³⁶ addresses ONE has a credit.
If we now assume that you can scan 2³⁶ addresses per second, then you need 2¹⁰⁰ seconds, which means 40196936841331 billion years, until you find this ONE address.

So it is quite unlikely that it will succeed. But we have already found 3. Hmm?

---

"According to your website, you produce 587 Megakeys per second. This is quite a lot. What hardware is behind it?"

---

That was yesterday. At the time when I write this answer, the pool has just 1196.22 Mkeys / s (During proofreading: 1238.53 Mkeys / s). Most are CPUs and a few GPUs. But however the hardware is less relevant than the software.

I reported about the people who scanned the directory.io with a script to parse and analyse it. They needed 20-30 seconds per page. On one side are 128 keys, 256 addresses (uncompressed, compressed). So they started with just 6 keys per second.

I tried to do better. With a little experimentation I could increase the rate of keys per second extremely.
First I used vanitygen, which let me managing 100 keys per second. Then I got the sources of directory.io parsed it directly, which enabled 13,000 keys per second. Then I thought why Base58, if hash160 is enough.
....40,000 keys / s
When Ryan Castellucci told me that his brainflayer is much faster, I tried it. :
I was at 520,000 keys / s !
Then I really worked into... SHA256, studied RIPEMD160, re-polished my C knowledge.
Slowly but steadily I rebuilt brainflayer to HRD core and i get 720,000 keys / s.
At the time, I had the fastest RIPEMD160 CPU implementation. But it wasn't fast enough yet.
So I looked into the secp256k1 code and tried to use GPUs.
But no one ever wanted to write a GPU adaptation.
So i developed it from the scratch.
It wasn't perfect, but it gave me 2.2 million keys / second.
But it goes even further: The user "arulbero" on Bitcointalk made some suggestions how to improve the elliptic curve arithmetic, and has worked on his own library for it. In the meantime, I added more operations to the GPU, and on 25.3.2017 we comdined it : We've thrown the libsecp256k1 out of the code and replaced it by the arulbero-EC arithmetic.

The result is currently 5.5 mio keys / s per CPU core !

The LBC pool now allows everyone to provide their hardware for search, as this search can be perfectly parallelized.
So there should be a few hundred CPU cores working with us.

---

"On the side with your statistics, you say: the probability is 0.0000000-something that you have a 50 percent chance of a collision over the next 24 hours.

Does that mean you won't find anything within 1,000 years (or so)? "

---

You know the story of the water lilies and the pond ?

• Day 1: 1 water lily
• Day 2: 2 water lilies
• Day 3: 4 water lilies
  etc.

After 27 days half the lake is full of water lilies. After how many days is the whole lake full?
You write 0,000something...
Let's take a closer look at the numbers:

0.00000000000000000045% (17.9.2016)
0.00000000000000200548% (23.9.2016)
0.00000000002801022860% (28.3.2017)
0.00000000016406321697% (04.4.2017)

I guess that everyone can see if we have to think about the future over a period of 1000 years...

"Recently you have succeeded some collisions with change money addresses. Were you surprised?"

I was 50% surprised ;)

"How can this happen several times? Were the addresses specially generated, for example with too little entropy?"

Nobody knows this. Some claim this because they frighten the alternative. Others have expressed doubts, whether these are actually findings or we simply "placed" it.
I can assure everyone that these findings are real ! Whether bad entropy or the first half of a collision - we don't know yet.

---

"The addresses had only minimum amounts. What do you do when you find the keys for the wallet from BitStamp by accident?"

---

It should be the same as with previous founds: Transfer to a depository address and make the find public. Than the "legal owner", can request the return in a period of 6 months: simply show his other key. We have our collision and he has his bitcoins.

---

"You have already found several "trophies" from a "puzzle" transaction. What's it all about?"

---

Ryan Castellucci got my attention to the puzzle transaction. This seems to be an almost 33 BTC expensive warning system that someone built, to see how secure Bitcoin P2PKH addresses are.
In this case, 0.001 bitcoin were deposited per bitentropy of the private key.
Up to number 50 all were cleared as early as 2015.
So you should not use 50 bit key lengths.

"There is this graphic with the sun, and it says: even if you would cover the whole surface of the sun with perfect processors and burn all the energy of the sun, there would be just a little chance of biting a Bitcoin address. Is this just marketing ?"

Yes. Graphic's like this also impressed me when I saw it for the first time, but the numbers are not realistic !
Bitcoin is protected "very good". But not as good as this (and others) mystify.

"Could a cluster of supercomputers clear Bitcoin addresses? Would it be possible to build an asic which is mining bitcoin this way ?"

Bitcoin addresses can be cleared without a calculator. If I have the associated private keys. Can a cluster of Supercomputers find private keys? Yes !

Could an ASIC do what CPU / GPU currently do with our software? Yes.
If the max. at GPUs is reached, I will look at FPGAs.

---

"Would a quantum computer help to find collisions?"

---

Possible, but I don't want to speculate.
Only so much: Even before the quantum computers, I see another technology, which would possibly make P2PKH / P2PSH addresses much more vulnerable. But this must be enough as a teaser. There are no details from me.

---

"How can users protect themselves against collisions? Is there any way to make it more unlikely?"

---

Regrettably, the (supposed) correct functioning of SHA256 and RIPEMD160 is responsible for the fact that I have to answer this question with "No".

A possibility was discussed to protect P2PKH addresses especially before the LBC. This would be the use of a private key from the range 2¹⁵⁹+ rand (2¹⁵⁸) - for these keys, the probability of collisions with other keys in the first 160bit search area is the least, and the longest time until the LBC will look into it.

---

"It's a bit disturbing. Would you currently store large Amounts of Money ​​in Bitcoin?"

---

Yes, I have some Bitcoins and the LBC is not changing this. But In my view it's to risky (independent of the LBC) that there are addresses storing 100,000+ Btc.
I wouldn't trust a combination of 160 zeros and ones an equivalent of more than 100 million US$.

LBC Trophies
https://lbc.cryptoguru.org/trophies

---