Topic: generating and guessing BTC-adresses (Read 3983 times)

no. never seen this site. thanks for the link.

and now i know the difference between joke and prank...

The math isn't that difficult.


My math is based on what is impossible today, and what will continue to be impossible in the near future.  The distant future is meaningless and not relevant to the discussion.


Yes.  Time travel was impossible in 1886.  Accelerating an object with mass to a velocity greater than the speed of light was impossible in 1886. Brute-forcing a randomly generated RIPEMD-160 was impossible in 1886.


Something can have a "non-zero mathematically calculated probability" and still be considered "impossible" within the confines of the real universe.


It doesn't need to be perfect.  Nobody is going to be able to brute-force a 160 bit number in 10 years.  Now, there certainly might be mathematical advances that make attacks on RIPEMD-160 easier within the next 10 years, but pure brute-force isn't going to be possible.  If RIPEMD-160 is sufficiently weakend, then a new algorithm will be used.  Fortunately bitcoins are protected by more than just RIPEMD-160.  A broken RIPEMD-160 will only let you generate the results of a SHA-256 hash.  Then you'd have to also break SHA-256 to generate a public key. Then, after that, you'd still need to break ECDSA to calculate a private key from the public key before you could successfully sign a transaction.


Only 100 million users?  Look back at my post.  I based my calculations off 1 BILLION computers all generating and checking the balances of 1 BILLION transactions per second. I also assume that there are 2.1 quadrillion addresses.  Your evil genius isn't very scary.


Absolutely!


Clearly.  You prefer to just say "it's possible" regardless of what that actually means and without any evidence at all.


No.  It isn't.


No. It isn't. Not with any reasonable definition of the word possible.


My math is fine for any "situation" that exists today or in the near future.


No. It doesn't. The graphic is talking about 2²⁵⁶.  That is a VERY different number than 2¹⁶⁰

2²⁵⁶ is almost 800,000,000,000,000,000,000,000,000 times bigger than 2¹⁶⁰

Would you say that a graphic about the number 1 makes it easier to imagine what sort of number 800,000,000,000,000,000,000,000,000 is?


Perhaps it isn't, no matter how many times you try to say that it is.


Please do.


What does any of this have to do with carbon dating?


I might not be able to tell you exactly how many calculations any one particular person can generate (and check the balance of) per second.  But I CAN demonstrate a number of calculations per second so large that any reasonable person will agree that that it is currently impossible.  Then, I can demonstrate that even with that unrealistically large number of computations, you still can't brute-force RIPEMD-160.  

Hello Danny and hello all,

I say your math is not accurate, and also I cannot fully agree with calculation made by David Perry.
I guess no one can calculate it accurately.

Reason is simple - your math is accurate with specific assumptions. But your assumptions may vary depends on a situation.


Do you know what was "impossible" in 1886?
As you already wrote "there is a non-zero mathematically calculated probability".

And I agree that it's (almost) "impossible".

Imagine a situation. Year 2025 - Bitcoin is still around and everyone loves it.
You don't know how fast the GPU and CPU will be in 10 years. Moore's law is not perfect as you know.

Let say that some evil genius built a botnet, botnet made from 100 000 000 of users. Possible, why not.
He will be able to generate such amount of addresses which we cannot imagine - per second.

Still, his chances are close to "none". But will you still say the, that this is impossible?


Yes, I did. I sent you a link because it's very interesting and it's bringing more infos about what we are talking about.
I didn't used it as a evidence.  I used it as a good thing to read if we talk about RIPEMD160.
I don't need the evidence that collision "is possible to" happen one day.
Simple math is telling me that it "can" happen.


It's hard to say how many addresses you can generate with super powerful computer. We can put any number as a variable... because we can make 20 million, 20 billion, more more ...
So that's making those calculations not really accurate.


I keep saying that... From theoretical point of view, collision is possible.
Your math is not accurate because at least one variable may change depends from a situation.


This graphic makes it easier to imagine what sort of a number we are talking about.


If it's so simple, why your calculation is not accurate? Let me ask some primary school student to teach you

This kind of a calculation is as accurate as carbon dating. So it's not accurate. And cannot be. Or maybe you can calculate how many addresses we can generate per second? How can you do that? You cannot. So it's not accurate.

