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$

1 Answer 1

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$
2
  • $\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$ Sep 23, 2017 at 15:34
  • $\begingroup$ One does not simply produce a fixed point. $\endgroup$
    – Q-Club
    Sep 23, 2017 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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