What is the main difference between linear cryptanalysis and differential cryptanalysis? For example in relation to DES?
Differential cryptanalysis works on differences. Linear cryptanalysis works on linearity. Neat, isn't it ?
Instead of speaking of how they differ, it is easier to list their common features. Both kinds of attacks:
- Use a lot of known pairs plaintext/ciphertext (many input messages encrypted with the same key, and, for each of them, the attacker knows both the block value before encryption, and after).
- Rely on an "approximation" of the internal behaviour of the encryption function, which holds with a small but non-zero probability for some input.
- Work with detected weaknesses in the internal structure of the algorithm; they don't work "generically".
With differential cryptanalysis, the known plaintext/ciphertext pairs must be organized in pairs where both plaintexts differ by a specific difference ("difference" being a XOR, a subtraction... whatever works well algebraically with the algorithm at hand; for DES, this is XOR). The "approximation" is that this input difference will yield another specific difference on the output with a probability which is somewhat higher than what could be obtained with pure randomness, and the exact difference which will most probably appear depends on some of the key bits. Successful differential cryptanalysis normally requires chosen plaintext/ciphertext pairs (the attacker gets to choose the plaintexts or the ciphertexts).
With linear cryptanalysis, the approximation is a linear formula (i.e. a bunch of XOR on bits) which links together some input bits, some output bits and some key bits, with a probability somewhat higher than what could be obtained with pure random. This "linear formula" works best (i.e. is fulfilled most often) when the hypothesis on the involved key bits is correct, so the analysis yields a few key bits.
The most salient difference between linear and differential cryptanalysis is the known/chosen plaintext duality. For linear cryptanalysis, known random plaintexts are sufficient, but differential cryptanalysis requires chosen plaintexts, which, depending on the context, may or may not be a significant problem for the attacker.