Potential attack vector in generating Bitcoin addresses?

[peach]

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

[netrin]

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.

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.

[DamienBlack]

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.

[TiagoTiago]

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)

[Enochian]

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.

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.

[CydeWeys]

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.

[TiagoTiago]

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

[DamienBlack]

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_?

[theymos]

This has been discussed so many times already...

There are currently 329,993 addresses in the Bitcoin network. Say that this number of addresses are created every day for the next 140 years. That's 16,862,642,300 addresses.

The chance that at least two of those addresses collided is about 9.7x10^-29, using the formula here. Calculation.

If every person on Earth makes ten addresses per second for 20 years (2x10¹⁸ total addresses), then the probability that two of these addresses collide is about 1.57x10^-12.

UUIDs have 2¹²⁸ possible identifiers. They are also designed to be collision-proof. Wikipedia says:

To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion, that means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.

Compare this to Bitcoin's 2¹⁶⁰ possible addresses. Bitcoin has:
1461501637330902918203684832716283019655932542976 addresses
UUIDs have:
340282366920938463463374607431768211456 identifiers

And...

Bitcoin already supports OP_HASH256 in script, so it would be trivial to increase the number of addresses if it ever became a problem.

[DamienBlack]

This has been discussed so many times already...

There are currently 329,993 addresses in the Bitcoin network. Say that this number of addresses are created every day for the next 140 years. That's 16,862,642,300 addresses.

The chance that at least two of those addresses collided is about 9.7x10^-29, using the formula here. Calculation.

If every person on Earth makes ten addresses per second for 20 years (2x10¹⁸ total addresses), then the probability that two of these addresses collide is about 1.57x10^-12.

UUIDs have 2¹²⁸ possible identifiers. They are also designed to be collision-proof. Wikipedia says:

To put these numbers into perspective, one's annual risk of being hit by a meteorite is estimated to be one chance in 17 billion, that means the probability is about 0.00000000006 (6 × 10−11), equivalent to the odds of creating a few tens of trillions of UUIDs in a year and having one duplicate. In other words, only after generating 1 billion UUIDs every second for the next 100 years, the probability of creating just one duplicate would be about 50%. The probability of one duplicate would be about 50% if every person on earth owns 600 million UUIDs.

Compare this to Bitcoin's 2¹⁶⁰ possible addresses. Bitcoin has:
1461501637330902918203684832716283019655932542976 addresses
UUIDs have:
340282366920938463463374607431768211456 identifiers

And...

Bitcoin already supports OP_HASH256 in script, so it would be trivial to increase the number of addresses if it ever became a problem.

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

[TiagoTiago]

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

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

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.

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?

[netrin]

If you collide an address, you don't have to do it with the same ECDSA key that the owner used.

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.

[bcearl]

If you collide an address, you don't have to do it with the same ECDSA key that the owner used.

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.

[netrin]

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.

[theymos]

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.

[bcearl]

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.

[netrin]

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.

[bcearl]

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:

7/6/2011

We were notified of an address that was in the block chain, but not in our database. This is a serious problem because it could cause us to give out incorrect firstbits addresses to Bitcoin addresses which are similar to the missing address.

We have taken the site offline until we fix and verify our database, this may take 2 days. We are very sorry for the inconvenience. The best thing about the firstbits rule is that anyone can implement a site or app that follows the same rule to make consistant firstbits conversions. Unfortunately, there is no other service to refer you to yet.

It is unlikely that any incorrect firstbits have been given before we took the site down, but please double check your addresses when we are back online.

[theymos]

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.