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.