Is/will Bitcoin wallet trawling become a thing/threat ?

[Fuzzy]

I recently realized that a private key is randomly generated by the client software (guess you could make one up too and pull the public key for it) without connecting to the network.
The client simply generates a random key for the wallet an calculates the public key for you to use.

I'm no programmer, but providing you had a copy of the blockchain, you could technically guess random private keys and check the corresponding public addresses to see if they have any bitcoins on them.

Note that I am fully aware there are ~2x62^33 possible combinations (maybe more?), and only a tiny fraction of those have ever been used for a wallet, let alone have any meager balance on them.

So, is this possible, despite being even more unlikely than winning the lottery?

[foggyb]

I'm no expert, but I expect this would take till all eternity just to find one. Even vanitygen takes days just to find one instance of a 10 digit word in a key at 22 million hashes/sec on a good GPU. Now imagine having to not only find a full valid key (impossible already), but also having to verify every privkey after generating it.

You could get lucky, but what are the odds of finding a wallet of any significant value? Doesn't vanitygen create millions of useless wallets per second, to add to the senseless nature of the exercise?

If someone can inform us on the actual probabilities, would be nice.

[Revalin]

I am an expert.  Yes, it's theoretically possible, but not plausible.  2^160 is a very large number and human civilization will end before a duplicate key is found either accidentally (simply not going to happen) or on purpose (physics imposes some hard limits on computation; we're nowhere near it now, but it will put a halt to moore's law before it becomes a plausible problem, let alone one that's economically worth pursuing).

Edit: I should add, "on purpose" only includes brute force approaches.  Quantum computers can reduce the complexity to 2^80; it's not certain that quantum computers capable of handling this much data are possible, let alone fast enough to process that many operations economically; but it's a possibility.  It's also possible that a cryptographic flaw will be discovered in RIPEMD, SHA, or ECDSA.  For now brute force is the only possible approach, and it's not a plausible problem.

[Fuzzy]

imagine having to not only find a full valid key (impossible already)

A valid PRIVATE key is just a randomly generated number, literally anything starting with a 1 or 3 followed by 33 more characters made of numbers, letters and capitals. The public key just uses the standard non-reversible algorithm to calculate the public address from the random Private key. No?

2^160 is a very large number.

Is 2^160 the actual number?

I thought a key starts with a 1 or a 3 (that's the 2x) followed by a number, a letter, or a capital (10 + 26 + 26) for the remaining 33 characters, 34 in all, so 2x62^33

Again, Joe Plumber here.

[DeathAndTaxes]

imagine having to not only find a full valid key (impossible already)

A valid PRIVATE key is just a randomly generated number, literally anything starting with a 1 or 3 followed by 33 more characters made of numbers, letters and capitals. The public key just uses the standard non-reversible algorithm to calculate the public address from the random Private key. No?

2^160 is a very large number.

Is 2^160 the actual number?

I thought a key starts with a 1 or a 3 (that's the 2x) followed by a number, a letter, or a capital (10 + 26 + 26) for the remaining 33 characters, 34 in all, so 2x62^33

Again, Joe Plumber here.

You are confusing private key with public address.

private key = 256 bit number.  It is simply a number it can be expressed in hexadecimal, binary, decimal, or base58 but it is simply a random number between 0 and  115,792,089,237,316,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000  (aprox).

public key = 256 bit number.  derived from the private key using ECDSA.

public address = 160 bit hash of the public key with some formatting, version information and cheksum added.

The public address is constructed from the public key which is derived from the private key.  Not every possible combination of digits in public key is a valid address, actually less than 1 in 4 billion are.

Despite the public & private keys being 256 bit since they are hashed into the public address the collission space is 2^160.  

There is no "feasible" attack on a random number that large.  Not even with all the computing power on the planet and millions of years.

[Etlase2]

And to add to D&T's post, while the hash space may only be 160 bits, you can't just search for a collision because you need the private key, not the public key, to do anything with it.
This means you need to calculate a public key from a private key which is about 100x slower (or somewhere thereabouts) than just searching for a collision.

But the whole "all the computers and a million years" is most certainly off. 160 bits is good for a really long time, but not eternally. 56-bit encryption used to be the security standard, and it was cracked in 23 hours a decade ago. But, it is likely that ECDSA will be the weak point before any hashing algorithm with QC or other vulnerabilities discovered down the road.

[Fuzzy]

it is simply a random number between 0 and  115,792,089,237,316,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000  (aprox).

Ok, well, let me rephrase the question then:

If someone were to build a time machine...

[Coinabul]

it is simply a random number between 0 and  115,792,089,237,316,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000  (aprox).

Ok, well, let me rephrase the question then:

If someone were to build a time machine...

And someone also bought a busload of chimps and made them type on typewriters...

[Revalin]

Is 2^160 the actual number?

The weakest link for brute force of any address is the RIPEMD-160 hash.  Yes, you can steal the coins from an address with a different key pair if you happen to find one that has the same RIPEMD-160(SHA256(pubkey)).  Good luck. 

Once coins have been sent FROM the address the pubkey is known and ECDSA is probably the weakest link (about 128 bits of security equivalent).  This may be plausible to attack in the distant future, but probably not in my lifetime unless a cryptographic flaw is discovered.

I thought a key starts with a 1 or a 3 (that's the 2x) followed by a number, a letter, or a capital (10 + 26 + 26) for the remaining 33 characters, 34 in all, so 2x62^33

Pubkey hashes always begin with 1.  It's base58 - I, l, 0, and O are excluded.  The actual address size is therefore 58^33.  That corresponds to 2^(160 (hash) + 32 (checksum)) plus an extra bit or two.

[Frozenlock]

I saved a quote from this forum for this kind of question:

Quote from: TiagoTiago on June 28, 2011, 09:14:06 pm
If mining hardware was instead dedicated to generating new addresses; how long do you think would it take till someone stumbled on an existing address that had more BTC stored than what the person would have earned by mining?
----
Never. Even if the whole generating network was behind it, it would probably never even stumble upon a previously used address, much less one that is worth more than the number of blocks it could have generated instead. Generating blocks is trivial compared to this.

Their are 2^160 possible addresses. Lets say 2^32 (4 billion) people use Bitcoin and each generate 2^16 (65 thousand) address. That gives us 2^48 total addresses out of 2^160 possible. The probability of a generated address matching one of these is 1/(2^112). The probably of finding a block at 35 times the current difficulty is around 1/(2^64). Therefore, it would take 2^48 (281 trillion) times longer to find a previously used address. So if it takes you ten minutes to find a block, it will take over five billion years to find a used address.

Now keep in mind that we don't have 4 billion users, most users have far less then 65 thousand addresses, and the current difficulty is much lower then I used in these calculations. Mining sounds a lot more profitable.

NOTE: I assumed generating an address took equal time as generating a proof-of-work hash. However, I believe generating an address is actually slower since it involves both EC key generation and hashing.
-EricJ2190

[Realpra]

Lots of people will be screwed if the random number generator is implemented badly:

Example:
"Gen()->Return time*12"

I can now easily find a bunch of keys by searching (generating key/address pairs) only the times from 2009 to 2012 - my chances would then be VERY good for finding some private keys with cash - even if "time" was milliseconds.

I am however assuming that the implementation is a lot better than my example or by now massive theft should have happened to all those with bad clients.