From: "Russell O'Connor" <roconnor@blockstream•io>
To: Mark Friedenbach <mark@friedenbach•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Fast Merkle Trees
Date: Thu, 7 Sep 2017 14:55:25 -0400 [thread overview]
Message-ID: <CAMZUoKk7dHy6urnGRzAB2UG_fkwXmQrRHDfFYOHa0sTStr=yAQ@mail.gmail.com> (raw)
In-Reply-To: <EB804508-715A-4CD6-9B87-09845368DAC0@friedenbach.org>
[-- Attachment #1: Type: text/plain, Size: 2308 bytes --]
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.
[-- Attachment #2: Type: text/html, Size: 3539 bytes --]
next prev parent reply other threads:[~2017-09-07 18:55 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-09-07 1:59 Russell O'Connor
2017-09-07 2:20 ` Mark Friedenbach
2017-09-07 15:43 ` Russell O'Connor
2017-09-07 17:42 ` Mark Friedenbach
2017-09-07 18:55 ` Russell O'Connor [this message]
2017-09-07 20:04 ` Mark Friedenbach
2017-09-12 11:44 ` Johnson Lau
2017-09-07 5:55 ` Peter Todd
2017-09-07 15:51 ` Russell O'Connor
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAMZUoKk7dHy6urnGRzAB2UG_fkwXmQrRHDfFYOHa0sTStr=yAQ@mail.gmail.com' \
--to=roconnor@blockstream$(echo .)io \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=mark@friedenbach$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox