Re: [bitcoin-dev] Fast Merkle Trees

[Johnson Lau via bitcoin-dev]

> On 8 Sep 2017, at 4:04 AM, Mark Friedenbach via bitcoin-dev 
>  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:
> 
>  CHECKSIGVERIFY HASH160  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  EQUALVERIFY CHECKSIGVERIFY HASH160 
>  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  CHECKSIGVERIFY

This requires just a few bytes of collision.




___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Fast Merkle Trees

[Mark Friedenbach via bitcoin-dev]

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:

 CHECKSIGVERIFY HASH160  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  EQUALVERIFY CHECKSIGVERIFY HASH160 
 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  wrote:
> 
> 
> 
> 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 

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor via bitcoin-dev]

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.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor via bitcoin-dev]

On Thu, Sep 7, 2017 at 1:55 AM, Peter Todd  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.
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor via bitcoin-dev]

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 
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 
> 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 0x8..100 (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
>>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Fast Merkle Trees

[Peter Todd via bitcoin-dev]

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


signature.asc
Description: Digital signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Fast Merkle Trees

[Mark Friedenbach via bitcoin-dev]

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  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 0x8..100 (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 
>>  wrote:
>> Fast Merkle Trees
>> BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
>> Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Fast Merkle Trees

[Russell O'Connor via bitcoin-dev]

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 0x8..100 (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
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev