首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[分享]Crack Tutorial Chap6-1-01 算法分析[新手入门级]
发表于: 2008-11-24 14:21 9105

[分享]Crack Tutorial Chap6-1-01 算法分析[新手入门级]

书呆彭 活跃值
6
2008-11-24 14:21
9105

【文章标题】: Crack Tutorial Chap6-1-01 算法分析【新手入门级】
【文章作者】: 书呆彭
【下载地址】: 【习题一】http://www.pediy.com/tutorial/chap6/Chap6-1-11.htm
【软件介绍】: 看雪站点上的教程中第六章习题一
【作者声明】: 原教程中已经给出了完整的分析，只是在算法中，某一中间结果作者注明了未经过证明，由实验得出，献丑将证明过程贴一下。
--------------------------------------------------------------------------------
【详细过程】
  看到有朋友问这个的算法
  
  http://bbs.pediy.com/showthread.php?t=77351
  
  
  拿来看了一下。分析完了，才发现这是看雪上的教程中的习题，原就不准备发了。
  
  后来看了下原教程中的分析，说到某一结果还未证明，而我刚好在分析过程中推导出了证明过程，就把它贴出来。
  
  对老鸟没什么价值，飘过即可。
  
  
  另外，这个程序比较简单易懂，就当是给初学者讲讲算法分析的基础吧。
  
  
  程序是汇编语言写的，非常简洁，在入口点函数中单步几下，来到这里（算是WinMain吧）：
  
  0040102B  |.  6A 00         PUSH    0                                ; /lParam = NULL
  0040102D  |.  50            PUSH    EAX                              ; |DlgProc => chap6-1-.00401041
  0040102E  |.  6A 00         PUSH    0                                ; |hOwner = NULL
  00401030  |.  68 00304000   PUSH    chap6-1-.00403000                ; |pTemplate = "dialog1"
  00401035  |.  FF75 08       PUSH    [ARG.1]                          ; |hInst
  00401038  |.  E8 33010000   CALL    <JMP.&USER32.DialogBoxParamA>    ; \DialogBoxParamA
  
  看参数DlgProc = 00401041,那么我们就直接来分析窗口过程00401041，我们只需要注意对WM_COMMAND的处理。
  
  打开OD的窗口浏览界面，看到CHECK按钮的ID是0BB9:
  
  Windows, 条目 4
   句柄=E00230636
   标题=Check
   父窗口=002203BC
   ID=00000BB9 (3001.)
   风格=50010001 BS_DEFPUSHBUTTON|WS_CHILD|WS_TABSTOP|WS_VISIBLE
   扩展风格=00000004 WS_EX_NOPARENTNOTIFY
   线程=主
   ClsProc=77D3B036 USER32.77D3B036
   类=Button
  
  Ctrl + G，来到 00401041，分析如下（参见注释）
  
  00401041  /.  >PUSH    EBP
  00401042  |.  >MOV     EBP, ESP
  00401044  |.  >MOV     EAX, [ARG.1]
  00401047  |.  >MOV     DWORD PTR DS:[403054], EAX
  0040104C  |.  >MOV     EAX, [ARG.2]
  0040104F  |.  >CMP     EAX, 110                         ;  Switch (cases 10..111) —— switch( uMsg )
  00401054  |.  >JNZ     SHORT chap6-1-.00401070
  00401056  |.  >PUSH    0BB8                             ; /ControlID = BB8 (3000.); Case 110 (WM_INITDIALOG) of switch 0040104F
  0040105B  |.  >PUSH    [ARG.1]                          ; |hWnd
  0040105E  |.  >CALL    <JMP.&USER32.GetDlgItem>         ; \GetDlgItem
  00401063  |.  >MOV     DWORD PTR DS:[403058], EAX
  00401068  |.  >PUSH    EAX                              ; /hWnd
  00401069  |.  >CALL    <JMP.&USER32.SetFocus>           ; \SetFocus
  0040106E  |.  >JMP     SHORT chap6-1-.004010C0
  00401070  |>  >CMP     EAX, 10
  00401073  |.  >JNZ     SHORT chap6-1-.00401081
  00401075  |.  >PUSH    0                                ; /Result = 0; Case 10 (WM_CLOSE) of switch 0040104F
  00401077  |.  >PUSH    [ARG.1]                          ; |hWnd
  0040107A  |.  >CALL    <JMP.&USER32.EndDialog>          ; \EndDialog
  0040107F  |.  >JMP     SHORT chap6-1-.004010C0
  00401081  |>  >CMP     EAX, 111
  00401086  |.  >JNZ     SHORT chap6-1-.004010B7
  00401088  |.  >MOV     EAX, [ARG.3]                     ;  Case 111 (WM_COMMAND) of switch 0040104F
  0040108B  |.  >CMP     AX, 0BB9           ; ID_CHECK == 0BB9
  0040108F  |.  >JNZ     SHORT chap6-1-.004010C0  ;这里F2下断
  00401091  |.  >SHR     EAX, 10
  00401094  |.  >OR      AX, AX
  00401097  |.  >JNZ     SHORT chap6-1-.004010B5
  00401099  |.  >PUSH    0A                               ; /Count = A (10.)
  0040109B  |.  >PUSH    OFFSET <chap6-1-.input[0]>       ; |Buffer = OFFSET <chap6-1-.input[0]> —— 接受输入code的缓冲区，加个标签input
  004010A0  |.  >PUSH    0BB8                             ; |ControlID = BB8 (3000.) —— Edit控件的ID
  004010A5  |.  >PUSH    DWORD PTR DS:[403054]            ; |hWnd = 002203BC ('Pusillus Crackme 1.0',class='#32770')
  004010AB  |.  >CALL    <JMP.&USER32.GetDlgItemTextA>    ; \GetDlgItemTextA
  004010B0  |.  >CALL    chap6-1-.004010C9            ; 这就是验证是否正确的函数了，F7进入
  004010B5  |>  >JMP     SHORT chap6-1-.004010C0
  004010B7  |>  >MOV     EAX, 0                           ;  Default case of switch 0040104F
  004010BC  |.  >LEAVE
  004010BD  |.  >RETN    10
  004010C0  |>  >MOV     EAX, 1
  004010C5  |.  >LEAVE
  004010C6  \.  >RETN    10
  
  
  F7进入004010C9中，
  
  004010C9  /$  >PUSH    ESI
  004010CA  |.  >PUSH    EDI
  004010CB  |.  >PUSH    ECX
  004010CC  |.  >XOR     ESI, ESI
  004010CE  |.  >XOR     EDI, EDI
  004010D0  |.  >MOV     ECX, 8
  004010D5  |.  >MOV     ESI, OFFSET <chap6-1-.input[0]>  ;  ASCII "input"
  004010DA  |>  >/XOR     BYTE PTR DS:[ESI], 32
  004010DD  |.  >|INC     ESI
  004010DE  |.^ >\LOOPD   SHORT chap6-1-.004010DA         ;  这个循环，将输入的8个字符与0x32进行异或
  004010E0  |.  >MOV     ESI, OFFSET <chap6-1-.input[0]>  ;  ASCII "input"
  004010E5  |.  >MOV     ECX, 4
  004010EA  |>  >/MOV     AL, BYTE PTR DS:[ESI]
  004010EC  |.  >|MOV     BL, BYTE PTR DS:[ESI+1]
  004010EF  |.  >|XOR     AL, BL
  004010F1  |.  >|MOV     BYTE PTR DS:[EDI+<EncryptKey[0]>;  用来存放4个异或结果，加标签为EncryptKey
  004010F7  |.  >|ADD     ESI, 2
  004010FA  |.  >|INC     EDI
  004010FB  |.^ >\LOOPD   SHORT chap6-1-.004010EA         ; 这个循环，将8个字符每相邻两个进行异或，得到4个结果，存放在一个数组中
  004010FD  |.  >MOV     ESI, OFFSET <chap6-1-.EncryptKey>
  00401102  |.  >MOV     AL, BYTE PTR DS:[ESI]
  00401104  |.  >MOV     BL, BYTE PTR DS:[ESI+1]
  00401107  |.  >XOR     AL, BL                           ;  key1 = EncryptKey[0] ^ EncryptKey[1]
  00401109  |.  >MOV     BL, BYTE PTR DS:[ESI+2]
  0040110C  |.  >MOV     CL, BYTE PTR DS:[ESI+3]
  0040110F  |.  >XOR     BL, CL                           ;  key2 = EncryptKey[2] ^ EncryptKey[3]
  00401111  |.  >XOR     AL, BL                           ;  key = key1 ^ key2
  00401113  |.  >MOV     ECX, 8
  00401118  |.  >MOV     ESI, OFFSET <chap6-1-.input[0]>  ;  ASCII "input"
  0040111D  |>  >/XOR     BYTE PTR DS:[ESI], AL
  0040111F  |.  >|INC     ESI
  00401120  |.^ >\LOOPD   SHORT chap6-1-.0040111D         ;  这个循环是对输入缓冲区再次进行异或加密，密钥就是刚才计算得到的key
  00401122  |.  >MOV     ECX, 8
  00401127  |.  >MOV     ESI, OFFSET <chap6-1-.input[0]>  ;  ASCII "input"
  0040112C  |.  >MOV     EDI, OFFSET <chap6-1-.machine>   ; 这里存放正确结果
  00401131  |>  >/MOV     AL, BYTE PTR DS:[ESI]
  00401133  |.  >|CMP     AL, BYTE PTR DS:[EDI]
  00401135  |.  >|JNZ     SHORT chap6-1-.00401154
  00401137  |.  >|INC     ESI
  00401138  |.  >|INC     EDI
  00401139  |.^ >\LOOPD   SHORT chap6-1-.00401131         ;  这个循环比较经过加密的input和正确结果是否相同
  0040113B  |.  >PUSH    40                               ; /Style = MB_OK|MB_ICONASTERISK|MB_APPLMODAL
  0040113D  |.  >PUSH    chap6-1-.00403035                ; |Title = "Crackme 1.0"
  00401142  |.  >PUSH    chap6-1-.00403010                ; |Text = "Good Work Cracker"
  00401147  |.  >PUSH    DWORD PTR DS:[403054]            ; |hOwner = 002203BC ('Pusillus Crackme 1.0',class='#32770')
  0040114D  |.  >CALL    <JMP.&USER32.MessageBoxA>        ; \MessageBoxA
  00401152  |.  >JMP     SHORT chap6-1-.0040116B
  00401154  |>  >PUSH    30                               ; /Style = MB_OK|MB_ICONEXCLAMATION|MB_APPLMODAL
  00401156  |.  >PUSH    chap6-1-.00403035                ; |Title = "Crackme 1.0"
  0040115B  |.  >PUSH    chap6-1-.00403022                ; |Text = "Bad Serial, Sorry!"
  00401160  |.  >PUSH    DWORD PTR DS:[403054]            ; |hOwner = 002203BC ('Pusillus Crackme 1.0',class='#32770')
  00401166  |.  >CALL    <JMP.&USER32.MessageBoxA>        ; \MessageBoxA
  0040116B  |>  >POP     EDI
  0040116C  |.  >POP     ESI
  0040116D  |.  >POP     ECX
  0040116E  \.  >RETN
  
  
  以上是直接静态阅读代码分析的，所以OD中的注释没有反应出input中内容的变化。自己跟的时候注意一下就行了。
  
  
  算法重现：
  
  bool  IsValid()
  {
  extern char input[8];    // 输入的注册码
  extern char machine[8];
  char encryptKey[4];
  
  int i;
  for ( i = 0; i < 8; ++i )
  {
      input[i] ^= 0x32;
  }
  
  for ( i = 0; i < 4; ++i )
  {
      encryptKey[i] = input[2*i] ^ input[2*i+1];
  }
  
  char  key = (encryptKey[0] ^ encryptKey[1] )^ (encryptKey[2] ^ encryptKey[3]);
  
  for ( i = 0; i < 8; ++i )
  {
      input[i] ^= key;
  }
  
  if ( memcmp( input, machine, 8) )
      return false;
  else
      return true;
  }
  
  
  说明：
  
  首先说几点数学知识：
  
  1.异或满足交换率和结合率，即 a ^ b == b ^ a; (a ^ b) ^ c == a ^ ( b ^ c )
  
  2.对同一个数进行偶数次异或后结果不变
  
  3.对同一个数进行奇数次异或结果与进行一次异或的结果相同
  
  
  第一趟循环异或后，记结果为input_0，即input_0[i] = 0x32 ^ input[i], i = 0,1,2,,,7
  
  对key的计算，化简后是 key = input_0[0] ^ input_0[1] ^ ... ^ input_0[7];
  
  因为input_0[i] = 0x32 ^ input[i],而上式共有8个项进行异或，8是偶数，所以key的值也等于
  
  input[0] ^ input[1] ^ ... ^ input[7]
  
  然后再用key与input_0进行循环异或，记结果为input_1
  
  若input_1与机器码相同则成功。
  
  
  解法：
  
  
  经过如下推导：
  
  input_1[i] = key ^ input_0[i]
             = key ^ input[i] ^ 0x32 , i = 0,1,2,,,7
  
  现在需要input_1与machine相同，即
  
  machine[0] = input_1[0] = 0x32 ^ input[0] ^ key
  machine[1] = input_1[1] = 0x32 ^ input[1] ^ key
  ....
  machine[7] = input_1[7] = 0x32 ^ input[7] ^ key
  
  把上面8个式子全部相异或，则可得到
  
  machin[0] ^ machine[1] ... ^ machine[7] == input[0] ^ input[1] ^ input[2] ... ^ input[7]
  
      == key
  
  
  所以证明了，使用机器码的8个字节进行异或得到的结果就是验证过程中用到的key。
  
  逆推注册码原文已经说得很详细了：
  
  把machine和key异或，得到的结果再与0x32相异或，即为注册码的ASCII值。
  
  给出正确结果：Z3r0Ring
  
--------------------------------------------------------------------------------
【经验总结】
  
  
  
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2008年11月24日 14:21:02


[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏
免费 ・7
支持
分享
最新回复 (14)
笨笨雄
雪    币： 846
活跃值： (221)
能力值： (RANK：570 )
在线值：
发帖
回帖
粉丝
私信
2 楼
支持~~~~~~~~
2008-11-24 14:30
0
Squn
雪    币： 340
活跃值： (15)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
3 楼
算法 我喜欢。
但 算法 不喜欢我。
扎实-就这2个字。
2008-11-24 14:38
0
newjueqi
雪    币： 251
活跃值： (25)
能力值： ( LV9，RANK：290 )
在线值：
发帖
回帖
粉丝
私信
4 楼
想高手学习一下
2008-11-24 16:22
0
冷血书生
雪    币： 443
活跃值： (200)
能力值： ( LV9，RANK：1140 )
在线值：
发帖
回帖
粉丝
私信
5 楼
猛男~~~~~~~~~~~~~学习！
2008-11-24 17:27
0
rxzcums
雪    币： 427
活跃值： (65)
能力值： ( LV6，RANK：90 )
在线值：
发帖
回帖
粉丝
私信
6 楼
学习了
算法牛人啊
讲得很清楚！
出个系列吧！！
可能从你的教程里我的算法能起步。
2008-11-24 17:33
0
logkiller
雪    币： 8222
活跃值： (3361)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
7 楼
对于我这样的新手是要好好多看几遍了
2008-11-24 18:33
0
ivancui
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
8 楼
自法学习要怎么去进行呢，总看文章也没有用啊。。。每次看过都觉得太厉害了。可还是不会。郁闷哦。我会C++和JAVA。

汇编正在看，不过头很大。。呵呵
2008-11-24 19:05
0
xiaofu
雪    币： 1564
活跃值： (3572)
能力值： ( LV13，RANK：420 )
在线值：
发帖
回帖
粉丝
私信
9 楼
膜拜......
2008-11-24 22:04
0
tensai
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
10 楼
char pszSerialOut[10]={0x71,0x18,0x59,0x1b,0x79,0x42,0x45,0x4c,0x0};
char pszSerialIn[10]={0};

/*
0x71 = In[0]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x18 = In[1]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x59 = In[2]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x1b = In[3]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x79 = In[4]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x42 = In[5]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x45 = In[6]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
0x4c = In[7]^0x32^In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];

设 key = In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];

上式子简化为

0x71 = In[0]^0x32^key;
0x18 = In[1]^0x32^key;
0x59 = In[2]^0x32^key;
0x1b = In[3]^0x32^key;
0x79 = In[4]^0x32^key;
0x42 = In[5]^0x32^key;
0x45 = In[6]^0x32^key;
0x4c = In[7]^0x32^key;

也就是 0x71^0x18^0x59^0x1b^0x79^0x42^0x45^0x4c
        = In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7]
        ^0x32^0x32^0x32^0x32^0x32^0x32^0x32^0x32
        ^key^key^key^key^key^key^key^key;

即:0x71^0x18^0x59^0x1b^0x79^0x42^0x45^0x4c = In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];
       => key = 0x71^0x18^0x59^0x1b^0x79^0x42^0x45^0x4c;
       
*/
BYTE key;

key=0x71^0x18^0x59^0x1b^0x79^0x42^0x45^0x4c;
for(int x=0; x<8; x++)
{
        pszSerialIn[x]=key^pszSerialOut[x]^0x32;
}
printf("OK (%.2X):%s\n",key,pszSerialIn);
2008-11-25 10:14
0
tensai
雪    币： 203
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
11 楼
char pszSerialIn[10]={"12345678"};
char pszSerialXor[5]={0};

for(int i=0; i<8; i++)
{
        pszSerialIn[i]=pszSerialIn[i]^0x32;               
}
for(int j=0,k=0; j<4; j+=2,k++)
{
        pszSerialXor[k]=pszSerialIn[j]^pszSerialIn[j+1];
}

pszSerialXor[0]=pszSerialXor[0]^pszSerialXor[1];
pszSerialXor[2]=pszSerialXor[2]^pszSerialXor[3];
pszSerialXor[0]=pszSerialXor[0]^pszSerialXor[2];//pszSerialXor[0]=In[0]^In[1]^In[2]^In[3]^In[4]^In[5]^In[6]^In[7];

for(int l=0; l<8; l++)
{
        pszSerialIn[l]=pszSerialIn[l]^pszSerialXor[0];
}
2008-11-25 11:08
0
北极狐狸
雪    币： 2368
活跃值： (81)
能力值： (RANK：300 )
在线值：
发帖
回帖
粉丝
私信
12 楼
支持，支持。多多教学贴............
2008-11-25 12:03
0
leolsj
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
13 楼
学习中....
2008-12-3 02:38
0
popeylj
雪    币： 360
活跃值： (77)
能力值： ( LV9，RANK：250 )
在线值：
发帖
回帖
粉丝
私信
14 楼
学习了....................
2008-12-4 12:14
0
雪yaojun
雪    币： 120
活跃值： (160)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
15 楼
慢慢读懂去，谢谢分享.
2009-2-4 19:56
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//