首页
社区
课程
招聘
一段难懂的算法分析.
发表于: 2007-1-1 15:12 4626

一段难懂的算法分析.

2007-1-1 15:12
4626
这个crackme 来源于CCDebuger 大侠的od教程中使用的crackme

地址:http://bbs.pediy.com/showthread.php?s=&threadid=21532

该crackme 下载地址:
http://bbs.pediy.com/attachment.php?s=&attachmentid=528

就象CCDebuger 大侠说的那样,这个crackme找出注册算法的位置相对容易,用字

符串参考找出算法关键位置:
004010EB  |.  BE 71214000   mov     esi, 00402171                    ;  ASCII "abcdabcdabcdabcd" //输入的注册码
004010F0  |>  41            /inc     ecx
004010F1  |.  AC            |lods    byte ptr [esi]
004010F2  |.  0AC0          |or      al, al
004010F4  |.  74 0A         |je      short 00401100
004010F6  |.  3C 7E         |cmp     al, 7E
004010F8  |.  7F 06         |jg      short 00401100
004010FA  |.  3C 30         |cmp     al, 30
004010FC  |.  72 02         |jb      short 00401100
004010FE  |.^ EB F0         \jmp     short 004010F0 //这段循环对输入的注册码每个字符进行简单的判断
00401100  |>  83F9 11       cmp     ecx, 11  //这里判断注册码长度,注册码16个字符就够了,
                                            //这里的17还包含了注册码后的结束字符\x0.长度小于16,无提示,且重新开始.
00401103      75 1A         jnz     short 0040111F
00401105  |.  E8 E7000000   call    004011F1 //这个call跟进去长长一段算法代码,
                                             //结果发现就是注册码的前四字符与name前四字符xor后再于一常数xor后得到的eax值有用.
                                             //这个call 我们标记为算法(1).
0040110A  |.  B9 01FF0000   mov     ecx, 0FF01
0040110F  |.  51            push    ecx
00401110  |.  E8 7B000000   call    00401190 //算法的难点在这个call里面,这个call运算完后ecx必须为1才能通过,
                                             //而这个call与输入的有关联的就是上面的那个call完后的eax的值.
                                            //这个call我们标记为算法(2).
00401115  |.  83F9 01       cmp     ecx, 1
00401118      74 06         je      short 00401120 //若ecx不为1就错误提示
0040111A  |>  E8 47000000   call    00401166
0040111F  |>  C3            retn
00401120  |>  A1 68214000   mov     eax, [402168]//name第把个字符开始的四个字符
00401125  |.  8B1D 6C214000 mov     ebx, [40216C]//name后四个字符
0040112B  |.  33C3          xor     eax, ebx
0040112D  |.  3305 82214000 xor     eax, [402182]//字符串常量0xFEDCBA98
00401133  |.  0D 40404040   or      eax, 40404040
00401138  |.  25 77777777   and     eax, 77777777
0040113D  |.  3305 79214000 xor     eax, [402179]//eax与注册码第八个字符开始的四个字符xor运算
00401143  |.  3305 7D214000 xor     eax, [40217D]//eax与注册码最后四字符xor运算
00401149    ^ 75 CF         jnz     short 0040111A //eax为0则注册成功,由此我们可以推断:name任意给定,
                                                  //注册码前12个字符任意给定,
                                                //在0040113D处运算完后的eax的值对应的四个字符作为注册码最后四个字符就可以成功注册.
0040114B  |.  E8 2B000000   call    0040117B
00401150  \.  C3            retn
00401151  /$  6A 00         push    0                                ; /Style = MB_OK|MB_APPLMODAL
00401153  |.  68 00204000   push    00402000                         ; |Title = "About this crackme"
00401158  |.  68 13204000   push    00402013                         ; |Text = "CycleCrackme by cW_",LF,"Try to get a serial for your name and write a keygen... no patching!",LF,"This should be not too hard..., if you understand how it works ;-)",LF,"Please send your solution to cW_6556@yahoo.com"
0040115D  |.  FF75 08       push    dword ptr [ebp+8]                ; |hOwner
00401160  |.  E8 58010000   call    <jmp.&USER32.MessageBoxA>        ; \MessageBoxA
00401165  \.  C3            retn
00401166  /$  6A 00         push    0                                ; /Style = MB_OK|MB_APPLMODAL
00401168  |.  68 DE204000   push    004020DE                         ; |Title = "Ahm. No!"
0040116D  |.  68 E7204000   push    004020E7                         ; |Text = "Please enter a valid serial for your name!"
00401172  |.  FF75 08       push    dword ptr [ebp+8]                ; |hOwner
00401175  |.  E8 43010000   call    <jmp.&USER32.MessageBoxA>        ; \MessageBoxA
0040117A  \.  C3            retn
0040117B  /$  6A 00         push    0                                ; /Style = MB_OK|MB_APPLMODAL
0040117D  |.  68 12214000   push    00402112                         ; |Title = "Wow!"
00401182  |.  68 17214000   push    00402117                         ; |Text = "Congratulations!",LF,"Write a tutorial/keygen an send it to cW_6556@yahoo.com"
00401187  |.  FF75 08       push    dword ptr [ebp+8]                ; |hOwner
0040118A  |.  E8 2E010000   call    <jmp.&USER32.MessageBoxA>        ; \MessageBoxA
0040118F  \.  C3            retn

