ZIP-316 revision 1 effectively blocks 1 transparent receiver about zips HOT 10 CLOSED

In including the note about the size of Feistel pieces being at least 24 bytes, I was just being conservative and giving the simplest reason to dismiss potential attacks based on the piece size. But I don't think there is any actual problem with smaller pieces, and in particular, with pieces that are 19 or 20 bytes; the heuristic analysis still holds.

@ebfull and I went through the heuristic analysis in ZIP 316 — including the thing I was worried about which is whether there is a useful attack based on finding collisions in any of $\mathsf{G}_ {0,1}$ or $\mathsf{H}_ {0,1}$. I'm now confident that there is no such collision-based attack, and so reducing the length restriction to 38 or 40 bytes would be fine. (Any mistake here is mine, not @ebfull's.) It was good to go through this anyway, since a collision-based attack would in theory take less work than Zcash's overall $2^{125}$ security goal. (In practice it probably would not be worth it for an adversary to expend $\sim 2^{96}$ work just to do an address malleation attack, though.)

from zips.

The 38 bytes will be comprised of:

• 1-byte typecode
• 1-byte encoding of length
• 20-byte transparent address hash
• 16-byte padding

The current minimum of 48 bytes allows for a single-receiver UA containing:

• 1-byte typecode
• 1-byte encoding of length
• 30-byte transparent address hash
  • The spec says "allows for the minimum size of a [..] encoding to be 32 bytes", but that glosses over the TLV encoding. In practice, we would have a minimum raw receiver length of 32 bytes, so the practical minimum that anyone would reach for shielded transactions is 50 bytes overall.
• 16-byte padding

Allowing an F4Jumble input shorter than 48 bytes starts to get into cryptographically problematic territory. The current heuristic analysis of security relies in part on the size of each piece being at least 24 bytes, which gives sufficient margin that we don't need to think too closely about it. Permitting shorter than that would require a) a new F4Jumble revision, and b) much more careful security analysis.

For example, the non-fixed (and adversarially-controllable) contribution to the padded half of the input is 8 bytes (64 bits), or a third of its input. If by contrast we allowed a minimum of 32 bytes (so a minimum of 16 bytes of user data), that would mean one half of the Feistel construction is entirely fixed (as it would only contain padding). I don't know if that makes the attack easier (by removing a variable) or harder (by removing adversarial control over that hash). Allowing a minimum of 38 bytes (just enough for a transparent-only single receiver UA) would mean each half of the Feistel construction is 19 bytes, and only 3 bytes (24 bits) in the padded half would be non-fixed; again the security of this against the attacks F4Jumble is designed to prevent would need to be studied.

Another thing we could do is consider altering the padding rule to be:

• At least 16 bytes of zeros;
• At most the length required for the total encoding to be a minimum of 48 bytes.

But I tend to be wary of variable padding rules, as they also have their fair share of cryptographic vulnerabilities.

I think the much simpler solution here is just to accept that indeed it is intentional that you still can't create a UA with a single item that is a transparent receiver; even with rev1 UAs that is a redundant encoding of a regular t-address. The rationale for allowing a rev1 UA to contain no shielded receivers is that you'd be combining a transparent receiver with some metadata, something that a t-address cannot do (and a TEX address can only do with a single axis of metadata).

If we consider a UA containing a transparent receiver and an Address Expiry Time, the raw encoding going into F4Jumble would be:

• 1-byte typecode
• 1-byte encoding of length
• 20-byte transparent address hash
• 1-byte typecode 0xE1
• 1-byte encoding of length
• 8-byte Unix Epoch Time encoding
• 16-byte padding

for a total of 48 bytes, which is perfect. You would be unable to represent a transparent receiver and an Address Expiry Height (as the latter is only 4 bytes not 8, so you'd have 44 bytes total), but you could represent a transparent receiver with both an Address Expiry Height and Address Expiry Time.

from zips.

Thanks for looking at this. I do think we should still update the analysis at some point to be more rigorous if we're decreasing the piece sizes, but if you are satisfied that the heuristic still applies for those specific minimum piece sizes, then that's fine.

So I would tentatively suggest changing the length requirement to $\geq$ 19 bytes (if we want to allow a bare P2PKH Receiver) or $\geq$ 20 bytes (if we want to require metadata).

I think you've mixed up the Feistel construction piece size with the F4Jumble length requirement? I believe you actually mean:

So I would tentatively suggest changing the length requirement to $\geq$ 38 bytes (if we want to allow a bare P2PKH Receiver) or $\geq$ 40 bytes (if we want to require metadata).

I personally would be inclined to require metadata, in line with my reasoning above (to continue to avoid a redundant address encoding, and because I do not believe that anyone is going to use UA-encoded transparent addresses when t-addresses are right there), but from an F4Jumble perspective if we're already happy decreasing the minimum length by 8 bytes (16.6%), then decreasing by 10 bytes (20.8%) instead is not going to make a whole lot of difference. (It's separately a "weird length", but we have other kinds of magic numbers in different parts of the protocol, and I still think decreasing to a minimum of 32 bytes is risky without further analysis.)

