BitcoinTalk
Stealing Coins

View all posts

External link

It's best if you tell it to me privately so it can be fixed first.

I just e-mailed you my e-mail address.  (or you could PM me here)
Red, thanks for telling me privately first!  Please go ahead and post it (and relieve the suspense for everyone!)

His point is that transactions paid to a Bitcoin Address are only as secure as the hash function.  To make Bitcoin Addresses short, they are a hash of the public key, not the public key itself.  An attacker would only have to break the hash function, not ECDSA.
If I figure out that Public Key 123456 generates Hash ABCD
and
Public Key 654321 also generates Hash ABCD
I'm still left without the Private Key.

But from what you are saying, all I need is Public Key 654321 and I can spend coin pretending to be Public Key 123456.
You would still have to sign it with public key 654321.  You need to find a collision using a public key for which you know the private key.

When you claim a Bitcoin Address transaction, you give your public key that matches the hash, then you must sign it with that key.

Red's point is that it's easy to quickly generate insecure public keys which you could break and find the private key after you find a collision.

He points out that if the public key was required to be a secure one, one which must have required significant work to find the prime numbers, that would increase the strength above that of the hash function alone.  Someone trying to brute force would have to take time generating a key for each attempt.
Quote
Here is a paper that claims to find SHA-1 collisions in 2^52 crypto operations. And optimally secure hash would take 2^80 operations. 2^52 time is still large, but it is getting into cluster and botnet range.
2^80 is if you can use a birthday attack.  You can't use a birthday attack for this, so the difficulty is the full 2^160 bits.  Although, if you were trying to crack any one of 1 million (2^20) transactions, you could do a partial birthday attack 2^160/2^20 = 2^140.

Bitcoin Addresses are the only place where 160-bit hash is used.  Everything else is SHA-256.  They're calculated as:

bitcoinaddress = RIPEMD-160(SHA-256(publickey))

Correct me if I'm wrong (please, and I'll gladly eat crow) but I think it would be hard to use an analytical attack on RIPEMD-160 in this case.  An analytical attack prescribes a certain range or pattern of inputs to try that will greatly increase your chance of finding a collision.  Here, you don't have that kind of control over RIPEMD-160's input, because the input is the output of SHA-256.  If an analytical attack helps you find an input to RIPEMD-160 that produces a collision, what are you going to do with it?  You still have to get SHA-256 to output that value, so you would still have to break SHA-256 too.

For brute force, RIPEMD-160(SHA-256(x)) is no stronger than RIPEMD-160 alone.  But for analytical attack, it seems like you must analytical attack both RIPEMD-160 and SHA-256.  If I'm wrong, then the strength is the same as RIPEMD-160 and the SHA-256 only serves as one round of key strengthening.
Sorry, actually it's ECDSA (Elliptic Curve Digital Signature Algorithm) not RSA.  I shouldn't have said "prime numbers".  ECDSA doesn't take much time to generate a keypair.