Sapling spec (5.6.4) requires that pk_d is validated as prime-order, is this enforced?

[daira]

The following issue came up in discussions of the Sapling security proof with @arielgabizon. In section 5.6.4 of the protocol spec, we have:

The raw encoding of a Sapling shielded payment address consists of: [diagram omitted]

• $11$ bytes specifying $\mathsf{d}$.
• $32$ bytes specifying the ctEdwards compressed encoding of $\mathsf{pk_d}$ (see §5.4.9.3 ‘ $\mathsf{Jubjub}$ ’ on p. 100).

When decoding the representation of $\mathsf{pk_d}$, the address MUST be considered valid if $\mathsf{abst}_{\mathbb{J}}$ returns $\bot$ or if the resulting $\mathsf{pk_d}$ is not of prime order.

[Edit: Later the last paragraph was changed to:

When decoding the representation of $\mathsf{pk_d}$, the address MUST be considered valid if $\mathsf{abst}_{\mathbb{J}}$ returns $\bot$.

[ZIP-216] specifies that the address MUST also be considered invalid if the resulting $\mathsf{pk_d}$ is not in the prime-order subgroup $\mathbb{J}^{(r)}$ , or if it is a non-canonical encoding as defined in § 4.1.9 ‘Represented Group’ on p. 30. This MAY be
enforced in advance of activation of NU5.

]

Looking at the C++ implementation of SaplingPaymentAddress in zcash/Address.cpp and zcash/Address.hpp, it isn't clear that either point validity or the prime-order restriction are enforced when the address is decoded, as required.

In sapling-crypto, the $\mathsf{pk_d}$ fields are declared with type edwards::Point<E, PrimeOrder> in Note and in PaymentAddress.

However, despite the name, edwards::Point<E, PrimeOrder> means only that the point is in the prime-order subgroup, which does not mean the same thing as "prime order" (the latter excludes the zero point $\mathcal{O}_{\mathbb{J}}$). The stricter specification in the spec was intended.

In addition, sapling-crypto:

• does not enforce by type that $\mathsf{g_d}$ is not $\mathcal{O}_{\mathbb{J}}$ (although the implementations of both circuits do enforce this: Spend, Output);
• does not enforce that the output of ViewingKey::ivk() is nonzero, so it is possible for the $\mathsf{pk_d}$ computed by ViewingKey::into_payment_address to be $\mathcal{O}_{\mathbb{J}}$ even if $\mathsf{g_d}$ is not.

So, I think the requirement of the spec to reject invalid addresses when they are decoded is not satisfied.

There doesn't appear to be any significant security issue here, because an adversary can't do anything by publishing an invalid address that they couldn't do by publishing an address and revealing its $\mathsf{ivk}$. (If they construct a $\mathsf{pk'_d}$ by adding a torsion component to an honest party's $\mathsf{pk_d}$, then they won't know the corresponding $\mathsf{ivk}$, so I don't believe there are any attacks based on this. However, it should be noted that the Output circuit explicitly does not check the order of $\mathsf{pk_d}$ for the new note, or that it is on the curve. The Spend circuit does, so notes with an invalid $\mathsf{pk_d}$ cannot be spent.)

[daira]

Oh, this is amusing. The implementation was changed to match the spec (in https://github.com/zcash/librustzcash/pull/109/files#diff-92d6b429f317a74bd65b2ad87d4f841e9fa9e334edab4199cdaba91172cd2d10R147), but the spec was also changed to match the previous implementation (in zcash/zips@1d71f6c and zcash/zips@18d30f3), under the mistaken assumption that the implementation was incorrect at that point. I will change the spec back (zcash/zips#664).