[protocol spec] Document multi-user security of AEAD_CHACHA20_POLY1305's MAC

[daira]

Poly1305 has a 128-bit authenticator, but the advantage in breaking its integrity without breaking AES is, roughly speaking, $q \cdot \ell_m \cdot 2^{-103}$ for $q$ queries where $\ell_m$ is the number of 16-byte input blocks. Document why this is not an issue despite Zcash having a $2^{125}$ target security level.

[daira]

[DGGP2024] analyses the multi-user security of this MAC. Note that we are using the IETF version of AEAD_CHACHA20_POLY1305 with a 96-bit AEAD nonce, not a 128-bit AEAD nonce as in [Bernstein2005]. As stated at the end of [DGGP2024, section 3] we have:

• $n = 512$ (block size in bits)
• $k = 256$ (key size in bits)
• $t = 128$ (width of the Poly1305 hash function $\bar{H}$ in bits)
• $\mu = 96$ (nonce size in bits)
• $\epsilon(\ell) = 2^{25} \cdot (\ell + 1)$ (security function of the almost $\Delta$-universal hash function $H$)
• $|Z| = 128$ (bit length of the constant $Z$ used in ChaCha20).

Then Corollary 6.1 says:

Zcash uses it with $1+11+8+32+512$ byte note plaintexts ($\ell^{\mathbf{np}}_m = 36$) and $32+32$ byte output plaintexts ($\ell^{\mathbf{op}}_m = 4$), i.e. we have a bound $\ell_m \leq 36$. It always uses the same zero nonce, relying on non-repetition of the 256-bit AES key for security.

We will assume there are a maximum of $2^{34}$ ciphertexts, because that is the maximum possible number of encryptions for Sapling and Orchard together (two encryptions per note for the note and output ciphertexts; two shielded protocols each with at most $2^{32}$ notes). So $d \leq 2^{34}$, $q_e \leq 2^{34}$, and the number of encrypted blocks $\sigma_e$ is bounded by $(\ell^{\mathbf{np}}_m + \ell^{\mathbf{op}}_m) \cdot 2^{33}$, i.e. $\sigma_e \leq 40 \cdot 2^{33}$.

Checking the assumptions, we always have $2 \leq t$, $3 \leq n - k \leq 2^{k-2}$, $\sigma_e \leq 2^{\frac{n-k}{2} - 1}$, $d \leq 2^{t-1}$, and in practice also $q_v \leq 2^{n-2} = 2^{510}$ and $p \leq \min(2^{t-1}, 2^{\frac{n-k}{2} - 1}) = 2^{127}$.

Plugging in the above values we get
$$\mathsf{Adv}^{\mathrm{muAE}}_{\mathrm{ChaCha20-Poly1305[\pi]}}(\mathcal{A}) \leq \frac{q_v \cdot (2^{25} \cdot 37 + 3)}{2^{128}} + \frac{2^{34} \cdot (p + 2^{34})}{2^{512}} + \frac{4p + 12q_v}{2^{513}} + \frac{(40 \cdot 2^{33} + 2^{34})^2}{2^{513}} + \frac{1}{2^{254}} + \frac{1}{2^{254}}$$

$$\mathsf{Adv}^{\mathrm{muAE}}_{\mathrm{ChaCha20-Poly1305[\pi]}}(\mathcal{A}) \leq q_v \cdot 2^{-97.79} + 2^{-478} + p \cdot (2^{-434} + 2^{-509}) + q_v \cdot 2^{-509.4} + 2^{-436.2} + 2^{-253}$$

i.e. roughly

$$\mathsf{Adv}^{\mathrm{muAE}}_{\mathrm{ChaCha20-Poly1305[\pi]}}(\mathcal{A}) \leq q_v \cdot 2^{-97.79}$$

Does this mean we only have 97.79-bit security? No, because the $q_v$ verification queries are online, i.e. each one attempts to forge an output that potential recipients will try to decrypt. In the best case for the adversary, when it has side channels for all potential recipients, it cannot tell whether this has been successful until the potential recipients actually try to decrypt it. This could be either in an on-chain transaction or in a transaction in the mempool, but either way it is not a feasible attack for reasonable assumptions about the number of potential recipients.