Address collision

[AliceWonder]

I'm asking this in newbie section because I can't be the first.

An ECDSA key is basically a 64 digit hex number (OK, 32 digit base256 but that's semantics)
A ripemd160 is basically a 40 digit hex number

A bitcoin version 1.0 address is basically a ripemd160 with a checksum, base58 encoded.

Um, let me do the math... carry the 3, add the four, yup - there are far more possible private keys than addresses.

I realize the odds are extremely low, but clearly collissions are possible where two different private keys generate the same ripemd160.

Wouldn't it be prudent to go to a version 2.0 address that uses something other than ripemd160 on the public key?? Like maybe a sha512sum ??

Code:

echo -n "test" |sha512sum 
ee26b0dd4af7e749aa1a8ee3c10ae9923f618980772e473f8819a5d4940e0db27ac185f8a0e1d5f84f88bc887fd67b143732c304cc5fa9ad8e6f57f50028a8ff

It would result in longer addresses but there wouldn't be guaranteed collissions at some point, even if that point is not likely to happen in our lifetime.

Or am I just missing something?

[rme]

2^256 private keys that generate 2^160 public keys

[AliceWonder]

2^256 private keys that generate 2^160 public keys

Yup. But the problem is addresses, not public keys - the actual public keys are x and y coords and I don't see a collision problem there.
The problem is we aren't actually using the public keys themselves but a hash of them, a hash that results in guaranteed collisions given enough actual public keys.

[AliceWonder]

I guess it really doesn't matter that much, 1.4x10^48 is still a really really really big number.

but even doing ripemd160($public) . md5($public) would give us the full range.

[CIYAM]

I guess it really doesn't matter that much, 1.4x10^48 is still a really really really big number.

Indeed it doesn't matter (and note that this question has been answered many, many times before).

[JoelKatz]

I guess it really doesn't matter that much, 1.4x10^48 is still a really really really big number.

but even doing ripemd160($public) . md5($public) would give us the full range.

Using the "full range" doesn't ensure there won't be collisions. The whole point of using 160-bit addresses was to keep them as short as possible while still meeting the security requirements. Increasing the expected time to the first collision from a hundred billion centuries to a trillion centuries isn't worth having all Bitcoin addresses be 80% longer.

[GoldBit78]

Is this correct that after such a Collision the Encryption will be useless ?

[DannyHamilton]

Is this correct that after such a Collision the Encryption will be useless ?

What encryption?

Bitcoin-Qt encrypts the wallet, but that has nothing to do with address collisions.

Bitcoin uses digital signatures and cryptographic hash functions.  Those will all continue to work fine.

[BurtW]

2^256 private keys that generate 2^160 public keys

I think you may have meant to say:

2^256 public/private key pairs get mapped onto 2^160 public Bitcoin addresses.

In other words every single Bitcoin address will map to 2^(256-160) = 2^96 different public/private key pairs.

Edit 1:

I forgot that every possible public/private key pair can map to TWO different public addresses (compressed and uncompressed) so the actual answer is

every single Bitcoin address will map to 2(2^(256-160)) = 2(2^96) = 2^97 different public/private key pairs.

Edit 2:

To be even more accurate the private key address space is not the full 2^256 since the private key is taken from a prime finite field, right?  So the actual number of possible public/private key pairs is given by the selected prime finite field.

[firstlast]

After a collision, the bitcoins held in that address will be useless (spent).

To put your mind at ease about collisions, brute forcing the private keys of some public address is somewhat like hashing a block and getting 0. The entire bitcoin mining operation up to this point hasn't been able to do this. In fact the smallest hash found led with 16 zeros out of the required 64, so we're still a long way off in terms of collective computing power from brute forcing addresses.

[cp1]

This will probably be a problem once 1208925819614629174706176 people start using bitcoin.

[firstlast]

Is that an exact number

[eve0]

Very unlikely is unlikely enough.

[JoelKatz]

Is this correct that after such a Collision the Encryption will be useless ?

No. What would make Bitcoin's implementation useless would be if someone could produce a private key whose public key hashes to a given address. There are many compromises less than that which would not threaten Bitcoin at all. For example, if an attacker could produce two private keys that both yield the same address, that would be a collision, but it wouldn't provide him any useful attack.

I suspect the reason Satoshi decided to use both SHA256 and RIPEMD-160 is that he feared that he could not be absolutely certain there might not be some weakness from the way ECDSA and RIPEMD-160 might interact that might permit a collision exploit, but the idea that there could be some exploitable interaction in ECDSA->SHA256->MD160 seemed rather absurd.

[BurtW]

For completeness of my previous post the actual number of possible key pairs is just a tad less than 2^256. it is:

p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

    = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1

( Just bumping my post count to try and stay ahead of Joel )