[RC5] What allows > 10,000 Tries a second?

Remi Guyomarch rguyom at mail.dotcom.fr
Thu Jan 7 03:51:45 EST 1999


On Mon, Jan 04, 1999 at 02:53:16PM -0400, Sean Watkins wrote:
> Hi,
> I've written a brute force version of Crack (for UNIX /etc/passwd) utilizing
> PVM (Parallel Virtual Machine). I've been looking at the distributed.net
> client for brute force DES key breaking and I'm curious about how
> it works.
> 
> Some of the clients can test some 1x10^6 keys a second. How is this
> possible? I admit, I know nothing of the DES algorithm internally.

Our bitslicer can check more than 1,000,000 keys per second on most
recent processors.

> In my version of Crack - basically I generate simple strings ie:
> 
> 	aaa
>  	aab
> 	aac
> 
> then crypt() the generated strings along with the original
> passwords salt (first 2 letters of password). Then compare the output
> with the original password. If they match, then I know the original password
> otherwise I know I have to try the next string in the sequence.
> 
> How can the distributed.net clients be testing that many keys a second? 
> Or have I misunderstood and that 1*10^6 number is the TOTAL keys
> per second? I am using a faster version of crypt() than available
> in libc.

First, the Unix crypt() function is not a pure DES algorithm. From
'man crypt' :

       It is based on the Data Encryption Standard algorithm with
       variations intended (among other things) to discourage use of
       hardware implementations of a key search.
       [...]
       The  DES  algorithm itself has a few quirks which make the
       use of the crypt(3) interface a very poor choice for  any­
       thing  other  than  password  authentication.   If you are
       planning on using the crypt(3) interface for a  cryptogra­
       phy  project,  don't  do it: get a good book on encryption
       and one of the widely available DES libraries.

Second, we're trying to find a 56-bit key which decrypt some known
ciphertext into some known clear text (the first 8 bytes of the clear
text is known).

You're trying to find a string, which after beeing modified by some
one-way hash function does encrypt a known cleartext into a known
cyphertext.

You're searching a human-readable and writable password, and we're
searching a machine-readable and writable 56-bit key.

We're not doing the same thing ! :-)

-- 
Rémi          Don't waste your computer's time. Distribute it!
      http://www.distributed.net/     http://www.distributed.net/cores/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 248 bytes
Desc: not available
Url : http://lists.distributed.net/pipermail/rc5/attachments/19990107/71ec5f9e/attachment-0001.bin


More information about the rc5 mailing list