Potential attack vector in generating Bitcoin addresses?

FreeMoney

legendary

Activity: 1246

Merit: 1016

Strength in numbers

Quote from: theymos on July 10, 2011, 06:25:29 PM

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.

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.

netrin

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

Quote from: theymos on July 10, 2011, 06:25:29 PM

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.

Quote from: bcearl on July 09, 2011, 04:58:43 AM

Firstbits seems broken right now:

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.

theymos

administrator

Activity: 5222

Merit: 13032

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.

bcearl

full member

Activity: 168

Merit: 103

Quote from: netrin on July 09, 2011, 03:47:08 AM

Quote from: bcearl on July 09, 2011, 02:47:03 AM

Quote from: theymos on July 07, 2011, 09:31:56 PM

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:

Quote

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.

netrin

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

Quote from: bcearl on July 09, 2011, 02:47:03 AM

Quote from: theymos on July 07, 2011, 09:31:56 PM

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

full member

Activity: 168

Merit: 103

Quote from: theymos on July 07, 2011, 09:31:56 PM

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.

theymos

administrator

Activity: 5222

Merit: 13032

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.

netrin

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

Quote from: bcearl on July 07, 2011, 12:55:38 AM

Quote from: netrin on July 06, 2011, 12:16:24 PM

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.

bcearl

full member

Activity: 168

Merit: 103

Quote from: netrin on July 06, 2011, 12:16:24 PM

Quote from: Enochian on July 05, 2011, 07:15:35 PM

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

sr. member

Activity: 322

Merit: 251

FirstBits: 168Bc

Quote from: Enochian on July 05, 2011, 07:15:35 PM

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

full member

Activity: 168

Merit: 103

Quote from: Enochian on July 05, 2011, 07:15:35 PM

Quote from: bcearl on July 05, 2011, 02:06:31 PM

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?

TiagoTiago

hero member

Activity: 616

Merit: 500

Firstbits.com/1fg4i :)

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

DamienBlack

jr. member

Activity: 56

Merit: 1

Quote from: theymos on July 05, 2011, 08:03:38 PM

This has been discussed so many times already...

Quote from: theymos on March 23, 2011, 10:33:23 PM

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.

Quote from: theymos on November 14, 2010, 02:52:33 AM

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.

Quote from: theymos on February 19, 2011, 03:27:06 PM

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

Quote

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

Quote from: theymos on June 30, 2011, 08:27:31 PM

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.

theymos

administrator

Activity: 5222

Merit: 13032

This has been discussed so many times already...

Quote from: theymos on March 23, 2011, 10:33:23 PM

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.

Quote from: theymos on November 14, 2010, 02:52:33 AM

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.

Quote from: theymos on February 19, 2011, 03:27:06 PM

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

Quote

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

Quote from: theymos on June 30, 2011, 08:27:31 PM

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

jr. member

Activity: 56

Merit: 1

Quote from: TiagoTiago on July 05, 2011, 07:50:49 PM

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

TiagoTiago

hero member

Activity: 616

Merit: 500

Firstbits.com/1fg4i :)

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

CydeWeys

full member

Activity: 154

Merit: 100

Quote from: Enochian on July 05, 2011, 07:15:35 PM

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.

Enochian

full member

Activity: 327

Merit: 124

Quote from: bcearl on July 05, 2011, 02:06:31 PM

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.

TiagoTiago

hero member

Activity: 616

Merit: 500

Firstbits.com/1fg4i :)

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)

DamienBlack

jr. member

Activity: 56

Merit: 1

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.

Topic: Potential attack vector in generating Bitcoin addresses? (Read 8066 times)