[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20071013085107.GA12581@openwall.com>
Date: Sat, 13 Oct 2007 12:51:07 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...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 figuring-out 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, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.
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.
