Potential attack vector in generating Bitcoin addresses?

[joepie91]

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?

[BitcoinPorn]

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.

[gentakin]

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.

[MiningBuddy]

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?

[Littleshop]

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.

[rabit]

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

[joepie91]

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.

[ribuck]

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

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.

[rabit]

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.

[legion050]

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.

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..

[rabit]

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.

[TiagoTiago]

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

[EricJ2190]

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 from the vanity address thread.

[bcearl]

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.

[DamienBlack]

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

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.

Many trillions of year. It is not possible.

[bcearl]

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

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.

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.

[jrmithdobbs]

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

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.

Many trillions of year. It is not possible.

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:

Code:

536074487209797201035050856521703277098472151229817426108599925962560.8

or

Code:

1468697225232321098726166730196447334516362058163883359201643632774.1

years

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

Code:

10721489744195944020701017130434065541969443024596348522171998519251.2

or

Code:

146869722523232109872616673019644733451636205816388335920164363277.4

years

[DamienBlack]

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

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.

Many trillions of year. It is not possible.

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:

Code:

536074487209797201035050856521703277098472151229817426108599925962560.8

or

Code:

1468697225232321098726166730196447334516362058163883359201643632774.1

years

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

Code:

10721489744195944020701017130434065541969443024596348522171998519251.2

or

Code:

146869722523232109872616673019644733451636205816388335920164363277.4

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.

[makomk]

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?

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.

[garyrowe]

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?

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.