我如何并行化这种蛮力攻击算法 [英] 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
它可以工作，但是我尝试过以多种方式实施OpenMP，要么我遇到了无法解决的非常混乱的比赛条件，要么就无法正常工作，我只是想问一些提示，我知道这是由我来完成任务.
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.
这是新代码
#include <omp.h>
#include <iostream>
#include <ctime>
#include <string>
#include <stdio.h>
using namespace std;
void crackPassword(string pass);
long long int attempt;
clock_t start_t, end_t;
string test2[3];
string alphabet;
static int digit[7], alphabetSet = 1;
string test;
int main() {
string password;
std::cout << "Enter the password to crack : ";
cin >> password;
crackPassword(password);
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[6] = 0; digit[6] < alphabet.length() ; digit[6]++)
for (digit[5] = 0; digit[5] < alphabet.length() ; digit[5]++)
for (digit[4] = 0; digit[4] < alphabet.length() ; digit[4]++)
for (digit[3] = 0; digit[3] < alphabet.length(); digit[3]++)
for (digit[2] = 0; digit[2] < alphabet.length() ; digit[2]++)
for (digit[1] = 0; digit[1] < alphabet.length() ; digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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[5] = 0; digit[5] < alphabet.length() ; digit[5]++)
for (digit[4] = 0; digit[4] < alphabet.length(); digit[4]++)
for (digit[3] = 0; digit[3] < alphabet.length() ; digit[3]++)
for (digit[2] = 0; digit[2] < alphabet.length(); digit[2]++)
for (digit[1] = 0; digit[1] < alphabet.length() ; digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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[4] = 0; digit[4] < alphabet.length(); digit[4]++)
for (digit[3] = 0; digit[3] < alphabet.length(); digit[3]++)
for (digit[2] = 0; digit[2] < alphabet.length(); digit[2]++)
for (digit[1] = 0; digit[1] < alphabet.length(); digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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[3] = 0; digit[3] < alphabet.length(); digit[3]++)
for (digit[2] = 0; digit[2] < alphabet.length(); digit[2]++)
for (digit[1] = 0; digit[1] < alphabet.length(); digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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[2] = 0; digit[2] < alphabet.length(); digit[2]++)
for (digit[1] = 0; digit[1] < alphabet.length(); digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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[1] = 0; digit[1] < alphabet.length(); digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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[1] = 0; digit[1] < alphabet.length(); digit[1]++)
for (digit[0] = 1; digit[0] < alphabet.length(); digit[0]++) {
attempt++;
if (attempt % 2500000 == 0) std::cout << ".";
test = alphabet[digit[0]];
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 crackPassword(string pass) {
start_t = clock();
while (1) {
#pragma omp parallel num_threads(7)
#pragma omp parallel
{
#pragma omp single
{
#pragma omp task
cases1(alphabetSet, pass, 1);
#pragma omp task
cases2(alphabetSet, pass, 2);
#pragma omp task
cases3(alphabetSet, pass, 3);
#pragma omp task
cases4(alphabetSet, pass, 4);
#pragma omp task
cases7(alphabetSet, pass, 7);
#pragma omp task
cases5(alphabetSet, pass, 5);
#pragma omp task
cases6(alphabetSet, pass, 6);
}
}
}
}
我现在使用的是g ++编译器，因为可视化studip不支持openMP 3.0，现在我编译时就这样做了
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
在我打开exe并输入密码后，它完全崩溃了，我还注意到，当我输入类似1的非常短的密码时，我看到似乎是一个无限循环或只是线程正在执行此操作，这也值得提到我使用的是Windows，而不是Linux.
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.
推荐答案
即使对任何事物进行成功的暴力攻击，通常也都涉及某种领域知识或渗透.要通过考试，请从教师桌的抽屉中获取密码.
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.
如果没有介绍中的建议，则可以使用迭代器构建密码生成器.这样可以很容易地与标准函数(例如for循环等)集成.取消引用的迭代器随后将返回密码.考虑到领域知识，可以使它在使用次数较少的密码之前生成使用最多的密码-但是对于直截了当的攻击，只需逐步解决所有可能的字符组合就可以了. operator++将使迭代器移至下一个密码.在我的示例中，我使用了从<space>到~(包括)的所有ASCII字符.
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).
生成器还将需要边界，开始密码和停止密码，以便能够生成例如从aaa到bbb的所有密码.这样就可以并行运行许多生成器-为它们提供唯一的生成密码范围.
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.
还需要一个分区程序来划分工作，以便您可以为所有生成器提供其唯一范围的密码来生成.它也应该有一个开始和停止密码，但是要设置更大的范围，例如，从no password到~~~~~~~(7个波浪号，这是我生成器中7个字符的密码中的最后一个).然后，它将使用硬件知识(可以同时运行多少个线程)，并用一个生成器启动那么多线程，每个生成器将提供要测试的整个密码范围的唯一部分.
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.
要使其更进一步，可以构建一个分区程序，并使用不限数量的密码进行测试.它会为本地分区程序集群提供服务，并为它们提供新的范围，以在它们用尽时进行测试.我没有在示例中包括它.相反，我制作了本地分区程序，以便它可以动态创建新范围.
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.
我建议您参考执行政策和find_if运行分区程序(可以，但是...).但是，在此示例中，我实现了一些与执行策略类似的方法，但是采用了一种以预定顺序创建密码生成器的方法，并且还采用了在找到答案后停止循环的方法.另外，还没有多少编译器支持执行策略.但是，此示例将在C ++ 17模式下与Visual Studio，g ++和clang ++一起使用.
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.
在Intel Core i9-7920X(12核，2线程/核)上收集的一些令人沮丧的统计数据:
Some discouraging statistics collected on an Intel Core i9-7920X (12 cores, 2 threads/core):
在不到3.9分钟的时间内即可找到任何0-6个字符的密码
在不到7.3小时的时间内找到了0-7个字符的密码
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
我没有为8个字符的密码运行它:-)
I didn't run it for 8 character passwords :-)
这篇关于我如何并行化这种蛮力攻击算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
