Cosmos-sdk: Potential attack vector with Merkle Commitments in ICS-23

[AdityaSripal]

zaki brought up a concern that a naive opening of merkle commitments could allow users to prove arbitrary data was committed on some blockchain to any other blockchain it is connected to by IBC.

Consider a chain A connected to chain B.
Suppose the state machine on Chain A allows users to submit arbitrary data into the application state tree
Suppose user wants to prove a nested leaf fakeLeaf exists in the state tree. User can construct a merkle tree locally with the desired leaf.

1. User submits root fakeRoot of locally created merkle tree as a leaf into the application state tree of ChainA.
2. User queries chainA for proof of fakeRoot being a leaf in the state tree
3. User then appends the locally generated proof of fakeLeaf to the chain-generated proof.
4. User then submits this falsified proof to chainB as an ICS-23 CommitmentPath.
5. User can prove that ChainA committed to fakeLeaf in a nested store that didn't actually exist in the application state

It's unclear to me how vulnerable the Multistore in the SDK is to this type of attack. The Multistore generates a simple merkle proof of the stores it contains. This simple merkle proof then gets appended by the single store proof (typically IAVL proof) to prove the existence of a particular key-value in state machine.
There is no way to insert a key-value pair directly into the Multistore as the Multistore only holds a list of storenames, and generates merkle proofs for them on the fly.
Similarly, I don't believe it is possible to interpret a leaf in an IAVLStore as the root for a substore. However, more investigation is necessary to confirm this.

Potential Solutions:

1. Any leaf of a merkle tree that is really a root of a nested substore should be byte-prefixed with 0x2 for example. All other leaves get prefixed with 0x1. This makes it impossible to mistake a regular leaf for the root of a nested subtree

Ref links:
https://github.com/cosmos/cosmos-sdk/blob/master/store/rootmulti/proof.go#L22
https://github.com/cosmos/cosmos-sdk/blob/master/store/rootmulti/proof.go#L104
https://github.com/cosmos/cosmos-sdk/blob/master/store/rootmulti/store.go#L543
https://github.com/cosmos/cosmos-sdk/blob/master/store/rootmulti/store.go#L444

cc: @zmanian @cwgoes @alexanderbez @fedekunze

[cwgoes]

I agree with the general concern, but I don't think this is specific to IBC (or hard to fix).

Suppose the state machine on Chain A allows users to submit arbitrary data into the application state tree

This just shouldn't be allowed - this is discussed in ICS 23 - the IBC keeper needs exclusive access to a particular subspace of the KV store. It's my understanding that in the current SDK model it has exclusive access, thanks to the StoreKey capability passed to the IBC keeper in app.go. Is that correct?

It's true that if the SDK allowed other modules to write to the IBC store, proofs could be falsified in this fashion - but that's a problem in general (for proving anything), not a problem specific to IBC.

It's also critical that the ICS 23 proofs be sound in the sense defined in ICS 23 - a proof for one commitment path must not be accepted for another. We should ensure that our ICS 23 implementation fulfils this requirement.

User can prove that ChainA committed to fakeLeaf in a nested store that didn't actually exist in the application state

Even if this were possible, it doesn't affect IBC - IBC only cares about what can be proved to exist (or not exist) in the subspace specific to the IBC implementation (e.g. the ibc substore).

Any leaf of a merkle tree that is really a root of a nested substore should be byte-prefixed with 0x2 for example. All other leaves get prefixed with 0x1. This makes it impossible to mistake a regular leaf for the root of a nested subtree

Sure, I think this is a good idea (are we not already doing it? We should be ensuring that this isn't possible independent of IBC). Ethan Frey's ICS 23 implementation should be able to support this kind of thing in the ProofSpec.

[zmanian]

@jaekwon was the person who originally proposed the attack.

The main thing to be aware of in this model is the ability of an attack to build an offchain IBC substore.

Ie. This store isn't in the state machine. It's completely off chain and there is simply a merkle commitment to the store in the main chain.

I think this attack can be mitigated if merkle trees in the store prefix leaves with a different byte if the leaf is expected to contain data or the root of another merkle tree.

[cwgoes]

I think this attack can be mitigated if merkle trees in the store prefix leaves with a different byte if the leaf is expected to contain data or the root of another merkle tree.

We should do that regardless, but Merkle proofs should already be positionally binding, so a proof of fakesubtree/packets/abc would not be accepted for ibc/packets/abc (right?).

[zmanian]

yes if the connection is already established but you can create a new connections to fakesubtree/packets/abc

[cwgoes]

yes if the connection is already established but you can create a new connections to fakesubtree/packets/abc

No, because fakesubtree/packets/abc is never used by the IBC handler logic, the IBC handler logic exclusively uses (and verifies proofs of) state under the ibc/ subtree.

[zmanian]

How can your differentiate fakesubtree/packets/abc and ibc/packets/abc until you are informed of the schema for the trees during the connection handshake?

[cwgoes]

How can your differentiate fakesubtree/packets/abc and ibc/packets/abc until you are informed of the schema for the trees during the connection handshake?

That's configurable - the schema for the trees can be part of the client configuration, in which case it's determined before the handshake starts, or part of the schema (e.g. the prefix fakesubtree or ibc) can be conveyed in the connection handshake, in which case modules could deny a handshake from the prefix fakesubtree (accepting only ibc) or users could never use a connection with that prefix. It does have to be clearly conveyed in the UX, but otherwise it doesn't seem different from correctly identifying the chain that you are interacting with in the first place (i.e. not sending coins to "cosmhub" by mistake).

[cwgoes]

cc @AdityaSripal @zmanian & I concluded that we should do "defense-in-depth" here - both prefixing the Merkle subtrees with some unique byte and ensuring that IBC handles this safely.

[cwgoes]

I'll deal with this. Thanks for raising the concern.

[cwgoes]

Ref https://github.com/cosmos/ics/issues/282#issuecomment-589690471
Ref https://github.com/confio/ics23/pull/28

We do need to be careful here, particularly on the RootMultiStore side.

[fedekunze]

Does #6178 fix this issue?

[cwgoes]

Does #6178 fix this issue?

When the ICS 23 proof specification is correctly implemented, it should, but we do need to check the multstore implementation of that specifically, we might need to add a prefix to each subtree.

[cwgoes]

Closed by the integration of ICS 23 with https://github.com/cosmos/cosmos-sdk/pull/6374, though this is an area to have a bug bounty specifically mention.