From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 0B006BE6 for ; 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 ; Thu, 7 Sep 2017 18:55:46 +0000 (UTC) Received: by mail-qk0-f180.google.com with SMTP id b82so1423456qkc.4 for ; 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: References: From: "Russell O'Connor" Date: Thu, 7 Sep 2017 14:55:25 -0400 Message-ID: To: Mark Friedenbach 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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


On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <= mark@friedenbach.= org> wrote:
I've been puzzling o= ver your email since receiving it. I'm not sure it
is possibl= e to perform the attack you describe with the tree structure
spec= ified in the BIP. If I may rephrase your attack, I believe you are
seeking a solution to the following:

Want: An in= nocuous script and a malign script for which

=C2= =A0 =C2=A0double-SHA256(innocuous)

is equal to eit= her

=C2=A0 =C2=A0fast-SHA256(double-SHA256(ma= lign) || r) or
=C2=A0 =C2=A0fast-SHA256(r || double-SHA256(malign= ))

or=C2=A0 fast-SHA256(fast-SH= A256(double-SHA256(malign) || r1) || r0)
or=C2=A0 fast-SHA25= 6(fast-SHA256(r1 || double-SHA256(malign)) || r0)
or ...
=
=C2=A0
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 sc= ript to spend.

Because of the double-SHA256 constr= uction I do not see how this can be
accomplished without a full b= reak of SHA256.

The partic= ular scenario I'm imagining is a collision between

=
=C2=A0=C2=A0=C2=A0 double-SHA256(innocuous)

a= nd

=C2=A0=C2=A0=C2=A0 fast-SHA256(fast-SHA256= (fast-SHA256(double-SHA256(malign) || r2) || r1) || r0).
where innocuous is a Bitcoin Script that is between 32 and 55 b= ytes long.

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).

Therefore, to get our collision it suffices to find = a collision between

=C2=A0=C2=A0=C2=A0 padding-SHA= 256(innocuous)

and

=C2=A0= =C2=A0=C2=A0 fast-SHA256(double-SHA256(malign) || r2) || r1
=
r1 can freely be set to the second half of padding-SHA256(in= nocuous), so it suffices to find a collision between

=C2=A0=C2=A0 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 fi= rst 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 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(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.

--001a114a6ebe09b74405589e02c5--