Bitcoin Forum
April 25, 2017, 07:09:49 AM
 News: If the forum does not load normally for you, please send me a traceroute.
 Home Help Search Donate Login Register
 Pages: 1 [2] 3  All
 Author Topic: Potential attack vector in generating Bitcoin addresses?  (Read 7468 times)
peach
Jr. Member

Offline

Activity: 42

An intermediary stage in the breakdown of stars

 July 05, 2011, 09:55:47 PM

DO IT
1ENhnpoUohq58A2xu5LxKejAeet9PxzrCg
1493104189
Hero Member

Offline

Posts: 1493104189

Ignore
 1493104189

1493104189
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1493104189
Hero Member

Offline

Posts: 1493104189

Ignore
 1493104189

1493104189
 Report to moderator
1493104189
Hero Member

Offline

Posts: 1493104189

Ignore
 1493104189

1493104189
 Report to moderator
1493104189
Hero Member

Offline

Posts: 1493104189

Ignore
 1493104189

1493104189
 Report to moderator
netrin
Sr. Member

Offline

Activity: 322

FirstBits: 168Bc

 July 05, 2011, 11:16:07 PM

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

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
DamienBlack
Jr. Member

Offline

Activity: 56

 July 05, 2011, 11:39:35 PM

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.

I trade bitcoin options at https://bitoption.org/ ... Join me.
I play poker at https://betco.in/ ... Join me.
Support the bitcoin economy, what do you do?
Tips: 1NfXhiTFEdKQTdLy49s6DYAP1K7MeFWyao
TiagoTiago
Hero Member

Offline

Activity: 616

Firstbits.com/1fg4i                :Ƀ

 July 05, 2011, 11:53:35 PM

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)

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
Enochian
Full Member

Offline

Activity: 126

 July 06, 2011, 12:15:35 AM

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
Full Member

Offline

Activity: 154

 July 06, 2011, 12:43:03 AM

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
Hero Member

Offline

Activity: 616

Firstbits.com/1fg4i                :Ƀ

 July 06, 2011, 12:50:49 AM

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

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
DamienBlack
Jr. Member

Offline

Activity: 56

 July 06, 2011, 12:54:09 AM

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

I trade bitcoin options at https://bitoption.org/ ... Join me.
I play poker at https://betco.in/ ... Join me.
Support the bitcoin economy, what do you do?
Tips: 1NfXhiTFEdKQTdLy49s6DYAP1K7MeFWyao
theymos
Legendary

Offline

Activity: 2632

 July 06, 2011, 01:03:38 AM

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 (2x1018 total addresses), then the probability that two of these addresses collide is about 1.57x10-12.

UUIDs have 2128 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 2160 possible addresses. Bitcoin has:
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
Jr. Member

Offline

Activity: 56

 July 06, 2011, 01:07:10 AM

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 (2x1018 total addresses), then the probability that two of these addresses collide is about 1.57x10-12.

UUIDs have 2128 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 2160 possible addresses. Bitcoin has:
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 2x1018 addresses, each address, on average, would have 0.0000000000105 BTC, less than a satoshi, in it.

I trade bitcoin options at https://bitoption.org/ ... Join me.
I play poker at https://betco.in/ ... Join me.
Support the bitcoin economy, what do you do?
Tips: 1NfXhiTFEdKQTdLy49s6DYAP1K7MeFWyao
TiagoTiago
Hero Member

Offline

Activity: 616

Firstbits.com/1fg4i                :Ƀ

 July 06, 2011, 01:22:21 AM

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

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
bcearl
Full Member

Offline

Activity: 168

 July 06, 2011, 10:12:02 AM

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?

Misspelling protects against dictionary attacks NOT
netrin
Sr. Member

Offline

Activity: 322

FirstBits: 168Bc

 July 06, 2011, 05:16:24 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.

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
bcearl
Full Member

Offline

Activity: 168

 July 07, 2011, 05:55:38 AM

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.

Misspelling protects against dictionary attacks NOT
netrin
Sr. Member

Offline

Activity: 322

FirstBits: 168Bc

 July 08, 2011, 02:23:51 AM

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.

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
theymos
Legendary

Offline

Activity: 2632

 July 08, 2011, 02:31:56 AM

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
Full Member

Offline

Activity: 168

 July 09, 2011, 07:47:03 AM

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.

Misspelling protects against dictionary attacks NOT
netrin
Sr. Member

Offline

Activity: 322

FirstBits: 168Bc

 July 09, 2011, 08:47:08 AM

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.

Greenlandic tupilak. Hand carved, traditional cursed bone figures. Sorry, polar bear, walrus and human remains not available for export.
bcearl
Full Member

Offline

Activity: 168

 July 09, 2011, 09:58:43 AM

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.

Misspelling protects against dictionary attacks NOT
theymos
Legendary

Offline

Activity: 2632

 July 10, 2011, 11: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.