0
$\begingroup$

Can we define one finite set of input strings for a SHA-3 hash (or SHAKE XOF) function so that the collision probability is arguably lower than for a random oracle, with a definition of the set making no reference to the function? If so, what's an example with the ratio of function's to oracle's collision probabilities particularly low?

The definition of the set must be without constants obtained with help of evaluations of the function, or it's internal constants (that would be considered a reference to the function). There must be a demonstration or heuristic argument of the desired property using only considerations about the (sponge) structure of the function and it's internal parameters (rate, capacity…), rather than evaluation.

The collision probability is for two elements of the set drawn uniformly at random without replacement, or another collision probability to be proposed.

I understand that no experimental verification using the function as a black box is possible, for it would be a break.


The question is inspired by this comment, that suggests $\operatorname{SHAKE}(y\mathbin\Vert z)$ has less collisions than expected for a random oracle if the length of $y$ is less than the rate, and some other conditions.

$\endgroup$
7
  • $\begingroup$ I'm a bit confused. Any set of values that does not collide under SHA-3 has a collision probability of zero for SHA-3, but a non-zero collision probability for a random oracle. $\endgroup$
    – Maeher
    Dec 14, 2023 at 12:52
  • $\begingroup$ @Maeher: Indeed. But that set definition contains "SHA-3" thus violates the "no reference to the function" prescription. I've now moved that important prescription into the first sentence. $\endgroup$
    – fgrieu
    Dec 14, 2023 at 14:11
  • 2
    $\begingroup$ What exactly is the probability space? $\endgroup$
    – Maeher
    Dec 14, 2023 at 15:30
  • $\begingroup$ @Maeher: indeed what probability I'm talking about was not specified. That's half on purpose, to give freedom to the answer. We can use: probability of collision between two elements of the set drawn uniformly at random without replacement. Added that. $\endgroup$
    – fgrieu
    Dec 14, 2023 at 15:51
  • $\begingroup$ I have accepted the answer, which matches the question's requirements, and explains the motivating comment. If there is some configuration with higher ratio of probabilities (or argument we can't do much better), please make another answer! $\endgroup$
    – fgrieu
    Dec 15, 2023 at 6:14

1 Answer 1

3
$\begingroup$

Well, since I made the comment that fgrieu responded to, I suppose I should be the one to answer.

I was using an intuitive notion; when we look at it analytically, there is indeed an (exceeding small) lower collision probability for SHAKE (although not "demonstrably lower").

Background on how SHAKE works internally for short (shorter than the "rate"; 168 bytes for SHAKE-128) inputs: SHAKE places the input into a 1600 bit array (and having fixed settings for the rest of the bits). It then performs a permutation (which we will model as a random permutation) on that 1600 bit array. Then, for the first 168 bytes of output (for SHAKE-128), it reads out bits from the array (and if more output is requested, it'll do another permutation, and output the next 168 bytes from there).

So, if we consider two distinct short inputs $A$ and $B$, the state after the permutation will be random, except that we know they are different. That is, if we consider the $A$ state as fixed, the $B$ state will be in one of $2^{1600}-1$ values. Of those $2^{1600}-1$ values, there will be $2^{256}-1$ values where the first 1344 bits (168 bytes) will be the same. Hence, the probability that the first 168 output bytes for both $A$ and $B$ will be the same is:

$$\frac{2^{256} - 1}{2^{1600}-1}$$

This value is (slightly) smaller than the $2^{-1344} = 2^{256} / 2^{1600}$ value we get for a random oracle.

$\endgroup$
2
  • 1
    $\begingroup$ I understand now. So the ratio of collision probabilities for this example is close to $1-2^{-256}$. $\endgroup$
    – fgrieu
    Dec 14, 2023 at 14:53
  • $\begingroup$ @fgrieu: yup; as I mentioned, it's there, just very small... $\endgroup$
    – poncho
    Dec 14, 2023 at 14:58

Your Answer

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

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