[NCC-E005955-DBV] zebra-chain: Unbounded Rejection Sampling with Possibility of Panics

[mpguerra]

Impact

The zebra-chain module implements random number generation for some types which are primarily used for testing, without guarding against possible panics.

Description

The use of fill_bytes() in the code snippet below (from zebra-chain/src/sapling/keys.rs) can potentially cause panics. It is recommended to use try_fill_bytes() to catch the random number generator’s failures¹.

In addition, the number of sampling retries by the loop has to be bounded.

zebra/zebra-chain/src/sapling/keys.rs

Lines 176 to 196 in 5a88fe7

	impl Diversifier {
	/// Generate a new _Diversifier_ that has already been confirmed
	/// as a preimage to a valid diversified base point when used to
	/// derive a diversified payment address.
	///
	/// <https://zips.z.cash/protocol/protocol.pdf#saplingkeycomponents>
	/// <https://zips.z.cash/protocol/protocol.pdf#concretediversifyhash>
	pub fn new<T>(csprng: &mut T) -> Self
	where
	T: RngCore + CryptoRng,
	{
	loop {
	let mut bytes = [0u8; 11];
	csprng.fill_bytes(&mut bytes);
	if diversify_hash(bytes).is_some() {
	break Self(bytes);
	}
	}
	}
	}

There is one instance where this can potentially be problematic for a full node with mining support. Generating a random Rho for an Orchard note uses the same unchecked RNG API.

A node with mining capabilities might use this API to generate a dummy Orchard input note as a nullifier for the output note when creating a miner’s reward note:

zebra/zebra-chain/src/orchard/note.rs

Lines 59 to 69 in 161bb80

	impl Rho {
	pub fn new<T>(csprng: &mut T) -> Self
	where
	T: RngCore + CryptoRng,
	{
	let mut bytes = [0u8; 32];
	csprng.fill_bytes(&mut bytes);
	Self(extract_p(pallas::Point::from_bytes(&bytes).unwrap()))
	}
	}

---

1. For instance OsRng can, in rare occasions, fail on some platforms, and thread_rng might return a
   warning if it fails to reseed itself. See https://rust-random.github.io/book/guide-err.html for more
   details.

Recommendation

Consider replacing the fill_bytes() usage with try_fill_bytes() and properly handle its possible failure.

Location

• zebra-chain/src/orchard/keys.rs, line 110
• zebra-chain/src/sapling/keys.rs, line 189
• zebra-chain/src/orchard/commitment.rs, line 30
• zebra-chain/src/sapling/commitment.rs, line 42
• zebra-chain/src/orchard/note.rs, line 30
• zebra-chain/src/orchard/note.rs, line 65

[mpguerra]

Hey team! Please add your planning poker estimate with Zenhub @arya2 @conradoplg @dconnolly @oxarbitrage @teor2345 @upbqdn

[teor2345]

This doesn't block starting work on Orchard shielded coinbase mining, but it does block running on mainnet.

[daira]

The documentation of when fill_bytes can panic (which is documented to be exactly when try_fill_bytes can return an error) does not convince me that zebra shouldn't actually panic in this situation:

This method should guarantee that dest is entirely filled with new data, and may panic if this is impossible (e.g. reading past the end of a file that is being used as the source of randomness).

We shouldn't read a file to get randomness, or anything similarly unreliable, for a cryptographic RNG. Note that this method is defined on RngCore, and the design of the rand crate makes CryptoRng just a marker trait, so it can't change the API. But it's likely that the design of RngCore was intended to allow a wide variety of possible sources of randomness that are not necessarily cryptographic, and that informed the error handling in ways that are less than ideal for a cryptographic RNG.

The Zcash protocols assume that it is always possible to get randomness. If an RNG returns an error, then either:

• The RNG is always going to fail for the rest of this process execution. In that case the process can't reasonably continue, since it's going to need randomness very frequently and there aren't many useful things it can do without it. Since zebra is designed to tolerate crashes, the best thing to do is to crash immediately.
• The failure is intermittent. In that case, how do we know that it isn't correlated with the output that the RNG would have returned? If it is, then that potentially biases future output. So again zebra should crash, in order to minimize the damage and make sure that the user knows something is seriously wrong.
• The failure could be a symptom of something else, like memory corruption / undefined behaviour. Again zebra should crash to minimize possible damage.

