On the security of Sprout/Sapling in-band encryption

I am investigating on the security properties of the in-band encryption scheme (IND-CCA2 and IK-CCA) of ZCash and I was looking for a formal security argument for the key-privacy. Reading the Specs and this thread (https://github.com/zcash/zcash/issues/558), I got that key-privacy derives from the fact that the in-band scheme is ECIES-based and on the security properties of curve used. Is there any formal proof or properties I am missing? Thanks.

1 Like

The proof of key privacy for ElGamal in Appendix A of https://cseweb.ucsd.edu/~mihir/papers/anonenc.html is straightforwardly adaptable to half-static Diffie-Hellman in general, and the scheme used by Zcash in particular. This is folklore; I haven’t seen the proof completely written out anywhere.

2 Likes

Thanks Daira, for the answer.

I have continued to study the encryption scheme, and another questions popped in my mind: I have noticed that the set of input parameters of the KDF are different in Sprout/Sapling.
Reading the DHAES paper (https://eprint.iacr.org/1999/007), only the ephemeral public key epk and the shared secret ss are used as input, instead in Sprout also pk_enc and hsig are taken into account. I have read on the Spec that hsig allows to construct a randomness extractor from a weak-PRF (by using a result in sec 7 of https://eprint.iacr.org/2011/708.pdf). Instead, I have not found the rationale for adding pk_enc. In Sapling, pk_enc and h_sig are not used anymore (h_sig is not available since Joinsplit is separated in Spend/Output transfers). Since the min-entropy of the key exchange in Curve25519 and Jubjub, should be roughly the same, is there a particular reason that justify that change? Thanks

Ps: maybe I should have opened a different thread :smiley:

1 Like

The reason for not including pk_enc in the KDF input for Sapling is to support diversified addresses. That is, pk_enc varies between diversified addresses for the same ivk, and so the KDF must not depend on it, in order for an ivk to be usable for decrypting ciphertexts to any corresponding diversified address.

The rationale for adding pk_enc to the KDF in Sprout was, if I remember correctly, that we believed it might be necessary for IND-CCA2 security and/or for post-quantum privacy (in the case where the quantum attacker does not have the public key). Actually it is not needed for either of those; for IND-CCA2 this follows from the DHAES security proof, and for post-quantum privacy see https://github.com/zcash/zcash/issues/570#issuecomment-296450324 . The latter was the more important issue since I think I already knew that pk_enc wasn’t required for IND-CCA2 when designing Sprout, and was just being cautious/conservative about that. (Including epk as an input, as in DHAES, is necessary for IND-CCA2 security, and Sapling still does that.)

The weak-PRF thing was just a nice-to-have that weakened assumptions on the hash; it was not necessary for security, since the stronger assumptions are entirely plausible for BLAKE2b-256.

4 Likes

Thanks Daira for all clarifications. I assume so that for the same reasons the counter variable has been removed from the KDF inputs.
By the way, here (Sec 6.1) there is a proof for IK-CCA of DHIES if you want to have a look :smiley:.

2 Likes

The latter was the more important issue since I think I already knew that pk_enc wasn’t required for IND-CCA2 when designing Sprout, and was just being cautious/conservative about that. (Including epk as an input, as in DHAES, is necessary for IND-CCA2 security, and Sapling still does that.)

In the updated paper called DHIES (section 3, https://web.cs.ucdavis.edu/~rogaway/papers/dhies.pdf) , they state that if the order of the group is prime then epk can be dropped as parameter of the KDF. If I am not wrong this is the case of Jubjub, so it could be removed, right?

Jubjub is not a prime-order group. It is a twisted Edwards curve, and has a prime-order subgroup with a small cofactor.

2 Likes

Sorry I was not so precise there: I meant the actual subgroup that is used has prime order.

My point was if we follow the protocol in the generation of g^u and g^v I don’t see how we could have the malleability issue that ephemeral public key as parameter of the Hash solves.

Since the secure group is prime, g^u and g^{uv} uniquely determine v and I cannot find a different v' s.t. the following are two ciphertexts of the same message m:

g^{v}||Sym_{H(g^{uv})}(m)

g^{v'}||Sym_{H(g^{uv})}(m)

as stated in DHIES paper (Sec 3, last paragraph).

Is there something I am missing here? Is epk used here as a further protection against those users that messes up with the system and use elements of the super group?

The fact that the subgroup is prime order is irrelevant; the group itself, in which points are represented and computed on, is not prime order. Sec 3, last paragraph is explicit about this:

THE GROUP G IS OF PRIME ORDER. We henceforth assume that |G| is prime. This is extremely important to ensure the security of DHIES or otherwise the scheme could be malleable. […] To prevent such attacks in groups not of prime order (e.g., Z*p), one should feed gu to H.

and again in the “Related Work” section on page 2:

DHIES is now embodied in three (draft) standards [2, 23, 31]. All of these assume an elliptic curve groupof prime order. To harmonize this paper with those standards, and to simplify complexity assumptions, we shall assume the the underlying group in which we work has prime order. When working with a group whose order is not prime a minor change can be made to the protocol so that it will still be correct. Namely, the value gu should be fed into the hash function H.

epk in our scheme is gu in DHIES.

1 Like

My bad, a counterexample follows:

Given (Z_{10}, +) and (2) a generator of the prime order subgroup of order 5. Then,

for u=2, v=4

2*4*(2) = 4*2*(2) = 4*(9)
where (9) is not in <(2)>.

Thanks for the insights!