其中算法(1)call进去代码为:
004011F1  /$  A1 60214000   mov     eax, [402160]//name 前四个字符
004011F6  |.  8B1D 64214000 mov     ebx, [402164]//name第四个字符开始的四个字符
004011FC  |.  3305 71214000 xor     eax, [402171]//eax xor 注册码前四个字符 后面一些列运算对eax影响不大,
                                                 //在算法(2)里用的也就是eax的最高位的值,而这个值在下面运算没有变化.
00401202  |.  331D 75214000 xor     ebx, [402175]//注册码第四个字符开始的四个字符
00401208  |.  25 0F1F3F7F   and     eax, 7F3F1F0F
0040120D  |.  81E3 00010307 and     ebx, 7030100
00401213  |.  33C9          xor     ecx, ecx
00401215  |>  8BF0          /mov     esi, eax
00401217  |.  8BFB          |mov     edi, ebx
00401219  |.  D3E6          |shl     esi, cl
0040121B  |.  D3E7          |shl     edi, cl
0040121D  |.  81E6 80808080 |and     esi, 80808080
00401223  |.  81E7 80808080 |and     edi, 80808080
00401229  |.  8BD6          |mov     edx, esi
0040122B  |.  C0EE 07       |shr     dh, 7
0040122E  |.  66:C1E2 07    |shl     dx, 7
00401232  |.  C1EA 08       |shr     edx, 8
00401235  |.  C0EE 07       |shr     dh, 7
00401238  |.  66:C1E2 07    |shl     dx, 7
0040123C  |.  C1EA 08       |shr     edx, 8
0040123F  |.  C0EE 07       |shr     dh, 7
00401242  |.  66:D1EA       |shr     dx, 1
00401245  |.  8BF2          |mov     esi, edx
00401247  |.  8BD7          |mov     edx, edi
00401249  |.  C0EE 07       |shr     dh, 7
0040124C  |.  66:C1E2 07    |shl     dx, 7
00401250  |.  C1EA 08       |shr     edx, 8
00401253  |.  C0EE 07       |shr     dh, 7
00401256  |.  66:C1E2 07    |shl     dx, 7
0040125A  |.  C1EA 08       |shr     edx, 8
0040125D  |.  C0EE 07       |shr     dh, 7
00401260  |.  66:C1EA 05    |shr     dx, 5
00401264  |.  8BFA          |mov     edi, edx
00401266  |.  33FE          |xor     edi, esi
00401268  |.  8BD7          |mov     edx, edi
0040126A  |.  81E2 FF000000 |and     edx, 0FF
00401270  |.  51            |push    ecx
00401271  |.  52            |push    edx
00401272  |.  BA 08000000   |mov     edx, 8
00401277  |.  91            |xchg    eax, ecx
00401278  |.  83F8 03       |cmp     eax, 3
0040127B  |.  7F 0F         |jg      short 0040128C
0040127D  |.  F6E2          |mul     dl
0040127F  |.  5A            |pop     edx
00401280  |.  83C0 08       |add     eax, 8
00401283  |.  91            |xchg    eax, ecx
00401284  |.  D3C0          |rol     eax, cl
00401286  |.  33C2          |xor     eax, edx
00401288  |.  D3C8          |ror     eax, cl
0040128A  |.  EB 0D         |jmp     short 00401299
0040128C  |>  83E8 03       |sub     eax, 3
0040128F  |.  F6E2          |mul     dl
00401291  |.  5A            |pop     edx
00401292  |.  91            |xchg    eax, ecx
00401293  |.  D3C3          |rol     ebx, cl
00401295  |.  33DA          |xor     ebx, edx
00401297  |.  D3CB          |ror     ebx, cl
00401299  |>  59            |pop     ecx
0040129A  |.  41            |inc     ecx
0040129B  |.  83F9 08       |cmp     ecx, 8
0040129E  |.^ 0F85 71FFFFFF \jnz     00401215
004012A4  \.  C3            retn

