4
$\begingroup$

Let $X$ denote a particular 512-bit sequence.
Let $A,B,C$ denote sequences of bits such that: $$len(X || A) = len(X || B) = len(X || C) = 1600$$

$$\operatorname{Keccak-}f(X||A) = X||B$$ $$\operatorname{Keccak-}f(X||B) = X||C$$ $$\operatorname{Keccak-}f(X||C) = X||A$$

then we have a loop, so the output of SHAKE (if my understanding of how the sponge construction works is correct and if $X||A$ happens to be the state which was output after xoring the final block of input) is nothing but an infinite concatenation of the same 512-bit block. Is it possible?

$\endgroup$
3
$\begingroup$

Minor correction: SHAKE generates either 1088 or 1344 bits per squeeze; not 512. So, the example you give will give a repeating pattern, but it'd be either 3264 or 4032 bits long, not 512.

Other than that, yes, that is possible, as far as we know. In fact, a far more likely repeat is:

$$\operatorname{Keccak-}f(A||X) = A||X$$

This would give a repeating pattern of 1088 or 1344 bits long.

In addition, not only is this possible, there's a good likelihood that there actually is such a $A || X$ pattern. Such a $A || X$ is known as a fixed point of the permutation; a random permutation has at least one fixed point with probability approximately $1 - 1/e \approx 0.6321$; assuming that $\operatorname{Keccak-}f$ does, in fact, act like a random permutation, then it's more likely than not that there is such a fixed point.

$\endgroup$
  • $\begingroup$ Thank you. I chose 512 bits per squeeze after reading the answer to “Does SHA-1024 hash exist?” which says that “SHAKE256-1024 would be a 1024-bit digest with the effective security of a 512-bit hash”, so I thought that should imply two squeezes, where each squeeze gives 512 bits. $\endgroup$ – lyrically wicked Sep 23 '17 at 15:34
  • $\begingroup$ One does not simply produce a fixed point. $\endgroup$ – Q-Club Sep 23 '17 at 15:57

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.