Ensure Spec mitigates Double Spending by Colliding InternalH · Issue #738 · zcas...

I think I found an attack that would let an attacker create as much money as they want for themselves at the cost of finding 128-bit hash collisions.

Background: A coin is a tuple (apk, v, ρ, r). The coin commitment CoinCommitment((apk, v, ρ, r)) is computed as:

InternalH = Leading128(CRH(apk || ρ))
k = CRH(r || InternalH)
cm = CRH(v || k)

The truncation of InternalH is done to make the commitment statistically-hiding, i.e no matter how much computational resources I have, I can't find out what v or apk are.

Attack: Because InternalH is only 128 bits, in 2^64 operations I can find some ρ != ρ' such that:

Leading128(CRH(apk || ρ)) = Leading128(CRH(apk || ρ'))

And therefore:

CoinCommitment((apk, v, ρ, r)) = CoinCommitment((apk, v, ρ', r))

To carry out a double-spend attack I first acquire some real Zcash (e.g. by buying it with USD), and then double spend it to myself as follows. Ignoring the faerie gold fix, I create a new coin for myself, but as I do so I make sure to find a collision (apk, v, ρ, r) and (apk, v, ρ', r) where ρ != ρ'. By completeness of the protocol, I'll be able to spend the (apk, v, ρ, r) coin, and so that's what I do. This will reveal the serial number PRFsnask(ρ). After that first spend has made it on to the ledger, as far as I can see, nothing prevents me from spending that coin again, using ρ', because:

• I can still give a path from the root to CoinCommitment((apk, v, ρ', r)), namely the same path as I gave in the first spend (and because of the zero-knowledge property nobody will know the path is the same).
• With high probability PRFsnask(ρ') is not equal to PRFsnask(ρ), and I can obviously still prove I computed PRFsnask(ρ') correctly inside the pour.
• I can still satisfy spend authority (I know ask for the apk I used).
• I have to use the same r (old) for both spends (otherwise the commitments won't collide), but again because of the zero-knowledge property I don't think anyone (except for me, the holder of ask) can tell it's been reused.

After the faerie gold fix, I'm forced to find colliding ρ by altering hsig, and I'm forced to commit to either ρ or ρ' because hsig gets published. This doesn't prevent the attack, since when I go to spend for the second time it is not going to be noticed that ρ' doesn't match the old hsig, at least not according to the current protocol.

Fix: Maybe CoinCommitment needs to be collision-resistant? Or maybe we should re-use hsig as a commitment to ρ and check it when I try to spend with ρ?