summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAnthony Towns <aj@erisian.com.au>2016-01-09 01:33:29 +1000
committerbitcoindev <bitcoindev@gnusha.org>2016-01-08 15:33:37 +0000
commitbb8936162d52ba3a01dc1ecf2c921d31b0fefbef (patch)
treeb9f4309216d373ba4e484a353b97bc6417b44e81
parent5d354b1743dcb1717e849d081198a632fdab9bad (diff)
downloadpi-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/0e1bd9478b094887e1a46c72d05c725fcfe8f7107
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
+
+