Why DES is insecure? How do we know when to stop iterating and that we've found out the key? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 8 years ago.

Improve this question

It's said that DES is insecure. I guess it's because the key is 55 bit long, so using brute-force would take max 2^55 iterations to find out the key which is not many nowadays. But if we iterate 2^55, when do we know when to stop?

Answer 1

It's 2⁵⁶ not 2⁵⁵.

There are a couple of options for how to know when to stop. One is that you're doing a known-plain-text attack -- i.e., you know the actual text of a specific message, use that to learn the key, then use that to be able to read other messages. In many cases, you won't know the full text, but may know some pieces anyway -- for example, you may know something about an address block that's used with all messages of the type you care about, or if a file has been encrypted may have a recognizable header even though the actual content is unknown.

If you don't know (any of) the text for any message, you generally depend on the fact that natural languages are generally fairly redundant -- quite a bit is known about their structure. For a few examples, in English, you know that a space is generally the most common character, e is the most common letter, almost no word has more than two identical letters in a row, nearly all words contain at least one vowel, etc. In a typical case, you do a couple different levels of statistical analysis -- a really simple one that rules out most possibilities very quickly. For those that pass that test you do a second analysis that rules out the vast majority of the rest fairly quickly as well.

When you're done, it's possible you may need human judgement to choose between a few possibilities -- but in all honesty, that's fairly unusual. Statistical analysis is generally entirely adequate.

I should probably add that some people find statistical analysis problematic enough that they attempt to prevent it, such as by compressing the data with an algorithm like Huffman compression to maximize entropy in the compressed data.

Answer 2

It depends on the content. Any key will produce some output, so there's no automatic way to know you've found the correct key unless you can guess what sort of thing you're looking for. If you expect that the encrypted data is text, you can check whether each decrypt contains mostly ASCII letters; similarly, if you expect that it's a JPEG file, you can check whether the decrypt starts with the characters "JFIF".

If you expect that the data is not compressed, you can run various entropy tests on the decrypts, looking for decrypts with low entropy.