[curves] Ed448-Goldilocks (sponges and collision resistance)

[Samuel Neves]

On 17-07-2014 01:57, Michael Hamburg wrote:
> Top replying!  I believe that the birthday attack still applies.
>
> The state is divided into two pieces, of sizes $rate and $capacity = $statesize - $rate.  The message blocks are xor’d into the $rate-sized piece, but the $capacity-sized piece is not changed.
>
> If the attacker can find two messages mA and mB which cause a collision on the $capacity-sized piece, he can set the message blocks for the next round to set the $rate-sized pieces of stateA and stateB to anything he wants (in particular, to the same thing), thereby causing a collision on the entire state.
>
> This birthday attack requires 2^($capacity/2) work and storage.  There’s probably also a rho attack which requires less storage.
>
> So postfixing with the nonce or key doesn’t help.

This is correct. The attacker has full control of the rate, and therefore collisions in the capacity are enough to
achieve full state collisions.

When a key is prepended to the state, the attacker has no way to "fix" the rate part to some desired value, since the
initial state is unknown. Therefore the (generic) attack complexity rises. This is explored in the original keyed sponge
proof [1], and also further in [2] (note: the security model in [2] is narrower than in [1], i.e., targeted at
nonce-based authenticated encryption).

[1] http://sponge.noekeon.org/SpongeKeyed.pdf
[2] https://eprint.iacr.org/2014/373


>
> Cheers,
> — Mike