A vulnerability in olalonde's implementation of gmaxwell's proof-of-solvency - page 2.

charlescharles

newbie

Activity: 11

Merit: 0

Hey Andy,

I'm not sure that fixes this issue, though. Let's call the properties of each node 'value' and 'hash' ('value' instead of 'sum'). Let's look at an 'end' node, node P, with two leaves, one customer A with 10 BTC and another one customer B with 5 BTC. Let's say you're the company and you want to pretend your liabilities are less than they actually are. Then you construct this node like

Code:

Node P
value = 10
hash = sha256(10 | hashA | hashB)

/                           \
customer A           customer B
value = 10            value = 5
hash = hashA        hash = hashB

In this case, when A wants proof of inclusion, you give node P to A, and tell A that her paired customer's value is 0. This checks out, so A believes you because P.value = 10 = 10 + 0. When B wants proof of inclusion, you still give the exact same node P to B, and tell B that his paired customer's value is 5, and this checks out for him because P.value = 10 = 5 + 5. There's no way for B to verify that the value hashed into hashA is actually 10, not 5.

You repeat this procedure for all the nodes on A's branch up to the root. Note that you never alter hashes, and the Merkle property holds; all you do is falsify the stub values you tell people for the other branch. Also note that this doesn't require any special pairing; this is a defect in the node-combining function itself.

Thanks for the info, by the way! I'll do that in the future.

andytoshi

full member

Activity: 179

Merit: 157

-

Hi charlescharles,

Good catch. This actually addressed in iwilcox's writeup --- grep for "similar customer pairing trick". In fact this is safe, since the sum for each node is part of its hash. This means that if you tried to zero out one of the children, that child's hash would change. So even though the unsummed child amounts are not explicitly hashed, the are committed to as part of the child nodes' hashes. I hope that make sense.

By the way, in future, if you think you've found a security/crypto bug, it's best to bug people in private (in this case olalonde or gmaxwell would be appropriate -- or go on IRC #bitcoin-wizards and ask to PM somebody). Especially if there is a possibility of loss of funds (if the wrong people know about something before it's fixed) responsible disclosure is critical.

Thanks for auditing code!

Andrew

charlescharles

newbie

Activity: 11

Merit: 0

I might be looking at an old version, but it seems like the combiner function for internal nodes (described here: https://github.com/olalonde/proof-of-liabilities#internal-node), which is the following:

Code:

function NodeCombiner (left_child, right_child) {
  var n = {};
  n.sum = left_child.sum + right_child.sum;
  n.hash = sha256(string(n.sum) + '|' + left_child.hash + '|' + right_child.hash);
  return n;
}

is vulnerable to an attack in which the prover replaces the expression for n.sum with

Code:

n.sum = max(left_child.sum, right_child.sum)

This is undetectable by anyone asking for a proof of inclusion in the liabilities Merkle tree. A fix for this would be to replace the expression for n.hash with something like

Code:

n.hash = sha256(string(left_child.sum) + '|' + string(right_child.sum) + '|' + left_child.hash + '|' + right_child.hash)

Has this been brought up/addressed? Let me know if this is unclear.

Topic: A vulnerability in olalonde's implementation of gmaxwell's proof-of-solvency - page 2. (Read 2166 times)