Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
no you should accept my answer and post a new question instead of post facto editing to make my answer wrong.. – user58512 Mar 16 '13 at 18:03
@caveman Fair enough. Here's the new question. – Psyberion Mar 16 '13 at 18:15
thanks - welcome to the site – user58512 Mar 16 '13 at 18:17
up vote 1 down vote accepted

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

share|cite|improve this answer
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. – Psyberion Mar 16 '13 at 17:36
@Psyberion, yeah I'm sure this is useless in the analysis. – user58512 Mar 16 '13 at 17:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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