(Not exploitable) flaw in the proof of Balance when PRF^addr is not collision-resistant

[daira]

The abstract Zerocash protocol requires PRF^addr only to be a PRF; it is not specified to be collision-resistant. This reveals a flaw in the proof of the Balance property. The flaw is not exploitable for the actual instantiation of PRF^addr in either Zerocash, or Zcash Protocol 2016.0/1 (to be Zcash 1.0), which is collision-resistant assuming that SHA256Compress is.

Suppose that an adversary finds a collision on PRF^addr such that a_sk¹ and a_sk² are distinct spending keys for the same a_pk. Because the note commitment is to a_pk, but the nullifier is computed from a_sk (and ρ), the adversary is able to double-spend the note, once with each a_sk. This is not detected because each spend reveals a different nullifier. The JoinSplit statements are still valid because they can only check that the a_sk in the witness is some preimage of the a_pk used in the note commitment.

The error is in the proof of Balance in section D.3. For the "A violates Condition I" case, the proof says:

(i) If cm^old₁ = cm^old₂, then the fact that sn^old₁ ≠ sn^old₂ implies that the witness a contains two
distinct openings of cm^old₁ (the first opening contains (a^old_sk,1, ρ^old₁), while the second opening contains (a^old_sk,2, ρ^old₂). This violates the binding property of the commitment scheme COMM.

But the openings don't actually contain a^old_sk at all; they contain a^old_pk.

The same argument is also relied on in the "A violates Condition II" case.

The proof is easily repairable — just rely on collision resistance of PRF^addr (on both its arguments) to argue that distinct a^old_sk,1 and a^old_sk,2, together with constraint 1(b) [address matching] of the JoinSplit statement, implies distinct a^old_pk,1 and a^old_pk,2, therefore distinct openings of COMM.

Thanks to @elibensasson for drawing my attention to the fact that it might not be sufficient for the PRFs to just be PRFs. (Finding this was also helped by drawing a dataflow diagram for the protocol; that's only in rough dead-tree form at the moment, but I'll try to post a version of it soon.)

[matthewdgreen]

Now that is a good catch. Please keep a note of this and all other typos/errors you've found in those proofs. I doubt anyone has cycles now, but we'll update them in the next 2-3 weeks.

On Apr 6, 2016, at 6:24 AM, Daira Hopwood notifications@github.com wrote:

The abstract Zerocash protocol requires PRFaddr only to be a PRF; it is not specified to be collision-resistant. This reveals a flaw in the proof of the Balance property. The flaw is not exploitable for the actual instantiation of PRFaddr in either Zerocash or Zcash, which is collision-resistant assuming that SHA256Compress is.

Suppose that an adversary finds a collision on PRFaddr such that a1sk and a2sk are distinct spending keys for the same apk. Because the note commitment is to apk, but the nullifier is computed from ask (and ρ), the adversary is able to double-spend the note, once with each ask. This is not detected because each spend reveals a different nullifier. The JoinSplit statements are still valid because they can only check that the ask in the witness is some preimage of the apk used in the note commitment.

The error is in the proof of Balance in section D.3. For the "A violates Condition I" case, the proof says:

(i) If cmold1 = cmold2, then the fact that snold1 ≠ snold2 implies that the witness a contains two
distinct openings of cmold1 (the first opening contains (aoldsk,1, ρold1), while the second opening contains (aoldsk,2, ρold2). This violates the binding property of the commitment scheme COMM.

But the openings don't actually contain aoldsk at all; they contain aoldpk.

The same argument is also relied on in the "A violates Condition II" case.

The proof is easily repairable — just rely on collision resistance of PRFaddr (on both its arguments) to argue that distinct aoldsk,1COMM aoldsk,2, together with constraint 1(b) [address matching] of the JoinSplit statement, implies distinct aoldpk,1 and aoldpk,2, therefore distinct openings of COMM.

Thanks to @elibensasson for drawing my attention to the fact that it might not be sufficient for the PRFs to just be PRFs. (Finding this was also helped by drawing a dataflow diagram for the protocol; that's only in rough dead-tree form at the moment, but I'll try to post a version of it soon.)

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub

[daira]

@matthewdgreen I added a label for that: Zerocash paper. (Note that some of those issues are closed because they have been addressed in our spec.)

[daira]

For the fix to our spec, see zcash/zips@75b8750

[imichaelmiers]

Fix is just to require it's collision resistant too ?

On Wed, Apr 6, 2016, 9:51 AM Daira Hopwood notifications@github.com wrote:

For the fix to our spec, see zcash/zips@75b8750
zcash/zips@75b8750

—
You are receiving this because you are subscribed to this thread.

Reply to this email directly or view it on GitHub
#836 (comment)

[daira]

@imichaelmiers wrote:

Fix is just to require it's collision resistant too ?

Yes.

[defuse]

Wow, awesome attack!

[daira]

Provably-not-exploitable security bugs are my favourite kind :-p

[nathan-at-least]

@ebfull Why is this on the agenda today?

[nathan-at-least]

The spec is updated and we've blogged about this, sufficient to close.