Topic: Bitcoin's Weakest Link (Read 988 times)

There was some talk on the dev list that RIPEMD-160 used in P2SH could be a weakness (segregated witness will use 32 bytes rather than just 20).  If two parties are creating the output together, then the last party to change the output script can create a hash collision with 'only' ~2⁸⁰ operations.

All the other security in Bitcoin is supposed to be at the 2¹²⁸ level.

For example, imagine Alice and Eve are creating a 2 of 2 multisig output.  Alice sends her public key to Eve.  Eve has to send back her public key to Alice, so they can form the 2 of 2 multisig.

Instead, Eve tries to find a hash collision where two different scripts hash to the same value.


and


Due to the birthday paradox, finding the collision only takes the square root of the search space, so 2¹⁶⁰ becomes ~2⁸⁰.

Eve sends the fake public key from the first output to Alice and Alice checks everything and doesn't see anything wrong.  Once Alice signs the transaction, Eve can use the other version of the output to claim the funds, since they both hash to the same P2SH value.

In practice, this isn't that big a deal, since 2⁸⁰ operations is massive and Eve has to do it which Alice is waiting for a reply.

Just to be clear, this attack doesn't have any effect on RIPEMD-160 as it is used currently.  If only one person is creating the key, as with most outputs Today, then it has the full 2¹⁶⁰ bits of security.

Old funds like the Satoshi's premine are locked by pubkeys, no ripemd160 involved.

The use of RIPEMD160(SHA256()) makes many, many vectors like the ones Length extension attack fairly difficult

I don't see how anyone would brute force such a large (160bit) search space. At some point you need to find some public key that hashes to some value. Making public keys is not the bottleneck, not even  the SHA256 and RIPEMD160 but the elliptic curve keygen. But the utxo database lookups are.

But at the end of the day, UTXO is not so large and the lookups are embarrassingly parallel so the attacker would end with 1 compute node per UTXO. The setup would (could) in fact look equivalent to mining setup, but instead of blocks you have random data blob and the difficulty is maximum possible (full preimage). The mine of block would mean that you cracked someone's Bitcoin private key. Except the hardware asic for RIPEMD160(SHA256(ecdsa is not available.

The question is: is it more profitable to mine user's wallets with nearly impossible difficulty or regular bitcoin rewards with easy difficulty.

A speed up of the hash function is terribly unlikely  because the sha(ecdsa keygen(x)) part is 256bit to 256bit  , collisions here should be terribly hard.

on the other end you have ripemd160. I don't know how anyone could have so deep understanding into the combined result of three different algorithms  that would yield a considerable speed up of the bruteforce.

double sha256 is used in quite a few places, the blockhash, the data that is signed, the address checksum and also for checksum of network messages.

While using different hash functions would require all of them to be solved to invert them, the danger of using any old hash function is that if any of them loses a lot of entropy, you could get a lot more collisions or just a clumping of outputs, which could cause bad behavior in other parts of the system that is expecting cryptographic strength hash

Hopefully, the resulting hashes are verified for collision resistance

James

on an unrelated issue, do you know what the likely range for the tx version field will be?

both version and locktime have very low entropy when viewed as an aggregate, but I dont want to encode it with too few bits if either of them will start being used actively. I think for locktime, encoding it as a relative to block or block timestamp for the cases it is nonzero could get both fields encoded into average of 8bits

I am using fixed space allocation though, so I need to make the worst case be as small as possible

James

It does use double SHA256 for the address checksum.  Perhaps they wanted to do something wildly different for the hash.

Some of the altcoins chain pretty much every known hash function for proof of work.  The idea being that if a bunch of them would be solved, the code would still be usable.

all usage of ripemd-160 in the bitcoin protocol is to the result of the sha256's 256 bits, there is OP_RIPEMD160 that does just the RIPEMD, but there is also OP_SHA1. Unless you are using custom scripts on a core that supports those script opcodes, you are safe from the dangers of weak hash funcs.

Not sure if there is a way for any function to reduce the entropy of the sha256 output in a meaningful way, short of using an anti-sha256 after the sha256, it is probably harmless to use ripemd-160, and it could even make things that much harder to inverse.

If to just rely on lower bits of sha256, then once that is fully solved, well, I guess a lot in crypto will be an open book at that point. and if sha256 is cracked, then probably ripemd160 is also cracked.

James

P.S. For consistency, taking lower 160 bits of double sha256 would have removed the need for a ripemd160 hashing, but probably the thinking was that it was incrementally safer to use two different hash functions

I just don't see any realistic attack vector that would use collisions in rimped160, which are (BTW) still due to be discovered.

If you want to scare me, or impress me, you need to show me a potential attack vector.

So is it your opinion that Bitcoin with broken RIPEMD-160 is as robust as Bitcoin with unbroken RIPEMD-160?

Given that I wrote a client, you'd think I would have remembered the extra SHA256 in there.

Back to the drawing board.

AFAIK, bitcoin protocol never uses RIPEMD-160 to hash data.

Whenever the protocol mentions RIPEMD160(data) it is actually RIPEMD160(SHA256(data))

Therefore, IMHO exploiting collisions is rather impossible.

I think that sometime in the next year, we should hard fork the reference client to use something other than RIPEMD-160 to hash addresses from keys, and strongly encourage people to move their BTC to new transactions employing the new message digest function.

RIPEMD-160 dates from 1996, and was estimated to have a lifetime of around 10 years.  So it's now 10 years past its original projected life.  It needs to remain unbreakable for as long in the future as people leave transactions in the blockchain, which could be another 10-20 years.

Competitive message digest functions from the same era include MD4, MD5, and SHA-1.  MD4 and MD5 have already had collisions demonstrated, and SHA-1 is deprecated, and the recommendation is to retire it sooner rather than later.

One suggestion would be to use SHA256d both for proof of work and hashing addresses.  It is believed to be secure well into the future, and using a single function to do all hashing in Bitcoin wouldn't leave multiple instances of things that could fail.  You could just take the lower order 160 bits of the SHA256d hash as the address hash.

If we leave things as they are, it is likely that sometime in the next 20 years, someone will demonstrate a computationally feasible pre-image attack on RIPEMD-160, and will be able to generate working Elliptic Curve keys from any address.  Using SHA256 and using it twice was a wise choice by Satoshi, and we should move to using that as the address hash.