Best regards.

While I'm willing to accept that I may have made an error in my maths, you didn't point out any errors at all. Please explain why you think my math is not accurate and where you believe I made the mistake.


There really isn't.  Sure you could say that there is a non-zero mathematically calculated probability, but that probability is so low that we humans would generally use the words "impossible" and "there isn't a real chance" to describe it.

There is also a non-zero mathematically calculated probability that oxygen molecules moving randomly around a room might spontaneously move far enough from the breathing holes in your face for long enough to suffocate you.  Are you really willing to say that "there's still a chance"?



And yet the article you linked to specifically says the following:

"While RIPEMD and RIPEMD-128 reduced to 3 rounds are vulnerable to the attack, it is not feasible for RIPEMD-160"

"we show that methods successfully used to attack SHA-1 are not applicable to full RIPEMD-160."

"no attack has been found for the original RIPEMD-160 hash function"

"we can state that RIPEMD-160 is secure against known attack methods"

"existing attacks on RIPEMD are not applicable to RIPEMD-160"

"we conclude that the final attack complexity would be too high for a reasonable attack"

"the probability of the found L-characteristic is too low for an attack on RIPEMD-160 following the strategy described"

"We found no attack on the original RIPEMD-160 hash function including all 5 rounds. In summary, we state that RIPEMD-160 is secure against known attacks. Neither the attack of Dobbertin or Wang et al. on RIPEMD can be extended to RIPEMD-160, nor recent methods used in the cryptanalysis of SHA-1 are applicable to full RIPEMD-160."

Did you even read that document before trying to use it as evidence that "RIPEMD-160 collision can happen"?


And my math was based on 1 BILLION computers all running 1 BILLION addresses per second.

How does a 20 million address GPU card make my math incorrect?


Sure, and in his article he indicates:

"Now we’re down to 2.43e+28 seconds between hits or 771,000,000,000,000,000,000 years between hits"

My estimate was 2,190,476 years, but that's because i was calculating a 1% chance of a hit instead of an almost certain hit.  Additionally, I explained that my calculations were based on the "worst case scenario" of the bitcoins being spread out to 2,100,000,000,000,000 addresses with exactly 1 satoshi in each address.  Realistically this would never happen, and Mr. Perry chose to work with only 60,000,000 addresses.


You keep saying this, and you keep saying that my math is incorrect, but you haven't provided any evidence yet of either of your statements being true.


It's a great graphic.  Did you read it?  It specifically states:

"brute-force attacks against 256 bit keys will be infeasible until computers are built from something other than matter and occupy something other than space"

Of course, I'm not sure why you even posted a link to that image since we are discussing a 160 bit hash and not a 256 bit key.



Yes it is.  That may be why people like you keep confusing others by saying that a collision is "possible".  If you could really comprehend such a large number, you wouldn't be saying that.


It's really a pretty simple calculation.  Why do you say it's "hard"?  I think any high school student should be capable of it (and probably many primary school students).

Hello,

Your math is not accurate.
I will share with you some interesting materials which I found few years ago when I was doing my own math for this situation.

But 1st let's start from the beginning:

A chance to generate same address - to generate a collision is tiny. But still - there's a chance.
If you will somehow manage to do that you will be a legend.

The RIPEMD-160 collision - because this is how we will perhaps name that moment - can happen.
https://securewww.esat.kuleuven.be/cosic/publications/article-1355.pdf

I said that your math is not accurate, because simple Radeon GPU card can generate more than 20 million addresses per second.

David Perry wrote very interesting article where he included his calculations : http://codinginmysleep.com/stealing-bitcoins-the-hardest-way/

Still - is it possible to generate same address - address which is already in use by other Bitcoiner and have some founds on it? Yes. It's possible.


