From: Gavin Andresen <gavinandresen@gmail•com>
To: Bitcoin Dev <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Time to worry about 80-bit collision attacks or not?
Date: Thu, 7 Jan 2016 14:02:05 -0500 [thread overview]
Message-ID: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 2810 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 4254 bytes --]
next reply other threads:[~2016-01-07 19:02 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-01-07 19:02 Gavin Andresen [this message]
2016-01-07 19:13 ` Matt Corallo
2016-01-07 19:19 ` Adam Back
2016-01-07 20:56 ` Dave Scotese
2016-01-07 21:06 ` Gavin Andresen
2016-01-07 22:56 ` Ethan Heilman
2016-01-07 23:39 ` Gavin Andresen
2016-01-08 1:26 ` Matt Corallo
2016-01-08 1:54 ` Gavin Andresen
2016-01-08 17:38 ` Pieter Wuille
2016-01-08 18:41 ` Peter Todd
2016-01-07 20:40 ` Ethan Heilman
2016-01-07 23:52 ` Pieter Wuille
2016-01-08 1:00 ` Gavin Andresen
2016-01-08 1:27 ` Watson Ladd
2016-01-08 3:30 ` Rusty Russell
2016-01-08 3:41 ` Matt Corallo
2016-01-08 12:02 ` Rusty Russell
2016-01-08 12:38 ` Gavin Andresen
2016-01-08 14:34 ` Watson Ladd
2016-01-08 15:26 ` Adam Back
2016-01-08 15:33 ` Anthony Towns
2016-01-08 15:46 ` Gavin Andresen
2016-01-08 15:50 ` Gavin Andresen
2016-01-08 15:59 ` Gavin Andresen
2016-01-11 20:32 ` Jorge Timón
2016-01-08 16:06 ` Gavin Andresen
2016-01-11 3:57 ` Rusty Russell
2016-01-11 6:57 ` Peter Todd
2016-01-11 23:57 ` Tier Nolan
2016-01-12 0:00 ` Tier Nolan
2016-01-12 12:08 ` Gavin Andresen
2016-01-12 23:22 ` Zooko Wilcox-O'Hearn
2016-01-08 18:52 ` Peter Todd
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com' \
--to=gavinandresen@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox