Multi-stream password unlocking algorithm

I made a multi-threaded C ++ program to break 7 characters long passwords (lowercase only) using a brute force algorithm.

My algorithm basically consists of 7 nested loops going from a to z and checking every possible combination.

Right now, I divide my work this way:
If I have 3 work streams,
Topic 1: axxxxxx - ixxxxxx
Topic 2: jxxxxxx - rxxxxxx
Topic 3: sxxxxxx to zxxxxxx

So the 3 threads will keep going and looping until they find a match.

The main thread will wait for the first thread to return.

My question is, is this the best way to split the work between my threads? Do you know how I can be more efficient?

Also, even if this is not the main body of my survey, can you think of a more efficient way than 7-loop iteration?

(Note that this program is for a school project, not for cracking passwords)


source to share

3 answers

If all keys are equally likely, and if the cost of evaluating a key is the same for each key, and if each thread can expect to be assigned to one processor without very many interruptions (for example, your process is the only processor intensive one is running), partitioning the keyspace evenly, as you did, would be very efficient.

If some of these assumptions are not valid, a more flexible way to structure the program is for one thread (producer thread) to pass key ranges for 1 or more consumer threads for processing. As soon as the specified thread exits, it will return to the manufacturer and request a new key range for analysis.

There's some overhead in the producer / consumer pattern, but it's more flexible.



I would look at intel TBB

I would use a construct parallel_for

on the outer circle and have an atomic variable to signal its detection.

This is pretty trivial using lambdas.

tbb::blocked_range<char> rng('a', 'z');
tbb::parallel_for(rng, [&](tbb::blocked_range<char> rng){ 
     for(char a=rng.begin(); a!=rng.end(); ++a)
         //a is your top level character


The advantage of using TBB is that, as mentioned in another answer, it is that if one thread ends before the other TBB has a work-stealing mechanism built into it to allow a fast thread to run out of a slower thread.



You must use the manufacturer template. Having a queue (Thread safe) for generating password candidate and consumer threads This should be more flexible.

There is nothing wrong with generating passwords in your method, but can be tedious with a longer password.

You can use a recursive schema to create it. or an iterative scheme with one loop, the az character in the ascii table is sequential, so you can use base 26 transform to create your candidate.



All Articles