path: root/2c/73cfd6654e26725fc8315496f6fb74865fb136

Return-Path: <dscotese@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id D04CCCF1
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu,  7 Jan 2016 20:56:35 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f51.google.com (mail-oi0-f51.google.com
	[209.85.218.51])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 80485A5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu,  7 Jan 2016 20:56:34 +0000 (UTC)
Received: by mail-oi0-f51.google.com with SMTP id y66so321991843oig.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 07 Jan 2016 12:56:34 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:sender:in-reply-to:references:date:message-id:subject
	:from:to:cc:content-type;
	bh=3cKBn7ynlxzEb8niE/kQWSXfgF6VBaIkQ6fCv5poS50=;
	b=NcuwI/KuwkZ1T1Z1pN+nyVE5zal4khQsiM1mtn8wFVcfv1WOTz61HdOVK7EjHeuMap
	4c2Mwz0+6GEUoaZ3+dgIkM3FTm3gvJmftwsJhkcyXBRWMDfF7QiSgr7IBz+EWZhFFPWY
	aVNqiiJV8CjL3L0/tyNTn4ydq79WjKwCQTGOvuCrK4PMbDRjYQDsTa4GXnsK0wEAJIGZ
	cr+vJ3m9cqVwnbUhs7I5rA24cM6UOUcSu/neG282CvwwJtMDQGF7GbsNqbNFH3CNIurj
	tLxGIEKdrileitKxfWDxvkhfLan/AXbMLRyGwG5JIVSTcuibQ6z2pnH5YVBSwCHGKjCj
	IInQ==
MIME-Version: 1.0
X-Received: by 10.202.197.21 with SMTP id v21mr62818606oif.35.1452200193959;
	Thu, 07 Jan 2016 12:56:33 -0800 (PST)
Sender: dscotese@gmail.com
Received: by 10.60.55.71 with HTTP; Thu, 7 Jan 2016 12:56:33 -0800 (PST)
In-Reply-To: <CALqxMTHjvFT2aCBYDEiG-6F5qvsXK57_LR6ttpPb3xUG2i443w@mail.gmail.com>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
	<CALqxMTHjvFT2aCBYDEiG-6F5qvsXK57_LR6ttpPb3xUG2i443w@mail.gmail.com>
Date: Thu, 7 Jan 2016 12:56:33 -0800
X-Google-Sender-Auth: 1JT74DdzZ27_nMVEB73y1djRrzw
Message-ID: <CAGLBAhczEceqDp6XPSVLJ0FuTcmZgYkVnUE4rspb3JdeHnZJUg@mail.gmail.com>
From: Dave Scotese <dscotese@litmocracy.com>
To: Adam Back <adam@cypherspace.org>
Content-Type: multipart/alternative; boundary=001a1134e05cb430120528c4b4cb
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,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 21:21:45 +0000
Cc: Bitcoin Dev <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: Thu, 07 Jan 2016 20:56:35 -0000

--001a1134e05cb430120528c4b4cb
Content-Type: text/plain; charset=UTF-8

Maybe I'm being dense, but I don't see why 2**80 storage is required for
this attack.  Also, I don't see why the attacker ever needs to get the
victim to accept "arbitrary_data".  Perhaps I'm wrong about how the
collision attack works:

   1. Create a script which is perfectly acceptable and would pass the
   sniff test Gavin proposed (no arbitrary_data).
   2. Set off CPU power to construct a second script that lets attacker
   keep his coins and has the same hash. (This is where you get
   "arbitrary_data").
   3. Send a transaction with the first script to the seller as payment.
   4. Wait for the transaction to be included in a block.
   5. Redeem the transaction with the second script, thus stealing the
   coins back.

So the seller would never see the I'd appreciate any correction to my
understanding here.  Where do you need 2**80 storage?  And when does the
seller have to accept "arbitrary_data"?
Thanks!

On Thu, Jan 7, 2016 at 11:19 AM, Adam Back via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> You could say 256 bit ECDSA is overkill lets go to 160 equivalently.
> Saves even more bytes.
>
> The problem with arguing down is where to stop.
>
> As Matt said these things dont degrade gracefully so a best practice
> is to aim for a bit of extra margin.
>
> 256-bit is quite common at this point since AES, SHA256 etc even in
> things with much less at stake than Bitcoin.
>
> You could send the compressed (unhashed) pubkey then there's no hash
> (and omit it from the sig).  Greg had mentioned that in the past.
>
> I think it might be possible to do both (reclaim the hash bits in the
> serialisation of the pub key).
>
> Adam
>
> On 7 January 2016 at 20:02, Gavin Andresen via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > 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
> >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>



