Re: Brute force attacks

["Ryan Russell" <ryanr () sybase com>]

This question was asked at Defcon of one of the
guys who designed the DES cracker for EFF.

Presumably he addresses this in the book, found at:

http://www.replay.com/mirror/cracking_des/cover.html

But I'll attempt to summarize:

You have to know what the output is ahead of time.

To qualify that a bit, you have to know exactly what it is,
suspect what it is, or have an idea what the general format is.
You're only working with 8 bytes at a time, so you make
some guesses about those 8 bytes.

The example the guy used was an IP stream, or an e-mail.
Typically, there is some fixed format to the start of a particular
kind of stream.  Say, perhaps a TCP header or a mail header.
Many times, you know what is it, or can guess what it is.

The other possibility is that you have some idea what the output
is, say you expect it to be ASCII.

So, you program your cracker to look for certain patterns.  The
EFF guys looked for ASCII.  Then, while it's working, the cracker
comes up with what it thinks is a candidate for a good key, and
hands it over to some controlling computer or person.  The controller
then tries to decrypt the whole message with the key, and sees
if the output looks reasonable.

Turns out the chances of two different DES keys decrypting an
encrypted stream of any reasonable length to two different
reasonable looking things is really small.

                         Ryan



The question I have is how do I check my output to validate that I have
the correct key?