Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. Now, let's denote $$ \delta= a \oplus a' $$ From Blowfish's algorithm we then get the following characteristic characteristic

which is iterated a number of times. Pi is a position in a key-array, consisting of 32-bit entries. The function F is defined as $$F(x) = S(s) + S(t) \oplus S(u) + S(v)$$ where s,t,u,v are derived from the input. The probability of this characteristic is, according to the analysis, $$1 \over 2^7$$ How do I calculate this probability?

share|improve this question
+1 this is an interesting question –  user58512 Mar 16 '13 at 18:17

Your Answer


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

Browse other questions tagged or ask your own question.