MultiThreaded password cracker

Question

I am experimenting with multithreading and password crackers seem like the simplest (easier then opengl) intensive task.

Would it be worth the time to write a multithreaded password cracker? would it boost efficiency on a hyper threaded duel core (4 cores)?

Would it be faster to have 1 thread generate the hash while another compares it or divide the generating amongst multiple threads.

A lot of questions I know, an answer to any of them would be great, thanks.

Answer 1

After extensive research I can say multithreading a password cracker is not the best use of time.

Multithreading, while capable of boosting resource efficiency, is also useful in server\client interactions.

In the example below multithreading is used to allow a server to accept and interact with multiple clients at the same time.

while (1) {

    listen(sd,10);
    cliLen=sizeof(cliAddr);
    printf("[LISTINING %u][%u]\n",SERVER_PORT,i);

    //Accept Connection

    newSd = accept(sd, (struct sockaddr *) &cliAddr, &cliLen);
    if(newSd < 0)
    {
        perror("cannot accept connection");
        exit(3);
    }

    pthread_create(&pth, NULL, &connectionManager, (void*)newSd);

    i++;         
}

.... ....

int connectionManager(newSd,data){


send(newSd,"[Connection Created on New Thread]\n\r",strlen("[Connection Created on New Thread]\n\r"), 0);
//pthread_create(&pthsend,NULL, &dataSender, (void*)newSd);
pthread_create(&pthget, NULL, &dataGetter, (void*)newSd);
pthread_join(pthsend, NULL);
pthread_join(pthget, NULL);
close(newSd);
pthread_exit; 


}

Further research can be done to determine an efficiency "sweet spot". This will likely be different for all Boxes.

Answer 2

There are actually many ways of doing this. For simplicity, you should divide the majority of the work. In this case, it is rather obvious that most of the work is done in computing the hash. In cases where it is not obvious, you will want to profile your application and find out where the majority of the time is being spent. But also remember there is overhead incurred for many thread creations/joins, so it best to allocate a subset of work to each thread before beginning the work (perhaps check some protected shared variable if someone has found the solution).

Notice, however, depending on the the kind of hashes you will be attempting to crack (I am assuming you will be brute-forcing), there is no guarantee that your program will finish. Most (by that, I mean any practical/effective one) hashing algorithms operate under the notion of computational infeasibility. If you will be generating random strings to crack, notice that all a cracker needs to do is find a collision. For instance, consider a situation where 'cat' and 'dog' map to the same hash value and the real password is 'dog.' If your cracker finds 'cat' as a solution, this solution is just as viable. This is still a very hard problem, however, and also not guaranteed to finish.

The other alternative is a dictionary attack (since this is educational - this should be feasible). If you are doing a simple dictionary attack and the word is not in the dictionary, you will simply be out of luck. This is guaranteed to finish at the end of your dictionary, however. To implement this, it would be best to split your dictionary. If you have 4 threads and a dictionary of 1000 words, then each thread should get a different subset of the dictionary (each with 250 entries to work on). In practice, however, most protected passwords probably have some form of salt as well (just something to think about).

Answer 3

The fastest multi-threading design typically is one thread per core. Why thread swap? the amount of work to be done remains the same. Many threads can be useful in some situations to ease design issues, but if you want full performance, then the design issues have to be met such that one thread per core can be used.

By core I typically mean a single non-hyperthreaded logical core. Of course, design tricks exist and the problem might be such that hyperthreading works fine or is desireable.