MIME-Version: 1.0
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"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
Precedence: list

--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">&lt;=
<a href=3D"mailto:mark@friedenbach.org" target=3D"_blank">mark@friedenbach.=
org</a>&gt;</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&#39;ve been puzzling o=
ver your email since receiving it. I&#39;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&#39;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&#39;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--