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 24CD6E32 for ; Fri, 8 Jan 2016 15:33:37 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from azure.erisian.com.au (cerulean.erisian.com.au [106.187.51.212]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 95BD116C for ; Fri, 8 Jan 2016 15:33:36 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.84 #2 (Debian)) id 1aHZ2i-0007wY-JY; Sat, 09 Jan 2016 01:33:34 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Sat, 09 Jan 2016 01:33:29 +1000 Date: Sat, 9 Jan 2016 01:33:29 +1000 From: Anthony Towns To: Gavin Andresen Message-ID: <20160108153329.GA15731@sapphire.erisian.com.au> References: <8760z4rbng.fsf@rustcorp.com.au> <8737u8qnye.fsf@rustcorp.com.au> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.24 (2015-08-30) X-Spam-Score: -1.9 X-Spam-Score-int: -18 X-Spam-Bar: - X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: bitcoin-dev@lists.linuxfoundation.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: Fri, 08 Jan 2016 15:33:37 -0000 On Fri, Jan 08, 2016 at 07:38:50AM -0500, Gavin Andresen via bitcoin-dev wrote: > 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. Using Ethan Heilman's procedure, the attacker can create two scripts: 2 V __A1__ 2 CHECKMULTISIG 2 V __A2__ 2 CHECKMULTISIG and find values A1 and A2 which hash the scripts to the same result with under 3*2**80 work. I think you can do that by setting the next private key as the result of RIPEMD(SHA256(script with pubkey)), so you could still spend either. But it doesn't change the script, so it's not *that* helpful -- you've just got two different keys you can use. Ah, but you can make the form of the script be a function of your key, so: if privkey % 2 == 0: script = "2 V %s 2 CHECKMULTISIG" % (pubkey) else: script = "%s CHECKSIG" % (pubkey) hash = ripemd160(sha256(script)) nextprivkey = hash Then you have a 50% chance of your cycle giving you a matching hash for one script with A1 and the other script with A2, and you can find the cycle with under 3*2**80 work. Doing five attempts should give you ~96% chance of hitting a usable pair, and should take under 15*2**80 work ~= 2**84 work, with trivial memory use. Trying that in python with a vastly weakened hash function (namely, the first five bytes of ripemd160(sha256()), with 40 bits of security and 3*2**20 work) works as expected -- I got a "useful" collision on my second try in about 7 seconds, seeding with "grumpycat3" ("grumpycat2" didn't work) with the result being: hexlify(ripemd160(sha256("foo%sbar"%unhexlify("86f9fbac1a")))[:5]) 'ae94d9f908' hexlify(ripemd160(sha256("baz%squux"%unhexlify("104fc5093f")))[:5]) 'ae94d9f908' Cheers, aj