# How can i parallelize this brute force attack algorithm

I'm a first year student pursuing computer engineering , we have an assignment to create a brute force algorithm that would crack a password provided by the user , I decided to go an extra mile and use parallel programming now this is the code without parallel programming :

``````EDIT:OLD CODE WAS HERE
``````

It works however I've tried implementing OpenMP in many ways I either endUp with a very messed up race condition i'm unable to solve or it just won't work , i'm only asking for hints I understand that it's up to me to get the task done.

EDIT : This is the new code

``````#include <omp.h>
#include <iostream>
#include <ctime>
#include <string>
#include <stdio.h>

using namespace std;
long long int attempt;
clock_t start_t, end_t;
string test2;
string alphabet;
static int digit, alphabetSet = 1;

string test;

int main() {

std::cout << "Enter the password to crack : ";

std::cout << "The number of attempts : " << attempt << endl;

return 0;
}
void alphabets(int alphabetSet) {

switch (alphabetSet) {
case 1: alphabet = "-0123456789";
break;
case 2: alphabet = "-abcdefghijklmnopqrstuvwxyz";
break;
case 3: alphabet = "-ABCDEFGHIJKLMNOPQRSTUVWXYZ";
break;
case 4: alphabet = "-0123456789abcdefghijklmnopqrstuvwxyz";
break;
case 5: alphabet = "-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
break;
case 6: alphabet = "-abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
break;
case 7: alphabet = "-0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
break;
}
}

void cases7( int alphabetSet, string pass, int passwordLength) {
while (alphabetSet < 8) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];
for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}
void cases6(int alphabetSet, string pass, int passwordLength) {
while (alphabetSet < 8) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length() ; digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];
for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}
void cases5(int alphabetSet, string pass, int passwordLength) {

while (alphabetSet < 8) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];
for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}
void cases4(int alphabetSet, string pass, int passwordLength) {
while (alphabetSet < 8) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];

for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}
void cases3(int alphabetSet, string pass, int passwordLength) {
while (alphabetSet < 8) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];
for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}
void cases2(int alphabetSet, string pass,int passwordLength) {
while (alphabetSet < 6) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];
for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}
void cases1(int alphabetSet, string pass, int passwordLength) {

while (alphabetSet < 4) {

alphabets(alphabetSet);

for (digit = 0; digit < alphabet.length(); digit++)
for (digit = 1; digit < alphabet.length(); digit++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit];
for (int i = 1; i < passwordLength; i++)
if (alphabet[digit[i]] != '-')test += alphabet[digit[i]];
if (pass.compare(test) == 0) {
end_t = clock(); std::cout << endl << endl << endl << ">\n>> CRACKED THE PASSWORD! >>\n>" << endl << endl << "The password : " << pass;
std::cout << "The time duration  passed : " << (double)(end_t - start_t) / 1000 << " seconds" << endl << endl;
system("pause");
}
}
alphabetSet++;
}
}

start_t = clock();

while (1) {
#pragma omp parallel
{
#pragma omp single
{

cases1(alphabetSet, pass, 1);
cases2(alphabetSet, pass, 2);
cases3(alphabetSet, pass, 3);
cases4(alphabetSet, pass, 4);
cases7(alphabetSet, pass, 7);
cases5(alphabetSet, pass, 5);

cases6(alphabetSet, pass, 6);

}
}
}

}

``````

I'm using now the g++ compiler since visual studip doesn't support openMP 3.0 , now when I compile and I do it like this

``````g++ Hello.cpp -o Hello.exe -fopenmp -lpthread
``````

after i open the exe and type my password it flat out crashes i've also noticed that when i enter a very short pass like 1 i see what seems to be an infinite loop or just threads doing there thing , it's also worth mentioning that i'm using windows not linux. On

Even successful brute force attacks on anything usually involves some kind of domain knowledge or infiltration. To ace your exam, go grab the password from the drawer in your teachers desk.

### Generator

If what's suggested in the intro isn't an option, you could build a password generator with iterators. That would make it easy to integrate with standard functions like for-loops etc. A dereferenced iterator would then return a password. With domain knowledge in mind, one would make it generate the most used passwords before the less commonly used ones - but for a blunt attack, just stepping through every possible combination of characters will have to do. `operator++` would make the iterator step to the next password. In my example, I use all ASCII characters from `<space>` to `~` (inclusive).

The generator will also need boundaries, a start and stop password to be able to generate all passwords from `aaa` to `bbb` for example. This will make it possible to run many generators in parallel - giving them unique ranges of passwords to generate.

### Local Partitioner

What's also needed is a partitioner to divide the work so that you can give all generators their unique range of passwords to generate. This should also have a start and stop password, but for a much bigger range, lets say, from `no password` to `~~~~~~~` (7 tildes, the last of the 7 character passwords in my generator). It would then use the knowledge of the hardware (how many threads that would be reasonable to run simultaneously) and start that many threads with one generator each that it gives a unique part of the full range of passwords to test.

### Master/Remote Partitioner

To be able to take it one step further, one could build a partitioner taking on an unlimited amount of passwords to test. It'd serve a cluster of local partitioners and feed them new ranges to test when they run out of work. I haven't included this in the example. Instead I've made the local partitioner so that it creates new ranges on the fly.

I suggest that you look into execution policies and `find_if` for running the partitioner (which will work, but ...). In this example I've however implemented something similar to the execution policies, but with a way to create password generators in a predetermined order - and also with a way to stop looping when the answer is found. Also, not many compilers support the execution policies yet. This example will however work with Visual Studio, g++ and clang++ in C++17 mode.

Some discouraging statistics collected on an Intel Core i9-7920X (12 cores, 2 threads/core):

any 0-6 character password is found in less than ~3.9 minutes
any 0-7 character password is found in less than ~7.3 hours

I didn't run it for 8 character passwords :-)

Full example @ Godbolt