[bitcoin-dev] Simple change to the "merkleblock" command to protect from SPV proof extension attacks

[bitcoin-dev] Simple change to the "merkleblock" command to protect from SPV proof extension attacks

[Sergio Demian Lerner]

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

Hi,
 While fixing RSK's SPV bridge I came up with an idea to fix the
MERKLEBLOCK command to prevent rogue peers from attacking SPV peers using
Bitcoin's Merkle tree structure flaws. The most annoying attack is the one
that tries to confuse a victim peer into thinking a transaction is an inner
node, extending such node with a new right-sided branch with a fake
transaction (*) .

The old idea to soft-fork Bitcoin to make invalid 64-byte transactions is
attractive, but also a coordination problem that could be avoided with this
new proposal.

The idea is simple, and it's not a fork, but a network protocol improvement.
Let A be the hash digest that must be combined with the hash digest B, such
that the upper node hash is SHA256(SHA256(A | B)).
Therefore A = SHA256(SHA256(X)) and B = SHA256(SHA256(Y)), and X and Y are
either Bitcoin transactions or other inner nodes.
Instead of storing A, the merkleblock structure should store a pre-image of
A, or SHA256(X).
If the block only has the coinbase, nothing is done.
The pre-image change could be done to both left and right hashes, but it's
enough to do it to all left-side hashes that do not have children in the
partial merkle tree structure (let's call them terminal hahes. to avoid
confusion with leaf hashes).

Verifiers (SPV nodes) would apply a single SHA256() operation to the
left-sided terminal hashes before combining them. The cost to the verifier
is in the worse case only 33% more.

This basically limits the attacker's ability to supply chosen-hash digests
in order to build a transaction. Because the left side contains most of the
previn hash, the attacker would need to bruteforce a huge space (about 208
bits) in order to come up with a pre-image that maps to a owned previn.
Meet-in-the-middle attacks would be expensive as UTXOs are not free.

To implement this change, a new command MERKLEBLOCK2 could be implemented
or the protocol version could be used to differentiate between the two
modes of the MERKLEBLOCK command.

If the idea gets community support, I may write the BIP/code or invite
anyone to do it.

regards

 (*)
https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/

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

[bitcoin-dev] Fwd: Simple change to the "merkleblock" command to protect from SPV proof extension attacks

[Sergio Demian Lerner]

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

Hi,
 While fixing RSK's SPV bridge I came up with an idea to fix the
MERKLEBLOCK command to prevent rogue peers from attacking SPV peers using
Bitcoin's Merkle tree structure flaws. The most annoying attack is the one
that tries to confuse a victim peer into thinking a transaction is an inner
node, extending such node with a new right-sided branch with a fake
transaction (*) .

The old idea to soft-fork Bitcoin to make invalid 64-byte transactions is
attractive, but also a coordination problem that could be avoided with this
new proposal.

The idea is simple, and it's not a fork, but a network protocol improvement.
Let A be the hash digest that must be combined with the hash digest B, such
that the upper node hash is SHA256(SHA256(A | B)).
Therefore A = SHA256(SHA256(X)) and B = SHA256(SHA256(Y)), and X and Y are
either Bitcoin transactions or other inner nodes.
Instead of storing A, the merkleblock structure should store a pre-image of
A, or SHA256(X).
If the block only has the coinbase, nothing is done.
The pre-image change could be done to both left and right hashes, but it's
enough to do it to all left-side hashes that do not have children in the
partial merkle tree structure (let's call them terminal hahes. to avoid
confusion with leaf hashes).

Verifiers (SPV nodes) would apply a single SHA256() operation to the
left-sided terminal hashes before combining them. The cost to the verifier
is in the worse case only 33% more.

This basically limits the attacker's ability to supply chosen-hash digests
in order to build a transaction. Because the left side contains most of the
previn hash, the attacker would need to bruteforce a huge space (about 208
bits) in order to come up with a pre-image that maps to a owned previn.
Meet-in-the-middle attacks would be expensive as UTXOs are not free.

To implement this change, a new command MERKLEBLOCK2 could be implemented
or the protocol version could be used to differentiate between the two
modes of the MERKLEBLOCK command.

If the idea gets community support, I may write the BIP/code or invite
anyone to do it.

regards

 (*)
https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/

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