Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 11 Apr 2020 07:50:37 -0500
From: Kevin Yochum <kevin@...ewerx.com>
To: john-users@...ts.openwall.com
Subject: Re: Can incremental mode be started in the middle?

On Sat, Apr 11, 2020 at 5:23 AM Solar Designer <solar@...nwall.com> wrote:
>
> On Fri, Apr 10, 2020 at 04:59:36PM -0500, Kevin Yochum wrote:
> > I'm experimenting with cracking a hash with a password that is known to be
> > an apparently random mix of upper ASCII, lower ASCII, and digits.
>
> If it's in fact random and with a uniform distribution, then e.g. an
> all-lowercase password is just as likely as any other.

Statistically, this is correct, in the same way that the numbers 1, 2,
3, 4, 5, 6 are just as likely as any other lottery combination, but
the first successive numbers have never been drawn in the history of
any lottery system. It is possible but has never occurred.

> > While these are possible solutions, for my test case, it is highly unlikely
> > that starting with all lower case will be the fastest solution.
>
> What makes you think so?

I know my problem space. These are sample known (previously cracked) passwords:

H5EWip7gw916385
UdAjKX4vRS2mt2
GgDjZEVsOXh0Fb
Pz7ocjGw1liQ7u
6AdI1n9VYwDMOR
G2eQNRy0t8ETU7Q
XG79hJEpa1
HvTn9axLHH
KHx3khpRdILHvYE

There are more uppercase letters (61) than lowercase letters  (45) and
the digits (27) are in the middle, not just at the end. If I have to
wait through the all-lowercase options with digits at the end before I
get to the options that are more likely in my problem space, am I not
waiting for at least 50% of the possible incremental mode combinations
that are almost certainly not the solution?

> You might be thinking that if the password is a "random mix of upper
> ASCII, lower ASCII, and digits", then it's unlikely that it's all lower
> case.  For random passwords from that possible password space, assuming
> a uniform distribution, that is in fact true.  However, it does _not_
> follow that "it is highly unlikely that starting with all lower case
> will be the fastest solution."  You need to consider not how likely it
> is that the password is of a particular pattern, but how likely each
> candidate password within that pattern is to be the one, as compared to
> the likelihood of each candidate password of another pattern being the
> one.  For a uniform distribution, these probabilities are the same.

If this were an academic exercise, I would completely agree. I don't
think that my problem space is a uniform distribution.

Based on the known passwords, I am fairly certain that the random
password is not all lower case. In fact, in my original query (below),
I said that I would eventually want to try the all-lowercase
passwords, but I wanted to try the more likely combinations first. I'm
trying to play the odds by configuring incremental mode to test the
more *probable* combinations, not just go through all of the
*possible* combinations because JtR can.

> Moreover, if there's even the slightest chance that the password is not
> uniformly random, but is from a distribution skewed even very slightly
> towards what was seen in other passwords before, then incremental mode's
> strategy is preferable.
>
> In other words, incremental mode's strategy generally does not hurt, and
> might help.
>
> However, you did not mention your hash type.  If it's a fast hash (where
> you're computing millions of hashes per second) and you're reasonably
> confident that incremental mode's strategy isn't helpful in your case,
> then you might want to switch to mask mode, which might be quicker at
> generating candidate passwords (and for fast hashes is able to do so on
> device side, such as on a GPU).  You'll need to compare the p/s rates.

It's certainly a slow hash. On my test hardware (which is a known
problem), I'm only getting 78 p/s. After 17 hours, I'm only up to
"siesendo..siellity" in incremental mode. (When I have the rules
configured the way I want them, I'll move the configuration to faster,
more expensive hardware.)

> > Rather than
> > start here, I'd like to start with a more random mix of upper and lower
> > ASCII and digits, then try all-lower options later, if needed. Is there any
> > way to tell JtR to start in the middle and work outward to the ends, or
> > something similar?
>
> Officially, no.  Unofficially, you may edit the .rec file.  I recommend
> that you don't.
>
> If you insist, you may try mask mode and include e.g. an uppercase
> letter somewhere in your mask, then move it to another position, etc.
> My opinion, though, is that this de-optimization is pointless, as I
> tried to explain above.
>
> For very slow hashes, you may also try combining incremental mode with
> an external filter - see the default "[List.External:Policy]" example.
> You can first run with the policy enforced, then with the policy
> inverted (anti-policy enforced).  Again, based on your description, I
> find this pointless, and a waste both of your time and of CPU time.
>
> Such policy enforcement would potentially make sense if you reasonably
> expect that a similar policy was also enforced when the password was
> generated or when it was set (that is, the password is _not_ entirely
> random, but e.g. is random with restrictions).  However, even in that
> special case the point is moot, see:
>
> https://openwall.info/wiki/john/policy
>
> Alexander

Very well. I'll take all of that as a "No. JtR can't start in the
middle." Thanks!

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.