Have a look at this interesting graphic (I will share a link instead of preview it here, it's quite large):
http://bitcoinet.pl/wp-content/uploads/2013/10/fYFBsqp.jpg


2^160 is a number which is really hard to image by human brain.


It's hard to calculate how many years you will need as today's computers are pretty fast, so you can literally generate (hundred) millions of addresses in your home with a standard gaming PC per second.

It equald to = Chance is pretty little and it's not worth such effort/time/energy.


Best regards.

Thanks Danny, Appreciate the help. These are hypothetical questions. The answers to which help me (and others who view this) better understand the inner-workings of the software.

No.  A single ECDSA public key on the Secp256k1 curve only corresponds to a single private key.

However, each bitcoin address corresponds to (on average) 7.9 X 10²⁸ ECDSA public keys on the Secp256k1 curve.


You can.  You would be wasting your time and your money, but you can try if you want.  You'll spend electricity to run the computer for a few billion years, and you probably still won't find the exact address.  Do you really think people will still be using bitcoin a few billion years from now?

Hey OP,

Have you seen this website: http://directory.io ?

Thanks for the clarification Danny, really appreciate your time and contribution. Great explanation

Help me get this straight... A single Public Key can have multiple private keys?

 I mean, can I use Vanitygen and input an exact address, in hopes of generating the keypair?

thanks

Addresses that have been used in the past are indirectly stored in the blockchian as part of the TX data. Pubkey/script is stored; address is the hash.


Bitcoin is not a server client system, which server are you talking about?


Not exactly, its just very unlikely see the answer by DannyHamilton direclty above your post.

Here are the answers according to what I think.
No, your wallet doesn't save all the addresses generated. In fact, it only saves address of your wallets which are you using currently. Nothing other than that. These addresses aren't saved in blockchain either. But, if someone in the future gets this address then, yes it will be saved on blockchain's server.
And two persons cannot generate the same address offline, its merely impossible for this to happen..
Such a long string of Numbers and alphabets can never be exactly the same.

If you run 1 billion computers that are each generating and checking the balance of 1 billion addresses per second, you would (at best) have a 1% chance of finding a 'used' address in about 2,190,476 years.

Lets look at the math.  It really isn't that difficult...

There are 2¹⁶⁰ possible addresses.

2¹⁶⁰ is approximately 1.46 X 10⁴⁸ total addresses.

If 1 billion computers are generating 1 billion addresses per second, that's:

1,000,000,000 X 1,000,000,000 = 1,000,000,000,000,000,000 (or 1 X 10¹⁸) addresses per second.

There are about 31,557,600 seconds in a year.

So if we multiply the number of seconds in a year by the number of addresses per second, you'll get about 3.16 X 10²⁵ addresses per year.

If we divide the total number of addresses possible by the number of addresses that can be checked per year, we find that it would take:

1.46 X 10⁴⁸ divided by 3.16 X 10²⁵ = 4.6 X 10²² years to check all the addresses.

Divide that number by 100, and we find that it will take 4.6 X 10²⁰ years to check 1% of the addresses.

There can never be more than 2,100,000,000,000,000 addresses storing a balance at any given moment in time.  Therefore, if we assume that bitcoins are spread out with exactly 1 satoshi in every address, we can divide the  4.6 X 10²⁰ years by the number of potential addresses...

4.6 X 10²⁰ divided by 2.1X10¹⁴ = 2,190,476 years.

I think your odds are very very very wrong. Do your research before posting.

There are 2^160 or about 1,460,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible addresses.
It is going to take a very very long time to exhaust all of those addresses. And the likelihood of a collision is so small that you won't be able to get a collision in 20 years.

If you're running several machines with full blast, I think you should get atleast 1 address in 10-20 years. I don't know the exact odds though.
Odds increase as more wallets are being created.
Sooner or later we do have to switch to a new algo because the rise of global computing power.

What if someone were to generate keypairs randomly while simultaneously scanning the blockchain for any addresses generated that have previous inputs? How unlikely is it to generate a 'used' address?

interesting. @John (John K.) thans for the background link. i think it is important to understand BTC if you want to use it.

The number of possibilities is so much more that it'll take more then the energy then the heat death of the universe to generate it.

More background: http://stackoverflow.com/questions/4014090/is-it-safe-to-ignore-the-possibility-of-sha-collisions-in-practice

Only because our brains ability to imagine possiblities when it comes to big numbers is very limited doesn't mean it is likley to happen.
If I remember correctly the adress space is something like 2^160, right? Good Luck finding a collision! 

If that is your conclusion, so is everything else. The connection to your online banking, to paypal, facebook, google and many other encrypted connections are secured by the same mathematical principles. Eliptic curves -> https://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography and our limitation to check all these possibilities.