<div dir="ltr"><div>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:<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 "arbitrary_data").<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'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"?<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"><<a href="mailto:bitcoin-dev@lists.linuxfoundation.org" target="_blank">bitcoin-dev@lists.linuxfoundation.org</a>></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'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"><<a href="mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br>
> I'm hoisting this from some private feedback I sent on the segregated<br>
> witness BIP:<br>
><br>
> I said:<br>
><br>
> "I'd also use RIPEMD160(SHA256()) as the hash function and save the 12<br>
> bytes-- a successful preimage attack against that ain't gonna happen before<br>
> we're all dead. I'm probably being dense, but I just don't see how a<br>
> collision attack is relevant here."<br>
><br>
> Pieter responded:<br>
><br>
> "The problem case is where someone in a contract setup shows you a script,<br>
> which you accept as being a payment to yourself. An attacker could use a<br>
> collision attack to construct scripts with identical hashes, only one of<br>
> which does have the property you want, and steal coins.<br>
><br>
> So you really want collision security, and I don't think 80 bits is<br>
> something we should encourage for that. Normal pubkey hashes don't have that<br>
> problem, as they can't be constructed to pay to you."<br>
><br>
> ... but I'm unconvinced:<br>
><br>
> "But it is trivial for contract wallets to protect against collision<br>
> attacks-- if you give me a script that is "gavin_pubkey CHECKSIG<br>
> arbitrary_data OP_DROP" with "I promise I'm not trying to rip you off, just<br>
> ignore that arbitrary data" a wallet can just refuse. Even more likely, a<br>
> contract wallet won't even recognize that as a pay-to-gavin transaction.<br>
><br>
> I suppose it could be looking for some form of "gavin_pubkey<br>
> somebody_else_pubkey CHECKMULTISIG ... with the attacker using<br>
> somebody_else_pubkey to force the collision, but, again, trivial contract<br>
> protocol tweaks ("send along a proof you have the private key corresponding<br>
> to the public key" or "everybody pre-commits pubkeys they'll use at protocol<br>
> start") would protect against that.<br>
><br>
> Adding an extra 12 bytes to every segwit to prevent an attack that takes<br>
> 2^80 computation and 2^80 storage, is unlikely to be a problem in practice,<br>
> and is trivial to protect against is the wrong tradeoff to make."<br>
><br>
> 20 bytes instead of 32 bytes is a savings of almost 40%, which is<br>
> significant.<br>
><br>
> The general question I'd like to raise on this list is:<br>
><br>
> Should we be worried, today, about collision attacks against RIPEMD160 (our<br>
> 160-bit hash)?<br>
><br>
> Mounting a successful brute-force collision attack would require at least<br>
> O(2^80) CPU, which is kinda-sorta feasible (Pieter pointed out that Bitcoin<br>
> POW has computed more SHA256 hashes than that). But it also requires O(2^80)<br>
> storage, which is utterly infeasible (there is something on the order of<br>
> 2^35 bytes of storage in the entire world). Even assuming doubling every<br>
> single year (faster than Moore's Law), we're four decades away from an<br>
> attacker with THE ENTIRE WORLD's storage capacity being able to mount a<br>
> collision attack.<br>
><br>
><br>
> References:<br>
><br>
> <a href="https://en.wikipedia.org/wiki/Collision_attack" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Collision_attack</a><br>
><br>
> <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>
><br>
><br>
> --<br>
> --<br>
> Gavin Andresen<br>
><br>
><br>
</div></div><div class="HOEnZb"><div class="h5">> _______________________________________________<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>
><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'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>"He ought to find it more profitable to play by the rules" - Satoshi Nakamoto</div></div>
</div>