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

On Wed, May 06, 2015 at 08:49:38PM +0300, Aleksey Cherepanov wrote:
> 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.

Yes.  Having the processing directly in set_key() is a bit outdated.
It worked well in simple cases, but not so well e.g. with the new
bitslice DES key setup in 1.7.9+ and with OpenMP.  Continuing this
example, what the bitslice DES code does now is have set_key() only
transpose the chars matrix, because it's roughly same cost per key as a
strcpy()-alike would be anyway, and is trivially undone in get_key(),
and have crypt_all() take care of the bit-level processing.

> 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.

Yes, although I don't recall us having this in any format currently.

There are saltless formats where set_key() doesn't fully setup the key,
but crypt_all() finishes that (to have more of the processing within an
OpenMP parallel section or/and benefiting from SIMD or/and interleaving).
A notable example is LM.  It works like I described above, but unlike
descrypt it lacks the flag you mentioned, because crypt_all() is only
called once.  The problem you mentioned does not arise there because the
key setup isn't finished in place: we read from xkeys and write to K.
get_key() would read from xkeys regardless of whether it's called before
or after crypt_all(), and it will produce the same result.

> 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.

I haven't looked into that format's specifics, but what you describe
sounds like one valid way to handle the problem.


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.