From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 66F70C64 for ; Thu, 7 Jan 2016 19:13:26 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail.bluematt.me (mail.bluematt.me [192.241.179.72]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id B8A67174 for ; Thu, 7 Jan 2016 19:13:25 +0000 (UTC) Received: from [172.17.0.2] (gw.vpn.bluematt.me [162.243.132.6]) by mail.bluematt.me (Postfix) with ESMTPSA id 188735BCAD; Thu, 7 Jan 2016 19:13:24 +0000 (UTC) To: Gavin Andresen , Bitcoin Dev References: From: Matt Corallo Message-ID: <568EB8D2.20104@mattcorallo.com> Date: Thu, 7 Jan 2016 19:13:22 +0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.3.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not? X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Development Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Jan 2016 19:13:26 -0000 We absolutely should be worried about 80-bit collision resistance. Collisions only take 2**80 work if the hash is theoretically perfect, which is never the case, not to mention that collision resistance is almost always the first thing to go for hash functions, and often starts to get easier slowly long, long before anyone is truly worried about the security of the hash function. I would never assume RIPEMD160's collision resistance is 2**80, and would definitely never wager a significant amount of money that this remains true for, say, five years. Matt On 01/07/16 19:02, Gavin Andresen via bitcoin-dev wrote: > I'm hoisting this from some private feedback I sent on the segregated > witness BIP: > > I said: > > "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12 > bytes-- a successful preimage attack against that ain't gonna happen > before we're all dead. I'm probably being dense, but I just don't see > how a collision attack is relevant here." > > Pieter responded: > > "The problem case is where someone in a contract setup shows you a > script, which you accept as being a payment to yourself. An attacker > could use a collision attack to construct scripts with identical hashes, > only one of which does have the property you want, and steal coins. > > So you really want collision security, and I don't think 80 bits is > something we should encourage for that. Normal pubkey hashes don't have > that problem, as they can't be constructed to pay to you." > > ... but I'm unconvinced: > > "But it is trivial for contract wallets to protect against collision > attacks-- if you give me a script that is "gavin_pubkey CHECKSIG > arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, > just ignore that arbitrary data" a wallet can just refuse. Even more > likely, a contract wallet won't even recognize that as a pay-to-gavin > transaction. > > I suppose it could be looking for some form of "gavin_pubkey > somebody_else_pubkey CHECKMULTISIG ... with the attacker using > somebody_else_pubkey to force the collision, but, again, trivial > contract protocol tweaks ("send along a proof you have the private key > corresponding to the public key" or "everybody pre-commits pubkeys > they'll use at protocol start") would protect against that. > > Adding an extra 12 bytes to every segwit to prevent an attack that takes > 2^80 computation and 2^80 storage, is unlikely to be a problem in > practice, and is trivial to protect against is the wrong tradeoff to make." > > 20 bytes instead of 32 bytes is a savings of almost 40%, which is > significant. > > The general question I'd like to raise on this list is: > > Should we be worried, today, about collision attacks against RIPEMD160 > (our 160-bit hash)? > > Mounting a successful brute-force collision attack would require at > least O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out > that Bitcoin POW has computed more SHA256 hashes than that). But it also > requires O(2^80) storage, which is utterly infeasible (there is > something on the order of 2^35 bytes of storage in the entire world). > Even assuming doubling every single year (faster than Moore's Law), > we're four decades away from an attacker with THE ENTIRE WORLD's storage > capacity being able to mount a collision attack. > > > References: > > https://en.wikipedia.org/wiki/Collision_attack > > https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/ > > > -- > -- > Gavin Andresen > > > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >