Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Data Encryption Standard (Wikipedia)

I know that with brute force there are 2^56 possible keys to check (56 bits, each either a 1 or 0). But let's say I know the message itself is only made up of letters (a-z, A-Z).

Would knowing things (like the limitation to just letters) about the plaintext make breaking the encryption easier?

share|improve this question

5 Answers 5

In a standard brute force search it is assumed you already know at least one plaintext and its associated encryption with a given key. So having the plaintext be from a restricted set is not going to help unless there is some other weakness you are taking advantage of.

share|improve this answer

For a brute force attack to actually succeed (even in a theoretical way), the attacker must know "something" about the plaintext, to know whether he found the right key or not. Said otherwise: if all the attacker knows about the plaintext is that it is a bunch of random bytes, then, for each tried key, that's exactly what he will get: a bunch of random-looking bytes.

On the other hand, if the attacker found it worthwhile to attack the system (because a 256 exhaustive search is, while feasible, quite expensive), then he must have some a priori knowledge of what he will find. This can be anything like a standard format (e.g. data is XML, beginning with a XML header; or data is compressed with gzip and thus begins with a gzip header) or even some basic information like "the plaintext is some text which 'makes sense'".

English text with ASCII encoding will use only some byte values, namely byte values from 32 to 126 (inclusive), and possibly also 9 (horizontal tabulation), 10 and 13 (LF and CR, respectively, for end-of-lines), 12 (vertical tabulation), and possibly 26 (end-of-file on DOS/Windows systems). So that's 100 out of 255 possible byte values. A decryption of a single DES block (8 bytes) with a wrong key has probability about (100/255)8 to consist only in this set of "plausible characters". Since the attacker has 256 keys to try, he must decrypt n blocks so that the probability of accepting a wrong key is no more than 2-56. This is achieved as soon as n = 6 (because (100/255)8*6 ≤ 2-56). This leads to an exhaustive search attack where the attacker decrypts 6 blocks per potential key, filtering out wrong keys by looking at the obtained characters.

Now, let's face it, "8g.;=7Zf" is not exactly "text which makes sense". So the attacker actually knows a lot more than "the plaintext consists only in printable ASCII characters". He could filter out wrong decryption which yield only printable characters but not plausible text excerpts. He could also get, say, a thousand "possible keys" (each yielding something which, from the point of view of a computer, is text-with-sense-like) and finish the job by hand (the human brain is very good at spotting real text among a list of gibberish-looking characters). So an attacker could use, say, two or three blocks and still get things done.

It is very hard to quantify how efficient the attacker will be at filtering out wrong decryption, because it depends on what the attacker "guesses", somthing which is in the realm of psychology, not computer science. Therefore, academics use the "safe convention" of considering that the attacker has a known plaintext block: he knows with 100% certainty an 8-byte plaintext for which he also has the corresponding ciphertext. This might not be true in an actual attack situation, but you cannot really foresee it.

share|improve this answer
1  
IT CAN BE QUANTIFIED. DES decryption on Deep Crack takes on average 4.5 days! In cryptography, the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the Electronic Frontier Foundation (EFF) in 1998 to perform a brute force search of DES cipher's key space... that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that DES's key is not long enough to be secure. They succeeded! No knowledge of the "decrypted data" needed. No "realm of psychology", just plain "computer science". It works, the result makes sense and is readable too. ;) –  user6373 Dec 27 '11 at 11:46
    
@e-sushi: the efficiency of Deep Crack is not in question here. Deep Crack tries all possible keys and stops when it finds a "matching" key. The question is how Deep Crack can decide that a key is "matching". The primary mode of Deep Crack is when it has a known plaintext block: 8 bytes of known cleartext, and the corresponding encrypted block. That's the ideal case for the attacker, because it suffices to try out possible keys -- which Deep Crack does in a few days. But availability of a plaintext block for the attacker may not be totally realistic. That's the whole point of my post. –  Thomas Pornin Dec 27 '11 at 23:02
1  
@e-sushi: in other words: yes, Deep Crack can try 2^56 keys in a few days. This is a given data, and not what I talk about here. I am talking about the stopping condition which Deep Crack must use to declare that a key is "the right one". Academics just use the safe rule that the attacker might be in the ideal conditions that Deep Crack lives in, i.e. a known plaintext block. –  Thomas Pornin Dec 27 '11 at 23:06
    
Well, "might" or "might not" isn't the question here. All in all it is generally agreed that DES is unsafe. Furthermore, it is an established fact that cryptography loses major parts of it's "individual safety state" the more an "attacker" knows about the encoded text and/or the key. Last but not least, I would be easy on thumbing down "academics" since 99.99% of the crypto out there was created/invented by them. You can trust in the fact that - in crypto - "might" is a valid way of thinking. Just one example: the Chinese government has "ideal conditions". Others too. Do you know mine? No! ;) –  user6373 Dec 28 '11 at 17:39

It would depend on how you are checking each key. If you start at 0 and keep incrementing then you would have to convert to the character set and verify if that character is valid. Or you chould work the other way, start with a character and only increment by a character within the set.

I think if you incremented by character instead of bit, you'd have a far smaller working set and therefore it would take less time to run through all the combinations.

share|improve this answer
    
Are you talking about keys or plaintexts? The op is talking about plaintexts. –  GregS Dec 10 '10 at 21:54
    
@GregS my bad... I read the question wrong –  Steve Dec 11 '10 at 0:58

Knowing that the possible solutions belong to a restricted set will help you because you can terminate early the decryption process.
In your case you can decrypt just a limited amount of encrypted/cipher-text (the first 8/16/... bytes for instance) and save for a later round only the decrypted/plain-texts that are only made up of letters (a-z, A-Z). Next you can increase the amount you decrypt if the saved solutions space is too large or simply go through all of them and decide which one is right.

share|improve this answer

The short answer is "theoretically yes".

But: that's not the main reason for DES to stumble over it's own feet.

Let me give you a bit more info...

Nowadays, DES is considered to be insecure for most applications. This is mainly caused by the 56-bit key size being too small. What this means becomes obvious when you know that in January 1999, the "Electronic Frontier Foundation" and "distributed.net" collaborated to successfully break a DES key in 22 hours and 15 minutes... in publicly.

The small key size was one of the reasons why DES has been withdrawn as a standard by the National Institute of Standards and Technology.

But: the algorithm is believed to be practically secure in the form of Triple DES, although there are theoretical attacks. In more recent years, the cipher has been superseded by the Advanced Encryption Standard (AES).

My 2 cents: "If you can avoid DES, avoid DES!"

share|improve this answer

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.