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
191
192
193
194
195
196
197
198
199
200
201
|
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 0B006BE6
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 18:55:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-qk0-f180.google.com (mail-qk0-f180.google.com
[209.85.220.180])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id BB9868A
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 7 Sep 2017 18:55:46 +0000 (UTC)
Received: by mail-qk0-f180.google.com with SMTP id b82so1423456qkc.4
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 07 Sep 2017 11:55:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream-io.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=zTRNjSsX1DVwq4C3n5ta3BqvrKdUEOIXQrKcnN1dUd8=;
b=nbwJt/HuEuasRexUUm6g2jZVo7g2xiXYg5dw2VSh/UJZSHbC8Ndg1CkF9Etpfz0rEN
cD3yXY7UlzjcPQBcvygVso1DyCNPcn6sx6XtCpYU8S/UUWIOmgh5+lD1Xznjg2R9zbBY
cMUwAJAQB2dBq2m3Gighr7FzBlpeJ8PbHW6+xDkop7rRqKTJiSg2qH3VoDgtgvTsVrvh
QMLoLXYV8s1F6CQrVM9RyMGr5ddqa1i2brZvormFd3/dnNpqvXt1XTRoSI1RLblsC9UD
cgVu5qi+/0i5go78rM5nkxRzMig5ieWcxC+uyMHVL47GteMEqs0FeHG2BmZjqNnq5uwx
XmYg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=zTRNjSsX1DVwq4C3n5ta3BqvrKdUEOIXQrKcnN1dUd8=;
b=HsbAQ5YIbw6ubnF54RBVMht+nNt4rSjSZoRPjxbzPsmG+2TFnK0kKTl0WfyS5wTL7c
gQZUvrV6GLJ4+MfTyGHEGqXHrgJ6kdXcDZBpbwDrrFGeVJPJ97lte/hVEm9N41FzprFc
q+QRFydEFaeTifwq5Dr9o8Xkn6AzZEP3nT+n1PziVQXgPB3sW2DYwmJPfX4SH/ypv+B7
ZP7Yo+vEQeOswm8tR24gAq/KSF5qdEGaJql1f6rp162Z+i2cXSJMRx/gjAD/zu38lVDR
CD++E/mItWUglzYJbNkDR6GwWqDkQaMPZqcJbZk1QbV3LKi6F2LWAgtQPNpUt+BOz/Ea
TLWw==
X-Gm-Message-State: AHPjjUiHnKdIrYoeiRhTZPkPMgwo8j6aQHiTqRcrBaJRsUH/GTtIHsVO
47lDVCR/DNmzPTXGlkEqaOYnC7e9jhcuyKwUrw==
X-Google-Smtp-Source: AOwi7QBtEuMl/Bl1K0gcTYsD6+Hca4S5Q4LmgRaOLKfTcclLIEGzjZosY7Pwl1WVWHbUx7VeYbouluCIjSidGQHGXw4=
X-Received: by 10.55.74.133 with SMTP id x127mr394340qka.239.1504810545812;
Thu, 07 Sep 2017 11:55:45 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.12.174.197 with HTTP; Thu, 7 Sep 2017 11:55:25 -0700 (PDT)
In-Reply-To: <EB804508-715A-4CD6-9B87-09845368DAC0@friedenbach.org>
References: <CAMZUoKmD4v4vn9L=kdyJNk-km3XHpNVkD_tmS+SseMsf6YaVPg@mail.gmail.com>
<F1D041D0-FC5A-425C-835D-37E7A9C0CFC5@friedenbach.org>
<CAMZUoKmhN=m4TFwJi7u1bibLJ6mYvpnkddWTZZWdHn7+mVcJvw@mail.gmail.com>
<EB804508-715A-4CD6-9B87-09845368DAC0@friedenbach.org>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Thu, 7 Sep 2017 14:55:25 -0400
Message-ID: <CAMZUoKk7dHy6urnGRzAB2UG_fkwXmQrRHDfFYOHa0sTStr=yAQ@mail.gmail.com>
To: Mark Friedenbach <mark@friedenbach.org>
Content-Type: multipart/alternative; boundary="001a114a6ebe09b74405589e02c5"
X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
HTML_MESSAGE,RCVD_IN_DNSWL_NONE autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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 Sep 2017 18:55:48 -0000
--001a114a6ebe09b74405589e02c5
Content-Type: text/plain; charset="UTF-8"
On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark@friedenbach.org>
wrote:
> I've been puzzling over your email since receiving it. I'm not sure it
> is possible to perform the attack you describe with the tree structure
> specified in the BIP. If I may rephrase your attack, I believe you are
> seeking a solution to the following:
>
> Want: An innocuous script and a malign script for which
>
> double-SHA256(innocuous)
>
> is equal to either
>
> fast-SHA256(double-SHA256(malign) || r) or
> fast-SHA256(r || double-SHA256(malign))
>
or fast-SHA256(fast-SHA256(double-SHA256(malign) || r1) || r0)
or fast-SHA256(fast-SHA256(r1 || double-SHA256(malign)) || r0)
or ...
> where r is a freely chosen 32-byte nonce. This would allow the
> attacker to reveal the innocuous script before funds are sent to the
> MAST, then use the malign script to spend.
>
> Because of the double-SHA256 construction I do not see how this can be
> accomplished without a full break of SHA256.
>
The particular scenario I'm imagining is a collision between
double-SHA256(innocuous)
and
fast-SHA256(fast-SHA256(fast-SHA256(double-SHA256(malign) || r2) || r1)
|| r0).
where innocuous is a Bitcoin Script that is between 32 and 55 bytes long.
Observe that when data is less than 55 bytes then double-SHA256(data) =
fast-SHA256(fast-SHA256(padding-SHA256(data)) || 0x8000...100) (which is
really the crux of the matter).
Therefore, to get our collision it suffices to find a collision between
padding-SHA256(innocuous)
and
fast-SHA256(double-SHA256(malign) || r2) || r1
r1 can freely be set to the second half of padding-SHA256(innocuous), so it
suffices to find a collision between
fast-SHA256(double-SHA256(malign) || r2)
and the first half of padding-SHA256(innocuous) which is equal to the first
32 bytes of innocuous.
Imagine the first opcode of innocuous is the push of a value that the
attacker claims to be his 33-byte public key.
So long as the attacker doesn't need to prove that they know the discrete
log of this pubkey, they can grind r2 until the result of
fast-SHA256(double-SHA256(malign) || r2) contains the correct first couple
of bytes for the script header and the opcode for a 33-byte push. I
believe that is only about 3 or 4 bytes of they need to grind out.
--001a114a6ebe09b74405589e02c5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <span dir=3D"ltr"><=
<a href=3D"mailto:mark@friedenbach.org" target=3D"_blank">mark@friedenbach.=
org</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"mar=
gin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1=
ex"><div style=3D"overflow-wrap: break-word;"><div>I've been puzzling o=
ver your email since receiving it. I'm not sure it</div><div>is possibl=
e to perform the attack you describe with the tree structure</div><div>spec=
ified in the BIP. If I may rephrase your attack, I believe you are</div><di=
v>seeking a solution to the following:</div><div><br></div><div>Want: An in=
nocuous script and a malign script for which</div><div><br></div><div>=C2=
=A0 =C2=A0double-SHA256(innocuous)</div><div><br></div><div>is equal to eit=
her</div><div><br></div><div>=C2=A0 =C2=A0fast-SHA256(double-SHA256(<wbr>ma=
lign) || r) or</div><div>=C2=A0 =C2=A0fast-SHA256(r || double-SHA256(malign=
))</div></div></blockquote><div><br></div><div>or=C2=A0 fast-SHA256(fast-SH=
A256(double-SHA256(<wbr>malign) || r1) || r0)</div><div>or=C2=A0 fast-SHA25=
6(fast-SHA256(r1 || double-SHA256(<wbr>malign)) || r0)</div><div>or ...<br>=
</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0p=
x 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><d=
iv style=3D"overflow-wrap: break-word;"><div>where r is a freely chosen 32-=
byte nonce. This would allow the</div><div>attacker to reveal the innocuous=
script before funds are sent to the</div><div>MAST, then use the malign sc=
ript to spend.</div><div><br></div><div>Because of the double-SHA256 constr=
uction I do not see how this can be</div><div>accomplished without a full b=
reak of SHA256. <br></div></div></blockquote><div><br></div><div>The partic=
ular scenario I'm imagining is a collision between</div><div><br></div>=
<div>=C2=A0=C2=A0=C2=A0 double-SHA256(innocuous)</div><div><br></div><div>a=
nd <br></div><div><br></div><div>=C2=A0=C2=A0=C2=A0 fast-SHA256(fast-SHA256=
(fast-SHA256(double-SHA256(<wbr>malign) || r2) || r1) || r0).</div><div><br=
></div><div>where innocuous is a Bitcoin Script that is between 32 and 55 b=
ytes long.<br></div><div><br></div><div>Observe that when data is less than=
55 bytes then double-SHA256(data) =3D fast-SHA256(fast-SHA256(padding-SHA2=
56(data)) || 0x8000...100) (which is really the crux of the matter).<br></d=
iv><div><br></div><div>Therefore, to get our collision it suffices to find =
a collision between</div><div><br></div><div>=C2=A0=C2=A0=C2=A0 padding-SHA=
256(innocuous)</div><div><br></div><div>and</div><div><br></div><div>=C2=A0=
=C2=A0=C2=A0 fast-SHA256(double-SHA256(<wbr>malign) || r2) || r1</div><div>=
<br></div><div>r1 can freely be set to the second half of padding-SHA256(in=
nocuous), so it suffices to find a collision between</div><div><br></div><d=
iv>=C2=A0=C2=A0 fast-SHA256(double-SHA256(<wbr>malign) || r2)</div><div><br=
></div><div>and the first half of padding-SHA256(innocuous) which is equal =
to the first 32 bytes of innocuous.</div><div><br></div><div>Imagine the fi=
rst opcode of innocuous is the push of a value that the attacker claims to =
be his 33-byte public key.</div><div>So long as the attacker doesn't ne=
ed to prove that they know the discrete log of this pubkey, they can grind =
r2 until the result of fast-SHA256(double-SHA256(<wbr>malign) || r2) contai=
ns the correct first couple of bytes for the script header and the opcode f=
or a 33-byte push.=C2=A0 I believe that is only about 3 or 4 bytes of they =
need to grind out.<br></div><div><br></div></div></div></div>
--001a114a6ebe09b74405589e02c5--
|
