Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 6 May 2015 20:49:38 +0300
From: Aleksey Cherepanov <>
Subject: Re: optimization idea for salted hashes

On Sun, May 03, 2015 at 08:09:38PM +0300, Solar Designer wrote:
> On Sun, May 03, 2015 at 01:02:42AM +0300, Aleksey Cherepanov wrote:
> > It is possible to lift some computations from the loop for some salted
> > hashes.
> > 
> > As the base, I consider a loop over all pairs salt + candidate. So if
> > a part of code is computed only for salt not depending on candidate
> > then it is possible to precompute it once for each salt. Similarly if
> > a part of code is computed only for candidate not depending on salt
> > then it may be computed once per candidate (it may be easy to
> > implement if we have "for each candidate { for each salt { ... }}"
> > structure of the loop).
> [...]
> > Is the optimization implemented in john?
> Sure.  Also, both salt setup and key setup may be moved out of the inner
> loop at once.  In fact, this was a reason to support and use higher
> max_keys_per_crypt even back when early JtR supported only descrypt, and
> before it was bitsliced.  With moderately high max_keys_per_crypt, the
> algorithm is roughly as follows:
> 	for each key
> 		set_key()
> 	end for
> 	for each salt
> 		set_salt()
> 		crypt_all()
> 	end for
> where crypt_all() may have an internal loop over previously prepared
> keys.  When there's just one salt, set_salt() is done just once, but
> that's a minor detail (with large max_keys_per_crypt, the salt setup
> overhead is low).

Some thoughts on design of formats:

At first, it looked natural to put the code that depends only on
password into set_key() but then I realized that set_key() may mangle
only 1 candidate while it would be more efficient to collect a pack
and process it. So the processing should be in crypt_all() that may
work with packs. So for salted hashes, a format have to store a flag
to indicate that a candidate is already processed.

Though the flag may be needed for non-salted hashes too for other
reason: we can't mangle candidates in-place without it: get_key() may
be called right after set_key() (at least during self test) and after
crypt_all() so get_key() have to decode the candidate back after and
only after crypt_all() and not right after set_key() when the
candidate is not mangled yet.

So raw-sha512 with sse does padding and alters endianity in set_key()
storing only the result in global buffer, in get_key() it does the
reverse to return candidate to john. Moving padding to crypt_all()
that modifies the global buffer needs the flag to make the reverse
actions optional.


Aleksey Cherepanov

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.