How long until bots can profitably guess private keys?

[HarmonLi]

OK, newbie here but please bear with me because I'm sure many people reading this thread would like to ask this same question but are afraid to look noob. You keep saying not to reuse addresses and keep balances on new addresses. Now as I understand it, in order to send coins to any address the network needs to be made aware of it by means of a transaction which will be forever recorded on the blockchain with the public keys of the addresses. So what's the point in tranferring the coins to a new address if its public key is going to be made public by the transaction anyway, even if the address owner only made that single transaction using that address?

Addresses aren't public keys.  Addresses are public key hashes (or script hashes).   Hashing functions are one way.   Knowing the hash doesn't allow anyone to know the key.  When you spend the coins you reveal the key and other nodes verify it hashes to the pubkeyhash in the output you are spending.

I never really totally understood the difference between an address and a public key. Some people say there's some difference, but what is it exactly and what are the consequences?

[DeathAndTaxes]

I just said exactly what it is.  The Address is a HASH-160 of the public key not the public key itself.  It also contains version and checksum information but is stripped away by the client.

PubKeyHash = RIPEMD-160(SHA-256(PubKey))

[HarmonLi]

I just said exactly what it is.  The Address is a HASH-160 of the public key not the public key itself.  It also contains version and checksum information but is stripped away by the client.

PubKeyHash = RIPEMD-160(SHA-256(PubKey))

Okay, some people now claim that you want to keep your public key unknown. Why is that so? I do understand, that an unknown private key is crucial, of course. But why the public key?

[DeathAndTaxes]

Okay, some people now claim that you want to keep your public key unknown. Why is that so? I do understand, that an unknown private key is crucial, of course. But why the public key?

If there is a flaw or weakness in ECDSA it will require knowing the public key to exploit it.  If quantum computers can ever implement Shor's algorithm to break public key systems it requires knowing the public key.  There are also other advantages of not reusing addresses.   If your wallet has a flawed PRNG using the same k value in signing is only a problem if the same private key is used.  If you aren't reusing addresses then you will never sign two transactions with the same private key so even if the same k value is used you won't have flawed signatures.  Not reusing addresses also improves pseudo-anonymity.

[HarmonLi]

Okay, some people now claim that you want to keep your public key unknown. Why is that so? I do understand, that an unknown private key is crucial, of course. But why the public key?

If there is a flaw or weakness in ECDSA it will require knowing the public key to exploit it.  If quantum computers can ever implement Shor's algorithm to break public key systems it requires knowing the public key.  There are also other advantages of not reusing addresses.   If your wallet has a flawed PRNG using the same k value in signing is only a problem if the same private key is used.  If you aren't reusing addresses then you will never sign two transactions with the same private key so even if the same k value is used you won't have flawed signatures.  Not reusing addresses also improves pseudo-anonymity.

Ah alright, thanks! But if ECDSA fails, the whole Bitcoin experiment will fail altogether, I guess

[DeathAndTaxes]

Ah alright, thanks! But if ECDSA fails, the whole Bitcoin experiment will fail altogether, I guess

Probably not.  Most people think of cryptography as "perfect" or "failed" but the reality is it is a lot more like a sliding scale.  SHA-1 is considered cryptographically weakened because collisions can be created in less time (2^61) than brute force (2^80).  Just because it is weakened doesn't mean you can trivially produce a collision; 2^61 is still a lot of computing power.  To date nobody has produced a SHA-1 collision despite it being "weak" for years now.  Bitcoin could have used SHA-1 for a proof of work and it would have worked just fine despite SHA-1 being "weak".

Imagine a scenario in the future where ECDSA is weakened and someone with a massive amount of computing power (say one month of time of a supercomputer) could break your private key if they know your public key.   If your public key is known they could steal your coins.  If it isn't they can't.  So Bitcoin could implement a new address system and funds could be safely transferred by owners whose public keys are not known.

[Malin Keshar]

If its going to happens, then 99% of world's crypto system will be as much vulnerable and the world will turn upside down amd the last of our concerns will be bitcoin private keys.

Also there are much more interesting and profitable things to do with such computer power, so I think our wallets are safe, at least in the sub-500b bitcoin's market cap.

[HarmonLi]

Ah alright, thanks! But if ECDSA fails, the whole Bitcoin experiment will fail altogether, I guess

Probably not.  Most people think of cryptography as "perfect" or "failed" but the reality is it is a lot more like a sliding scale.  SHA-1 is considered cryptographically weakened because collisions can be created in less time (2^61) than brute force (2^80).  Just because it is weakened doesn't mean you can trivially produce a collision; 2^61 is still a lot of computing power.  To date nobody has produced a SHA-1 collision despite it being "weak" for years now.  Bitcoin could have used SHA-1 for a proof of work and it would have worked just fine despite SHA-1 being "weak".

Imagine a scenario in the future where ECDSA is weakened and someone with a massive amount of computing power (say one month of time of a supercomputer) could break your private key if they know your public key.   If your public key is known they could steal your coins.  If it isn't they can't.  So Bitcoin could implement a new address system and funds could be safely transferred by owners whose public keys are not known.

