
Date: Thu, 9 Feb 2006 03:50:38 +0300 From: Solar Designer <solar@...nwall.com> To: johnusers@...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