算法(2)的代码如下:
00401190  /$  5F            pop     edi                              ;  cycle.00401115
00401191  |.  59            pop     ecx
00401192  |.  57            push    edi
00401193  |.  81F9 80000000 cmp     ecx, 80  //近来前ecx被赋值0xff01
00401199  |.  7E 55         jle     short 004011F0
0040119B  |.  51            push    ecx
0040119C  |.  8BF1          mov     esi, ecx
0040119E  |.  81E1 FF000000 and     ecx, 0FF
004011A4      8BF8          mov     edi, eax //算法(1)里得到的eax给edi
004011A6      83F9 08       cmp     ecx, 8
004011A9  |.  7E 05         jle     short 004011B0
004011AB  |.  8BFB          mov     edi, ebx
004011AD  |.  C1E9 04       shr     ecx, 4
004011B0  |>  C1C7 08       /rol     edi, 8
004011B3  |.  D1E9          |shr     ecx, 1
004011B5  |.^ 75 F9         \jnz     short 004011B0
004011B7  |.  C1EE 08       shr     esi, 8
004011BA  |.  23FE          and     edi, esi
004011BC  |.  81E7 FF000000 and     edi, 0FF//取edi低八位,实际上是算法(1)得到的eax的最高八位.
004011C2  |.  59            pop     ecx
004011C3  |>  BE 80000000   mov     esi, 80 //最后的ecx的值就是由esi变化得到的,这里esi初始为0x80.
004011C8  |>  85FE          /test    esi, edi //这里是一个循环,搞不懂的循环,
                                             //自己分析了好久感觉,没法让最后的ecx等于1.
004011CA  |.  74 20         |je      short 004011EC //esi,edi 相与不为0时 开始计算ecx值.
004011CC  |.  33FE          |xor     edi, esi
004011CE  |.  57            |push    edi
004011CF  |.  81E1 00FF0000 |and     ecx, 0FF00//取ecx高8位,ecx初始为0xff01.
004011D5  |.  87CE          |xchg    esi, ecx //ecx与esi交换
004011D7  |.  32E9          |xor     ch, cl   //将cx高四位与低四位异或
004011D9  |.  33F1          |xor     esi, ecx//实际上将0xff00 xor ecx
004011DB  |.  87F1          |xchg    ecx, esi //得到的值给ecx.
004011DD  |.  51            |push    ecx
004011DE  |.  FF05 82214000 |inc     dword ptr [402182]
004011E4  |.  E8 A7FFFFFF   |call    00401190  //回到算法(2)的开始,
004011E9  |.  5F            |pop     edi
004011EA  |.^ EB D7         |jmp     short 004011C3
004011EC  |>  D1EE          |shr     esi, 1
004011EE  |.^ 75 D8         \jnz     short 004011C8//当edi为0时 esi为0会退出循环.
004011F0  \>  C3            retn

分析了下,要使得算法(2)运算完后ecx为1才能去正确注册,否则弹出对话框
"Please enter a valid serial for your name!"
而算法(2)ecx的值与算法(1)里 name前四个字符 xor 输入的注册码前四个字符 得到的eax的值 再 与0x7F3F1F0F 相与后得到的eax值的最高 八位有关.

实际上就是name的第四个字符 同输入的注册码第四个字符 异或后 在同0x7F相与 有关系.最后这个值给算法(2)里的edi了.

算法(2)里由esi 的值来得到 ecx ,把edi做为判断标准来定esi的值.
esi初始为0x80即 二进制:01000 0000,把它与edi相与,为0时 ,esi右移,当esi为0就退出.也就是说,esi最后的值就是edi 最高为的1保留,其他几为全为0的值.
要使ecx为1,那么ecx低八位 为1 高八位为0才行,而中间

xchg    esi, ecx
xor     ch, cl 将cx高四位与低四位异或
//这一步完了必须使ecx为 0xff01才能是下面的运算后ecx为1.
xor     esi, ecx//实际上将0xff00 xor ecx

这样要求esi(esi当成16位)高八位为fe,第八位为01 就不可能实现了,根据上面分析esi里所有位上只有一个1才对.

想了很久都没搞明白.感觉说的很乱.见笑了,希望高手分析下,上面哪里分析的有错误,敬请批评,谢谢!

[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 0
支持
分享
最新回复 (3)
雪    币: 10948
活跃值: (3298)
能力值: (RANK:520 )
在线值:
发帖
回帖
粉丝
2
哪个传说中的大侠来指点一下啊  我是真的想守得云开见月明.
希望给我点精神安慰.谢谢了!
2007-1-5 19:47
0
雪    币: 313
活跃值: (440)
能力值: ( LV12,RANK:530 )
在线值:
发帖
回帖
粉丝
3
0040112D |. 3305 82214000 xor eax, [402182]//字符串常量0xFEDCBA98

这是你前面的分析,不对把
004011DE |. FF05 82214000 |inc dword ptr [402182]

看这个,是不是相关的呢.呵呵,那个算法2函数是个递归把,而且每执行一次那个数字+1,基数是FEDCBA98.
2007-1-10 10:16
0
雪    币: 10948
活跃值: (3298)
能力值: (RANK:520 )
在线值:
发帖
回帖
粉丝
4
谢谢,楼上的大侠!

当时看这个算法,看了很久都没结果,后来就看不下去了,放下了,我找时间再去从新分析一边.

感谢您的指点,希望大侠有空了把算法跟踪出来!渴望学习!

ps:有点怕递归,脑袋递进去,就出不来了.
2007-1-10 10:49
0
游客
登录 | 注册 方可回帖
返回
//