That's an interesting analysis! I really wonder when people effectively would consider bitcoins cryptography to be 'broken' for it to fail. Interesting!

[joele]

Here is the database of all bitcoin addresses and private keys
http://directory.io

Good luck finding an address with fund  

[HarmonLi]

Here is the database of all bitcoin addresses and private keys
http://directory.io

Good luck finding an address with fund  

Woah, awesome! I will now go through them and empty a few! Finally! Quick, before this affects the price....

[Yakamoto]

Here is the database of all bitcoin addresses and private keys
http://directory.io

Good luck finding an address with fund  

This exists... Why?

And how... How did they get all of this information?

I suddenly feel more worried about brute force attacks...

Even if they have all those pages, it still is a bigger threat than having people try and guess them. A group of efficient bots could easily run through a lot of addresses if they're given all that info...

On an unrelated topic, how would one be able to use another private address  

[jonald_fyookball]

  If your wallet has a flawed PRNG using the same k value in signing is only a problem if the same private key is used.  

I understand reuse is bad, even for multiple receives because at some point you need
to get the money out of the address and thus there's an attack vector of a listening node
that probes for duplicate k on the same transaction, since each input has it's own scriptSig.

What is unclear to me now, though, is why is this different from just receiving a single transaction
with multiple inputs (for example dust gathered from a wallet and sent out).

In both cases you have multiple inputs, so why is it a problem if they were sent in separate transactions vs together?

[deluxeCITY]

Here is the database of all bitcoin addresses and private keys
http://directory.io

Good luck finding an address with fund  

Woah, awesome! I will now go through them and empty a few! Finally! Quick, before this affects the price....

I don't think this is actually all of the possible private keys as this would take a very long time to download.

[Yakamoto]

Here is the database of all bitcoin addresses and private keys
http://directory.io

Good luck finding an address with fund  

Heh... Millions upon millions of pages that you have to manually click through...

Welp, my hunting is over, although someone else is surely going to go through a lot of them. I won't be that person, though. So many addresses that are nearly the same...

[Yakamoto]

REALLY?

REALLY GUYS?

YOU'RE ACTUALLY SEARCHING?

Well, I guess it can't be helped, but I really didn't think everyone would suddenly go gung-ho and start checking every key for funds...

Kinda sad actually. So many people who want to get rich quick, and just want to take stuff for themselves...

[jonald_fyookball]

REALLY?

REALLY GUYS?

YOU'RE ACTUALLY SEARCHING?

Well, I guess it can't be helped, but I really didn't think everyone would suddenly go gung-ho and start checking every key for funds...

Kinda sad actually. So many people who want to get rich quick, and just want to take stuff for themselves...

Don't be stupid.  They don't have every key.

You could have a trillion trillion trillion trillion terabyte drives and still
have but a tiny fraction of the diskspace required.

[Yakamoto]

REALLY?

REALLY GUYS?

YOU'RE ACTUALLY SEARCHING?

Well, I guess it can't be helped, but I really didn't think everyone would suddenly go gung-ho and start checking every key for funds...

Kinda sad actually. So many people who want to get rich quick, and just want to take stuff for themselves...

Don't be stupid.  They don't have every key.

You could have a trillion trillion trillion trillion terabyte drives and still
have but a tiny fraction of the diskspace required.

True, but even just trying for the ones they DO have, it's kind of annoying.

And that is a HUGE amount of pages, and 99.999% of addresses (While I was searching for fun) have 0 funds. So it is useless to even go through a database of them, especially since there are so many addresses...

I still can't believe how many pages it has, though...

904625697166532776746648320380374280100293470930272690489102837043110636675 pages...

It would still take forever to go through anyways, so I wouldn't be too worried about someone cracking it like this. But you never know...

[jonald_fyookball]

I still can't believe how many pages it has, though...

904625697166532776746648320380374280100293470930272690489102837043110636675 pages...
 

That's because it doesn't.

[Yakamoto]

I still can't believe how many pages it has, though...

904625697166532776746648320380374280100293470930272690489102837043110636675 pages...
 

That's because it doesn't.

Yes it does...

I can even type in directory.io/904625697166532776746648320380374280100293470930272690489102837043110636675 and it will give me new keys, just like every other page.

So... what do you mean? They're all new addresses, so I don't see why they don't have so many pages.

[DeathAndTaxes]

What is unclear to me now, though, is why is this different from just receiving a single transaction
with multiple inputs (for example dust gathered from a wallet and sent out).

In both cases you have multiple inputs, so why is it a problem if they were sent in separate transactions vs together?

I may misunderstand the question but all that matter is multiple unique messages (sub txns) being signed with the same key and same k.  If that happens the k value can be recovered and from the k value the private key.   It doesn't matter if this occurs in a single txn (spending multiple outputs) or multiple txns (each spending one output).  If either k is unique or the key is unique there it is infeasible to recover k.  Obviously k "should" be unique and if it is there is no risk of reusing an address (at least not due to k exploit).  If however you were unlucky and used a wallet with the flawed android PRNG you would still be safe if each key only had a single input to spend.