谈一个CrackMe解密算法的数学原理,CrackMe,加密算法 2008年06月22日 星期日 下午 11:55 【文章标题】: 再谈一个CrackMe解密算法的数学原理 【文章作者】: kaien 【作者邮箱】: kkaien@hotmail.com 【软件名称】: echap511.exe 【加壳方式】: 无壳 【使用工具】: OllyDbg,winxp自带的计算器,VC(写注册机用) 【操作平台】: winxp -------------------------------------------------------------------------------- 【详细过程】 昨天看到WAKU写的一篇题为“<<加密与解密第二版>>光盘中的一个CrackMe破解”的破解文章。我看文章前直接下了CrackMe自己破了一下。发现虽然很简单,但是很精彩!!! 所以忍不住要借WAKU的光也写一篇破解文章。好东西就是不厌其谈,百遍不穿啊! 本文我将侧重与讨论这个解密算法的数学原理和演变方法,从而大大的简化了解密过程。 这是本人在看雪的第二篇破文,希望本人这篇拙作能对新手们有所帮助。 算法部分代码如下,很好理解,看我后面的注释: 004010CE |. 33FF xor edi,edi ; edi清零 004010D0 |. B9 08000000 mov ecx,8 ; 下面的循环次数为8次(估计密码是8位) 004010D5 |. BE 44304000 mov esi,echap511.00403044 ; 取密码到esi 004010DA |> 8036 32 /xor byte ptr ds:[esi],32 ; 每个字母都和32 xor 004010DD |. 46 |inc esi 004010DE |.^ E2 FA \loopd short echap511.004010DA 004010E0 |. BE 44304000 mov esi,echap511.00403044 ; 变换后的密码的地址给esi 004010E5 |. B9 04000000 mov ecx,4 ; ecx=4 这里就是说,下面循环4次 004010EA |> 8A06 /mov al,byte ptr ds:[esi] ; 取第一位 004010EC |. 8A5E 01 |mov bl,byte ptr ds:[esi 1] ; 取第二位 004010EF |. 32C3 |xor al,bl ; al=al^bl 004010F1 |. 8887 4C304000 |mov byte ptr ds:[edi 40304C],al ; 因为前面edi已经清零了(看第一行)。所以第一次循环时这里就是取地址40304c 004010F7 |. 83C6 02 |add esi,2 ; 地址跳两位 004010FA |. 47 |inc edi ; edi 004010FB |.^ E2 ED \loopd short echap511.004010EA 004010FD |. BE 4C304000 mov esi,echap511.0040304C ; 计算后把地址给esi.其实40304c在内存里面,就在前面8位密码后面 00401102 |. 8A06 mov al,byte ptr ds:[esi] ; 在4个计算结果中,取第一位给al 00401104 |. 8A5E 01 mov bl,byte ptr ds:[esi 1] ; 取第二位给bl 00401107 |. 32C3 xor al,bl ; al=al^bl 00401109 |. 8A5E 02 mov bl,byte ptr ds:[esi 2] ; 第三位->bl 0040110C |. 8A4E 03 mov cl,byte ptr ds:[esi 3] ; 第四位->cl 0040110F |. 32D9 xor bl,cl ; bl=bl^cl 00401111 |. 32C3 xor al,bl ; 两个xor后的结果再xor给al 00401113 |. B9 08000000 mov ecx,8 ; ecx=8,就是下面循环8次 00401118 |. BE 44304000 mov esi,echap511.00403044 ; esi其实就是第一次变换后的密码的开始地址 0040111D |> 3006 /xor byte ptr ds:[esi],al ; 把密码的每一位都和al xor 0040111F |. 46 |inc esi 00401120 |.^ E2 FB \loopd short echap511.0040111D 00401122 |. B9 08000000 mov ecx,8 ; 现在得到了新的密码 00401127 |. BE 44304000 mov esi,echap511.00403044 ; esi = 密码开始地址 0040112C |. BF 08304000 mov edi,echap511.00403008 ; edi,这个地址403008的内容是怎么得到的? (OD中搜索所有常量403008(也可以设内存写入断点)会发现没有其他语句修改这段内存,而且这些数值从一开始就没有变化,估计这些是程序设计好的8个字符,而不是计算出来的,应该是用来做比较的字符常量) 00401131 |> 8A06 /mov al,byte ptr ds:[esi] ; 把两段字符串(8个字符)做比较,不相等就完蛋 00401133 |. 3A07 |cmp al,byte ptr ds:[edi] 00401135 |. 75 1D |jnz short echap511.00401154 00401137 |. 46 |inc esi 00401138 |. 47 |inc edi 00401139 |.^ E2 F6 \loopd short echap511.00401131 OD内存窗口里看到,地址403008处的8个字符的16进制分别为: 71 18 59 1B 79 42 45 4C 分析和总结: 首先,密码必须8位。然后进行密码验证。 密码验证算法: 1。先把密码的8个数分别和32 xor 2。然后两个两个的取,每两个数都xor一下,这样就得到了4个数 3。把上面计算出的4个数分成前后两组。每组的两个数都xor,又得到两个数 4。再把这两个数xor给al 5。我们下面就要使用al了。先把前面变换后的密码(即经过第1步运算后的密码)每位都和al xor.然后把结果和 71 18 59 1B 79 42 45 4C这8个数比较。不等就game over! 下面才是本文的关键所在,请大家仔细看好了,认真理解! 上面5个步骤地代数表示形式为: 假设输入的原密码为: c1 c2 c3 c4 c5 c6 c7 c8 第一步: Ci=ci^32 i=1..8 第二步: A1=C1^C2 A2=C3^C4 A3=C5^C6 A4=C7^C8 第三步: B1=A1^A2=C1^C2^C3^C4 B2=A3^A4=C5^C6^C7^C8 第四步: al = B1^B2 = C1^C2^C3^C4^C5^C6^C7^C8 = (c1^32)^(c2^32)^....^(c8^32) = c1^c2^c3^c4^c5^c6^c7^c8 即al = C1^C2^C3^C4^C5^C6^C7^C8 = c1^c2^c3^c4^c5^c6^c7^c8 上式表明,原密码所有位数xor的值 = 变换后的密码所有位数xor的值 = al的值 第五步: C1^al=71 C2^al=18 C3^al=59 C4^al=1B C5^al=79 C6^al=42 C7^al=45 C8^al=4C 我们看到,如果我们把第5步中得到的8个等式xor,即(C1^al)^(C2^al)^...^(C8^al) = C1^C2^C3^C4^C5^C6^C7^C8 = 71^18^59^1B^79^42^45^4C = 19 这是一个常数 结合第四步的结果,我们有如下结论: al = C1^C2^C3^C4^C5^C6^C7^C8 = c1^c2^c3^c4^c5^c6^c7^c8 = 71^18^59^1B^79^42^45^4C = 19 这是多么美妙的式子啊!!! 请大家注意了,我们回头再来看看我们的问题。 我们的问题是找注册码,即:求解所有的ci,i=1..8 如果我们可以求解出Ci,i=1..8,那么就等同于求解出了ci,因为ci = Ci^32 也就是说,我们需要求解第5步所给出的方程组。 到这里,解密的问题完全变成一个数学问题了。 我们仔细观察一下会发现, 这个方程组中有8个方程和8个未知数。 且这8个方程是彼此线性无关的。 也就是说,如果存在解。那么解就是唯一的。 这样,我们就从理论上证明了解的唯一性了!^_^ 下面的问题就是,怎么求解方程组呢? 方法很多! 首先,让我们用第一个等式分别和其他七个等式xor. 我们可以得到: (C1^al)^(C2^al) = C1^C2 = c1^32^c2^32 = c1^c2 = 71^18 即 c1^c2 = 71^18 依此类推 c1^c3=71^59 ........... c1^c8=71^4C 注意:上面有七个方程。而且形式已经非常简单了。 我们看到,只要我们给定任意一个c1则分别可以唯一的计算出c2,c3,...c8来, 因为我们有如下变换: c2=71^18^c1 c3=71^59^c1 ........... c8=71^4C^c1 也就是说,我们只要确定c1的值,就能通过上面的7个方程唯一的计算出c2,...,c8的值。 问题一:我们可以随便取c1吗? 答案很明显是不可以。因为我们已经从理论上证明了解的唯一性了。 问题二:那么,如何计算c1呢? 我们来看, al = c1^c2^c3^c4^c5^c6^c7^c8 = 19 这一点我们已经证明了。 所以说al=19是个常数,确定无疑。 那么,根据第5步中的第一个方程C1^al=71 我们可以得到。 C1^al = c1^32^al = c1^32^19 = 71 注意到了吗?这里只有一个未知数c1。 所以,我们可以唯一的计算出c1 = 71^32^19 = 5A = 'Z' 这样c1的值也被确定了。 总结注册码算法如下: 算法一: c1 = 71^32^19 = 5A c2=71^18^c1 c3=71^59^c1 c4=71^1B^c1 c5=71^79^c1 c6=71^42^c1 c7=71^45^c1 c8=71^4C^c1 通过数学的分析和变换,我们看到算法大大的被简化了。 而且,此问题有且只有一个解: Z3r0Ring 其实,本问题还有更直接、更简单的解法。^_^ 我上面介绍的是先找到c1和c2,...,c8的关系,然后通过变换求解出c1,就可以依次计算出c2,...,c8的数值。 这是求解方程组的一种常用的思路。 然而,对于这个问题,其实完全不用这么做。 明眼的人可能已经注意到了我前面的提示以及如何计算c1的过程了。 事实上,我们完全可以用同样的方法,直接计算出c2,...,c8来。 我们有算法二: C2^al=18 => c2^32^al = c2^32^19 = 18 => c2 = 18^32^19 即 c2 = 18^32^19 = '3' 同理 c3 = 59^32^19 = 'r' c4 = 1B^32^19 = '0' c5 = 79^32^19 = 'R' c6 = 42^32^19 = 'i' c7 = 45^32^19 = 'n' c8 = 4C^32^19 = 'g' 这算法够直白了!直接计算,已经化简到不能再简单了吧!:) 因为算法已经被简化到了极限,所以第二个算法的注册机就不写了。 贴一个第一种算法的注册机好了, C代码如下: #include void main() { char c[8],al,b[8]={0x71,0x18,0x59,0x1B,0x79,0x42,0x45,0x4C}; al=b[0]; for(int i=1;i<=7;i ) al=al^b[i]; //或者直接写al=0x19就可以了,可以省略计算al的运算 :) c[0]=b[0]^0x32^al; //计算c0 for(i=1;i<=7;i ) { c[i]=b[0]^b[i]^c[0]; //分别计算c1...c7 } c[8]='\0'; printf("注册码: %s\n",c); //输出结果 } 这是我在看雪的第二篇教程,希望在文中我已经解释的足够清楚了。 还有对解密算法不理解的可以提问, 也希望这篇教程大家能喜欢。^_^ 破解完毕! -------------------------------------------------------------------------------- 【下载地址】: 还没上传权限!:( 大家请先到WAKU的帖子里下 (http://bbs.pediy.com/showthread.php?s=&threadid=21636&highlight=<<加密与解密第二版>>光盘中的一个CrackMe破解) 【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢! |
|小黑屋|最新主题|手机版|微赢网络技术论坛 ( 苏ICP备08020429号 )
GMT+8, 2024-9-30 03:24 , Processed in 0.239411 second(s), 12 queries , Gzip On, MemCache On.
Powered by Discuz! X3.5
© 2001-2023 Discuz! Team.