<div dir="ltr"><div>Maybe I&#39;m being dense, but I don&#39;t see why 2**80 storage is required for this attack.  Also, I don&#39;t see why the attacker ever needs to get the victim to accept &quot;arbitrary_data&quot;.  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 construct a second script that lets attacker keep his coins and has the same hash. (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 for 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 seller would never see the I&#39;d appreciate any correction to my understanding here.  Where do you need 2**80 storage?  And when does the seller have to accept &quot;arbitrary_data&quot;?<br></p>Thanks!</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 7, 2016 at 11:19 AM, Adam Back via bitcoin-dev <span dir="ltr">&lt;<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left: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).  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="HOEnZb"><div class="h5">&lt;<a href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br>
&gt; I&#39;m hoisting this from some private feedback I sent on the segregated<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 save the 12<br>
&gt; bytes-- a successful preimage attack against that ain&#39;t gonna happen 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 is<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 collision<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 to rip you off, just<br>
&gt; ignore that arbitrary data&quot; a wallet can just refuse. Even more likely, a<br>
&gt; contract wallet won&#39;t even recognize that as a pay-to-gavin transaction.<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 contract<br>
&gt; protocol tweaks (&quot;send along a proof you have the private key corresponding<br>
&gt; to the public key&quot; or &quot;everybody pre-commits pubkeys they&#39;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 takes<br>
&gt; 2^80 computation and 2^80 storage, is unlikely to be a problem in practice,<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 least<br>
&gt; O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin<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).  Even assuming doubling 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 mount a<br>
&gt; collision attack.<br>
&gt;<br>
&gt;<br>
&gt; References:<br>
&gt;<br>
&gt; <a href="https://en.wikipedia.org/wiki/Collision_attack" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Collision_attack</a><br>
&gt;<br>
&gt; <a href="https://vsatglobalseriesblog.wordpress.com/2013/06/21/in-2013-the-amount-of-data-generated-worldwide-will-reach-four-zettabytes/" rel="noreferrer" target="_blank">https://vsatglobalseriesblog.wordpress.com/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="HOEnZb"><div class="h5">&gt; _______________________________________________<br>
&gt; bitcoin-dev mailing list<br>
&gt; <a href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a><br>
&gt; <a href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br>
&gt;<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href="https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" rel="noreferrer" target="_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><div dir="ltr">I like to provide some work at no charge to prove my value. Do you need a techie?  <br>I own <a href="http://www.litmocracy.com" target="_blank">Litmocracy</a> and <a href="http://www.memeracing.net" target="_blank">Meme Racing</a> (in alpha). <br>I&#39;m the webmaster for <a href="http://www.voluntaryist.com" target="_blank">The Voluntaryist</a> which now accepts Bitcoin.<br>I also code for <a href="http://dollarvigilante.com/" target="_blank">The Dollar Vigilante</a>.<br>&quot;He ought to find it more profitable to play by the rules&quot; - Satoshi Nakamoto</div></div>
</div>