Sapling: don't rely on knowledge soundness of Output proofs to prevent diversified-address-linking oracle attacks

[ebfull]

We decided here that the Output circuit would check that the corresponding epk was computed from a known esk w.r.t. the g_d used in the note. The intention of this is to prevent a diversified address linking attack in an interactive setting. This check is enforced under the knowledge soundness assumption of the zk-SNARK scheme (and discrete log of Jubjub, which is not interesting for this attack).

It would be better to send esk to the recipient (in the ciphertext) so that we don't depend on knowledge soundness. This is a pretty simple change that we should consider for Blossom.

There is some concern that including esk in the ciphertext would break the security proof because of some kind of key-dependent encryption thing, but I (personally) would much rather break the security proof and argue heuristically that this is correct than depend on knowledge soundness.

[zookozcash]

Re key-dependent encryption, yeah, I don't believe that a real encryption scheme like ChaCha20 is going to actually endanger any users if it is used to encrypt a secure hash of its own symmetric encryption key.

[zookozcash]

As I understand it, the potential impact of this involuntary linkage between diversified addresses (i.e. the attacker can find out that two of your diversified addresses are both attached to the same spending key, which you might not have wanted them to know), but only under active attack (the attacker has to send specially crafted payments to your diversified address(es) and detect something about your response, like whether you spend the money or whether you say "Thank you"), and only if the attacker can forge ZKPs!

So this is not a problem assuming that attackers can't forge ZKPs. However, if we fixed this, then we could go back to saying "Your privacy doesn't depend on the soundness of the ZKPs!", which would be nice to be able to summarize without this footnote that says "… Unless you're using diversified addresses and the attacker performs an active attack while also breaking ZKP soundness in order to link your diversified addresses".

A potential mitigation for this is to post a "WE DO NOT RECOMMEND THAT YOU USE DIVERSIFIED ADDRESSES", and then we can say "Your privacy (assuming you follow our recommendations) does not depend on the soundness of the ZKP!".

Note that I have other concerns about diversified addresses, namely that they may confused simple users about the difference between two separate normal addresses versus two diversified addresses, and they may confuse enterprise (i.e. big exchanges) about the consequences of disclosing view keys (that is, if you disclose a view key for one of your diversified addresses, that is effectively a view key for all of your diversified addresses. There aren't per-diversified-address view keys, although there are per-normal-address view keys).

So I'm kind of in favor of "WARN EVERYONE NOT TO USE DIVERSIFIED ADDRESSES FOR ANYTHING" as at least a temporary mitigation for this issue.

[daira]

I agree that we should improve this in Blossom the next circuit change, but I don't agree that we should or need to warn against all use of diversified addresses in the meantime; there are plenty of cases where they're safe to use. In the exchange use case, for example, you get a diversified address that is unique to you, and that normally would not be further distributed. There's really no significant attack from diversified address linking in that situation (and linking of diversified addresses is the only privacy exposure here; there's no exposure of note contents or of the transaction graph).

[ebfull]

@daira I'm not so sure. There are a lot of people that are too lazy to set up their own wallet and are happy to use the exchange as a wallet instead.

We haven't deployed this feature to users yet. I think that we probably shouldn't until we're confident in its security properties and assumptions, and I'm personally not comfortable with unlinkability between addresses depending on SNARK knowledge soundness.

[daira]

This could be fixed without a network upgrade. Define a new note plaintext version (2) that includes an Ed25519 signature with the esk/epk key pair, over some value that is unique to the output. This would take 64 bytes from the memo field, reducing it to 448 bytes. The switch to the new note plaintext version would occur at a given block height to avoid a client version distinguisher (and to allow recipients time to upgrade), but it wouldn't be a consensus change. The reason to use a signature instead of sending esk in the new note plaintext is that it prevents any problem with old clients leaking esk. The signature is a proof (not depending on knowledge soundness of the Output proofs) that the sender knew esk, tied to this output for freshness.

You can add a flag in the new note plaintext format to indicate whether the memo is used, for light client support, at the same time (also decoupling that change from Blossom).

It needs to be proven that making a signature with esk/epk is jointly secure with the encryption, but I think that's already been proven in section 4.4 of https://eprint.iacr.org/2011/615.pdf . (Squint and you can see that it doesn't matter whether the signature is using the ephemeral key pair or the recipient key pair; the same proof applies. The BLAKE2b-256 hash in KDF^Sapling and the SHA-512 hash in Ed25519 can safely be treated as independent. It is also obvious that adding the signature doesn't interfere with key privacy, for two reasons: the signature is securely encrypted with ChaCha20-Poly1305, and the signature is not dependent on the recipient public key, only on the ephemeral key which is already public.)

[daira]

The above signature option has some disadvantages over a potential change in Blossom to include esk in the note plaintext:

• It reduces the memo field capacity by 64 bytes.
• It is 32 bytes less bandwidth-efficient than the Blossom option, per Output description, taking into account the reduction in memo field capacity.
  • The actual bandwidth does not increase; in fact, an Output description is 32 bytes smaller in this option than in the Blossom option.
• There's another Ed25519 signature per output.
  • This only needs to be generated by senders and verified by recipients, so it doesn't increase cost of tx validation.
• If recipients haven't upgraded by the specified block height, they could potentially misinterpret received memo fields.
  • If we want old clients to reject the payment instead, that's possible. There's no permanent loss of funds in that case, because an upgraded client that rescans from that height will see the payment.

On the other hand:

• It can be deployed sooner.
• It also allows the light client memo flag to be deployed sooner.
• Doing this separately reduces the complexity and risk of Blossom.

[daira]

I'm not sure why "Blossom wishlist" was removed, since my recollection was that we didn't make a decision on whether to include this or not.