-- 
I like to provide some work at no charge to prove my value. Do you need a
techie?
I own Litmocracy <http://www.litmocracy.com> and Meme Racing
<http://www.memeracing.net> (in alpha).
I'm the webmaster for The Voluntaryist <http://www.voluntaryist.com> which
now accepts Bitcoin.
I also code for The Dollar Vigilante <http://dollarvigilante.com/>.
"He ought to find it more profitable to play by the rules" - Satoshi
Nakamoto

--001a1134e05cb430120528c4b4cb
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Maybe I&#39;m being dense, but I don&#39;t see why 2*=
*80 storage is required for this attack.=C2=A0 Also, I don&#39;t see why th=
e attacker ever needs to get the victim to accept &quot;arbitrary_data&quot=
;.=C2=A0 Perhaps I&#39;m wrong about how the collision attack works:<br><ol=
><li>Create a script which is perfectly acceptable and would pass the sniff=
 test Gavin proposed (no arbitrary_data).</li><li>Set off CPU power to cons=
truct a second script that lets attacker keep his coins and has the same ha=
sh. (This is where you get &quot;arbitrary_data&quot;).<br></li><li>Send a =
transaction with the first script to the seller as payment.</li><li>Wait fo=
r the transaction to be included in a block.</li><li>Redeem the transaction=
 with the second script, thus stealing the coins back.</li></ol><p>So the s=
eller would never see the I&#39;d appreciate any correction to my understan=
ding here.=C2=A0 Where do you need 2**80 storage?=C2=A0 And when does the s=
eller have to accept &quot;arbitrary_data&quot;?<br></p>Thanks!</div></div>=
<div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Thu, Jan 7, 20=
16 at 11:19 AM, Adam Back via bitcoin-dev <span dir=3D"ltr">&lt;<a href=3D"=
mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev=
@lists.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class=3D"gm=
ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
ft:1ex">You could say 256 bit ECDSA is overkill lets go to 160 equivalently=
.<br>
Saves even more bytes.<br>
<br>
The problem with arguing down is where to stop.<br>
<br>
As Matt said these things dont degrade gracefully so a best practice<br>
is to aim for a bit of extra margin.<br>
<br>
256-bit is quite common at this point since AES, SHA256 etc even in<br>
things with much less at stake than Bitcoin.<br>
<br>
You could send the compressed (unhashed) pubkey then there&#39;s no hash<br=
>
(and omit it from the sig).=C2=A0 Greg had mentioned that in the past.<br>
<br>
I think it might be possible to do both (reclaim the hash bits in the<br>
serialisation of the pub key).<br>
<br>
Adam<br>
<br>
On 7 January 2016 at 20:02, Gavin Andresen via bitcoin-dev<br>
<div class=3D"HOEnZb"><div class=3D"h5">&lt;<a href=3D"mailto:bitcoin-dev@l=
ists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wro=
te:<br>
&gt; I&#39;m hoisting this from some private feedback I sent on the segrega=
ted<br>
&gt; witness BIP:<br>
&gt;<br>
&gt; I said:<br>
&gt;<br>
&gt; &quot;I&#39;d also use RIPEMD160(SHA256()) as the hash function and sa=
ve the 12<br>
&gt; bytes-- a successful preimage attack against that ain&#39;t gonna happ=
en before<br>
&gt; we&#39;re all dead. I&#39;m probably being dense, but I just don&#39;t=
 see how a<br>
&gt; collision attack is relevant here.&quot;<br>
&gt;<br>
&gt; Pieter responded:<br>
&gt;<br>
&gt; &quot;The problem case is where someone in a contract setup shows you =
a script,<br>
&gt; which you accept as being a payment to yourself. An attacker could use=
 a<br>
&gt; collision attack to construct scripts with identical hashes, only one =
of<br>
&gt; which does have the property you want, and steal coins.<br>
&gt;<br>
&gt; So you really want collision security, and I don&#39;t think 80 bits i=
s<br>
&gt; something we should encourage for that. Normal pubkey hashes don&#39;t=
 have that<br>
