Intuition for SHA3 sponge construction

Question

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!

Answer 1

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.

Answer 2

You have correctly identified the crux of SHA-3’s security. It has a fairly complex domain extender to handle all of the different digest lengths. The first mechanism pads up to the rate size for message sizes below the respective rate size of the digest length. The second mechanism (called the capacity) pads a constant number of lanes containing only zeros to the respective rate size until the full state size is reached.

For the XOR function to be called the message size must exceed the rate size for the specified digest length. Now keep in mind that one of the state chunks will always be appended with zeros (i.e. the capacity). There are also some issues with message sizes that equal the rate size, in which case an empty string is automatically appended to the end of the message. I’ve never been able to find any security reasons for adding this string, or even get someone else to acknowledge that this string exists. But it’s there and I can prove it. You should be able to overwrite the state without calling XOR and not compromise security. This has to do with the theta function being initialized with a full state of zeros. YES, regardless of your definition of theta, it’s initialized with a full state of zeros.

Now the current goal of cryptographers is to find a capacity that contains all zeros, and thus prove the existence of a collision in SHA-3. We’ve already found those values (we know the collisions are out there just sitting smugly…those bastards), but it was the result of carefully crafting an inverse function that violated the two mechanisms outline in the first paragraph. But out of this effort certain statistical advantages were gained by processing the inverse function. Bit prediction through chi is statistically relevant, verifiable, and represents the only real talking point with regards to the otherwise extremely robust security of SHA-3. The attacker must bind the state’s output capacity region at zero, and run the inverse function (a whole bunch of times) hoping the resulting input state also has a capacity region filled with zeros. Google might be able to take a swing at it with some deep meet-in-the-middle vector magic, but right now free start collisions is the only thing I can find.