[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20111017010131.GA30732@openwall.com>
Date: Mon, 17 Oct 2011 05:01:31 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: filter performances
On Sun, Oct 16, 2011 at 11:11:15PM +0200, J?r?me Loyet wrote:
> I have a single traditional DES password to bruteforce. I know its
> policy: 8 characters long (or more) and it uses at least one lower
> case, one upper case, one numerical and one "other" char.
As others have pointed out (thanks!), the length must thus be exactly 8
(due to truncation), but you don't really know whether those 8 characters
alone satisfy the policy (also due to truncation). On the other hand,
the policy might have been applied in a hash type aware way (e.g.,
passwdqc does that when the max=8 option is specified to it).
> If I'm bruteforcing using the mode All (with a fixed 8 chars len) I
> have 95^8 = 6634204312890625 possibilities
>
> I want to reduce the number of tries as I know the policy. I have
> 95^4*26*26*33*10 = 18170005425000 possibilities
As Brad has pointed out (thanks!), this number is wrong. The correct
one appears to be 3025989069143040 combinations, which is roughly 45% of
the original total. I computed it with the attached comb.c program,
which I had tested with smaller settings (comparing its output vs.
actual results).
> I'm using OpenMPI to parralize to 2 servers (16 cores each) and I can
> compute around 40387K combinations per sec.
It sounds like those machines are 8-core each, not 16-core. Perhaps
they use SMT, so have two logical CPUs per core. Indeed, you do need to
make use of all logical CPUs for optimal performance (so run 16
processes per machine, 32 total), but the performance will be that of 8
cores per machine (16 total), not 16 per machine (32 total).
> Which means the following ETA for trying all the passwords
>
> 6634204312890625 / 40387000 / 60 / 60 / 24 = 1901 days
Right. But you should expect your password to be cracked much sooner
than that. Even if the password were cryptographically random, it'd
take half that time on average. But if the password is human chosen,
then all.chr's statistics should help get it cracked much sooner - quite
possibly in a month.
> 18170005425000 / 40387000 / 60 / 60 / 24 = 5 days
Corrected to:
3025989069143040 / 40387000 / 60 / 60 / 24 = 867 days
However, on one hand you should similarly expect the password to be
cracked after a lot fewer candidates tried, but on the other applying
the policy slows the c/s rate down.
> The first case cannot be considered :)
> But the second case is far more easy to considered
With the math corrected, they're actually very similar to each other.
In both cases, your best bet is to rely on smarter searches - and in
fact incremental mode is quite smart. :-)
> To filter the password not corresponding to the policy, I've tried to
> apply a filter similar to the optimized one described in
> http://www.openwall.com/lists/john-users/2009/10/28/11
You didn't post your code. I've attached my take at it (policy4.conf) -
it might be slightly more optimal than yours.
> But the performances are horrible. Here is a small benchmark (one
> single john instance is running - aka one core, one server):
>
> [root@...xxx run]# ./john -i:All8 --external=test --session=test pass.txt
> Loaded 1 password hash (Traditional DES [128/128 BS SSE2-16])
> guesses: 0 time: 0:00:00:16 0.00% c/s: 5733 trying: cow_ie2M - cadry S9
> guesses: 0 time: 0:00:01:26 0.00% c/s: 36918 trying: ccosh-L3 - ccohB#40
[...]
> guesses: 0 time: 0:00:20:35 0.00% c/s: 85975 trying: 3dygut N - 3dygkb-F
> guesses: 0 time: 0:00:26:28 0.00% c/s: 86144 trying: 5myaf0$K - 5myon St
>
>
> [root@...xxx run]# ./john -i:All8 --session=test pass.txt
> Loaded 1 password hash (Traditional DES [128/128 BS SSE2-16])
> ... c/s is constant around 2408k
> guesses: 0 time: 0:00:00:53 0.00% c/s: 2408K trying: 323akbab - 323agemc
>
>
> Without filter I can compute 2408K and with the filter enabled the
> computation rate is much lower.
This means that you're actually filtering out the majority of candidate
passwords that incremental mode generates. This is no surprise: early
on, incremental mode focuses on more common passwords, which tend not to
meet the policy. The reported c/s rate is for the few policy-compliant
passwords that remain after filtering.
Now recall that we calculated that on average 45% of candidate passwords
will pass, for a "full" run of JtR (which would take years). This means
that the c/s rate will increase - a lot - if you run John in this way
for much longer.
In order to see whether the filtering is beneficial or not, you need to
apply a filter that is of a similar processing cost, but that will allow
all passwords to pass. If the resulting c/s rate is greater than 45% of
the original, then the filtering is likely beneficial even in the long
run. And it is likely beneficial early on even if it slows the c/s rate
down to below 45% - e.g., if it filters out 99% of passwords that would
be tried in the first hour, but only slows things down by a factor of
30 during this same hour, that is nevertheless beneficial (3 times
quicker progress), under the possibly wrong(!) assumption that the
policy was in fact being correctly enforced on the target system.
> (And I don't understand why the c/s is increasing and then stall).
This suggests that passwords generated by incremental mode during this
time (the first 26 minutes of your test run) were mostly similar to each
other, without significant increase in the percentage of policy
compliant passwords after the first few minutes, during which such
increase was seen. You should expect another increase later on.
> Is there a way to achieve my goal with the same performances ?
I'm afraid not. Even if we implement some sort of policy matching in
JtR itself, there will be some performance hit from it - albeit a much
lower hit than external mode's.
I hope this helps.
Alexander
View attachment "comb.c" of type "text/plain" (746 bytes)
View attachment "policy4.conf" of type "text/plain" (609 bytes)
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.