&gt; problem, as they can&#39;t be constructed to pay to you.&quot;<br>
&gt;<br>
&gt; ... but I&#39;m unconvinced:<br>
&gt;<br>
&gt; &quot;But it is trivial for contract wallets to protect against collis=
ion<br>
&gt; attacks-- if you give me a script that is &quot;gavin_pubkey CHECKSIG<=
br>
&gt; arbitrary_data OP_DROP&quot; with &quot;I promise I&#39;m not trying t=
o rip you off, just<br>
&gt; ignore that arbitrary data&quot; a wallet can just refuse. Even more l=
ikely, a<br>
&gt; contract wallet won&#39;t even recognize that as a pay-to-gavin transa=
ction.<br>
&gt;<br>
&gt; I suppose it could be looking for some form of &quot;gavin_pubkey<br>
&gt; somebody_else_pubkey CHECKMULTISIG ... with the attacker using<br>
&gt; somebody_else_pubkey to force the collision, but, again, trivial contr=
act<br>
&gt; protocol tweaks (&quot;send along a proof you have the private key cor=
responding<br>
&gt; to the public key&quot; or &quot;everybody pre-commits pubkeys they&#3=
9;ll use at protocol<br>
&gt; start&quot;) would protect against that.<br>
&gt;<br>
&gt; Adding an extra 12 bytes to every segwit to prevent an attack that tak=
es<br>
&gt; 2^80 computation and 2^80 storage, is unlikely to be a problem in prac=
tice,<br>
&gt; and is trivial to protect against is the wrong tradeoff to make.&quot;=
<br>
&gt;<br>
&gt; 20 bytes instead of 32 bytes is a savings of almost 40%, which is<br>
&gt; significant.<br>
&gt;<br>
&gt; The general question I&#39;d like to raise on this list is:<br>
&gt;<br>
&gt; Should we be worried, today, about collision attacks against RIPEMD160=
 (our<br>
&gt; 160-bit hash)?<br>
&gt;<br>
&gt; Mounting a successful brute-force collision attack would require at le=
ast<br>
&gt; O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bi=
tcoin<br>
&gt; POW has computed more SHA256 hashes than that). But it also requires O=
(2^80)<br>
&gt; storage, which is utterly infeasible (there is something on the order =
of<br>
&gt; 2^35 bytes of storage in the entire world).=C2=A0 Even assuming doubli=
ng every<br>
&gt; single year (faster than Moore&#39;s Law), we&#39;re four decades away=
 from an<br>
&gt; attacker with THE ENTIRE WORLD&#39;s storage capacity being able to mo=
unt a<br>
&gt; collision attack.<br>
&gt;<br>
&gt;<br>
&gt; References:<br>
&gt;<br>
&gt; <a href=3D"https://en.wikipedia.org/wiki/Collision_attack" rel=3D"nore=
ferrer" target=3D"_blank">https://en.wikipedia.org/wiki/Collision_attack</a=
><br>
&gt;<br>
&gt; <a href=3D"https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-20=
13-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/" rel=
=3D"noreferrer" target=3D"_blank">https://vsatglobalseriesblog.wordpress.co=
m/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four=
-zettabytes/</a><br>
&gt;<br>
&gt;<br>
&gt; --<br>
&gt; --<br>
&gt; Gavin Andresen<br>
&gt;<br>
&gt;<br>
</div></div><div class=3D"HOEnZb"><div class=3D"h5">&gt; __________________=
_____________________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@l=
ists.linuxfoundation.org</a><br>
&gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-=
dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org=
/mailman/listinfo/bitcoin-dev</a><br>
&gt;<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.=
linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</div></div></blockquote></div><br><br clear=3D"all"><br>-- <br><div class=
=3D"gmail_signature"><div dir=3D"ltr">I like to provide some work at no cha=
rge to prove my value. Do you need a techie?=C2=A0 <br>I own <a href=3D"htt=
p://www.litmocracy.com" target=3D"_blank">Litmocracy</a> and <a href=3D"htt=
p://www.memeracing.net" target=3D"_blank">Meme Racing</a> (in alpha). <br>I=
&#39;m the webmaster for <a href=3D"http://www.voluntaryist.com" target=3D"=
_blank">The Voluntaryist</a> which now accepts Bitcoin.<br>I also code for =
<a href=3D"http://dollarvigilante.com/" target=3D"_blank">The Dollar Vigila=
nte</a>.<br>&quot;He ought to find it more profitable to play by the rules&=
quot; - Satoshi Nakamoto</div></div>
</div>

--001a1134e05cb430120528c4b4cb--