[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20060209005038.GA17261@openwall.com>
Date: Thu, 9 Feb 2006 03:50:38 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: Incremental Alpha Quagmire
Actually, this explanation got complicated enough that I got a few
things inconsistent. Here are the corrections:
On Tue, Feb 07, 2006 at 11:24:25PM +0300, Solar Designer wrote:
> 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
Here, the real and not the effective c/s rate should be used. If the
real c/s rate is 500,000 - like I had mentioned for a previous example -
then this would be:
(52 ** 8) * 4096 / 86400 / 365 / 500000 = 13887 years
Alternatively, the number of password hashes and not the number of
different salts should be substituted. For example, if there are
100,000 password hashes loaded for cracking (I picked a number this
large to reasonably use all of the 4096 salts and match the example
above), then we get:
(52 ** 8) * 100000 / 86400 / 365 / 12207000 = 13887 years
Yes, at 100,000 password hashes with only 4096 different salts, the
effective c/s rate would be up to 12 million. (It can be a little bit
lower in practice, but I used the exact value calculated under the
simplified model here.)
> 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
The same correction applies here - it should have been 500,000 c/s to be
consistent with the first example.
> 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. ;-)
There's another assumption I made - when there are matching salts, the
division by two in the first example:
(52 ** 8) / 86400 / 1000000 / 2 = 309 days
(to calculate the average time between guesses) is not strictly correct,
but it gives a good estimate for as long as only a small portion of the
keyspace is searched. The reasons for this are a bit too subtle, so I
won't go into them unless you ask.
--
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.
