1
$\begingroup$

I understand that with more encryption rounds the more complex the ciphertext becomes due to multiple substitutions and permutations. What I don't understand is the purpose of these features.

I am under the impression that key length and the number of subkeys are the dominant factors in deciding the strength of a cipher as they are what encrypts the plaintext. I’m not disregarding the fact that plaintext must also undergo diffusion to avoid statistical analysis and confusion to obscure the relationship between the texts.

What benefits do substitution boxes and permutation boxes offer in DES? Don't these permutations and substitutions become redundant after a few rounds? Do the effects eventually plateau?

$\endgroup$
  • $\begingroup$ Everything would be linear without S-boxes. $\endgroup$ – Aleph Oct 5 '14 at 10:38
2
$\begingroup$

In general, the key length and number of rounds are the dominant factors in deciding cipher strength. But you need to consider how the rounds are constructed and how the key is used.

Substitution and permutation are the bread and butter of DES. That's literally all it is - substitution, permutation, and XOR.

Here is a diagram of the DES fiestel function for reference.

The DES substitution boxes ($S1$ through $S8$ in the diagram) are the only non-linear part of the cipher. Without them, the cipher would be nothing but XOR operations. It would be easy to come up with (relatively simple) linear equations relating the key, plaintext, and ciphertext bits.

The DES permutations ($E$ and $P$ in the diagram) propagate and distribute the bits of the previous output. Without these permutations, any small change in the plaintext/ciphertext would result in a small change in the resulting ciphertext/plaintext.

Suppose $E$ and $P$ don't exist and there are two plaintexts which are identical except for a difference in the first bit.

Since the difference is in the first bit, it will be fed into $S1$. $S1$ outputs 4 bits, so at most the first 4 bits will be different.

Repeat for the 2nd round. Since $S1$ takes the first 6 bits as input, those 4 bits go through $S1$ and output another 4-bit difference.

As you can see, after any number of rounds, the difference will still only be in the first 4 bits.

Because of the Feistel structure of DES where the left and right halves get swapped through the cipher, up to 8 ciphertext bits can be different: the first 4 bits in the left 32-bit half, and the first 4 bits in the right 32-bit half. Not only does a small change in the plaintext result in a small change in the ciphertext, the differences have locality. This makes differential cryptanalysis very easy to perform.

I hope that was the answer you were looking for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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