Security proofs of schemes like the sponge construction assumes that a permutation $P$ is chosen uniformly at random and the attacker is given access to oracles for $P$ and $P^{-1}$. When the sponge construction is actually used in the real world, it is instantiated with a publicly specified permutation such as Keccak-f[1600] or Gimli.
My question is how can we judge the security of a real, public permutation such as Keccak-f[1600]. For block ciphers, we can evaluate them against an "ideal" security model such as PRP, and we announce a break if it deviates from the PRP conditions. We might try something similar for public permutations, and say that they are broken if they can be distinguished from a random permutation. However, since they lack a key, there are always trivial distinguishers like $\mathcal{A}^P = [P(0) = c]$ for a suitably hard-coded $c$.
How can we define a security model to include only actual "structural" distinguishers? Maybe we can sample a random permutation $\sigma$ and ask the attacker to distinguish $\sigma \circ P \circ \sigma^{-1}$. However, the random permutation $\sigma$ can hide weaknesses in $P$. For example, if $P$ has a single fixed point, the attacker can no longer find it in polynomial amount of queries. It seems like even if $\sigma \circ P \circ \sigma^{-1}$ is indistinguishable from random, it does not imply that $P$ can be safely used with the sponge construction (or other constructions proven secure in a ideal permutation model).
Update: In other words, what do we mean by saying a specific public permutation $P$ such as Gimli is "secure" (or alternatively, broken), in the general sense? We cannot simply say "Real: The attacker is given oracles for $P$ and $P^{-1}$; Random: Sample a random permutation $\sigma$, and give oracles for $\sigma$ and $\sigma^{-1}$; if the attacker can distinguish real from random then $P$ is broken". The reason is that the attacker cam precompute $P(0)$.
Let's look at what various papers use as their security model:
- Cryptanalysis of 22 1/2 rounds of Gimli: Builds a keyed PRF out of Gimli by $F_k(x) = \mathrm{snd}(\mathrm{Gimli}(k || x))$, then attack the PRF
- Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis: Instantiates Keccak and attacks the entire sponge construction together
- Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi: Shows the existence of subsets of initial states, such that after applying Keccak-f to each, the results sum to 0.
I certainly agree that each of these papers demonstrates a break, but it is not clear what essential feature of the permutation they are breaking. What counts as "distinguished from a randomly chosen permutation" (that still excludes trivial distinguishers we don't care about)?