from zips.

#797 updates ZIP 316 to change the minimum length, fixing this issue. Review needed.

from zips.

I have been persuaded that it is fine to change the minimum to 38 bytes. The motivation in the previous comment still holds, but the argument made by @nuttycom (with concurrence from @str4d, @arya2, and @conradoplg) is that, on the presumption that there will be pervasive UA support from Consumers at some future time, at that time it would be useful to reduce complexity by removing bare t-addr support from Producers and, eventually, Consumers.

Action item for me: in #797, change the minimum length to 38 (and 19 for each half in the analysis), and make it explicit that Producers SHOULD nevertheless produce bare t-addrs if the UA would be encodable as such.

from zips.

Thanks for that detailed analysis.
Maybe the ZIP should call out this fallout so it isn't overlooked or implementations don't assume a bug and reduce the minimum F4Jumble input length.

from zips.

Yes I will include this in my PR to update ZIP 316 and ZIP 320, whatever we decide. Thanks for catching it.

Note that future Metadata Items could have a 0-byte item encoding (i.e. 2 bytes with typecode and length). That would result in a 40-byte input to $\mathsf{F4Jumble}^{-1}$ for a P2PKH Receiver with such a Metadata Item, or 20-byte Feistel pieces in the F4Jumble construction. In fact we have a proposed Metadata Item with a one-byte item encoding already (Source Restriction Metadata).

In general, a 4-round Feistel construction can't be expected to have better concrete security as an SPRP than that obtained in distinguishing any of its component functions from random functions ([Ramzan and Reyzin 2000]). However in our case we are mainly concerned with an adversary's ability to obtain F4Jumble input/output pairs where both input and output are related to those of an existing UA/UVK, so that they can take advantage of a user potentially mistaking one UA/UVK encoding for another. This does not actually depend on F4Jumble strongly approximating a random permutation (it is not even well defined to say that an unkeyed function does that). In including the note about the size of Feistel pieces being at least 24 bytes, I was just being conservative and giving the simplest reason to dismiss potential attacks based on the piece size. But I don't think there is any actual problem with smaller pieces, and in particular, with pieces that are 19 or 20 bytes; the heuristic analysis still holds.

If UAs with a P2PKH Receiver and any Metadata Item were long enough to satisfy the $\mathsf{F4Jumble}^{-1}$ input length requirement, then I'd agree that there is no reason to change it. However, the fact that a UA with a P2PKH Receiver and (only) Address Expiry Height metadata does not meet the length requirement is an ugly wart, that could lead to bugs in implementations that have not carefully considered error handling for that case. There could also be future Metadata Items with a smaller encoding, as noted above. So I would tentatively suggest changing the length requirement to $\geq$ 38 bytes (if we want to allow a bare P2PKH Receiver) or $\geq$ 40 bytes (if we want to require metadata). [Edit: fixed typo pointed out by @str4d.]

from zips.

I do not believe that anyone is going to use UA-encoded transparent addresses when t-addresses are right there

I don't think they would either, to share those addresses. But for internal machinations, it's useful that almost any viewing key can now be represented by a UVK, including sapling and transparent ones. Now code can just pass around a UVK instead of an enum/struct for various key types. Perhaps the same can be useful if any Zcash address type can be passed around via the unified encoding instead of 'everything is unified except boring old transparent addresses.'

from zips.

@daira Thank you for preparing this change. Was there any particular reason you opted for the 40 minimum instead of 38, considering that 38 would allow a UA rev. 1 address to support any receiver type, thereby allowing a UnifiedAddress type in a library to encode everything, thereby simplifying APIs from having to support a UA or a transparent address?

from zips.

@daira Thank you for preparing this change. Was there any particular reason you opted for the 40 minimum instead of 38, considering that 38 would allow a UA rev. 1 address to support any receiver type, thereby allowing a UnifiedAddress type in a library to encode everything, thereby simplifying APIs from having to support a UA or a transparent address?

The original motivation for not allowing a single bare transparent addr to be encoded as a UA still holds: the Base58 t-addr provides better interoperability. It's only transparent addresses with additional metadata that can't be expressed that way.

from zips.