[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 23 Dec 2011 07:33:07 +0530
From: piyush mittal <piyush.cse29@...il.com>
To: john-dev@...ts.openwall.com
Subject: Re: Bit slice implementation of DES based hashes
>
> A straightforward approach would be to have a get_hash() function that
> would for a given index (bit layer if we're talking bitslice) return the
> full computed hash value.
>
Bit layer here means to say any perticular Nth bit of all words present.
On Fri, Dec 23, 2011 at 1:25 AM, Solar Designer <solar@...nwall.com> wrote:
> On Thu, Dec 22, 2011 at 11:31:14PM +0530, piyush mittal wrote:
> > > Also, do you understand why the get_hash() functions process a few
> > > initial elements of B[] only?
> >
> > No this I am not getting.Why here only B[0] have taken?
>
> Not only B[0] is taken, but several initial elements of B[] are - from 4
> for DES_bs_get_hash_0() to 27 for DES_bs_get_hash_6(). (I am referring
> to 1.7.9's revision of these.)
>
> > Is here just 1st bit of each hash is checking??
>
> JtR has several algorithms to check whether the computed hash matches
> one of those loaded for cracking or not. Which one of these algorithms
> is used depends on the number of loaded hashes with a given salt.
>
> A straightforward approach would be to have a get_hash() function that
> would for a given index (bit layer if we're talking bitslice) return the
> full computed hash value. For DES-based hashes, this function would
> typically return a 64-bit value. With a bitslice implementation, this
> value would be based on all elements of B[] (with one bit taken out of
> each element). JtR would then compare this value against each hash
> loaded for cracking (or each with the current salt, if applicable).
>
> But this would be inefficient, so JtR does not do it. Instead, when the
> number of loaded hashes (which share a given salt) is small, it calls
> cmp_all() to compare one of the loaded hashes against all recently
> computed hashes. For example, a bitslice implementation on a machine
> with 128-bit SIMD vectors (e.g., x86-64 with SSE2) may compute 128
> hashes at a time. The corresponding cmp_all() function compares one
> loaded hash against all of the 128 computed hashes in fewer than 128
> iterations. On x86-64 it does this in 12 iterations on average (this is
> 2*log2(64)).
>
> Now, when the number of loaded hashes is large (for the current salt, if
> applicable), even the cmp_all() algorithm is not good enough. We'd have
> to be calling this function for each loaded hash, which would be
> time-consuming. Thus, one of the get_hash*() functions is called for
> every computed hash instead, returning partial hashes (4-bit to 27-bit
> in version 1.7.9). This function's return value is used as array index
> to identify the hash bucket that might contain the computed hash (if we
> have a full match). Typically, the get_hash*() function and the hash
> table size to use are chosen such that very few loaded hashes share a
> hash bucket, if at all. In fact, some hash buckets may be empty (in
> those cases, it is instantly determined that a computed hash does not
> match any of the hashes loaded for cracking).
>
> If the number of hashes computed at a time is N (128 in the example
> above) and the number of hashes loaded for cracking that share a given
> salt is M, then complexity of the two algorithms is roughly:
>
> log2(N) * M for the cmp_all() algorithm
> N for the algorithm involving get_hash*()
>
> As you can see, the former is preferable for small M and the latter for
> large M.
>
> In either case, if the algorithm indicates a likely match, it might not
> tell us which of the loaded hashes was cracked and what the
> corresponding index is (such that we can retrieve the corresponding
> plaintext password that was tested). Additionally, partial hashes may
> be used with these algorithms (e.g., 32-bit), which is why I wrote
> "likely". Thus, in those relatively infrequent cases, further checks
> are done with cmp_one() and cmp_exact() to confirm a match and to
> identify which hashes got cracked (yes, more than one may get cracked
> with one set of hash computations).
>
> Do you see why get_hash*() do not need to return the full hash values?
>
> > and Does DEPTH here represents total number of words present??
>
> No. DEPTH is a macro that may expand either to empty string or to
> [depth]. The latter is used when we're dealing with SIMD vectors larger
> than machine word size - e.g., 128-bit with SSE2, whereas the native
> word size is just 64 or 32 bits. In get_hash*() functions, we need to
> extract some bits from just one bit layer. We do this with regular
> (non-SIMD) operations and machine words (in fact, even these are wider
> than necessary since we're dealing with just one bit layer in these
> functions). Thus, we split the bit layer index into two components:
> native machine word "depth" (which word in a SIMD vector we're dealing
> with currently) and bit position in that word. You can see this in the
> init_depth() macro:
>
> #define init_depth() \
> depth = index >> ARCH_BITS_LOG; \
> index &= (ARCH_BITS - 1);
>
> Alexander
>
--
Piyush Mittal
Department of Computer Science and Engineering
National Institute of Technology,Rourkela
INDIA
Content of type "text/html" skipped
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.
