[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150506174938.GA22997@openwall.com>
Date: Wed, 6 May 2015 20:49:38 +0300
From: Aleksey Cherepanov <lyosha@...nwall.com>
To: john-dev@...ts.openwall.com
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.
Thanks!
--
Regards,
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.
