Intuition for SHA3 sponge construction I would like to get some intuition on the security of the sponge construction. I'm referring to this diagram and notation. 



Let's consider the case where we have don't apply $f$ in the squeezing phase i.e. we simply take the bits in the r-space ($Z_0$ in the figure) at the end of absorption and call that the hash of our message.

The Wikipedia article says that one could replace the XOR function and simply choose to overwrite the $r$ bits with the message instead of using XOR. The security level is not compromised if this is done and makes it easier for me to understand.

Reading a few other answers, it seems to be the case that the core thing that keeps SHA3 safe is the lack of knowledge about the state of $c$ in the final step. But this seems problematic.

For instance, let's say I have the hash of a known message (and therefore the internal states $c$ corresponding to this message at all stages) and would like to modify the last part i.e the $P_{n-1}$ bits. It seems like I have a very localized problem i.e. I know $(r_1, c_1) \xrightarrow{f} (r_2, c_2)$ and must find $(r_1', c_1) \xrightarrow{f} (r_2, c_2')$ for arbitrary $c_2'$. If I want to do it for any intermediate block, $P_k$, then $(r_1', c_1) \xrightarrow{f} (r_2', c_2)$ is the constraint, where $r_2'$ is arbitrary. This is because the bitrate is overwritten in intermediate blocks so that part of the output can be arbitrary while for the last block the state of the capacity is not used so it can be arbitrary. Moreover $f$ is just a permutation and so this task seems... not too hard?

I want to add, I know that hundreds of very clever people have tried various attacks and failed so this has a good resolution. This isn't some crackpot "I broke SHA3" post - it's more of a "what aspect of SHA3 am I missing" post!
So if it's just a permutation of 0s and 1s as we've concluded, what is hard about finding an alternate message string that satisfies the constrains I've mentioned on the permutation outcome? 


To be more precise, it is a pseudo-random permutation from $\mathbb{Z}_{2^{1600}}$ to $\mathbb{Z}_{2^{1600}}$. It is not just 0s and 1s changing positions.

Because of the size of $\mathbb{Z}_{2^{1600}}$ (which contains $2^{1600}$ elements!), the input and output are related in a somewhat random (but  deterministic way), and it cannot be predicted without actually evaluating the permutation (or its inverse) on a given input and checking the result.

There are tools such as linear and differential cryptanalysis that can be used to try and predict the output, but keccak-f was explicitly designed so that using these techniques would be computationally intractable.


  It seems like I have a very localized problem


You cannot isolate parts of the state and work on them independently. Changing one bit of the state and then applying the permutation diffuses those changes across the entire state in an unpredictable manner.