|
|
【文章标题】: 再谈一个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<stdio.h>
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=%3C%3C%BC%D3%C3%DC%D3%EB%BD%E2%C3%DC%B5%DA%B6%FE%B0%E6%3E%3E%B9%E2%C5%CC%D6%D0%B5%C4%D2%BB%B8%F6CrackMe%C6%C6%BD%E2）
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!
2006年11月24日 15:43:08
|
|
