Bitcoin Forum

So, I was thinking about the address generation scheme that is used for Bitcoin. Please note I did not do any math here yet to see if it is likely to happen, it's just a concept.


To my understanding no network communication takes place when generating Bitcoin addresses. It's basically done locally. From my understanding Bitcoin address generation is also predictable in the sense that generating the same address twice, while unlikely, will result in the same private and public keypair.

Now from what I understood, the chance of a collision (that you would get an address that already belongs to someone else) is possible, but so unlikely that it's discountable. All fine up to this point.

Now what if someone made a botnet generate addresses all the time, 24/7, and would import those addresses into a wallet.dat to try and see if someone else already generated the address, and has funds 'assigned' to it - essentially trying to find collisions? Wouldn't this be an extremely efficient way to generate addresses until an address was found that held funds, to then steal the funds on that address by transfering them elsewhere?

Is this a possible attack vector and if yes, how likely is it to succeed?

Damn fine theory, I don't know specifics enough to say if such schemes would work, but if the way things work the way you say they do, then in theory it seems like that would be possible.

It is possible.

At the same time - right now, it is much more profitable to just use all that power needed for such an attack for mining.

I was thinking bout this last night while playing around with vanitygen.
So in theory, I could ask vanitygen to generate an address that I already know and use this to find the key pairs?

You could not do that with all of the computing power on earth.  Well not in the next 100 years at least.

The botnet would need many years for reaching a 50% probability of key collision.

The point is I am not talking about targeting one specific address and finding collisions, but about targeting "every address", just generating until you find addresses that hold BTC to some extent, and taking whatever it is you find on the way.

Many millions of years.

It's not impossible for a collision to be found, but there's not enough profit in it. Even if someone can find one address every hundred million years, all they get to spend is the balance of that one address. This equates to an averaged cost of fraud of way less than a millionth of a cent per transaction.

It's not worth worrying about, when any simple trojan or social engineering attack is sure to net a few wallets.

The set of all used addresses is so small compared to the 2^160 possible addresses, so that it really doesnt matter if you search for one or for all used.

I think it is semi-possible.

while going for one address is unlikely to the extreme, just going after multiple random addresses is much more likely..

I was testing keygen and memory once, and I had bitcoin generate 1 million keypairs.
If a botnet was to do this scheme, I would think that there would be a good probablility of getting a small few. however the likelyhood of getting a single address with a large amount of bitcoins, is as impossible as attacking one address.

I also wonder how many addresses most people have..

Here is a short computation: assuming that a botnet can compute 1000000^2 addresses per second, then it would compute lesser than 2^75 keys in 1000 years. So ~0% of all addresses can be computed by a botnet in 1000 years.

I've been told that the odds are there will be no collision before the heat death of the universe even if everyone dedicated all their machines to that goal

