[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20050901045759.GA990@openwall.com>
Date: Thu, 1 Sep 2005 08:57:59 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: Using john des routines for 3des (or straight des) cracking
On Thu, Sep 01, 2005 at 05:14:57AM +0200, dvorak wrote:
> What is missing from the bitslice implementation?
> Just decryption and the permutations?
Yes, and it has the input blocks (all 0's or the LM magic) hardcoded.
It appears that you have the skills to overcome this hurdle. :-)
> I think the permutation are not needed since they should cancel each other
> out in ede mode.
>
> basicly it should do
> input -> 3des-ede-decrypt -> compare to something
> input and the something can be pre-permutated.
>
> And decryption should only be a change of order in the subkeys used so
> with some luck i can find that.
Yes, you're right. But you may need the initial permutation performed
on your known plaintext and on the ciphertext once at startup (that's
the precomputation you're referring to above). Ideally, John would do
that for you. This is why I suggested that you use the DES_std.[ch]
functions for that like John does for undoing the final permutation with
DES-based hashes.
> OpenSSL routines are way too slow (in my tests they spent about 40-50%
> in the key setup phase, presumable john is much faster in this.
Actually, while bitslice DES is indeed much faster (you can check more
candidate passwords per second), you should expect that a large
_percentage_ of CPU time will be spent on key setup "overhead" with it.
To give you an idea, the current development versions of John spend 50%
to 80% of CPU time on key setup with LM hashes (which are single DES
encryptions). The larger your word size is, the larger the key setup
"overhead" _percentage_ would be (because actual DES encryption becomes
even cheaper while key setup cost remains almost the same).
For 3DES, key setup will be responsible for a smaller percentage of CPU
time, perhaps 25% to 60%.
You may further improve this (a lot!) by optimizing the order of
candidate passwords to try for the smallest number of bits to change
from whatever password occupied a given bit layer previously. In fact,
I am considering to enhance John such that it would "interleave"
candidate passwords it produces with "incremental" mode, specifically
for better performance at fast bitslice DES-based algorithms.
For others reading this: these large "overhead" percentages do not apply
to crypt(3) hashes, which use multiple iterations of DES. There, the
cost of key setup is typically around 10% of the cost of actual hashing,
and key setup only needs to be done once for all salts. So it's only
fast non-iterated DES-based hashes, such as the LM hash, and DES/3DES
encryption, which may benefit from further key setup optimizations a lot.
> thanks for the response in case i am able to get something useable i'll
> post an update here.
Yes, please.
--
Alexander Peslyak <solar at openwall.com>
GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598
http://www.openwall.com - bringing security into open computing environments
Was I helpful? Please give your feedback here: http://rate.affero.net/solar
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
