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 D394DDD8 for ; Fri, 8 Jan 2016 15:26:53 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mout.perfora.net (mout.perfora.net [74.208.4.194]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 04B54164 for ; Fri, 8 Jan 2016 15:26:52 +0000 (UTC) Received: from mail-ig0-f179.google.com ([209.85.213.179]) by mrelay.perfora.net (mreueus003) with ESMTPSA (Nemesis) id 0M5ehC-1a1wvM0QMS-00xZg2 for ; Fri, 08 Jan 2016 16:26:52 +0100 Received: by mail-ig0-f179.google.com with SMTP id mw1so75739744igb.1 for ; Fri, 08 Jan 2016 07:26:51 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.50.92.41 with SMTP id cj9mr22450623igb.38.1452266811110; Fri, 08 Jan 2016 07:26:51 -0800 (PST) Received: by 10.36.130.130 with HTTP; Fri, 8 Jan 2016 07:26:50 -0800 (PST) In-Reply-To: References: <8760z4rbng.fsf@rustcorp.com.au> <8737u8qnye.fsf@rustcorp.com.au> Date: Fri, 8 Jan 2016 16:26:50 +0100 X-Gmail-Original-Message-ID: Message-ID: From: Adam Back To: Watson Ladd Content-Type: text/plain; charset=UTF-8 X-Provags-ID: V03:K0:X4jTBK13NxYsljHkAF8OxdWjoGaXInxexlgPqqVBCof/6KWjcA0 tjh1MPCLf/yyZ8GuUKFerDE9ucQc0MiUghgRvLYLxD3VtAiYZIM5zwlgyIjwAgBx9nB25oQ 6XnU1gMuJRmmk8WgOWT7XspOfraitfd84qDqrM+UTFSE85uA+Iroh2UT+9EzguZ7Gu8YHGQ KEjDOtVWZSnxkQrNEDxjw== X-UI-Out-Filterresults: notjunk:1;V01:K0:STfpS7cDjPc=:y/LqaMgZJaoFOM8WWXRWCo 2zDfagnRQ4eukw1GlJ/jB+4/L5k68KXslcsY7iq55LwvmwuCNUem+5yA2gJci9JHWNt0Sle9Q mKAzN6kx+2ZIQpRHB5DcqATZmSvdg0YtOKtUSjP6JxHDfEc7JizqQEAwPFS35rT+TWIQPXQAT zC3oh4ldsClVYgm/aMP85ggHkGMLEitf+YBjSgqk64ohxxU0SL7FkD/I8RWtmDg0ELt9456Pb Fz60Rlds+N0rVJtq1zruEzigDlaNovK4fuFsu8iIWZxpzfNwC+U63yb62oWRQ+KjBnmHySY13 Mgw9DWV3f8D7lw580BBaeOiEAo+Rsf9qJPCBhcOrqR/nI82lsaiVOPqMEQpnlPJkQspA92kWz g94fnwa8i9Vqkj1krJiBHZ0i2uhAduB7/+clsJFwbk3nJXxEkue6RtqX1THzjn53znd8QxyLw +VryrUKu39/4edWOmcFSEjU6Bk4PFNyfFm+PBLpp//VncQV7bG+CXrSV4HrqaxTxSsr1RI+q8 iIO/eIb/nboUdtBU0PrnD078DdrebwNQV0ku4U2HdSHSIU52W4S9izv2RkYOoknmb7wCWMnrn 2SFsIX3IRqsXFhKkSTNiWNRxJ7HMiAqHBCy7l8EunxZC1DyPcLKPIMY+9/LUQx/+cOLA9Vl4K vlWD5KIOiIP1IxJa/RgPRyeigSz3i7CUzfCHtzuL8SbczsgD2NoKVN4R+7CKpWya1pVNMaZFQ iDkXrlde4kPFrpLl X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org 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 15:26:53 -0000 Tricky choice. On the one hand I had spotted this too before and maybe one or two more exceptions to bitcoin's 128-bit security target and been vaguely tut-tutting about them in the background. It's kind of a violation of crypto rule of thumb that you want to balance things and not have odd weak points as Watson was implying, it puts you closer to the margin if there is a slip or other problem so you have an imbalanced crypto format. On the other hand it's not currently a problem as such and it's less change and slightly more compact. RIPEMD probably is less well reviewed than SHA2. However SHA1 has problems, and SHA2 is a bigger SHA1 basically so, hence the NIST motivation for SHA3 designed to fix the design flaw in SHA1 (and SHA2 in principle). So then if we agree with this rule of thumb (and not doing so would fly against best practices which we probably shouldnt look to do in such a security focussed domain) then what this discussion is more about is when is a good time to write down tech debt. I think that comes to segregated-witness itself which writes down a tidily organised by lines of code robust fix to a bunch of long standing problems. Doing a 2MB hard-fork in comparison fixes nothing really. Leaving known issues to bake in for another N years eventually builds up on you (not even in security just in software engineering) as another rule of thumb. I mean if we dont fix it now that we are making a change that connects, when will we? In software projects I ran we always disguised the cost of tech-debt as non-negotiable baked into our estimates without a line item to escape the PHB syndrome of haggling for features instead of tech debt (which is _never_ a good idea:) Pragmatism vs refactoring as you go. But for scale I think segregated-witness does offer the intriguing next step of being able to do 2 of 2, 3 of 3 and N of N which give size of one sig multisig (indistinguishable even for privacy) as well as K of N key tree sigs, which are also significantly more compact. There was also the other thing I mentioned further up the thread that if we want to take an approach of living with little bit of bloat from getting back to a universal 128-bit target, there are still some fixable bloat things going on: a) sending pubKey in the signature vs recovery (modulo interference with Schnorr batch verify compatibility*); b) using the PubKey instead of PKH in the ScriptPubKey, though that loses the nice property of of not having the key to do DL attacks on until the signed transaction is broadcast; c) I think there might be a way to combine hash & PubKey to keep the delayed PubKey publication property and yet still save the bloat of having both. * I did suggest to Pieter that you could let the miner decide to forgo Schnorr batch verifiability to get compaction from recovery - the pub key could be optionally elided from the scriptSig serialisation by the miner. The other thing we could consider is variable sized hashes (& a few pubkey size choices) that is software complexity however. We might be better of focussing on the bigger picture like IBLT/weak-blocks and bigger wins like MAST, multiSig Schnorr & key tree sigs. Didnt get time to muse on c) but a nice crypto question for someone :) Another thing to note is combining has been known to be fragile to bad interactions or unexpected behaviours. This paper talks about things tradeoffs and weaknesses in hash combiners. http://tuprints.ulb.tu-darmstadt.de/2094/1/thesis.lehmann.pdf Weak concept NACK I think for losing a cleanup opportunity to store it up for the future when there is a reasonable opportunity to fix it? Adam On 8 January 2016 at 15:34, Watson Ladd via bitcoin-dev wrote: > 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. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev