Russell O'Connor [ARCHIVE] on Nostr: 📅 Original date posted:2017-09-07 📝 Original message:On Thu, Sep 7, 2017 at ...
📅 Original date posted:2017-09-07
📝 Original message:On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170907/724c4de6/attachment.html>;
📝 Original message:On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170907/724c4de6/attachment.html>;