
Date: Tue, 7 Feb 2006 23:24:25 +0300 From: Solar Designer <solar@...nwall.com> To: johnusers@...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 8character 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 betterlooking "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