[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20070704120235.GC13292@openwall.com>
Date: Wed, 4 Jul 2007 16:02:35 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: "incremental" mode vs. dumb exhaustive searches
On Wed, Jul 04, 2007 at 12:33:46AM +0100, Larry Bonner wrote:
> multi-core/parallel processing is one reason why a maxlength of 8 characters
> isn't sufficient today.
Frank is correct that "multi-core" is not a valid argument here (yet).
That's maybe just a factor of 4 (or whatever) improvement in performance.
However, increasing password length by one character increases the
search space by 10 to 95 times (depending on what your character set
is). If you try your candidate passwords in a "dumb" order, that's also
the increase in search time.
Full-blown distributed processing is another thing.
> also, on the arguement that jtr cracks passwords quicker, i never
> understood this arg really..
My guess is that you haven't run enough comparisons of JtR against other
tools (or against JtR itself forced into a dumb external mode). Also do
it on different hash types - both fast and slow ones.
> what difference does it make if jtr finds a password of 6 characters in
> length before
> another tool going through the exact same sequence, except in different
> order..ok, it finds it a little bit faster.
Maybe "6 characters" and "a little bit" weren't a good example: you must
have been using a fast hash of a password that is too simple, so it got
cracked quickly enough either way.
When you pick more complicated passwords and/or slower hashes, you will
likely have to interrupt a cracking run before all of your passwords are
cracked (and that's the point in cracking passwords with the purpose of
identifying weak ones!) At this point, you're going to have a larger
percentage of password hashes cracked with JtR's "incremental" mode than
you would with "dumb" searches that other tools implement. (Of course,
in either case you're supposed to run through "single crack" and wordlist
modes first - which JtR does when you run it with no options.)
Another real-world example is penetration testing, where you may only
have a single or a few password hashes to crack, but your time is also
very limited. If your hashes are salted, you can't reasonably use
rainbow tables (because they haven't been pre-computed for your specific
salt). So you run JtR or another cracker. With JtR's "incremental"
mode, your chances of getting your hash(es) cracked within the allotted
time are higher.
> at the end of the day, both crackers will/should find passwords anyway..
It depends on when "the day" ends for you.
> how is one password "weaker" than another?
>
> define a weak password based on its arrangement...
A weaker password is one that is likely easier or quicker for an
attacker to find. In practice, it means that a more common password is
the weaker one, because it makes sense for attackers to try more common
passwords first (and vice versa). Also, since human population is
finite and not all possible passwords have actually been used at least
once (and since we can't manage the complete set of possible passwords
anyway), passwords that are similar to common ones should be treated as
likely more common than those that are not even similar.
> for the sequence to process with:
> AAA
> BAA
> CAA
>
> as is done in passwords pro, you are only modifying the first byte and only
> the first 4 byte "block" of input...
> This has the advantage of allowing optimizations against poorly designed
> algorithms used in hashing algorithms, such as MD4 used for NTLM1.
That's a valid argument. In fact, there has been a change between JtR
1.6 and 1.7 in the ordering of candidate passwords produced with
"incremental" mode that helped reduce the number of operations needed on
average in DES key setup (for DES-based hashes). This specific change
did not make the order any less optimal in terms of trying more likely
passwords first. Further improvements in this area are still possible.
I must admit that the maximum key setup overhead reduction (or
precomputation, as with MD4-like hashes) is possible only by giving up
on "incremental" mode in favor of a dumb or hash-specific ordering of
candidate passwords. I might implement such a "dumb" cracking mode in a
future version of JtR for use in special / uncommon cases when the
entire keyspace is to be searched anyway and it is unimportant to get
more hashes cracked earlier. It will also help the "marketing" by
allowing for one-to-one comparisons of c/s rate against other tools.
(The downside is that people doing such comparisons will often disregard
the availability of the better "incremental" mode for its potentially
lower c/s rate, although it may be faster in terms of actual passwords
cracked in a fixed time.)
> if you use the pp method when attacking ntlm1 up to 10 characters in length,
> it is much faster than anything out there at the moment.
Are you referring to stored NTLM hashes or to on-the-wire NTLMv1
challenge/response pairs? If the latter, is the challenge fixed or not
(becoming kind of a "salt")? How much faster is PasswordsPro (or
SAMInside? not sure) compared to the code currently in the "jumbo" patch
for JtR 1.7.2? In terms of c/s rate? In terms of percentage of hashes
cracked, say, in 1 minute, 1 hour, and 1 day with a fixed number of
hashes loaded for cracking (and what number)? If you could do those
tests and post the results, that would be some useful information.
My expectation for your results:
The performance for NTLM hashes should be similar (or JtR may actually
be faster), due to Alain Espinosa's optimized code:
http://www.openwall.com/lists/john-users/2007/04/24/1
The performance for NTLMv1 challenge/response, if these are even
supported by either PasswordsPro or SAMInside, which is not immediately
clear from the InsidePro website, might be lower in JtR in terms of c/s
rate (this code is unoptimized and it uses OpenSSL libcrypto). I would
not be too surprised if this unoptimized code in JtR is slower than some
optimized implementation by a factor of 10.
However, even in the latter case I would expect JtR to outperform other
tools in terms of real-world passwords cracked in a fixed time,
specifically due to "incremental" mode. This is what I've seen happen
in practice in my tests (on other hash types, including LM hashes that
are similarly fast).
--
Alexander Peslyak <solar at openwall.com>
GPG key ID: 5B341F15 fp: B3FB 63F4 D7A3 BCCC 6F6E FC55 A2FC 027C 5B34 1F15
http://www.openwall.com - bringing security into open computing environments
--
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.
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.
