diff options
author | Anthony Towns <aj@erisian.com.au> | 2016-01-09 01:33:29 +1000 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2016-01-08 15:33:37 +0000 |
commit | bb8936162d52ba3a01dc1ecf2c921d31b0fefbef (patch) | |
tree | b9f4309216d373ba4e484a353b97bc6417b44e81 | |
parent | 5d354b1743dcb1717e849d081198a632fdab9bad (diff) | |
download | pi-bitcoindev-bb8936162d52ba3a01dc1ecf2c921d31b0fefbef.tar.gz pi-bitcoindev-bb8936162d52ba3a01dc1ecf2c921d31b0fefbef.zip |
Re: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
-rw-r--r-- | 4c/0e1bd9478b094887e1a46c72d05c725fcfe8f7 | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/4c/0e1bd9478b094887e1a46c72d05c725fcfe8f7 b/4c/0e1bd9478b094887e1a46c72d05c725fcfe8f7 new file mode 100644 index 000000000..a8880e10b --- /dev/null +++ b/4c/0e1bd9478b094887e1a46c72d05c725fcfe8f7 @@ -0,0 +1,107 @@ +Return-Path: <aj@erisian.com.au> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id 24CD6E32 + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <aj@erisian.com.au> +To: Gavin Andresen <gavinandresen@gmail.com> +Message-ID: <20160108153329.GA15731@sapphire.erisian.com.au> +References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com> + <CAPg+sBhH0MODjjp8Avx+Fy_UGqzMjUq_jn3vT3oH=u3711tsSA@mail.gmail.com> + <8760z4rbng.fsf@rustcorp.com.au> + <C4B5B9F1-9C53-45BC-9B30-F572C78096E3@mattcorallo.com> + <8737u8qnye.fsf@rustcorp.com.au> + <CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com> +MIME-Version: 1.0 +Content-Type: text/plain; charset=us-ascii +Content-Disposition: inline +In-Reply-To: <CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com> +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 <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 + + |