Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What is the main difference between linear cryptanalysis and differential cryptanalysis? For example in relation to DES?

share|improve this question
1  
What research have you done? Have you read about linear cryptanalysis and differential cryptanalysis? There's lots written about them; that would be the best place to start. –  D.W. Sep 13 '13 at 20:28
add comment

migrated from security.stackexchange.com Sep 13 '13 at 20:23

This question came from our site for Information security professionals.

1 Answer

up vote 7 down vote accepted

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.

Linear cryptanalysis is easier to grasp, so begin with that one. This PhD thesis is a nice introduction. For differential cryptanalysis, read this well-explained article.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.