What is wrong with "keccak256(abi.encode(_a ^ _b))" considering merkle tree security?

user_4491610 0
Viewed 28

In this article MERKLE PROOFS FOR OFFLINE DATA INTEGRITY there is a paragraph:

Warning: Cryptography is harder than it looks. The initial version of this article had the hash function hash(a^b). That was a bad idea because it meant that if you knew the legitimate values of a and b you could use b' = a^b^a' to prove any desired a' value. With this function you'd have to calculate b' such that hash(a') ^ hash(b') is equal to a known value (the next branch on the way to root), which is a lot harder.

I can see that this code seems to be insecure:

function pairHash(uint _a, uint _b) internal pure returns(uint) {
  return uint(keccak256(abi.encode(_a ^ _b)));
}

Could somebody explain why and provide an example(real code appreciated)? Or maybe just a URL to corresponding article (the closest one I've found is this one)

Thanks in advance

blockchain solidity ethereum cryptography security
1 Answers

Let's say we have two values a and b and we create the pair as hash(a^b). The issue is that we can create the same pair by passing two different values a' and b' such that b' = a^b^a' for every a'.

The proof is easily done knowing that the xor operation is commutative and x^x = 0:

hash(a'^b') = hash(a'^(a^b^a')) = hash(a'^a'^a^b) = hash(a^b)

The most basic example is a tree with a and b as only leaves, so with root equal hash(a^b). Let's say the leaves are tokens amounts for an airdrop. We are supposed to claim the tokens by passing a as value and [b] as merkle proof for example. However someone can pass any value a' with proof [a^b^a'], as this still verifies the merkle root.

(PS: the issue from the codearena audit is a different one)

user_190627790
Related