Re: Brute force attacks

[Adam Shostack <adam () weathership homeport org>]

        This is covered in great detail in the EFF's book "Cracking
DES," which is available from the usual online bookstores, or its been 
scanned by jya.com.

        In brief, you usually have a pretty good idea of the structure
of the plaintext you're after.  You do a rough match against the
structure first to see if you have a possible valid decrypt.  If you
know that you have text, for example, you can eliminate all but (1 /
2^8) decrypts by checking the high bit is not set in all 64 bits of
the output block.  If you pass this test, you might do a slightly more
complex search, ie, checking that bits 2 & 3 are not set (which would
push the ascii code up to something greater than 192), and your odds
of a false match in this step are roughly (1 / 2^ 16) or (1 / 2^24)
overall.

        If this hits, you pass to a next level, which checks the text 
for looking something like the text you expect, which is code
customized for the job to match the data against the expected
plaintext.  (Does it start with "From [A-Za-z0-9-_+]" would be good
for our email thread.)  Since you're getting about one plaintext per 8 
billion keys tested, you can spend a few cycles on this sort of
matching, and anything that vaugely passes, you put on an operator
console for eyeball checking.

Adam


On Wed, Aug 12, 1998 at 05:48:38AM -0700, joe harlin wrote:
| Slightly off pure FW topics, but still germane, I have a question about 
| brute-force attacks.
| 
| Using DES as en example, a brute force attack has 2(56) possible keys.
| 
| The question I have is how do I check my output to validate that I have 
| the correct key?
| 
| I start with the first possible key and get output.  Now that I have 
| this output 1 of 2(56), how do I determine if this output is meaningful 
| or gibberish??
| 
| Thanks!
| 
| 
| 
| ______________________________________________________
| Get Your Private, Free Email at http://www.hotmail.com