DES - Weakness in Sbox

Question

In the book "Introduction to Cryptography with Coding Theory ", in the chapter about the Differential Cryptanalysis for Four Rounds for DES algorithm, the authors say:

There is a weakness in the box $s_{1}$. If we look at the 16 input pairs with XOR equal to 0011, we discover that 12 of them have output XOR equal to 011. Of course, we expect on the average that two pairs should yield a given output XOR, so the present case is rather extreme. A little variation is to be expected; we’ll see that this large variation makes it easy to find the key. There is a similar weakness in $s_{1}$, though not quite as extreme. Among the 16 input pairs with XOR equal to 1100, there are 8 with output XOR equal to 010.

I've understood the attack in case of a 3-round scenario. However, it's not clear to me how this particular weakness of sboxes is used in order to attack the DES algorithm in a 4-rounds scenario. Can you explain to me ?

ps: you find the book writing on google "Introduction to Cryptography with Coding Theory pdf" and taking the first link. The related chapter is 4.3

Answer 1

The attack on 3 rounds is deterministic. It is extended to 4 rounds in a probabilistic manner, which is the normal way of carrying out differential cryptanalysis, see for example Heys' tutorial on linear and differential cryptanalysis which is easy to find online and uses a simple toy cipher to explain these concepts.

Basically, given enough input output pairs, one can use the fact that those differences will statistically dominate. Scan through a set of subkey bit patterns and declare the subkey bit pattern which leads to the most biased output difference distribution as the correct key bit pattern.