diff options
| author | Gavin Andresen <gavinandresen@gmail.com> | 2016-01-07 14:02:05 -0500 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2016-01-07 19:02:07 +0000 |
| commit | 2777bcfe5e5d7cdce65e4719134a92091973f414 (patch) | |
| tree | 0f503fd6d087919494b03e3e1b4127117476041f | |
| parent | 0e3584dbc879f5d61bf4e676542d029991b742e7 (diff) | |
| download | pi-bitcoindev-2777bcfe5e5d7cdce65e4719134a92091973f414.tar.gz pi-bitcoindev-2777bcfe5e5d7cdce65e4719134a92091973f414.zip | |
[bitcoin-dev] Time to worry about 80-bit collision attacks or not?
| -rw-r--r-- | 3b/7e3ae71e4d8a612a426d700c264959cc3e148c | 190 |
1 files changed, 190 insertions, 0 deletions
diff --git a/3b/7e3ae71e4d8a612a426d700c264959cc3e148c b/3b/7e3ae71e4d8a612a426d700c264959cc3e148c new file mode 100644 index 000000000..654777700 --- /dev/null +++ b/3b/7e3ae71e4d8a612a426d700c264959cc3e148c @@ -0,0 +1,190 @@ +Return-Path: <gavinandresen@gmail.com> +Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org + [172.17.192.35]) + by mail.linuxfoundation.org (Postfix) with ESMTPS id E0B56B5D + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 7 Jan 2016 19:02:07 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.7.6 +Received: from mail-lb0-f182.google.com (mail-lb0-f182.google.com + [209.85.217.182]) + by smtp1.linuxfoundation.org (Postfix) with ESMTPS id D0934CC + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 7 Jan 2016 19:02:06 +0000 (UTC) +Received: by mail-lb0-f182.google.com with SMTP id sv6so205461981lbb.0 + for <bitcoin-dev@lists.linuxfoundation.org>; + Thu, 07 Jan 2016 11:02:06 -0800 (PST) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; + h=mime-version:date:message-id:subject:from:to:content-type; + bh=KoSTMEczF4hxan5oEdQ9U7lhEPxOlpwIrXmMlUoGHUQ=; + b=kh8UTSdRYpBLvEU3cVBcd7KtPvbr2yclHm3Ygbi3zHeB6ef+MHDdh6TRehk1GpfZad + MLRyPZd0AZ5M6VcQXKTfnakQAqNaS/+UvIWgOVs0KGjuVAsqTUZTp8taR6g4LMQG9R98 + R0AG4/mJmnmKiyLhdqpcTn84csCBskMAgxO+p9lgY4BN29m79UYxdBWyC57gigaY02nu + ES8U2NDMt4GlMy6hjzv+THVwOirJUajtp26ywLCekIzLoNxzFDrEILxfq9hD6yA13fS+ + 7xppeYAe2I5zHyXXUfbXazCJTBaBnWQGzUU8gm7BBXB3lypYqQF9hfao52jvvJhqHNbV + oV5w== +MIME-Version: 1.0 +X-Received: by 10.112.219.101 with SMTP id pn5mr10112863lbc.123.1452193325211; + Thu, 07 Jan 2016 11:02:05 -0800 (PST) +Received: by 10.25.25.78 with HTTP; Thu, 7 Jan 2016 11:02:05 -0800 (PST) +Date: Thu, 7 Jan 2016 14:02:05 -0500 +Message-ID: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com> +From: Gavin Andresen <gavinandresen@gmail.com> +To: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary=001a11c3c26c4b6c4c0528c31b10 +X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED, + DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,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: Thu, 07 Jan 2016 19:05:19 +0000 +Subject: [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: Thu, 07 Jan 2016 19:02:08 -0000 + +--001a11c3c26c4b6c4c0528c31b10 +Content-Type: text/plain; charset=UTF-8 + +I'm hoisting this from some private feedback I sent on the segregated +witness BIP: + +I said: + +"I'd also use RIPEMD160(SHA256()) as the hash function and save the 12 +bytes-- a successful preimage attack against that ain't gonna happen before +we're all dead. I'm probably being dense, but I just don't see how a +collision attack is relevant here." + +Pieter responded: + +"The problem case is where someone in a contract setup shows you a script, +which you accept as being a payment to yourself. An attacker could use a +collision attack to construct scripts with identical hashes, only one of +which does have the property you want, and steal coins. + +So you really want collision security, and I don't think 80 bits is +something we should encourage for that. Normal pubkey hashes don't have +that problem, as they can't be constructed to pay to you." +... but I'm unconvinced: + +"But it is trivial for contract wallets to protect against collision +attacks-- if you give me a script that is "gavin_pubkey CHECKSIG +arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just +ignore that arbitrary data" a wallet can just refuse. Even more likely, a +contract wallet won't even recognize that as a pay-to-gavin transaction. + +I suppose it could be looking for some form of "gavin_pubkey +somebody_else_pubkey CHECKMULTISIG ... with the attacker using +somebody_else_pubkey to force the collision, but, again, trivial contract +protocol tweaks ("send along a proof you have the private key corresponding +to the public key" or "everybody pre-commits pubkeys they'll use at +protocol start") would protect against that. + +Adding an extra 12 bytes to every segwit to prevent an attack that takes +2^80 computation and 2^80 storage, is unlikely to be a problem in practice, +and is trivial to protect against is the wrong tradeoff to make." + +20 bytes instead of 32 bytes is a savings of almost 40%, which is +significant. + +The general question I'd like to raise on this list is: + +Should we be worried, today, about collision attacks against RIPEMD160 (our +160-bit hash)? + +Mounting a successful brute-force collision attack would require at least +O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin +POW has computed more SHA256 hashes than that). But it also requires +O(2^80) storage, which is utterly infeasible (there is something on the +order of 2^35 bytes of storage in the entire world). Even assuming +doubling every single year (faster than Moore's Law), we're four decades +away from an attacker with THE ENTIRE WORLD's storage capacity being able +to mount a collision attack. + + +References: + +https://en.wikipedia.org/wiki/Collision_attack + +https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/ + + +-- +-- +Gavin Andresen + +--001a11c3c26c4b6c4c0528c31b10 +Content-Type: text/html; charset=UTF-8 +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr">I'm hoisting this from some private feedback I sent on= + the segregated witness BIP:<div><br></div><div>I said:</div><div><br></div= +><div><span style=3D"color:rgb(80,0,80);font-size:12.8px">"I'd als= +o use RIPEMD160(SHA256()) as the hash function and save the 12 bytes-- a su= +ccessful preimage attack against that ain't gonna happen before we'= +re all dead. I'm probably being dense, but I just don't see how a c= +ollision attack is relevant here."</span></div><div><font color=3D"#50= +0050"><span style=3D"font-size:12.8px"><br></span></font></div><div><font c= +olor=3D"#500050"><span style=3D"font-size:12.8px">Pieter responded:</span><= +/font></div><div><p dir=3D"ltr" style=3D"color:rgb(80,0,80);font-size:12.8p= +x">"The problem case is where someone in a contract setup shows you a = +script, which you accept as being a payment to yourself. An attacker could = +use a collision attack to construct scripts with identical hashes, only one= + of which does have the property you want, and steal coins.</p><p dir=3D"lt= +r" style=3D"color:rgb(80,0,80);font-size:12.8px">So you really want collisi= +on security, and I don't think 80 bits is something we should encourage= + for that. Normal pubkey hashes don't have that problem, as they can= +9;t be constructed to pay to you."</p></div><div><font color=3D"#50005= +0"><span style=3D"font-size:12.8px">... but I'm unconvinced:</span></fo= +nt></div><div><font color=3D"#500050"><span style=3D"font-size:12.8px"><br>= +</span></font></div><div><font color=3D"#500050"><span style=3D"font-size:1= +2.8px">"</span></font><span style=3D"font-size:12.8px">But it is trivi= +al for contract wallets to protect against collision attacks-- if you give = +me a script that is "gavin_pubkey CHECKSIG arbitrary_data OP_DROP"= +; with "I promise I'm not trying to rip you off, just ignore that = +arbitrary data" a wallet can just refuse. Even more likely, a contract= + wallet won't even recognize that as a pay-to-gavin transaction.</span>= +<div class=3D"gmail_quote" style=3D"font-size:12.8px"><div><br></div><div>I= + suppose it could be looking for some form of "gavin_pubkey somebody_e= +lse_pubkey CHECKMULTISIG ... with the attacker using somebody_else_pubkey t= +o force the collision, but, again, trivial contract protocol tweaks ("= +send along a proof you have the private key corresponding to the public key= +" or "everybody pre-commits pubkeys they'll use at protocol s= +tart") would protect against that.</div><div><br></div><div>Adding an = +extra 12 bytes to every segwit to prevent an attack that takes 2^80 computa= +tion and 2^80 storage, is unlikely to be a problem in practice, and is triv= +ial to protect against is the wrong tradeoff to make."</div><div><br><= +/div><div>20 bytes instead of 32 bytes is a savings of almost 40%, which is= + significant.</div><div><br></div><div>The general question I'd like to= + raise on this list is:</div><div><br></div><div>Should we be worried, toda= +y, about collision attacks against RIPEMD160 (our 160-bit hash)?</div><div>= +<br></div><div>Mounting a successful brute-force collision attack would req= +uire at least O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed ou= +t that Bitcoin POW has computed more SHA256 hashes than that). But it also = +requires O(2^80) storage, which is utterly infeasible (there is something o= +n the order of 2^35 bytes of storage in the entire world).=C2=A0 Even assum= +ing doubling every single year (faster than Moore's Law), we're fou= +r decades away from an attacker with THE ENTIRE WORLD's storage capacit= +y being able to mount a collision attack.</div><div><br></div></div><div><b= +r></div><div>References:=C2=A0</div><div><br></div><div><a href=3D"https://= +en.wikipedia.org/wiki/Collision_attack">https://en.wikipedia.org/wiki/Colli= +sion_attack</a><br></div><div><br></div><div><a href=3D"https://vsatglobals= +eriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-wor= +ldwide-will-reach-four-zettabytes/">https://vsatglobalseriesblog.wordpress.= +com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-fo= +ur-zettabytes/</a><br></div><div><br></div><div><br></div>-- <br><div class= +=3D"gmail_signature">--<br>Gavin Andresen<br></div><div class=3D"gmail_sign= +ature"><br></div> +</div></div> + +--001a11c3c26c4b6c4c0528c31b10-- + |