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
|
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 16E98E8D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Jan 2016 12:38:53 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-lb0-f171.google.com (mail-lb0-f171.google.com
[209.85.217.171])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 16CA5137
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Jan 2016 12:38:52 +0000 (UTC)
Received: by mail-lb0-f171.google.com with SMTP id sv6so216319322lbb.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 08 Jan 2016 04:38:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
h=mime-version:in-reply-to:references:date:message-id:subject:from:to
:cc:content-type;
bh=aqB7HQJZRcE525AAPeeqfklfhIPnwsowGmn7W25IsF0=;
b=U8oTY5JE6sKiIvo85F0z6RMdClbZRIYvE1XfUxTVp9eGHvxvhu41Majn6AADxIgs4L
pXo4YC98zjAinAEFOqxIJ0ma9d3mKGPXcZN1V9wg5Y777Msc3ZlBunBGaF5MSVHK7zDh
soQponjIXyLr5H2m6tAB7CGAF58i7hLjCYKSqC0WG3g57l4W/gKe9ClhDwVZpwLQe4hs
Tp6l7r+ZnfiKM33Kx0jJAjdXACPrfxEJ0OmGgsLenfY9oC+ROtJ5dBJLCi9v2Gh/l3Vk
btAWjPWLODcFOgEVAd9cMsJVHBo2ZBBE4XIR2/GP+DcSAP8CbPcXBPx9Igqc+cmiQBuh
RzMA==
MIME-Version: 1.0
X-Received: by 10.112.201.3 with SMTP id jw3mr4460485lbc.27.1452256730586;
Fri, 08 Jan 2016 04:38:50 -0800 (PST)
Received: by 10.25.25.78 with HTTP; Fri, 8 Jan 2016 04:38:50 -0800 (PST)
In-Reply-To: <8737u8qnye.fsf@rustcorp.com.au>
References: <CABsx9T3aTme2EQATamGGzeqNqJkUcPGa=0LVidJSRYNznM-myQ@mail.gmail.com>
<CAPg+sBhH0MODjjp8Avx+Fy_UGqzMjUq_jn3vT3oH=u3711tsSA@mail.gmail.com>
<8760z4rbng.fsf@rustcorp.com.au>
<C4B5B9F1-9C53-45BC-9B30-F572C78096E3@mattcorallo.com>
<8737u8qnye.fsf@rustcorp.com.au>
Date: Fri, 8 Jan 2016 07:38:50 -0500
Message-ID: <CABsx9T1gmz=sr_sEEuy8BQU6SXdmi58O30rzRWNW=0Ej98fi4A@mail.gmail.com>
From: Gavin Andresen <gavinandresen@gmail.com>
To: Rusty Russell <rusty@rustcorp.com.au>
Content-Type: multipart/alternative; boundary=001a11c372d48ca3a40528d1de41
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: Fri, 08 Jan 2016 12:54:04 +0000
Cc: Rusty Russell via 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: Fri, 08 Jan 2016 12:38:53 -0000
--001a11c372d48ca3a40528d1de41
Content-Type: text/plain; charset=UTF-8
On Fri, Jan 8, 2016 at 7:02 AM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> Matt Corallo <lf-lists@mattcorallo.com> writes:
> > Indeed, anything which uses P2SH is obviously vulnerable if there is
> > an attack on RIPEMD160 which reduces it's security only marginally.
>
> I don't think this is true? Even if you can generate a collision in
> RIPEMD160, that doesn't help you since you need to create a specific
> SHA256 hash for the RIPEMD160 preimage.
>
> Even a preimage attack only helps if it leads to more than one preimage
> fairly cheaply; that would make grinding out the SHA256 preimage easier.
> AFAICT even MD4 isn't this broken.
>
It feels like we've gone over that before, but I can never remember where
or when. I believe consensus was that if we were using the broken MD5 in
all the places we use RIPEMD160 we'd still be secure today because of
Satoshi's use of nested hash functions everywhere.
> But just with Moore's law (doubling every 18 months), we'll worry about
> economically viable attacks in 20 years.[1]
> That's far enough away that I would choose simplicity, and have all SW
> scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, but it's
> not a no-brainer.
Lets see if I've followed the specifics of the collision attack correctly,
Ethan (or somebody) please let me know if I'm missing something:
So attacker is in the middle of establishing a payment channel with
somebody. Victim gives their public key, attacker creates the innocent
fund-locking script '2 V A 2 CHECKMULTISIG' (V is victim's public key, A
is attacker's) but doesn't give it to the victim yet.
Instead they then generate about 2^81scripts that are some form of
pay-to-attacker ....
... wait, no that doesn't work, because SHA256 is used as the inner hash
function. They'd have to generate 2^129 to find a cycle in SHA256.
Instead, they .. what? I don't see a viable attack unless RIPEMD160 and
SHA256 (or the combination) suffers a cryptographic break.
--
--
Gavin Andresen
--001a11c372d48ca3a40528d1de41
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On F=
ri, Jan 8, 2016 at 7:02 AM, Rusty Russell <span dir=3D"ltr"><<a href=3D"=
mailto:rusty@rustcorp.com.au" target=3D"_blank">rusty@rustcorp.com.au</a>&g=
t;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0=
.8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"">Matt Co=
rallo <<a href=3D"mailto:lf-lists@mattcorallo.com">lf-lists@mattcorallo.=
com</a>> writes:<br>
> Indeed, anything which uses P2SH is obviously vulnerable if there is<b=
r>
> an attack on RIPEMD160 which reduces it's security only marginally=
.<br>
<br>
</span>I don't think this is true?=C2=A0 Even if you can generate a col=
lision in<br>
RIPEMD160, that doesn't help you since you need to create a specific<br=
>
SHA256 hash for the RIPEMD160 preimage.<br>
<br>
Even a preimage attack only helps if it leads to more than one preimage<br>
fairly cheaply; that would make grinding out the SHA256 preimage easier.<br=
>
AFAICT even MD4 isn't this broken.<br></blockquote><div><br></div><div>=
It feels like we've gone over that before, but I can never remember whe=
re or when. I believe consensus was that if we were using the broken MD5 in=
all the places we use RIPEMD160 we'd still be secure today because of =
Satoshi's use of nested hash functions everywhere.</div><div><br></div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
<br>
But just with Moore's law (doubling every 18 months), we'll worry a=
bout<br>
economically viable attacks in 20 years.[1]</blockquote><blockquote class=
=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd=
ing-left:1ex">
<br>
That's far enough away that I would choose simplicity, and have all SW<=
br>
scriptPubKeys simply be "<0> RIPEMD(SHA256(WP))" for now, b=
ut it's<br>
not a no-brainer. =C2=A0</blockquote><div><br></div><div>Lets see if I'=
ve followed the specifics of the collision attack correctly, Ethan (or some=
body) please let me know if I'm missing something:</div><div><br></div>=
<div>So attacker is in the middle of establishing a payment channel with so=
mebody. Victim gives their public key, attacker creates the innocent fund-l=
ocking script =C2=A0'2 V A 2 CHECKMULTISIG' (V is victim's publ=
ic key, A is attacker's) but doesn't give it to the victim yet.</di=
v><div><br></div><div>Instead they then generate about 2^81scripts that are=
some form of pay-to-attacker ....</div><div>... wait, no that doesn't =
work, because SHA256 is used as the inner hash function.=C2=A0 They'd h=
ave to generate 2^129 to find a cycle in SHA256.</div><div><br></div><div>I=
nstead, they .. what? I don't see a viable attack unless RIPEMD160 and =
SHA256 (or the combination) suffers a cryptographic break.</div></div><br c=
lear=3D"all"><div><br></div>-- <br><div class=3D"gmail_signature">--<br>Gav=
in Andresen<br></div>
</div></div>
--001a11c372d48ca3a40528d1de41--
|
