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.