Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 72F85E4E for ; Fri, 8 Jan 2016 14:34:10 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-yk0-f177.google.com (mail-yk0-f177.google.com [209.85.160.177]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id DD927F5 for ; Fri, 8 Jan 2016 14:34:09 +0000 (UTC) Received: by mail-yk0-f177.google.com with SMTP id k129so341205482yke.0 for ; Fri, 08 Jan 2016 06:34:09 -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 :cc:content-type; bh=ntAewp8E1JhXpnKB8QcOGVzwXfYxXzDtVyAdMThvw4M=; b=DhZ0Q9ysTHdJLNon++M+iqELIlLuVIMHRV3psH9W1JkCsRJubFPlkRbiWcyiwkWc8R uBWyc5vglYQheLG1oZpt1zncp1ZTi0KB56aDeJaT9u3WpggdPd8GwgvHY3PP+Io4yCMk ccuxdySIw9CBoDLE3sPsNqrtnbbrfPjSMs026ieLijG4+w9bs5pPQckRZTrSYOjw+aO5 bNkRiHnb1308lk+0UkZNCY7BDE4itoCqf+gQ/kBQLqWhn1DFinb/FCKyPQECe46jB7go Lv24xMeNUu5n5GFYFHDVFz1V0WsNK6dYex+rty/c77/KgSnWog5H94kKwWhpf+rtehtr epFw== MIME-Version: 1.0 X-Received: by 10.13.213.215 with SMTP id x206mr83515861ywd.97.1452263649247; Fri, 08 Jan 2016 06:34:09 -0800 (PST) Received: by 10.13.216.150 with HTTP; Fri, 8 Jan 2016 06:34:09 -0800 (PST) In-Reply-To: References: <8760z4rbng.fsf@rustcorp.com.au> <8737u8qnye.fsf@rustcorp.com.au> Date: Fri, 8 Jan 2016 06:34:09 -0800 Message-ID: From: Watson Ladd To: Gavin Andresen 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: Fri, 08 Jan 2016 14:37:04 +0000 Cc: Rusty Russell via bitcoin-dev 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: Fri, 08 Jan 2016 14:34:10 -0000 On Fri, Jan 8, 2016 at 4:38 AM, Gavin Andresen via bitcoin-dev wrote: > On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell wrote: >> >> Matt Corallo writes: >> > Indeed, anything which uses P2SH is obviously vulnerable if there is >> > an attack on RIPEMD160 which reduces it's security only marginally. >> >> I don't think this is true? Even if you can generate a collision in >> RIPEMD160, that doesn't help you since you need to create a specific >> SHA256 hash for the RIPEMD160 preimage. >> >> Even a preimage attack only helps if it leads to more than one preimage >> fairly cheaply; that would make grinding out the SHA256 preimage easier. >> AFAICT even MD4 isn't this broken. > > > It feels like we've gone over that before, but I can never remember where or > when. I believe consensus was that if we were using the broken MD5 in all > the places we use RIPEMD160 we'd still be secure today because of Satoshi's > use of nested hash functions everywhere. > >> >> But just with Moore's law (doubling every 18 months), we'll worry about >> economically viable attacks in 20 years.[1] >> >> >> That's far enough away that I would choose simplicity, and have all SW >> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's >> not a no-brainer. > > > Lets see if I've followed the specifics of the collision attack correctly, > Ethan (or somebody) please let me know if I'm missing something: > > So attacker is in the middle of establishing a payment channel with > somebody. Victim gives their public key, attacker creates the innocent > fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A is > attacker's) but doesn't give it to the victim yet. > > Instead they then generate about 2^81scripts that are some form of > pay-to-attacker .... > ... wait, no that doesn't work, because SHA256 is used as the inner hash > function. They'd have to generate 2^129 to find a cycle in SHA256. For 2^80 they simply generate 2^80 scripts that look innocent, and 2^80 that are not. With high probability there is a collision. I agree that most cryptanalysis won't work because of the nesting, but 2^80 is not good. > > Instead, they .. what? I don't see a viable attack unless RIPEMD160 and > SHA256 (or the combination) suffers a cryptographic break. > > > -- > -- > Gavin Andresen > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > -- "Man is born free, but everywhere he is in chains". --Rousseau.