Date: Thu, 19 Jan 2006 19:15:23 +0300 From: Solar Designer <solar@...nwall.com> To: john-users@...ts.openwall.com Subject: Re: Re: salt manipulation On Wed, Jan 18, 2006 at 07:41:59PM +0000, Radim Horak wrote: > The reason for c/s values in benchmarks being different for > multiple salts is not easy to explain. John uses algorithms optimized for > multiple "parallel" hashing operations with the use of MMX. It is therefore > little faster to use multiple salts in single run then multiple runs with single > salt. The c/s values reflect this effectivity in the benchmarking values. Actually, the difference in performance for single vs. multiple salts comes primarily from the key setup "overhead". Key setup is done once per candidate password (cipher key) to try, regardless of the number of different salts loaded. When attacking multiple salts at once, each performed key setup is re-used for hashing the candidate password against each of the loaded salts. You can think of key setup as the part of the hashing operation that is not dependent on the salt, -- so there's no reason to perform it for each salt separately. As it relates to John exploiting the parallelism inherent to password cracking, John does that regardless of the number of different salts. For example, the implementations of DES-based crypt(3) and LM hashes try 64 candidate passwords in parallel on x86/MMX. In order to also benefit from being able to do key setup only once per candidate password (with multiple salts loaded), John has to keep the results of key setup (some intermediate values - neither plaintext passwords, nor final hashes) in its buffers for all 64 candidate passwords and re-use those for hashing against each salt. If anyone is curious, even on architectures where the use of a bitslice implementation of DES is not feasible, such as on plain x86 without MMX, John does this sort of buffering of DES "key schedules" in order to keep both the key setup and the salt setup out of the inner loop. If it prepares N key schedules, then it needs to do the salt setup N times less often. And with M salts, it also needs to do the N key setups M times less often. For this algorithm, the value of N may be arbitrary (unlike with bitslice DES, it does not have to be a multiple of the processor word size in bits). N=100 eliminates 99% of the salt setup overhead. In practice, John uses values of N from 64 to 256, or sometimes smaller than 64 when fewer candidate passwords are readily available to try. -- 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.