Even if you have enough CPU power it takes you only a minute to generate a block at the current difficulty, it will probably take you billions of years to find a collision with another already used address. See my post (http://forum.bitcoin.org/index.php?topic=1387.msg299291#msg299291) from the vanity address thread.

Low chances to get a collision. You could do the same trick with any ECDSA signature, if you could do it with bitcoin.


Assuming that there are 10 million Bitcoin addresses out there in the block chain with value. The ECDSA keys are 256 bit.

This means you have to try out 2^256/10^7 = 1.2 * 10^70 addresses to get a match.

Many trillions of year. It is not possible.

Not exactly that easy. As Bitcoin is meant to last a while and computers get faster exponentially, you have to look what's up in 50 years. Bitcoin will adapt newer crypto parameters as times passes, but old bitcoins have to be transferred to new addresses then.

Highly improbable. Not impossible.

Let's assume you can gen and encode 2500 pubkeys a second with known privkeys. Right now that's this many days to exhaust the entire key space:

or
years

Now let's assume you can make that 50 times faster ... then it'd take this many days:
or
years

I believe you have a better chance of quantum tunneling a tennis ball through a wall by throwing it. At that point, I call it impossible. And it is for all intents and purposes.

Not really. Let's try some really ridiculous figures. Suppose that everyone in the world had, on average, 1 million bitcoin addresses with money in. Further suppose that you control a billion computers, each of which can try a billion possible addresses a second. If my calculations are correct, you'd still only find an address every 6.6 million years on average.

Edit: Or another way of looking at it: if you had a billion computers testing a billion addresses per second, on average you'd expect to earn one satoshi every 22 million years.

And given the non-inflationary aspect of Bitcoin, that satoshi would probably get you a cup of coffee.

http://www.youtube.com/watch?v=KX5jNnDMfxA

From what I understand, the keys are 256 bits (10^77) and there are what? 1 billion keys?

http://en.wikipedia.org/wiki/Birthday_paradox
http://en.wikipedia.org/wiki/Universally_Unique_Identifier#Random_UUID_probability_of_duplicates

1-e^(-(n^2)/2x)

EDIT:

1-e^(-(1000000000^2)/(2^256)) =
1-e^(-(10^18)/(10^77)) =
1-e^(-1/(10^59)) =
10^(-60)

Current Block Probability: ~ 10^(-16)

So, getting the block is 10^45 times more likely than a single collision. An attacker would have to hope for colliding with wallets containing trillions of times more coins than will ever have been created. But if an attacker can change the value of 'n' to 10^39 (duodecillion attempts) then he'll likely be quite profitable... but then again he'll only be colliding with his own keys.

I don't think there are a billion keys holding money now. Maybe in the future. If that were the case, the average key would only have .006 bitcoins in it. Not very much of a find if you do collide.

http://www.wolframalpha.com/input/?i=1-e^%28-%281000000000^2%29%2F%282^256%29%29+ (http://www.wolframalpha.com/input/?i=1-e^%28-%281000000000^2%29%2F%282^256%29%29+)
(I didn't check the formula, i've just copy/pasted what was already here)

If you collide an address, you don't have to do it with the same ECDSA key that the owner used.  This is basically a birthday attack on a 160 bit hash.  160 bits is probably enough.  I recall that early digital money schemes had users picking random 64 bit integers and assumed no collisions.  Loom is 64 bits too, as I recall.

The birthday problem isn't relevant though.  Say you generated 2^80 addresses and managed to collide two, well, odds are better than 2^50 to 1 that the collision you just found is with another address that you created ... that has no money on it.  So it's not a birthday problem; you need to collide with one of the vanishingly small number of addresses (out of the entire keyspace) that actually has an appreciable amount of money stored in it.

Or keep monitoring the ones you created so far waiting for someone else to collide with one of them and receive some money there

Do you realize how much hard drive space you would need to hold all the keys you generate in such an attack? Lets just say, that much doesn't exist in the entire world right now.

And then how long it would take going through them all checking for money. The average user could live and die using an address on your attack list and never get compromised because you don't get around to it in time.

Why do people have such a hard time understanding _BIG_NUMBERS_?

This has been discussed so many times already...




And...

And remember, if there were 2x10¹⁸ addresses, each address, on average, would have 0.0000000000105 BTC, less than a satoshi, in it.

So there is no point in avoiding repeating the same address over and over again, hell, you could dedicate all your processing power to just generating one address in the beginning and keep monitoring it for the rest of your life for the same effect

It is not a birthday attack. So it will take 2^159/2^26 = 2^133 tries on average to get that done, if there are 16 million addresses out there in use.

With a birthday attack, you could generate two keys with identical addresses rather than forging somebody else's address with SQRT(2^160) = 2^80 tries, but what attack could you do with that?

That's interesting. I wonder why we don't just use the full 256 bit public key as the address (not hashed) -- and then use the 'first bits' rule in the every day.

Satoshi made it this way, and it was ready when adopted, I think. Maybe he didn't think of that. Maybe he thought that ECDSA will require longer key length before SHA160 is broken.

No props lost on Satoshi for overlooking the "first bits" concept.

I doubt a hash protects the public key (immediately today). As a mechanism for expanding the key, it's an elegant solution. But still as I understand, the public key must be available to the block chain to verify each transaction. It seems to me then, the hash serves no purpose beyond convenience. I believe we could allow arbitrary length keys, referenced by their earliest unambiguous prefix.

A secure cryptographic hash can be truncated and still retain most of its strength, but this is not necessarily true for unhashed public keys. Possibly you'll lose more bits of strength than you would expect. It's safer to use a hash, which is designed for this.

OP_CAT is also disabled in script, while OP_HASH160 and OP_HASH256 are not.

What could you lose, it is just the public key. If two are identical, the first in block chain counts. There is absolutely no collisions then.

...and I am not suggesting truncating the key. I suggest the public key IS the address. We just refer to them (address) not by 30 char hash, but unambiguously by their "first bits" (shortest unambiguous prefix compared against all previous keys in the block chain). There should be no restriction on key length. Recommend 256 today or 384 tomorrow.

Firstbits seems broken right now:

To run Firstbits, you need a complete copy of the block chain. Most nodes will not have a full copy in the future, so you'd have to rely on a central service.

The miners as always would require the entire block chain to discover the public key corresponding to the 'first bits' but the sender does not. The sender only signs a transaction to an address, he does not verify that the receiving address is valid nor that anyone has the corresponding private key.


Firstbits.com happens to also be a web service by the same name. But the concept is decentralized. It is a deterministic FACT derived from the chronological appearance of addresses in the block chain.

It's the same as Bitcoin in that sense. You don't have to have the chain to use Bitcoin or FirstBits, but you can, and that's what will keep the data providers honest.