Description

In circuits/src/keccak/multivar.rs, the function KeccakMultiVarHasher::absorb_var checks that the length of the input fits in MAX_BIT_SIZE bits but nothing stricter:

assert!(input.len() < 1 << MAX_BIT_SIZE, "input too long");

So a length of (1 << MAX_BIT_SIZE) - 1 is in principle possible.

Then, in add_slice_at_offset, there is the following snippet:

// Require `len <= padded input length`
let padded_input_len = source.len();
let padded_input_len_plus_one =
    ctx.load_constant(F::from(padded_input_len as u64 + 1));
range.range_check(ctx, len, MAX_BIT_SIZE);
range.check_less_than(ctx, len, padded_input_len_plus_one, MAX_BIT_SIZE);

Here, source is one of the input vectors from absorb_var, so padded_input_len can in principle have value (1 << MAX_BIT_SIZE) - 1, and hence padded_input_len_plus_one can have value 1 << MAX_BIT_SIZE. This is a value that does not fit in MAX_BIT_SIZE bits, which is an assumption required for the soundness of check_less_than, however.

Impact

The range check

range.check_less_than(ctx, len, padded_input_len_plus_one, MAX_BIT_SIZE);

is unsound in the case of inputs of the very specific padded length for a variable length input of (1 << MAX_BIT_SIZE) - 1. Note that a typical attacker cannot control this padded length, which is determined at verification-key--generation time. It seems very unlikely that the circuit will be instantiated with a variable length input of this length on accident, in particular due to MAX_BIT_SIZE being 32, so that this would amount to a quite large variable-length input.

Assuming a variable-length input with padded length (1 << MAX_BIT_SIZE) - 1, we cannot assume that the above range check constrains len to be smaller than padded_input_len_plus_one = 1 << MAX_BIT_SIZE. This is as the assumption that padded_input_len_plus_one fits in MAX_BIT_SIZE bits fails. However, as len is potentially able to be chosen by the attacker, that it fits in MAX_BIT_SIZE bits is checked with an explicit range check in the line right before:

range.range_check(ctx, len, MAX_BIT_SIZE);

This ensures that len < (1 << MAX_BIT_SIZE). Thus, the intended inequality len < padded_input_len_plus_one still holds.

Recommendations

Due to the reasoning outlined in the impact section, the code is not vulnerable as is, due to the separate range check on len. However, for best practice, we recommend to use a slightly stricter check on the padded input length in the function KeccakMultiVarHasher::absorb_var:

-assert!(input.len() < 1 << MAX_BIT_SIZE, "input too long");
+assert!(input.len() < (1 << MAX_BIT_SIZE) - 1, "input too long");

This will ensure that padded_input_len_plus_one is at most MAX_BIT_SIZE bits wide.

Remediation

This issue has been acknowledged by Nebra, and a fix was implemented in commit 3d3567ad↗.