Probability of collision in S-box

Question

I'm trying to understand a cryptanalysis of the Blowfish cipher, and I need to calculate the probability of collision in the cipher's S-boxes. Basically an S-box is a list of 256 semi-random 32-bit numbers. We can assume that the values are random for convenience. I need to know how I calculate the probability that

$$ S(a) = S(a') $$$$ a \neq a' $$

where a and a' are positions in the S-box.

no you should accept my answer and post a new question instead of post facto editing to make my answer wrong.. — , Mar 16 '13 at 18:03

score 1 · Accepted Answer · answered Mar 16 '13 at 17:22

1

After thinking about it for some time it seems the problem is trivial: The probability is just $\frac{1}{2^{32}}$.

If we're modelling S boxes as random functions from 8 bit numbers (but this doesn't even matter) to 32 bit numbers, then the chance of $a'$ (a number distinct from $a$) having the same $S$ value (which is just a random 32 bit number) as $a$ is just $\frac{1}{2^{32}}$.

answered Mar 16 '13 at 17:22

Yes, that does make sense. Makes me wonder if I missinterpreted the analysis though, since they gave another value there. I'll add some information to the question. – EscalatedQuickly Mar 16 '13 at 17:36
@Psyberion, yeah I'm sure this is useless in the analysis. – Mar 16 '13 at 17:45

Probability of collision in S-box

1 Answers1