The classic text by the inventors of this technique is Differential Cryptanalysis of the Data Encryption Standard by Eli Biham and Adi Shamir, published in 1993.
These notes summarize three attacks on reduced versions of DES: 1, 3 and 6 round DES. One round DES introduces some few ideas about the typology of DES that are used in the attack. Three round DES introduces the use of differential cryptanalysis for the way it penetrates around unknown keys. Six round DES introduces the probabilistic component of the attack - that the differentials proposed only sometimes develop according to the attacker's plan.
1-round DES
In explaining these attacks the initial and final permutation and the final left-right swap are ignored. Since the permutations are known they do not enhance the security and, if a computer is used to keep track of everything, do not hinder the attack. We simply drop them from discussion.
Label the left and right input to 1-round DES as L_0 and R_0; the outputs are L_1, R_1 and the key is K_1. Since L_1 = R_0, the input to the F-Box is immediately available to the attacker. Since R_1 = F-Box( R_0, K_1 ) XOR L_0, and L_0 is known, F-Box( R_0, K_0 ) is known. Tracing up through the known P-Box and down through the known E-Box, the outputs of the S-Boxes are known, and so we can propose 4 inputs for each S-Box. The inputs to the S-Boxes are the XOR of the output of the E-Box and K_1, so four candidates for K_1 are known.
Trying various L_0, R_0, we intersect at each attempt the possible K_1 until only one candidate remains.
3-round DES
The discussion of 1-round DES noted that it is possible to know the inputs and outputs of the last DES round F-Box - except that in 3-round DES L_2 will not be known. In this 3-round attack we find that we cannot know L_2 but we can know the XOR difference of two L_2's, gotten by applying a pair of inputs (L_0, R_0) and (L_0*, R_0*). This is because the XOR's pass through the key mixing unchanged:
L_i' = L_i XOR L_i*
R_i' = R_i XOR R_i*
By presenting pairs in which R_0=R_0*, then the differential input
to the first round F-Box is 0, that means that the differential output
of the F-Box is 0:
F-Box( R_0, K_1 ) = F-Box( R_0*, K_1 )
So L_2' = R_1' = L_0'. Knowing L_2' allows us to caluculate the
differential output of the third round F-Box as L_2' XOR R_3'.
Tracing this up through the P-Box gives us the XOR output for
the S-Boxes, which limits the XOR inputs possible for the S-Boxes,
and indeed the possible inputs of the S-Boxes. Again the input
to the S-Boxes before XOR with K_3 are known as the E-Box applied
to the visible L_3, so we can begin to list candidates for
K_3.
The attack looks for the intersection of all candidates as we try various (L_0,R_0),(L_0*,R_0*) pairs, subject to R_0=R_0*. We readily narrow down the candidates. This gives 48 of the 56 bits of K. The remaining 8 bits are found by brute force.
6-round DES
The differential idea of the 3-round attack is used, but now it is not possible to know with certainty L_5'. When the XOR input to the S-Boxes is 0, so must be the XOR output. But other values for XOR inputs can give a variety of possible XOR outputs. At least we are still immune to the values of K_i along the way!
We choose L_0' and R_0' taking advantage that for certain XOR inputs, you can say with good probability what the XOR output will be. By good probablity we are taking of small probabilities like 1/4. And as the L_i' and R_i' penetrate down into the second and third rounds, these probabilities multiply, so that we can only predict L_5' with a small but not insignificant probability. The structure of (L_i',R_i)'s starting from i=0 and arriving at i=k with probabilities of being correct along the way is called a characteristic. Finding good characteristics is the art of cracking DES.
For 6-round DES we find two 3-round characteristics with probability 1/16 of being right. We then follow the differentials through the final 3 rounds in a way which is certain but which losses total information about three of the S-Boxes. The two characteristics completement each other in this way so that the S-Boxes missed by one characteristic are picked up by the other. (Actually, one S-Box remains missed by both.)
Since we only know what these S-Box XOR outputs will be probably, we get a lot of wrong information. This shows up as a lot of wrong guesses about K_6 which average themselves out. The right guesses slowly assert themselves through repetition. Counting the repetition of K_6 guesses we ferret out the true K_6 (less 6 bits of the missed S-Box) and brute force the remaining 14 bits of K.