[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20060119161523.GA16513@openwall.com>
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.
