DES strength and weakness

Question

I'm looking to discover what DES's Strengths and Weaknesses are.

I understand that DES is a block fiestel cipher operating on 64 bit blocks and 56 bit keys (after deduction of 8 bits). And I realise that DES is weak against Brute force in this day and age.

But I'm looking to understand firstly, why is/was DES so strong originally. I.e. how does it defend against common attacks. And secondly: other than key space, are there any DES specific weaknesses that can be practically exploited? If so, is there an obvious solution to preventing that weakness?

As a side note, I'm not very mathematically inclined so a high level explanation is likely needed, additionally I'm not as interested in Double or triple DES.

Answer 1

The wikipedia article @SEJPM links to is about as high level of an overview as you can really get. We can elaborate on some of the points.

DES is weak against Brute force in this day and age.

Actually, it was weak against brute force pretty much as soon as it was standardized. According to the wikipedia article, the cipher was standardized in 1977. Reading further, in the section about brute force attacks:

In 1977, Diffie and Hellman proposed a machine costing an estimated US$20 million which could find a DES key in a single day.

So it is arguable that DES was never strong against brute force attacks (the standardized post-NSA consultation version anyways - originally the designers did propose a "real" key size).

Why was DES so strong originally

Let's look at the section of the article for attacks faster then brute force:

• Differential cryptanalysis is one area where DES was relatively strong. It's understood that IBM and the NSA both knew about differential cryptanalysis when DES was designed, and chose to keep this information secret. There exists differential attack(s) against DES, but they are not as devastating as they are against some other ciphers (i.e. FEAL)
  • Resistance to differential attack is determined by differential characteristics of the S-box. The DES s-box was designed with this in mind.
  • A "differential" is a pair of differences: The difference between two inputs to the function, and the difference between the two corresponding outputs. The probability that this output difference occurs for a pair of inputs with the given difference is the basis for the attack.

Are there any DES specific weaknesses that can be practically exploited?

Continuing further in the same section of the article as before, they discuss linear cryptanalysis.

• DES was not known to be written with defense against linear cryptanalysis in mind. It is arguable whether or not the mentioned attacks constitute a "practical" break; These attacks only require known plaintext-ciphertext pairs, which are actually not uncommon in practice (i.e. HTTP GET) and can be practical to obtain, but it does require a large number of such pairs.

  • It is possible to defend against linear cryptanalysis by choosing s-box values appropriately, similarly to differential cryptanalysis. "Linearity" can be a somewhat nebulous concept and difficult to understand.. Put possibly over simplified, the s-box should be as different as possible from any linear equation. Basically, it should be difficult to come up with a simple equation that accurately approximates the equation of the s-box.

• DES has weak keys

  • A stronger key schedule should prevent weak keys
  • Weak keys are technically uncommon, but it's arguable that all 56 bit keys are weak

• The 64 bit block size could be larger

  • This is technically more relevant to the security of the mode of operation used with the cipher then the cipher itself

Answer 2

To add an extra perspective to @Ella's answer: DES is expensive in software, and hard to implement efficiently in constant time. DES was designed with hardware in mind, so it uses operations that can be very efficiently translated to a custom circuit (e.g. bit permutations, which boil down to simple wiring), but are comparatively much more expensive in software.

A big part of DES is the "S-boxes", which are 6→4 functions. A typical DES implementation will use lookup tables, with the bit permutation merged into the tables (i.e. the output of each table is a 32-bit word, which maps the 4-bit S-box output to its permuted emplacement). Such an implementation can be observed there. Unfortunately, this means that encryption entails array accesses at indices that depend on secret data, which can lead to successful side-channel attacks (in a nutshell, these accesses "kick out" previous data from the level-1 cache in the CPU, making ulterior accesses that exercise the same cache lines slower, in a way detectable by attackers). Making a constant-time DES implementation that does not suffer from this issue requires some heavy tricks such as bitslicing, without the benefit of a parallel encryption mode (since DES and 3DES are typically used with CBC mode, not CTR). One such implementation can be seen there, and while it is constant-time, it is also three times slower than the table-based implementation, which is already quite slow by modern standards.

Triple-DES ("3DES") fixes most of the cryptanalytic issues with DES, except the 64-bit block size, which is close to allowing practical attacks; however, it also makes the performance issues three times worse.

We can thus say that DES, and its "improvement" 3DES, have a big conceptual weakness which is that they make it real hard to implement both securely and efficiently, leading to uncomfortable trade-offs (and, in practice, non-secure implementations, because implementers always favour performance, which can be measured, over security, which cannot).

Answer 3

Why was DES so strong originally?

It uses a 56 bit key. So there are $2^{56}$ possible keys which then would take a decade to find the correct key using a brute-force attack. But now in the age of parallel computing, breaking DES has become easy with the help of brute force attacks.