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$)?
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$– kelalakaMay 21, 2021 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 PentMay 21, 2021 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$– kelalakaMay 21, 2021 at 14:57
-
$\begingroup$ No, I'm asking if this is possible: lim L-> +infinity (shake(input1, L) = shake(input2, L)) $\endgroup$– Teste PentMay 21, 2021 at 14:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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...
$\begingroup$
$\endgroup$
No, not necessarily.
Shake256 is based on the Keccak and that is used Sponge construction.
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!
answered May 21, 2021 at 15:12