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 BB0A7D36 for ; Thu, 7 Jan 2016 20:40:05 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f41.google.com (mail-wm0-f41.google.com [74.125.82.41]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CDE7D141 for ; Thu, 7 Jan 2016 20:40:04 +0000 (UTC) Received: by mail-wm0-f41.google.com with SMTP id f206so112711518wmf.0 for ; Thu, 07 Jan 2016 12:40:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=LMkG4tifrqujJZJ56iatRICQGCYlJ4k7tmHLqlOMiHI=; b=T9A6EXeyMtP8/0DYo87aoJxUik1Ru4MqfZtqN2ewtSEOBPxccoWSXqbeW0/huWnRcL oSbPG+LbnEWXwPraZE0fpMPtKKoUrUXAp6gaXoYX8i53qc/j3Eu/vrxhuDAqM8986i+t YoTYfufwI6auxjtuomrGIGXENCS/szwofEj1WaT82LgzF883v1wgETurtfV26EVZGb8j b+Icpd0JeAbiaFZIH9Qkoa6F6Qc+JiUYpvrX+dSbed7Gm3No5tU1bHRtdxJjtlQqiMQa cwUeoYCeyEy15Zv78c7dV1P2dycPt5pzOnjh++Qed2smLqBTM8Rt30lHft5UbyQXPA+Z wN8Q== MIME-Version: 1.0 X-Received: by 10.194.113.38 with SMTP id iv6mr16574596wjb.19.1452199203648; Thu, 07 Jan 2016 12:40:03 -0800 (PST) Received: by 10.27.217.12 with HTTP; Thu, 7 Jan 2016 12:40:03 -0800 (PST) In-Reply-To: References: Date: Thu, 7 Jan 2016 15:40:03 -0500 Message-ID: From: Ethan Heilman To: Bitcoin Dev Content-Type: text/plain; charset=UTF-8 X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Thu, 07 Jan 2016 21:22:06 +0000 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 20:40:05 -0000 Based on current GH/s count of 775,464,121 Bitcoin tests 2^80 every 19 days. log2(775464121*(1000*1000*1000*60*60*24*19)) = ~80.07 I don't fully understand the security model of segwit, so my analysis will assume that any collision is bad. >But it also requires O(2^80) storage, which is utterly infeasible You don't store all 2^80 previous hashes, instead you just hash a seed value 2^80 times, then look for a cycle. seed = {0,1}^160 x = hash(seed) for i in 2^80: ....x = hash(x) x_final = x y = hash(x_final) for j in 2^80: ....if y == x_final: ........print "cycle len: "+j ........break ....y = hash(y) If at any point x collides with a prior value of x it will form a cycle. Thus y will also cycle and collide with x_final. j gives you the cycle length, which allows you find the collision: hash^(2^80-j)(seed) == hash^(j)(hash^(2^80-j)(seed)). Worst case: First loop costs 2**80, second loop costs 2**80=j, finding the colliding value is 2**80. Total cost 2**80+2**80+2**80 = 2**81.5 and requires storing less than a kilobyte. This is a toy example, does not exploit parallelism, time memory trade offs, can be easily made better, etc... On Thu, Jan 7, 2016 at 2:02 PM, 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 >