
Date: Sat, 13 Oct 2007 12:51:07 +0400 From: Solar Designer <solar@...nwall.com> To: johnusers@...ts.openwall.com Subject: Re: List.External:Parallel section in the example john.conf On Fri, Oct 12, 2007 at 11:03:43AM +0200, Francesco Minafra wrote: > As I am not so good at figuringout how algorithms work > "on the fly", I have reproduced the behavior of the filter() > function in a small perl program: ... > Please correct me if I am wrong, but I see from the output that there is > an overlap on the keyspace assigned to each node. As you had expected, you're wrong. There's an overlap in the values of "number", but not in the candidate passwords tried. The output of your (first) Perl script is (with some abbreviations): We are on node 1 Initial value for number is: 0 Number is now: 0 1 modulo 4 = 1 2 modulo 4 = 2 3 modulo 4 = 3 Number is now: 4 5 modulo 4 = 1 ... We are on node 2 Initial value for number is: 1 1 modulo 4 = 1 2 modulo 4 = 2 3 modulo 4 = 3 Number is now: 4 5 modulo 4 = 1 6 modulo 4 = 2 7 modulo 4 = 3 Number is now: 8 9 modulo 4 = 1 Notice how with your Perl script, the first node would be trying the very first candidate password (the line "Number is ..." is printed right away), then the 5th, and so on, whereas the second node would skip the first 3 candidate passwords and would only be trying the 4th. So there's no overlap between the nodes. > This can be prevented by introducing a suitable "offset": Now this produces an overlap: We are on node 1 Initial value for number is: 0 Number is now: 0 1 modulo 4 = 1 2 modulo 4 = 2 3 modulo 4 = 3 Number is now: 4 ... We are on node 2 Initial value for number is: 1 Number is now: 1 2 modulo 4 = 2 3 modulo 4 = 3 4 modulo 4 = 0 Number is now: 5 As you can see, both nodes would be trying the same candidate passwords  the first, 4th, and so on. The values of "number" are irrelevant. > and in the john.conf I used the following (e.g. for the fifth node): Yes, you broke it too. This "trivial parallel processing example" (as the comment says) has other limitations and drawbacks  just not the "bug" you thought you had discovered. Specifically, it won't work right for "single crack" mode (not that you need any parallel processing with that mode) and it might not work right for restored sessions. Also, it is only efficient with slow hashes, many salts, and/or few nodes. With fast saltless hashes, such as LM hashes and those supported with some contributed patches, it is too costly to generate but filter out candidate passwords.  Alexander Peslyak <solar at openwall.com> GPG key ID: 5B341F15 fp: B3FB 63F4 D7A3 BCCC 6F6E FC55 A2FC 027C 5B34 1F15 http://www.openwall.com  bringing security into open computing environments  To unsubscribe, email johnusersunsubscribe@...ts.openwall.com and reply to the automated confirmation request that will be sent to you.
Powered by blists  more mailing lists