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.