[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
```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
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

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