Bitcoin Address Collisions | Bitcointalksearch.org

FreeMoney

legendary

Activity: 1246

Merit: 1016

Strength in numbers

Quote from: Luke490 on June 09, 2011, 01:15:21 AM

Quote from: satoshi on February 23, 2010, 11:26:09 AM

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block. You could have got a lot more money by generating blocks.

What if your network of computers already generated and tested all the possible blocks?
Sure the address haystack of possibilities is much bigger and harder to test... but if the other haystack(block generating) has bean fully counted what else is there to do?

This is sillier than asking what happens after all the atoms have been examined. Nothing, nothing happens. Even if you could look at the entire space eventually (you cannot, one trillion of you cannot) you can't remember it either.

Luke490

newbie

Activity: 7

Merit: 0

Quote from: satoshi on February 23, 2010, 11:26:09 AM

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block. You could have got a lot more money by generating blocks.

What if your network of computers already generated and tested all the possible blocks?
Sure the address haystack of possibilities is much bigger and harder to test... but if the other haystack(block generating) has bean fully counted what else is there to do?

molecular

donator

Activity: 2772

Merit: 1019

Quote from: error on May 24, 2011, 01:23:46 AM

I wonder if I could just set my GPU to generating all possible addresses... no wait, that won't work.

It'll work fine. You can even proove it will finish. It'll just take a loooong time.

error

hero member

Activity: 588

Merit: 500

I wonder if I could just set my GPU to generating all possible addresses... no wait, that won't work.

da2ce7

legendary

Activity: 1222

Merit: 1016

Live and Let Live

Instead of stopping the address collisions, we should focus on *every other doomsday scenario* because they are all way more likely.

Gavin Andresen

legendary

Activity: 1652

Merit: 2301

Chief Scientist

RE: moving to another hashing algorithm for bitcoin addresses:

Did you read what Satoshi wrote?

If you want to make money, you are far, far, far, far, far, far better off using your hardware to generate blocks than trying to find a bitcoin address collision and steal bitcoins. Potential address collisions are not a weakness, and switching to another algorithm would be just busy-work for us developers who should be spending time on REAL weaknesses (like figuring out how to make bitcoin more secure against trojans and viruses).

theymos

administrator

Activity: 5222

Merit: 13032

Quote from: matt.collier on May 22, 2011, 03:02:58 PM

In 2006, the NIST made this recommendation:

Quote

Federal agencies should stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010.

http://csrc.nist.gov/groups/ST/hash/policy.html
http://en.wikipedia.org/wiki/SHA-2

If an electronic currency isn't an "application that requires collision resistance", I don't know what is.

That recommendation was made because SHA-1 is cryptographically weak. RIPEMD-160 is generally considered to be about equal in strength to truncated SHA-2.

matt.collier

member

Activity: 105

Merit: 10

In 2006, the NIST made this recommendation:

Quote

Federal agencies should stop using SHA-1 for digital signatures, digital time stamping and other applications that require collision resistance as soon as practical, and must use the SHA-2 family of hash functions for these applications after 2010.

http://csrc.nist.gov/groups/ST/hash/policy.html
http://en.wikipedia.org/wiki/SHA-2

If an electronic currency isn't an "application that requires collision resistance", I don't know what is.

RustyShackleford

newbie

Activity: 43

Merit: 0

Quote from: matt.collier on May 22, 2011, 12:24:53 PM

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions? Will we be able to move to a 224/256 bit hash if and when the need arises, even if it's 100 years from now?

I'm not a programmer, I don't work on bitcoin code, but I do understand how both of those things work. I'm going to say "yes". It might take everyone moving to Bitcoind v2.1.744 in the year 2121; but it really doesn't sound THAT difficult.

error

hero member

Activity: 588

Merit: 500

It's far more likely that every single miner on the network will all find a block at exactly the same time.

kjj

legendary

Activity: 1302

Merit: 1026

Quote from: matt.collier on May 22, 2011, 12:24:53 PM

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions? Will we be able to move to a 224/256 bit hash if and when the need arises, even if it's 100 years from now?

You could use 4096 bit hashes, and still get a freak accident in 5 minutes.

matt.collier

member

Activity: 105

Merit: 10

Or it could happen by some freak accident 5 minutes from now.

Your response was aimed at strengthening the computationally expensive argument.

Why are we using a 160 bit hash instead of something that is more resistant to collisions? Will we be able to move to a 224/256 bit hash if and when the need arises, even if it's 100 years from now?

molecular

donator

Activity: 2772

Merit: 1019

Quote from: matt.collier on May 22, 2011, 10:28:33 AM

Are we using a 160 bit hash (which provides for the possibility of a collision) vs a 224/256 bit hash (no possibility of a collision) so that bitcoin addresses can be shorter in length? If so, is it possible for us to transition to using a 256 bit hash at some later date?

I don't buy the argument that it's TOO computationally expensive to intentionally create a collision. We have already seen the use of GPUs radically alter the bitcoin mining paradigm. In the future, we may well see devices designed specifically for the task of performing hashing functions. Perhaps those devices already exist.

Why build the opportunity for fraud into bitcoin? I don't think we need to be concerned about the number of characters of a bitcoin address when we're copying and pasting them or using QR codes anway.

