Sources:
The Impact
Double spending, while creating money out of thin air
Someone with enough computing power to find 128-bit hash collisions would have been able to double-spend money to themselves, creating Zcash out of thin air.
For every 128-bit hash collision the attacker finds, they can effectively double their wealth by combining all of their Zcash into one double-spendable note and then double-spending it to themselves. So even though the operations to find a collision aren’t cheap, the attack quickly pays off.
The Mistake
Note/Coin (base object in Zcash) contains (Apk,v,ρ,r)
- Apk – Address public key – Published publicly enabling others to direct payments to the user (similar to inboxes via emails)
- v – the corresponding amount of the note (i.e. value)
- ρ – is a secret value that determines the coin’s serial number
- serial number = a unique string associated with the coin, which is used to prevent double-spending (similar to a UUID)
- Nullifier is likely the new term for “serial number” in Zcash
*- we set ρ to be the nullifier of the spent note*- r – used (within CRH(sn‖r)) to compute the random number of the note commitment (I think)
Security Properties from Commitment Schemes
- Binding and Hiding are two key pieces for the security of a commitment scheme. Binding in this case has failed.
- Dan Boneh does a great job in this course explaining the purpose and function of binding/hiding within this lecture. (highly recommended lecture)
Below is a simple example of the binding and hiding properties through a Bulletproof (kind of range-proof) – Image source
Formal explanation from Dan’s lecture above
128-bit hash collision (similar to MD5)
The time it’ll take depends on the computation the attacker has, but from one reference within the blog post, we can see…
To illustrate the use of parallel collision search for practical cryptanalytic problems, designs were given for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in GF(2^155) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days; the second find MD5 collisions in expected time 21 days;
- Note: It would’ve taken three $10 million computers, running for 21 days to achieve the above exploit on Zcash.
Here’s an intuitive explanation of what “hash collisions” are by Computerphile.
The Fix
Swap out the commitment scheme that has secure binding
Make a trade-off between statistically “perfect” hiding and computationally strong hiding.
In order to keep the Zcash zero-knowledge proofs efficient to compute, we dropped the powerful statistical hiding property and settled for the regular one.
cm=SHA256(0xB0 || apk || v || ρ || r)>- Updated to SHA256, with “0xB0” included
More details
InternalH was chosen to be 128 bits in order to give the commitment scheme a very strong property called statistical hiding. The ordinary hiding property is computational: it says that you can’t learn anything about the input unless you have an absurdly fast computer (i.e. capable of breaking SHA256). Statistical hiding says that even if you have an infinitely fast computer, you still can’t learn anything about the input. This would have allowed Zcash to retain its privacy guarantees even if one day the SHA256 hash function was broken.