[dconnolly]

The documentation of when fill_bytes can panic (which is documented to be exactly when try_fill_bytes can return an error) does not convince me that zebra shouldn't actually panic in this situation:

This method should guarantee that dest is entirely filled with new data, and may panic if this is impossible (e.g. reading past the end of a file that is being used as the source of randomness).

We shouldn't read a file to get randomness, or anything similarly unreliable, for a cryptographic RNG. Note that this method is defined on RngCore, and the design of the rand crate makes CryptoRng just a marker trait, so it can't change the API. But it's likely that the design of RngCore was intended to allow a wide variety of possible sources of randomness that are not necessarily cryptographic, and that informed the error handling in ways that are less than ideal for a cryptographic RNG.

The Zcash protocols assume that it is always possible to get randomness. If an RNG returns an error, then either:

• The RNG is always going to fail for the rest of this process execution. In that case the process can't reasonably continue, since it's going to need randomness very frequently and there aren't many useful things it can do without it. Since zebra is designed to tolerate crashes, the best thing to do is to crash immediately.
• The failure is intermittent. In that case, how do we know that it isn't correlated with the output that the RNG would have returned? If it is, then that potentially biases future output. So again zebra should crash, in order to minimize the damage and make sure that the user knows something is seriously wrong.
• The failure could be a symptom of something else, like memory corruption / undefined behaviour. Again zebra should crash to minimize possible damage.

All of these sources of randomness are happening in a library, which in general terms should not panic, but raise an error. The consumer of the library should determine their behavior on catching such an error, such as panic, for example if they are a wallet. We don't have a wallet yet. If zebrad is generating Rho's for Orchard notes for mining, or generating note commitments, we should catch the error at the application level and panic, but I don't think we are doing that yet: we are generating block templates that miners use. For shielded coinbase (Sapling and Orchard), we (zebrad / zebra-consensus, the consumer of zebra-chain) will catch any of these errors and then panic.

[mpguerra]

Can we document this in the code for future use cases?

[daira]

All of these sources of randomness are happening in a library, which in general terms should not panic, but raise an error. The consumer of the library should determine their behavior on catching such an error, such as panic, for example if they are a wallet. We don't have a wallet yet. If zebrad is generating Rho's for Orchard notes for mining, or generating note commitments, we should catch the error at the application level and panic, but I don't think we are doing that yet: we are generating block templates that miners use. For shielded coinbase (Sapling and Orchard), we (zebrad / zebra-consensus, the consumer of zebra-chain) will catch any of these errors and then panic.

I disagree, and I've told you my considered professional opinion as a cryptographic engineer. The auditors are wrong, and a panic is the appropriate behaviour. It does not matter whether the panic happens at the library or application layer, except that the latter has slightly greater risk of the panic not actually happening, or of there being negative consequences of undefined behaviour if the failure is due to that.

(If zebra didn't follow crash-only design, it might be appropriate to do a controlled shutdown that flushes data to disk for example. But it does, so that argument doesn't apply.)

[teor2345]

(If zebra didn't follow crash-only design, it might be appropriate to do a controlled shutdown that flushes data to disk for example. But it does, so that argument doesn't apply.)

At this point a controlled shutdown isn't required in Zebra, because we commit each verified block to disk in a database transaction. So either the transaction commits and the database is valid with the new block, or it is rolled back on restart and it's valid with the old block. Losing a block doesn't matter, because we drop the last 100 blocks in memory every time we restart anyway.

This would be different if we had a wallet, or any other kind of non-transactional persistent data. In that case, we'd probably want to do an atomic switch to the new version of the file (or directory):
https://users.rust-lang.org/t/how-to-write-replace-files-atomically/42821
https://docs.rs/atomicwrites/latest/atomicwrites/struct.AtomicFile.html#method.new

[teor2345]

(This is just for info, it's not related to the specific decision about cryptographic panics.)