0
$\begingroup$

Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?

$\endgroup$
4
  • $\begingroup$ Welcome to Cryptography.SE. The $k$ is not a parameter for key, it is output size, $\ell$ is a way better letter to represent. Your question is not totally clear. Are you asking the collision probability for a given length $\ell$? $\endgroup$
    – kelalaka
    May 21 at 14:53
  • $\begingroup$ Thanks! My question is whether it is possible to have two inputs that will collide for any size of output (sorry if there are English errors). $\endgroup$
    – Teste Pent
    May 21 at 14:57
  • $\begingroup$ Are you asking that if $Shak256(m_1, 128) = Shake256(m_2,128)$ then does it implies that $Shak256(m_1, 129) = Shake256(m_2,129)$? $\endgroup$
    – kelalaka
    May 21 at 14:57
  • $\begingroup$ No, I'm asking if this is possible: lim L-> +infinity (shake(input1, L) = shake(input2, L)) $\endgroup$
    – Teste Pent
    May 21 at 14:59
1
$\begingroup$

Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?

Yes, it is possible. In fact, it is inevitable that some such pair $input_1, input_2$ exists.

Shake256 maps the input into a 1600 bit state, and then converts this state into an arbitrarily long sequence. If two different inputs map to the same state, then they're produce the same sequence (independent of how much output you ask for).

In particular, if we consider all 1601 bit inputs, there must be (by the pigeon hole principle) two different inputs that map to the same state; that observation gives us an upper bound on the required size of $input_1, input_2$. Almost certainly much smaller pairs exist.

Now, finding such a pair, well, that's a different (and far more difficult) problem...

$\endgroup$
0
$\begingroup$

No, not necessarily.

Shake256 is based on the Keccak and that is used Sponge construction.

enter image description here

means that there is the capacity (c) in the sponge that is never output. The next request ($Z_i$) from the squeezing step mangles all parts (f). So if you somehow a collision, i.e $Z_0, Z_1,..., prefix(Z_n)$ are equal for two different inputs, to extend the collision to $Z_j$ where $j>n$ then you need to have a collision in the capacity part, too. There is a possibility, but that is negligible!.

Note that, infinity has no meaning, no such input. If $d > 1600$ there may be no preimage at, all.

There may be a stage that, the output is so large that, the capacity must be the same. There is no need to calculate this meaningless size since it is beyond all!

$\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.