Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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.
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.
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!"
