Quote from: falcoiii on March 31, 2013, 06:10:03 PM

I have done a bit of homework and have a CS/math degree. My field is not crypto, but I know about fields, groups, graph theory and SHA-256. Any answers, review or corrections of my questions would be appreciated.

Has it been proven that there will be no hash-collisions where 2 private addresses share the same public address?

See below.

Quote from: falcoiii on March 31, 2013, 06:10:03 PM

What is the process to create a private and public address ?

The address creation process looks like a random private first, then generate public address from the private...

It looks like there are Process to create a public address from a private address:

3 SHA-256 hashes and 1 RIPEMD-160 hash, plus some other simple manipulation.

https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

I would describe it more as one SHA-256 hash then one RIPEMD-160 hash. It's the 160-bit RIPEM hash that is presumed to be unique. The other two SHA-256 hashes are for computing a 32-bit checksum for the 160-bit hash. This is so typographical errors in an address won't cause a transfer to go to the bit-bucket. (bitcoin-bucket?) [There's about a 1 in 4 billion chance a random syntactically correct sequence of bytes will be accepted as a valid address.

private key --> ECDSA --> public key --> [SHA-256] --> [RIPEM-160] --> (pre-checksum) address

On address collisions: There is no proof that collisions cannot occur.

If our hashes are perfect, there is no way to steer a particular public key to a particular 160-bit hash. The birthday paradox says we will have to encode about 2^80 public keys before we have a 50% chance of an address collision.

Weaknesses have been found in many hash algorithms. But, since the input to RIPEM is not under our direct control (input to RIPEM is an output from SHA-256), I think the chances of manipulating the inputs to RIPEM to deliberately produce a collision are low.

Can we get collisions in the SHA-256 output? The birthday paradox says we will have to encode about 2^128 public keys before we have a 50% chance of a collision in the SHA-256 output.

We do have direct control over the inputs to SHA-256. While there are cases of two distinct inputs producing identical MD5 (128-bit) outputs, I am not aware of that feat having been performed for SHA-256.

Even if two SHA-256 hashes are found to be identical, the input to SHA-256 was a public key. At this point, the answer to your question is "yes". Two private addresses share the same public address. There remains the problem of converting your hand-crafted public key into a private key that you can spend. We know it exists, but you can't figure it out any better than you can figure out anybody else's private key from their public key.

IMHO, there are more potential attack vectors aimed at public keys than most other security aspects of Bitcoin. A fatal flaw in RIPEM could lead to an attack against addresses. A fatal flaw in SHA-256 could lead to an attack against addresses (and other components of Bitcoin). And a fatal flaw in ECDSA would be fatal to Bitcoin as we know it. I'm not too worried. But ask me again in 20 years.

Blowfeld

Posts

Merits