How can Blowfish be resistant against differential cryptanalysis if it doesn't have S-boxes tuned for that?

Question

The S-boxes used in DES were carefully tuned for resistance against differential cryptanalysis, a technique not known to the public at that time but known to designers of DES. It was later discovered that even a small change to DES would make it more susceptible to differential cryptanalysis.

My understanding is that Blowfish isn't particularly vulnerable to differential cryptanalysis. However, its S-boxes are based on "nothing up my sleeve numbers", digits of pi. So the designer of Blowfish couldn't tune the S-boxes for resistance against differential cryptanalysis.

How can Blowfish therefore be resistant against differential cryptanalysis, if its S-boxes weren't tuned for that but rather used "nothing up my sleeve numbers"? Is this related to the big size of the Blowfish S-boxes, the highly complex key schedule, or the fact that the S-boxes are dependent on the key?

Answer 1

The short answer is to have more rounds. This article provides an equation to determine the number of chosen plaintexts required for a differential cryptographic attack on a Blowfish with multiple rounds, The formula is : $$ 2^{2 + 7 \left( \frac{r - 2}{2} \right)} $$ where $r$ represents the number of rounds. For example, with $16$ rounds, this calculation yields $ 2^{51} $ chosen plaintexts.

To achieve security for a 64-bit plaintext size, you need at least $ 2^{64} $ chosen plaintexts. Using the formula provided:

$$ 2^{2 + 7 \left( \frac{r - 2}{2} \right)} = 2^{64} $$

Solving for $ r $:

$$ 2 + 7 \left( \frac{r - 2}{2} \right) = 64 $$

$$ 7 \left( \frac{r - 2}{2} \right) = 62 $$

$$ \frac{r - 2}{2} = \frac{62}{7} $$

$$ r - 2 = \frac{124}{7} $$

$$ r = \frac{124}{7} + 2 \approx 19.71 $$

Therefore, a minimum of 20 rounds is required to reach the 64-bit security level.