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.