Algorithm

[Spardan]

Hey guys... thought I might be able to pick your brains with this...

I'm developing a distributed password cracker, in order to look at different load balancing algorithms. Most, such as DJohn and LC5, break up the task beforehand and you then load each machine in the cluster with their portion of the task and wait for them to complete. I'm aiming to do this dynamically.

So far, I have a recursive algorithm to generate all the combinations of a character set for a set string length, e.g., for a charset of "ab" and a string length of 3, the algorithm will generate all combinations of a and b in a 3-character string.

I'm doing this with 2 arrays. One contains the character set, the other is an integer array, the length of the string, with all bits initialised to 0.

The algorithm works by incrementing the integer array as if it were a counter, and generating the string from the values in the arrays, such as:

char array : 0 | 1 |
a | b |
int array 0 | 0 | 0 | so string is aaa
int array 1 | 0 | 0 | so string is baa

and so on.

This is all working fine though it may seem a bit kludgey to some. My problem is that I need to find a way to break up the possible variations of the int array to pass them out dynamically, e.g. tell one machine to start from 0 | 0 | 0 | and end at 1 | 1 | 0 |, tell another to start at 1 | 1 | 1 | and end at n | n | n |

I'm guessing this needs recursion too, as the single machine method I've developed does (in order to increment an n length array successfully), but I can't see it, as doing it this way basically means I'm working with different-base number systems for different string lengths.

Any ideas at all, no matter how random would be appreciated, or if anyone knows a forum full of applied math geeks who won't kill me for not knowing calculus, that would be great.

[CompGeek01]

I'd like to help you, but I'm not sure a password cracker is the best application for distributed systems programming.

[Spardan]

Fair enough. If it's the ethics of the thing that concern you, I'd point you to David Bernick's talk on distributed password cracking at the Hope 5 conference: http://www.the-fifth-hope.org/hoop/5hope_speakers.khtml where he talks at length on legitimate uses of such a tool, particularly his own work, where he uses various closed clusters to unencrypt evidence for use in criminal trials. (No, I'm not going to wave the kiddy porn banner at this point - the case for is strong enough without having to be crass).

Distributed projects like this one have been used to expose weaknesses in many algorithms - it was proven that 40-bit encryption was of no value to anyone wanting to encrypt anything sensitive in one RSA challenge; only recently SHA-1 has been shown to have collisions.

I did wonder if I'd get the usual concerns regarding anything that can be used both nefariously and for the common good, but I decided not to lie - that would suck, because then people would be helping me do something they may not agree with.

As has been asserted by the pioneers of open cryptography, from Whitfield Diffie through to Bruce Schneider, Ronald Rivest to Phil Zimmerman, and as is (hopefully) common knowledge in 70%-80% of the computing industry, security through obscurity does not work.

If it could be shown once and for all just how weak certain implementations of password algorithms are, they would be rejected at the cost of the developers (more time/expense) and at the benefit of the end users (better security) because users would demand it.

If by using tools like this we can get rid of that pesky LM password implementation for once and for all, for example, I (and a lot of other people) would consider the 'opening of pandora's box' (which in this instance is hardly the case anyway) more than worth it.


That said, this is my opinion, naturally you're entitled to your own [how kind of me! ;)] and if you have read this, thanks, and I hope it gave you some interesting issues to consider.

By the way, for what I'll be doing, it's gonna be fast enough to have the Load Balancer simply cycle through the array - there's no other processing needed, just to get the array to the next position - and this, with the latency of message passing, means it'll be plenty fast enough, even once the dynamic load balancing algorithms are implemented.

Thanks, and regards,

TDS