1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
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--
|
