4
$\begingroup$

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

enter image description here

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!

$\endgroup$
  • $\begingroup$ @user1936752 To correct the previous (thoroughly wrong) user, who has now deleted their comment, keccak-f (the $f$ used in SHA3) is a permutation. It is a bijection and does not output collisions for any two distinct inputs. Please don't allow them to confuse you. $\endgroup$ – Ella Rose Nov 1 '18 at 21:39
  • $\begingroup$ 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? $\endgroup$ – user1936752 Nov 1 '18 at 22:49
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Some parts of the question aren't crystal clear to me, but I think this should answer it (or at least help). $\endgroup$ – Ella Rose Nov 1 '18 at 23:27
  • 1
    $\begingroup$ Thanks for the answer. Could you elaborate on the "effectively random but deterministic" statement? If the function $f$ is a bijective permutation and invertible, it isn't clear why it behaves in such an intractable manner. Regarding your second comment, I do enforce the constraint that the state after the permutation stays the same despite a different input. Perhaps the key is to understand why finding $(r_1', c_1) \neq (r_1, c_1)\xrightarrow{f} (r_2, c_2)$ is hard. $\endgroup$ – user1936752 Nov 1 '18 at 23:49
  • $\begingroup$ random in the sense of unpredictable, and deterministic meaning that the permutation applied to the same input yields the same output (which is clearly non-random behavior). The fact that it is invertible has effectively no bearing on the ability to determine the output for a given input without evaluating the function (disregarding the advantage given by previously evaluated pairs being ruled out). It is difficult to predict because it was designed to be resistant against all known analysis methods that are capable of performing such predictions. (1/2) $\endgroup$ – Ella Rose Nov 2 '18 at 0:13
  • 1
    $\begingroup$ @user1936752 if you go forward you have a Birthday paradox problem over the rate, if you go backward, do not forget that you need to match the first capacity = 0, this is a pre-image problem. You can also find a collision in the capacity and then generate two equal states from it. $\endgroup$ – Biv Nov 2 '18 at 16:27
  • 1
    $\begingroup$ The reason why adding constraint does not work because it is like creating a big equation system. The problem is that going backward the equation systems grows exponentially and in the end you have too many equations to solve. $\endgroup$ – Biv Nov 2 '18 at 16:29
-1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.