[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20060207202425.GB13018@openwall.com>
Date: Tue, 7 Feb 2006 23:24:25 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: Incremental Alpha Quagmire
On Mon, Feb 06, 2006 at 02:33:12PM -0800, Arias Hung wrote:
> On Mon, 06 Feb 2006, Solar Designer delivered in simple text monotype:
>
> > Oh, and if you're going to be restricting John to 8-character long
> > passwords, you really don't want it to consider all characters equally
> > probable. Just do some simple math:
> >
> > (52 ** 8) / 86400 / 1000000 / 2 = 309
[...]
> (52 ** 8) <-- Sorry with my unfamiliarity with this notation but i'm assuming
> this is 52 * 8 * 8 ?
As you've correctly figured out later, this is 52 raised to the 8th
power. This is the Fortran notation. I tend to avoid the better-looking
"52 ^ 8" because of the ambiguity resulting from the C meaning of the
caret character (bitwise exclusive OR).
> 86400 <-- seconds in a day
Correct.
> 1,000,000 < --- average combinations/second based on current a hardware bm's
Yes, but for multiple salts the _effective_ rate would apply here. So
if you have a CPU capable of, say, 500,000 c/s raw (as output by
"john --test") and you load twice more password hashes than there are
different salts, then your effective c/s rate (reported while cracking)
will be around 1M c/s.
> 2 < --- ? Not sure what the division by two is for
We're interested in the average time until we have a guess, assuming
that the order in which we try candidate passwords is in no way
correlated with their probabilities. Hence we divide the time that
would be needed to search the keyspace exhaustively against one salt
by two.
> Also, where are you factoring in the number of salts 4096 ?
I don't need to. Instead, I choose the appropriate words in the
statement I make:
> > This means that at an effective rate of 1M c/s, you will be getting
> > roughly one password cracked per year.
Note that I am not speaking of the time it'd take for the John run to
terminate, but rather of the expected average time between guesses,
assuming that all passwords actually fall somewhere within the keyspace
that we search.
If we would be interested in the time it'd take for John to run to
completion, assuming that no passwords get cracked (yes, that's quite a
different assumption) and all the possible 4096 salts are in use, it
would be calculated as follows:
(52 ** 8) * 4096 / 86400 / 365 / 1000000 = 6944 years
In practice, passwords will be getting cracked (in fact, all of them
should get cracked eventually, per our previous assumption). If the
number of remaining password hashes would be decreasing linearly (which
would be the case if there's no correlation between the order in which
candidate passwords are tried and their probabilities) and there's
exactly one password hash per salt (not realistic), then we should halve
the number:
(52 ** 8) * 4096 / 2 / 86400 / 365 / 1000000 = 3472 years
If there are matching salts, then both the number of salts will be
decreasing more slowly and the effective c/s rate will be dropping the
longer John runs - so the total time will be larger than one calculated
using the above expression. However, having matching salts helps
achieve a higher effective c/s rate initially, so the 1M c/s might need
to be replaced with something larger, too, reducing the actual time.
Yes, the previous estimates also assume that the effective c/s rate
stays constant - which is not the case in reality. However, since
you're not going to let this run for thousands of years, most of your
passwords will remain uncracked in the foreseeable future, and it is
reasonable to assume that the effective c/s rate is almost constant. So
the success rate estimate (roughly 1 guess per year) is correct for your
lifetime. ;-)
However, you might be able to achieve a higher success rate by improving
your effective c/s rate. If you pick only the salts for which there are,
say, 20 or more password hashes ("--salts=20"), then your effective c/s
rate will be 10M+ initially (assuming the same raw rate of 500,000 c/s),
so you will be getting one password cracked per month or even better.
Does this explanation help, or is it overly complicated?
--
Alexander Peslyak <solar at openwall.com>
GPG key ID: B35D3598 fp: 6429 0D7E F130 C13E C929 6447 73C3 A290 B35D 3598
http://www.openwall.com - bringing security into open computing environments
Was I helpful? Please give your feedback here: http://rate.affero.net/solar
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.
