[Bug] Variable-input-length collision in poseidon sponge

[zklimaleo]

🐛 Bug Report

(Copied from HackerOne) In the current implementation of the poseidon sponge, absorbing some $0{\mathbb{F}_p}$ has no effect (as long as the absorption doesn't lead to a permute(), i.e. the number of $0{\mathbb{F}_p}$ to absorb + next_absorb_index < RATE).

In some ways, $0{\mathbb{F}_p}$ can't be absorbed, and it is easy to forge two different inputs that have the same hash.

Expected Behavior

Should not be possible to forge two different inputs with the same hash leading to a collision.

[vicsn]

Which snarkVM crate is this about?

Note to readers: we analysed and this cannot be exploited - but it would still be nice to add defense in depth.

[zklimaleo]

@vicsn

Should be this: https://github.com/ProvableHQ/snarkVM/blob/staging/algorithms/src/crypto_hash/poseidon.rs#L178

And recommended fix is concatenate the input with $1{\mathbb{F}_p}$, and add some $0{\mathbb{F}_p}$ until reaching a multiple of RATE as the total length according to 4.2 section of poseidon paper:

fn squeeze_native_field_elements(&mut self, num_elements: usize) -> SmallVec<[F; 10]> {
        if num_elements == 0 {
            return SmallVec::<[F; 10]>::new();
        }
        let mut output = if num_elements <= 10 {
            smallvec::smallvec_inline![F::zero(); 10]
        } else {
            smallvec::smallvec![F::zero(); num_elements]
        };

        match self.mode {
            DuplexSpongeMode::Absorbing { next_absorb_index } => {
                // Modifications happen here
                let nb_0_needed = (RATE + RATE - next_absorb_index - 1) % RATE; // The addition of RATE is for avoid subtraction overflow
                let pad = [vec![F::one()], vec![F::zero(); nb_0_needed]].concat(); // Can surely be optimized
                self.absorb_native_field_elements(&pad);
                //
                self.permute();
                self.squeeze_internal(0, &mut output[..num_elements]);
            }
            DuplexSpongeMode::Squeezing { mut next_squeeze_index } => {
                if next_squeeze_index == RATE {
                    self.permute();
                    next_squeeze_index = 0;
                }
                self.squeeze_internal(next_squeeze_index, &mut output[..num_elements]);
            }
        }

        output.truncate(num_elements);
        output
    }