Don't worry, "If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block.". This means, if you have a computer that is 1 million times as powerfull as all current miners combined, it will still take an average of 1,618,542,460,620,902,128,345,579,373 years to generate a collision.

Even if Moores law holds true in the most generous way, we still have over 100 years left before this becomes feasable.

And also: yes, devices designed specifically for performing bitcoin mining exist (Artforz had himself some ASICs (custom chips) made)

matt.collier

member

Activity: 105

Merit: 10

Are we using a 160 bit hash (which provides for the possibility of a collision) vs a 224/256 bit hash (no possibility of a collision) so that bitcoin addresses can be shorter in length? If so, is it possible for us to transition to using a 256 bit hash at some later date?

I don't buy the argument that it's TOO computationally expensive to intentionally create a collision. We have already seen the use of GPUs radically alter the bitcoin mining paradigm. In the future, we may well see devices designed specifically for the task of performing hashing functions. Perhaps those devices already exist.

Why build the opportunity for fraud into bitcoin? I don't think we need to be concerned about the number of characters of a bitcoin address when we're copying and pasting them or using QR codes anway.

satoshi

founder

Activity: 364

Merit: 7248

Quote from: NewLibertyStandard on February 23, 2010, 02:04:47 PM

Are generated bitcoins encrypted with whichever address is currently displayed in the main Bitcoin window?

No, each generated transaction uses a new, single-use address.

Nothing uses the address in the main window, it's just there for convenience for you to copy. 0.2.5 has a "New..." button next to it to make it easy to change each time you use it.

NewLibertyStandard

sr. member

Activity: 252

Merit: 268

Thanks for the explanation. I think it all makes sense.

Are generated bitcoins encrypted with whichever address is currently displayed in the main Bitcoin window? I may have mentioned this in an email message quite a while ago, but it would be cool for some very future version to allow people to see which of their bitcoins are encrypted with which of their addresses.

satoshi

founder

Activity: 364

Merit: 7248

There's a separate public/private keypair for every bitcoin address. You don't have a single private key that unlocks everything. Bitcoin addresses are a 160-bit hash of the public key, everything else in the system is 256-bit.

If there was a collision, the collider could spend any money sent to that address. Just money sent to that address, not the whole wallet.

If you were to intentionally try to make a collision, it would currently take 2^126 times longer to generate a colliding bitcoin address than to generate a block. You could have got a lot more money by generating blocks.

The random seed is very thorough. On Windows, it uses all the performance monitor data that measures every bit of disk performance, network card metrics, cpu time, paging etc. since your computer started. Linux has a built-in entropy collector. Adding to that, every time you move your mouse inside the Bitcoin window you're generating entropy, and entropy is captured from the timing of disk ops.

ec

newbie

Activity: 7

Merit: 69

Quote from: NewLibertyStandard on February 23, 2010, 04:22:47 AM

Are you referring to the private key which is generated the first time a person runs Bitcoin? If someone were to successfully duplicate someone else's key then after they downloaded all the blocks, they would have the same balance as the person with the original key. That's what you're saying, right?

Yes, that is correct. They would share the wallet, and it becomes a race on spending the money first.

Quote from: NewLibertyStandard on February 23, 2010, 04:22:47 AM

I was referring to the custom Bitcoin addresses which you can label with the name of the person who is going to send you bitcoins so that you know from whom the payment came. I think these addresses are generated from the private key mentioned previously. I'm wondering about collisions because although they are very unique, they are easily generated over and over again by all by all bitcoin clients.

If I read the source code correctly, keys are always made in pairs. That means, every address has an associated private key. When you click "New Address", you call GenerateKey in main.cpp, which generates a new key pair. So the duplicate address is ultimately a duplicate public key. Which is very unlikely.

While keys still are "easily generated", you should have to generate a whole lot of keys before a collision. While I am not certain, it seems that the keys generated have a space of 256 bits, which is a lot more than the 122 bits put in perspective in the wikipedia article on uuids. Remember, 123 bits have half the probability of collision as 122 bit, 124 half of that again etc.

NewLibertyStandard

sr. member

Activity: 252

Merit: 268

Are you referring to the private key which is generated the first time a person runs Bitcoin? If someone were to successfully duplicate someone else's key then after they downloaded all the blocks, they would have the same balance as the person with the original key. That's what you're saying, right?

I was referring to the custom Bitcoin addresses which you can label with the name of the person who is going to send you bitcoins so that you know from whom the payment came. I think these addresses are generated from the private key mentioned previously. I'm wondering about collisions because although they are very unique, they are easily generated over and over again by all by all bitcoin clients.

ec

newbie

Activity: 7

Merit: 69

For two addresses to be equal, two identical private/public elliptical curve (ec

) keys have to be generated. Without looking at the source code, let's assume the probability for this is 2^(-128) for a keyspace of 128 bits. See here for a perspective on how probable it is with a 122 bit collision.

However, if something similar to the Debian ssl-scandal happens, similar keys could indeed be generated. The effect of an individual generating an existing key, is (if I understand it correctly) in effect to make a copy of wallet.dat. Not good at all, but not devastating for all the members of the p2p network.

Topic: Bitcoin Address Collisions (Read 23940 times)