Re: [bitcoin-dev] Fast Merkle Trees

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 832 bytes --]

The fast hash for internal nodes needs to use an IV that is not the
standard SHA-256 IV. Instead needs to use some other fixed value, which
should itself be the SHA-256 hash of some fixed string (e.g. the string
"BIP ???" or "Fash SHA-256").

As it stands, I believe someone can claim a leaf node as an internal node
by creating a proof that provides a phony right-hand branch claiming to
have hash 0x80000..0000100 (which is really the padding value for the
second half of a double SHA-256 hash).

(I was schooled by Peter Todd by a similar issue in the past.)

On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Fast Merkle Trees
> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
>

[-- Attachment #2: Type: text/html, Size: 1497 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Mark Friedenbach]

[-- Attachment #1: Type: text/plain, Size: 1169 bytes --]

This design purposefully does not distinguish leaf nodes from internal nodes. That way it chained invocations can be used to validate paths longer than 32 branches. Do you see a vulnerability due to this lack of distinction?

> On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream.io> wrote:
> 
> The fast hash for internal nodes needs to use an IV that is not the standard SHA-256 IV. Instead needs to use some other fixed value, which should itself be the SHA-256 hash of some fixed string (e.g. the string "BIP ???" or "Fash SHA-256").
> 
> As it stands, I believe someone can claim a leaf node as an internal node by creating a proof that provides a phony right-hand branch claiming to have hash 0x80000..0000100 (which is really the padding value for the second half of a double SHA-256 hash).
> 
> (I was schooled by Peter Todd by a similar issue in the past.)
> 
>> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> Fast Merkle Trees
>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree

[-- Attachment #2: Type: text/html, Size: 2032 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 720 bytes --]

On Wed, Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev wrote:
> The fast hash for internal nodes needs to use an IV that is not the
> standard SHA-256 IV. Instead needs to use some other fixed value, which
> should itself be the SHA-256 hash of some fixed string (e.g. the string
> "BIP ???" or "Fash SHA-256").

Note that in general, designs should *not* create new hash functions by using
custom IVs, but rather use bog-standard SHA256, and make a fixed first block.
That allows unoptimised implementations to just hash a block with the second
initialization value, and optimized implementations to start with the fixed
midstate.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 455 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 3928 bytes --]

In that case, you may as well remove all references to leaves and double
SHA-256 from your BIP since your design has no method for distinguishing
between internal nodes and leaves.

I think that if this design stands, it will play a role in some future
CVEs.  The BIP itself is too abstract about its data contents to
specifically say that it has a vulnerability; however, I believe it is
inviting vulnerabilities.
For example, I might agree with a counterparty to a design of some sort of
smart contract in the form of a MAST.  My counterparty has shown me all the
"leaves" of our MAST and I can verify its Merkle root computation.
After being deployed, I found out that one of the leaves wasn't really a
leaf but is instead a specially crafted "script" with a fake pubkey chosen
by my couterparty so that this leaf can also be interpreted as a fake
internal node (i.e. an internal node with a right branch of 0x8000...100).
Because the Fast Merkle Tree design doesn't distinguish between leaves and
internal nodes my counter party gets away with building an Inclusion Proof
through this "leaf" to reveal the evil code that they had designed into the
MAST at a deeper level.

Turns out my counterparty was grinding their evil code to produce an
internal node that can also be parsed as an innocent script.  They used
their "pubkey" to absorb excess random data from their grinding that they
cannot eliminate.
(The counterparty doesn't actually know the discrete log of this "pubkey",
they just claimed it was their pubkey and I believed them).


Having ambiguity about whether a node is a leaf or an internal node is a
security risk. Furthermore, changing the design so that internal node and
leaves are distinguishable still allows chained invocations.
Arbitrary data can be stored in Fast Merkle Tree leaves, including the
Merkle root of another Fast Merkle Tree.
Applications that are limited to proof with paths no longer than 32
branches can still circumvent this limit by staging these Fast Merkle Trees
in explicit layers (as opposed to the implicit layers with the current
design).

By storing a inner Fast Merkle Tree root inside the (explicit) leaf of an
outer Fast Merkle Tree, the application can verify a Inclusion Proof of the
inner Fast Merkle Tree Root in the outer Fast Merkle Tree Root, and then
verify a second Inclusion Proof of the desired data in the inner Faster
Merkle Tree Root.  The application will need to tag their data to
distinguish between inner Fast Merkle Tree Roots and other application
data, but that is just part of the general expectation that applications
not store ambiguous data inside the leaves of Fast Merkle Trees.


On Wed, Sep 6, 2017 at 10:20 PM, Mark Friedenbach <mark@friedenbach.org>
wrote:

> This design purposefully does not distinguish leaf nodes from internal
> nodes. That way it chained invocations can be used to validate paths longer
> than 32 branches. Do you see a vulnerability due to this lack of
> distinction?
>
> On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream.io>
> wrote:
>
> The fast hash for internal nodes needs to use an IV that is not the
> standard SHA-256 IV. Instead needs to use some other fixed value, which
> should itself be the SHA-256 hash of some fixed string (e.g. the string
> "BIP ???" or "Fash SHA-256").
>
> As it stands, I believe someone can claim a leaf node as an internal node
> by creating a proof that provides a phony right-hand branch claiming to
> have hash 0x80000..0000100 (which is really the padding value for the
> second half of a double SHA-256 hash).
>
> (I was schooled by Peter Todd by a similar issue in the past.)
>
> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Fast Merkle Trees
>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
>>
>

[-- Attachment #2: Type: text/html, Size: 5320 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor]

[-- Attachment #1: Type: text/plain, Size: 1138 bytes --]

On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd <pete@petertodd.org> wrote:

> On Wed, Sep 06, 2017 at 09:59:54PM -0400, Russell O'Connor via bitcoin-dev
> wrote:
> > The fast hash for internal nodes needs to use an IV that is not the
> > standard SHA-256 IV. Instead needs to use some other fixed value, which
> > should itself be the SHA-256 hash of some fixed string (e.g. the string
> > "BIP ???" or "Fash SHA-256").
>
> Note that in general, designs should *not* create new hash functions by
> using
> custom IVs, but rather use bog-standard SHA256, and make a fixed first
> block.
> That allows unoptimised implementations to just hash a block with the
> second
> initialization value, and optimized implementations to start with the fixed
> midstate.


I 100% agree.

With SHA256 every final state is also a valid midstate.  Therefore, using a
custom IV of the SHA256 hash of some fixed string results in a hash of data
that is functionally equivalent to prefixing the data with the padded
version of the fixed string and using a regular SHA256 hash of the combined
data.  This is important and I should have explicitly pointed it out.

[-- Attachment #2: Type: text/html, Size: 1564 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Mark Friedenbach]

[-- Attachment #1: Type: text/plain, Size: 6087 bytes --]

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

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 trick of setting r
equal to the padding only works when a single SHA256 is used for leaf
values. This is why double-SHA256 is specified in the BIP, and I will
edit the text to make that more clear.

Which brings us to the point that I think your original request of
separating the hash function of leaves from internal nodes is already
in the specification. I misunderstood your request at first to be that
MERKLEBRANCHVERIFY should itself perform this hash, which I objected
to as it closes of certain use cases such as chained verification of
proofs. But it is explicitly the case that leaf values and internal
updates are calculated with different hash functions.

I'm not intrinsicly opposed to using a different IV for fast-SHA256 so
as to remove the incompatability with single-SHA256 as the leaf hash
function, if that is the consensus of the community. It just adds
complication to implementations and so I want to make sure that
complication is well justified.

Sincerely,
Mark Friedenbach

> On Sep 7, 2017, at 8:43 AM, Russell O'Connor <roconnor@blockstream.io> wrote:
> 
> In that case, you may as well remove all references to leaves and double SHA-256 from your BIP since your design has no method for distinguishing between internal nodes and leaves.
> 
> I think that if this design stands, it will play a role in some future CVEs.  The BIP itself is too abstract about its data contents to specifically say that it has a vulnerability; however, I believe it is inviting vulnerabilities.
> For example, I might agree with a counterparty to a design of some sort of smart contract in the form of a MAST.  My counterparty has shown me all the "leaves" of our MAST and I can verify its Merkle root computation.
> After being deployed, I found out that one of the leaves wasn't really a leaf but is instead a specially crafted "script" with a fake pubkey chosen by my couterparty so that this leaf can also be interpreted as a fake internal node (i.e. an internal node with a right branch of 0x8000...100).
> Because the Fast Merkle Tree design doesn't distinguish between leaves and internal nodes my counter party gets away with building an Inclusion Proof through this "leaf" to reveal the evil code that they had designed into the MAST at a deeper level.
> 
> Turns out my counterparty was grinding their evil code to produce an internal node that can also be parsed as an innocent script.  They used their "pubkey" to absorb excess random data from their grinding that they cannot eliminate.
> (The counterparty doesn't actually know the discrete log of this "pubkey", they just claimed it was their pubkey and I believed them).
> 
> 
> Having ambiguity about whether a node is a leaf or an internal node is a security risk. Furthermore, changing the design so that internal node and leaves are distinguishable still allows chained invocations.
> Arbitrary data can be stored in Fast Merkle Tree leaves, including the Merkle root of another Fast Merkle Tree.
> Applications that are limited to proof with paths no longer than 32 branches can still circumvent this limit by staging these Fast Merkle Trees in explicit layers (as opposed to the implicit layers with the current design).
> 
> By storing a inner Fast Merkle Tree root inside the (explicit) leaf of an outer Fast Merkle Tree, the application can verify a Inclusion Proof of the inner Fast Merkle Tree Root in the outer Fast Merkle Tree Root, and then verify a second Inclusion Proof of the desired data in the inner Faster Merkle Tree Root.  The application will need to tag their data to distinguish between inner Fast Merkle Tree Roots and other application data, but that is just part of the general expectation that applications not store ambiguous data inside the leaves of Fast Merkle Trees.
> 
> 
> On Wed, Sep 6, 2017 at 10:20 PM, Mark Friedenbach <mark@friedenbach.org <mailto:mark@friedenbach.org>> wrote:
> This design purposefully does not distinguish leaf nodes from internal nodes. That way it chained invocations can be used to validate paths longer than 32 branches. Do you see a vulnerability due to this lack of distinction?
> 
> On Sep 6, 2017, at 6:59 PM, Russell O'Connor <roconnor@blockstream.io <mailto:roconnor@blockstream.io>> wrote:
> 
>> The fast hash for internal nodes needs to use an IV that is not the standard SHA-256 IV. Instead needs to use some other fixed value, which should itself be the SHA-256 hash of some fixed string (e.g. the string "BIP ???" or "Fash SHA-256").
>> 
>> As it stands, I believe someone can claim a leaf node as an internal node by creating a proof that provides a phony right-hand branch claiming to have hash 0x80000..0000100 (which is really the padding value for the second half of a double SHA-256 hash).
>> 
>> (I was schooled by Peter Todd by a similar issue in the past.)
>> 
>> On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
>> Fast Merkle Trees
>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a <https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a>
>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree <https://github.com/maaku/bitcoin/tree/fast-merkle-tree>
> 


[-- Attachment #2: Type: text/html, Size: 9042 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor]

[-- 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 --]

Re: [bitcoin-dev] Fast Merkle Trees

[Mark Friedenbach]

[-- Attachment #1: Type: text/plain, Size: 5551 bytes --]

TL;DR I'll be updating the fast Merkle-tree spec to use a different
      IV, using (for infrastructure compatability reasons) the scheme
      provided by Peter Todd.

This is a specific instance of a general problem where you cannot
trust scripts given to you by another party. Notice that we run into
the same sort of problem when doing key aggregation, in which you must
require the other party to prove knowledge of the discrete log before
using their public key, or else key cancellation can occur.

With script it is a little bit more complicated as you might want
zero-knowledge proofs of hash pre-images for HTLCs as well as proofs
of DL knowledge (signatures), but the basic idea is the same. Multi-
party wallet level protocols for jointly constructing scriptPubKeys
should require a 'delinearization' step that proves knowledge of
information necessary to complete each part of the script, as part of
proving the safety of a construct.

I think my hangup before in understanding the attack you describe was
in actualizing it into a practical attack that actually escalates the
attacker's capabilities. If the attacker can get you to agree to a
MAST policy that is nothing more than a CHECKSIG over a key they
presumably control, then they don't need to do any complicated
grinding. The attacker in that scenario would just actually specify a
key they control and take the funds that way.

Where this presumably leads to an actual exploit is when you specify a
script that a curious counter-party actually takes the time to
investigate and believes to be secure. For example, a script that
requires a signature or pre-image revelation from that counter-party.
That would require grinding not a few bytes, but at minimum 20-33
bytes for either a HASH160 image or the counter-party's key.

If I understand the revised attack description correctly, then there
is a small window in which the attacker can create a script less than
55 bytes in length, where nearly all of the first 32 bytes are
selected by the attacker, yet nevertheless the script seems safe to
the counter-party. The smallest such script I was able to construct
was the following:

    <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL

This is 56 bytes and requires only 7 bits of grinding in the fake
pubkey. But 56 bytes is too large. Switching to secp256k1 serialized
32-byte pubkeys (in a script version upgrade, for example) would
reduce this to the necessary 55 bytes with 0 bits of grinding. A
smaller variant is possible:

    DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160 <preimage> EQUAL

This is 46 bytes, but requires grinding 96 bits, which is a bit less
plausible.

Belts and suspenders are not so terrible together, however, and I
think there is enough of a justification here to look into modifying
the scheme to use a different IV for hash tree updates. This would
prevent even the above implausible attacks.


> On Sep 7, 2017, at 11:55 AM, Russell O'Connor <roconnor@blockstream.io> wrote:
> 
> 
> 
> On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark@friedenbach.org <mailto: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: 9261 bytes --]

Re: [bitcoin-dev] Fast Merkle Trees

[Johnson Lau]

> On 8 Sep 2017, at 4:04 AM, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
> If I understand the revised attack description correctly, then there
> is a small window in which the attacker can create a script less than
> 55 bytes in length, where nearly all of the first 32 bytes are
> selected by the attacker, yet nevertheless the script seems safe to
> the counter-party. The smallest such script I was able to construct
> was the following:
> 
>     <fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL
> 
> This is 56 bytes and requires only 7 bits of grinding in the fake
> pubkey. But 56 bytes is too large. Switching to secp256k1 serialized
> 32-byte pubkeys (in a script version upgrade, for example) would
> reduce this to the necessary 55 bytes with 0 bits of grinding. A
> smaller variant is possible:
> 
>     DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160 <preimage> EQUAL
> 
> This is 46 bytes, but requires grinding 96 bits, which is a bit less
> plausible.
> 
> Belts and suspenders are not so terrible together, however, and I
> think there is enough of a justification here to look into modifying
> the scheme to use a different IV for hash tree updates. This would
> prevent even the above implausible attacks.
> 

I think you overestimated the difficulty. Consider this MAST branch (an example in BIP114)

"Timestamp" CHECKLOCKTIMEVERIFY <fake-pubkey> CHECKSIGVERIFY

This requires just a few bytes of collision.