{"type":"rich","version":"1.0","author_name":"npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","author_url":"https://nostr.ae/npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcu","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2016-01-07\n📝 Original message:We absolutely should be worried about 80-bit collision resistance.\nCollisions only take 2**80 work if the hash is theoretically perfect,\nwhich is never the case, not to mention that collision resistance is\nalmost always the first thing to go for hash functions, and often starts\nto get easier slowly long, long before anyone is truly worried about the\nsecurity of the hash function.\n\nI would never assume RIPEMD160's collision resistance is 2**80, and\nwould definitely never wager a significant amount of money that this\nremains true for, say, five years.\n\nMatt\n\nOn 01/07/16 19:02, Gavin Andresen via bitcoin-dev wrote:\n\u003e I'm hoisting this from some private feedback I sent on the segregated\n\u003e witness BIP:\n\u003e \n\u003e I said:\n\u003e \n\u003e \"I'd also use RIPEMD160(SHA256()) as the hash function and save the 12\n\u003e bytes-- a successful preimage attack against that ain't gonna happen\n\u003e before we're all dead. I'm probably being dense, but I just don't see\n\u003e how a collision attack is relevant here.\"\n\u003e \n\u003e Pieter responded:\n\u003e \n\u003e \"The problem case is where someone in a contract setup shows you a\n\u003e script, which you accept as being a payment to yourself. An attacker\n\u003e could use a collision attack to construct scripts with identical hashes,\n\u003e only one of which does have the property you want, and steal coins.\n\u003e \n\u003e So you really want collision security, and I don't think 80 bits is\n\u003e something we should encourage for that. Normal pubkey hashes don't have\n\u003e that problem, as they can't be constructed to pay to you.\"\n\u003e \n\u003e ... but I'm unconvinced:\n\u003e \n\u003e \"But it is trivial for contract wallets to protect against collision\n\u003e attacks-- if you give me a script that is \"gavin_pubkey CHECKSIG\n\u003e arbitrary_data OP_DROP\" with \"I promise I'm not trying to rip you off,\n\u003e just ignore that arbitrary data\" a wallet can just refuse. Even more\n\u003e likely, a contract wallet won't even recognize that as a pay-to-gavin\n\u003e transaction.\n\u003e \n\u003e I suppose it could be looking for some form of \"gavin_pubkey\n\u003e somebody_else_pubkey CHECKMULTISIG ... with the attacker using\n\u003e somebody_else_pubkey to force the collision, but, again, trivial\n\u003e contract protocol tweaks (\"send along a proof you have the private key\n\u003e corresponding to the public key\" or \"everybody pre-commits pubkeys\n\u003e they'll use at protocol start\") would protect against that.\n\u003e \n\u003e Adding an extra 12 bytes to every segwit to prevent an attack that takes\n\u003e 2^80 computation and 2^80 storage, is unlikely to be a problem in\n\u003e practice, and is trivial to protect against is the wrong tradeoff to make.\"\n\u003e \n\u003e 20 bytes instead of 32 bytes is a savings of almost 40%, which is\n\u003e significant.\n\u003e \n\u003e The general question I'd like to raise on this list is:\n\u003e \n\u003e Should we be worried, today, about collision attacks against RIPEMD160\n\u003e (our 160-bit hash)?\n\u003e \n\u003e Mounting a successful brute-force collision attack would require at\n\u003e least O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out\n\u003e that Bitcoin POW has computed more SHA256 hashes than that). But it also\n\u003e requires O(2^80) storage, which is utterly infeasible (there is\n\u003e something on the order of 2^35 bytes of storage in the entire world). \n\u003e Even assuming doubling every single year (faster than Moore's Law),\n\u003e we're four decades away from an attacker with THE ENTIRE WORLD's storage\n\u003e capacity being able to mount a collision attack.\n\u003e \n\u003e \n\u003e References: \n\u003e \n\u003e https://en.wikipedia.org/wiki/Collision_attack\n\u003e \n\u003e https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/\n\u003e \n\u003e \n\u003e -- \n\u003e --\n\u003e Gavin Andresen\n\u003e \n\u003e \n\u003e \n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e"}