首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[原创]再谈一个CrackMe解密算法的数学原理
2006-11-28 03:40 4847

[原创]再谈一个CrackMe解密算法的数学原理

kaien 活跃值
4
2006-11-28 03:40
4847
【文章标题】: 再谈一个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

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法

收藏
免费 ・7
打赏
分享
最新回复 (1)
binbinbin
雪    币： 405
活跃值： (10)
能力值： ( LV9，RANK：1130 )
在线值：
发帖
回帖
粉丝
私信
binbinbin 28 2006-11-28 10:58
2 楼
0
http://www.pediy.com/tutorial/chap6/Exercise/section01/chap6-1-1-01.zip

这个就是看雪主页上的“序列号保护”的第一个crackme。

我顺便粘贴出来。大家都比较下。

楼主写得很详细。精神非常可嘉。继续啊....

破解chap6-1-1-01

* Referenced by a CALL at Address:
|:004010B0  
|
:004010C9 56                      push esi
:004010CA 57                      push edi
:004010CB 51                      push ecx
:004010CC 33F6                    xor esi, esi
:004010CE 33FF                    xor edi, edi
:004010D0 B908000000              mov ecx, 00000008          ---定义循环次数
:004010D5 BE44304000              mov esi, 00403044          ---调出输入的密码
:004010DA 803632                  xor byte ptr [esi], 32      ---把密码个字节与32取异或
:004010DD 46                      inc esi
:004010DE E2FA                    loop 004010DA              ---向上循环
:004010E0 BE44304000              mov esi, 00403044         
:004010E5 B904000000              mov ecx, 00000004          ---8变4
:004010EA 8A06                    mov al, byte ptr [esi]
:004010EC 8A5E01                  mov bl, byte ptr [esi+01]
:004010EF 32C3                    xor al, bl                ---把变化后的密码前后取异或
:004010F1 88874C304000            mov byte ptr [edi+0040304C], al
:004010F7 83C602                  add esi, 00000002         
:004010FA 47                      inc edi
:004010FB E2ED                    loop 004010EA              ---向上循环
:004010FD BE4C304000              mov esi, 0040304C          ---将生成的4个数变成2个
:00401102 8A06                    mov al, byte ptr [esi]
:00401104 8A5E01                  mov bl, byte ptr [esi+01]
:00401107 32C3                    xor al, bl
:00401109 8A5E02                  mov bl, byte ptr [esi+02]
:0040110C 8A4E03                  mov cl, byte ptr [esi+03]
:0040110F 32D9                    xor bl, cl
:00401111 32C3                    xor al, bl                  ---再由2个变1个放入AL
:00401113 B908000000              mov ecx, 00000008
:00401118 BE44304000              mov esi, 00403044
:0040111D 3006                    xor byte ptr [esi], al  ---将生成的1个与原来的取异或
:0040111F 46                      inc esi
:00401120 E2FB                    loop 0040111D
:00401122 B908000000              mov ecx, 00000008          ---从这往下开始比较
:00401127 BE44304000              mov esi, 00403044          ---放入算出的结果

* Possible StringData Ref from Data Obj ->"q"
                                  |
:0040112C BF08304000              mov edi, 00403008          ---放入正确的结果
:00401131 8A06                    mov al, byte ptr [esi]
:00401133 3A07                    cmp al, byte ptr [edi]
:00401135 751D                    jne 00401154                ---跳向出错
:00401137 46                      inc esi
:00401138 47                      inc edi
:00401139 E2F6                    loop 00401131              ---向上循环
:0040113B 6A40                    push 00000040

模拟运算:
如果输入12345678
机器码                31  32  33  34  35  36  37  38  
与32异或              03  00  01  06  07  04  05  0A  ----(1)
8变4为                  03      07      03      0F
4变2为                      04              0C
2变1为                              08                ----(2)
(1)与08取异或          0B  08  09  0E  0F  0C  0D  02

00403008 内正确的为    71  18  59  1B  79  42  45  4C

根据正确反推注册码:  (关键是如何计算(2))
                    由算法可知(2)是由机器码反复取异或得到，其实由它的正确的密码重复这                    一算法也可求的(2),实验得出。缺少证明。

机器码                71  18  59  1B  79  42  45  4C
8变4为                  69      42      3B      09
4变2为                      2B              32
2变1为                              19                ----正确的密码的(2)值应为19

接着反推正确的注册码:
机器码                  71  18  59  1B  79  42  45  4C
与19取异或              68  01  40  02  60  5B  5C  55
与32取异或              5A  33  72  30  52  69  6E  67
查表得正确的注册码为:    Z  3  r  0  R  i  n  g  (Z3r0Ring)
ZXEM 2000.3.20
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回