万里长征第一步:ECTool 7.01注册算法分析

解密者:冲天剑@pediy
解密工具:PEId0.94,OllyICE1.10



0. 导言

   ECTool是一个功能强大的国际象棋通讯赛对局管理程序,用它可以方便地管理各种国际
象棋(电子邮件,纸质邮件等)通讯赛对局。该软件主页可见hxxp://www.ectool.nu/(抱歉,
不提供可点击的链接,如果你愿意访问该站点,请自行改成正确格式的URL。)近日该软件作者
在其主页上放出了免费版本的注册码,并声称已没有时间和精力投入后续的开发与维护。

   鄙人是一个国际象棋爱好者,数年前就开始使用这个软件,但当时只限于在网络上寻找
注册码。现在趁此机会,对这个软件的注册算法研究一番,希望能写出注册机。


1. 预分析

   所谓预分析就是搜集对于推测算法有帮助的信息的工作。具体如下:在网上搜得二个可
用序列号,其密码部分有如下共同特征:纯由数码(0-9)构成;长度为12;最高位为1;低二
位为00。因此推测此算法可能是纯粹的数值算法。


2. 反向工程

   (1) 首先用PEid0.94查壳,显示Borland Delphi 2.0。——说到查壳,最初的时候我查
壳的意识并不强。那时觉得既然调试器可加载运行就行了,何必查壳呢?直到有一次调试器发出
警告,说代码段经过压缩,分析结果可能错误云云时,我才意识到有壳并且重视起查壳这道工序
来。——还好这个程序没壳,否则,以鄙人目前的技术水平也搞不定。

   (2) 运行原程序,试注册,出现错误提示信息:"The User Name or Password are not 
correct, please try again"。然后用OllyICE加载,查找此字串。


//////////////////////     以下是代码     ////////////////////

004F89CD  |.  8B83 B4010000 MOV     EAX, [EBX+1B4]
004F89D3  |.  E8 D065F2FF   CALL    0041EFA8
004F89D8  |.  8B85 54FEFFFF MOV     EAX, [EBP-1AC]
004F89DE  |.  8D95 58FEFFFF LEA     EDX, [EBP-1A8]                          ;  断点
004F89E4  |.  E8 3FFEFFFF   CALL    004F8828                                ;  算密码CALL
004F89E9  |.  8B85 58FEFFFF MOV     EAX, [EBP-1A8]
004F89EF  |.  50            PUSH    EAX
004F89F0  |.  8D95 54FEFFFF LEA     EDX, [EBP-1AC]
004F89F6  |.  8B83 B0010000 MOV     EAX, [EBX+1B0]
004F89FC  |.  E8 A765F2FF   CALL    0041EFA8
004F8A01  |.  8B95 54FEFFFF MOV     EDX, [EBP-1AC]
004F8A07  |.  58            POP     EAX
004F8A08  |.  E8 03B1F0FF   CALL    00403B10                                
004F8A0D  |.  0F85 9F010000 JNZ     004F8BB2                                ;  关键跳转
004F8A13  |.  8B15 48BE5200 MOV     EDX, [52BE48]
004F8A19  |.  8D85 58FEFFFF LEA     EAX, [EBP-1A8]
004F8A1F  |.  E8 FCAEF0FF   CALL    00403920

//  ……此段代码省略

004F8BB2  |>  B8 908C4F00   MOV     EAX, 004F8C90                           ;  ASCII "The User Name or Password are not correct, please try again"
004F8BB7  |.  E8 7403F4FF   CALL    00438F30

//////////////////////     以上是代码     ////////////////////


这个字串出现的位置恰好是一个跳转的目标,因此判定该跳转即为关键跳转。这个跳转N长(看
地址差即可明白),因而我省略了中间一段非关键的代码。如果要爆破,把这个跳转占的几个字
节全部改成90H就OK了,但现在的目标是要找注册算法。在这个跳转前面还有好几个CALL,究竟
哪一个才是生成注册密码的CALL呢?为此在这些CALL之前分别尝试下断点,然后单步步过。直到
看到步过某个CALL之后,堆栈区(或者别的某个地方)出现了注册码字串,而在之前并没有,便
可肯定刚才步过的就是包含密码算法的CALL。以下跟进此CALL中:


//////////////////////     以下是代码     ////////////////////

004F8828  /$  55            PUSH    EBP
004F8829  |.  8BEC          MOV     EBP, ESP
004F882B  |.  83C4 EC       ADD     ESP, -14
004F882E  |.  53            PUSH    EBX
004F882F  |.  56            PUSH    ESI
004F8830  |.  57            PUSH    EDI
004F8831  |.  33C9          XOR     ECX, ECX
004F8833  |.  894D F0       MOV     [EBP-10], ECX
004F8836  |.  894D EC       MOV     [EBP-14], ECX
004F8839  |.  8955 F8       MOV     [EBP-8], EDX
004F883C  |.  8945 FC       MOV     [EBP-4], EAX
004F883F  |.  8B45 FC       MOV     EAX, [EBP-4]
004F8842  |.  E8 6DB3F0FF   CALL    00403BB4
004F8847  |.  33C0          XOR     EAX, EAX
004F8849  |.  55            PUSH    EBP
004F884A  |.  68 4F894F00   PUSH    004F894F
004F884F  |.  64:FF30       PUSH    DWORD PTR FS:[EAX]
004F8852  |.  64:8920       MOV     FS:[EAX], ESP
004F8855  |.  33FF          XOR     EDI, EDI
004F8857  |.  8B45 FC       MOV     EAX, [EBP-4]
004F885A  |.  E8 A1B1F0FF   CALL    00403A00                                ;  EAX <=== 用户名串长
004F885F  |.  8BF0          MOV     ESI, EAX
004F8861  |.  85F6          TEST    ESI, ESI
004F8863  |.  7E 59         JLE     SHORT 004F88BE
004F8865  |.  BB 01000000   MOV     EBX, 1
004F886A  |>  8B45 FC       /MOV     EAX, [EBP-4]
004F886D  |.  0FB64418 FF   |MOVZX   EAX, BYTE PTR [EAX+EBX-1]              ;  从用户名字符串中读一字符
004F8872  |.  25 01000080   |AND     EAX, 80000001
004F8877  |.  79 05         |JNS     SHORT 004F887E                         ;  所读数值为正,跳
004F8879  |.  48            |DEC     EAX
004F887A  |.  83C8 FE       |OR      EAX, FFFFFFFE
004F887D  |.  40            |INC     EAX
004F887E  |>  85C0          |TEST    EAX, EAX
004F8880  |.  75 1D         |JNZ     SHORT 004F889F                         ;  字符ASCII码为奇数,跳
004F8882  |.  8B45 FC       |MOV     EAX, [EBP-4]
004F8885  |.  0FB64418 FF   |MOVZX   EAX, BYTE PTR [EAX+EBX-1]
004F888A  |.  69C0 CEC10400 |IMUL    EAX, EAX, 4C1CE                        ;  EAX乘以311758
004F8890  |.  8945 F4       |MOV     [EBP-C], EAX
004F8893  |.  DB45 F4       |FILD    DWORD PTR [EBP-C]
004F8896  |.  E8 31A3F0FF   |CALL    00402BCC
004F889B  |.  03F8          |ADD     EDI, EAX
004F889D  |.  EB 1B         |JMP     SHORT 004F88BA
004F889F  |>  8B45 FC       |MOV     EAX, [EBP-4]
004F88A2  |.  0FB64418 FF   |MOVZX   EAX, BYTE PTR [EAX+EBX-1]
004F88A7  |.  69C0 0B581500 |IMUL    EAX, EAX, 15580B                       ;  EAX乘以1398795
004F88AD  |.  8945 F4       |MOV     [EBP-C], EAX
004F88B0  |.  DB45 F4       |FILD    DWORD PTR [EBP-C]
004F88B3  |.  E8 14A3F0FF   |CALL    00402BCC
004F88B8  |.  03F8          |ADD     EDI, EAX                               ;  EDI存放累加值
004F88BA  |>  43            |INC     EBX
004F88BB  |.  4E            |DEC     ESI
004F88BC  |.^ 75 AC         \JNZ     SHORT 004F886A
004F88BE  |>  8B45 FC       MOV     EAX, [EBP-4]
004F88C1  |.  E8 3AB1F0FF   CALL    00403A00                                ;  EAX <== 用户名字符串长度
004F88C6  |.  25 01000080   AND     EAX, 80000001
004F88CB  |.  79 05         JNS     SHORT 004F88D2
004F88CD  |.  48            DEC     EAX
004F88CE  |.  83C8 FE       OR      EAX, FFFFFFFE
004F88D1  |.  40            INC     EAX
004F88D2  |>  85C0          TEST    EAX, EAX
004F88D4  |.  75 2C         JNZ     SHORT 004F8902                          ;  串长为奇数,跳
004F88D6  |.  8B45 F8       MOV     EAX, [EBP-8]
004F88D9  |.  50            PUSH    EAX
004F88DA  |.  8D45 F0       LEA     EAX, [EBP-10]
004F88DD  |.  50            PUSH    EAX
004F88DE  |.  8D55 EC       LEA     EDX, [EBP-14]
004F88E1  |.  8BC7          MOV     EAX, EDI
004F88E3  |.  E8 E0E3F0FF   CALL    00406CC8
004F88E8  |.  8B45 EC       MOV     EAX, [EBP-14]
004F88EB  |.  B1 31         MOV     CL, 31                                  ;  以1补高位,补足10位
004F88ED  |.  B2 0A         MOV     DL, 0A
004F88EF  |.  E8 98650100   CALL    0050EE8C
004F88F4  |.  8B45 F0       MOV     EAX, [EBP-10]
004F88F7  |.  B1 30         MOV     CL, 30                                  ;  以0补低位,补足12位
004F88F9  |.  B2 0C         MOV     DL, 0C
004F88FB  |.  E8 4C660100   CALL    0050EF4C
004F8900  |.  EB 2A         JMP     SHORT 004F892C
004F8902  |>  8B45 F8       MOV     EAX, [EBP-8]
004F8905  |.  50            PUSH    EAX
004F8906  |.  8D45 F0       LEA     EAX, [EBP-10]
004F8909  |.  50            PUSH    EAX
004F890A  |.  8D55 EC       LEA     EDX, [EBP-14]
004F890D  |.  8BC7          MOV     EAX, EDI
004F890F  |.  E8 B4E3F0FF   CALL    00406CC8                                ;  处理过程
004F8914  |.  8B45 EC       MOV     EAX, [EBP-14]
004F8917  |.  B1 37         MOV     CL, 37                                  ;  以7补高位,补足10位
004F8919  |.  B2 0A         MOV     DL, 0A
004F891B  |.  E8 6C650100   CALL    0050EE8C                                ;  只取10位
004F8920  |.  8B45 F0       MOV     EAX, [EBP-10]
004F8923  |.  B1 39         MOV     CL, 39                                  ;  以9补低位,补足12位
004F8925  |.  B2 0C         MOV     DL, 0C
004F8927  |.  E8 20660100   CALL    0050EF4C
004F892C  |>  33C0          XOR     EAX, EAX
004F892E  |.  5A            POP     EDX
004F892F  |.  59            POP     ECX
004F8930  |.  59            POP     ECX
004F8931  |.  64:8910       MOV     FS:[EAX], EDX
004F8934  |.  68 56894F00   PUSH    004F8956
004F8939  |>  8D45 EC       LEA     EAX, [EBP-14]
004F893C  |.  BA 02000000   MOV     EDX, 2
004F8941  |.  E8 66AFF0FF   CALL    004038AC
004F8946  |.  8D45 FC       LEA     EAX, [EBP-4]
004F8949  |.  E8 3EAFF0FF   CALL    0040388C
004F894E  \.  C3            RETN
004F894F   .^ E9 34ABF0FF   JMP     00403488
004F8954   .^ EB E3         JMP     SHORT 004F8939
004F8956   .  5F            POP     EDI
004F8957   .  5E            POP     ESI
004F8958   .  5B            POP     EBX
004F8959   .  8BE5          MOV     ESP, EBP
004F895B   .  5D            POP     EBP
004F895C   .  C3            RETN

//////////////////////     以上是代码     ////////////////////


这段代码的核心部分我已做了分析,关键的指令已加了注释。但需要说明的是我并没有跟进每一
个CALL中去(我最初也尝试那样做,但很快就被浩瀚的代码搅得晕头转向找不着北。),那怎么
保证分析结果是可靠的呢?简单的说还是靠动态测试,这一点在下面一小节中再详加说明。现在
把分析结果简单总结如下:

  读入并储存用户名(User Name)字串……
  依次取此字串各字符ASCII码,并视其为偶数或奇数,而分别乘以311758或1398795
  将这些乘积累加……和数记为S
  若S大于或等于10H^8(4294967296),模10H^8
  若S大于8*10H^7(2147483648),取S的补码(S=10H^8-S),并在前添负号
  若S十进制表示不足10字符,则高位用1(当UserName串长为偶数)或7(否则)补足10位
  若S十进制表示(包含负号)超过10字符,则截尾使S为10字符
  在S后添00(当UserName串长为偶数)或99(否则),得最终密码


   (3) 上面已说过,不读完一个过程的所有代码也可得知此过程的主要功能,靠的就是动
态测试,或者说是黑盒测试。象上面一段代码中的CALL 00403A00这个过程,我最初并不知道它
是干什么用的。但几次试运行通过这个语句时,EAX的值都变成一个很小的数(通常不超过
10H),我就猜测它可能是测字符串长之类的函数。于是我每次尝试输入不同长度的用户名,并
默记这个串长,同此处的EAX值比较,结果支持了我的推断。

   既然算法分析用的是不完全归纳,自然也需要验证。于是准备如下几组用户名数据:

     a)  "BB"——'B'=66为偶数,66*2*311758=41152056,串长为偶数,期望输出结果:
   114115205600,结果——符合预测。
 
          b)  "A"——'A'=65为奇数,65*1398795=90921675,串长为奇数,期望输出结果:
   779092167599,结果——符合预测。

          c)  "yyyyyyyyyyyy"——'y'=121为奇数,121*12*1398795=2031050340,本身已满
      10位,但未超过2147483648。串长为偶数,期望输出结果:
      203105034000,结果——符合预测。

          d)  "yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy"——共39个y——这组数据本来
   是用来检测,既然EDI存放累加和,如果溢出会导致什么结果?跟踪发现溢出后简单地把
   最高位舍去,也即模去10H^8。但输出的密码中却出现了负号:-19890209899。这时我意
   识到问题没有那么简单,可能程序把累加和当有符号数处理了。经过跟踪来到:


//////////////////////     以下是代码     ////////////////////

004077C2  /$  24 DF         AND     AL, 0DF
004077C4  |.  88C1          MOV     CL, AL
004077C6  |.  B8 01000000   MOV     EAX, 1
004077CB  |.  8B5D F8       MOV     EBX, [EBP-8]
004077CE  |.  3B5D 08       CMP     EBX, [EBP+8]
004077D1  |.  77 50         JA      SHORT 00407823
004077D3  |.  FF45 F8       INC     DWORD PTR [EBP-8]
004077D6  |.  8B75 0C       MOV     ESI, [EBP+C]
004077D9  |.  8D34DE        LEA     ESI, [ESI+EBX*8]
004077DC  |.  8B06          MOV     EAX, [ESI]                       ;  EAX=上述累加和
004077DE  |.  0FB65E 04     MOVZX   EBX, BYTE PTR [ESI+4]
004077E2  |.  FF249D E97740>JMP     [EBX*4+4077E9]
004077E9  |.  30784000      DD      ectool32.00407830                ;  分支表 被用于 004077E2
004077ED  |.  21784000      DD      ectool32.00407821
004077F1  |.  93784000      DD      ectool32.00407893
004077F5  |.  2A794000      DD      ectool32.0040792A
004077F9  |.  BF784000      DD      ectool32.004078BF
004077FD  |.  0C794000      DD      ectool32.0040790C
00407801  |.  EC784000      DD      ectool32.004078EC
00407805  |.  21784000      DD      ectool32.00407821
00407809  |.  21784000      DD      ectool32.00407821
0040780D  |.  21784000      DD      ectool32.00407821
00407811  |.  21784000      DD      ectool32.00407821
00407815  |.  D0784000      DD      ectool32.004078D0
00407819  |.  26794000      DD      ectool32.00407926
0040781D  |.  9E784000      DD      ectool32.0040789E
00407821  |>  31C0          XOR     EAX, EAX                         ;  Default case of switch 00407930
00407823  |>  8B55 F0       MOV     EDX, [EBP-10]
00407826  |.  8B4D E0       MOV     ECX, [EBP-20]
00407829  |.  29D1          SUB     ECX, EDX
0040782B  |.  E8 0CFEFFFF   CALL    0040763C
00407830  |>  80F9 44       CMP     CL, 44                           ;  Switch (cases 44..58)
00407833  |.  74 11         JE      SHORT 00407846                   ;  十进制数?
00407835  |.  80F9 55       CMP     CL, 55
00407838  |.  74 1E         JE      SHORT 00407858                   ;  无符号?
0040783A  |.  80F9 58       CMP     CL, 58
0040783D  |.^ 75 E2         JNZ     SHORT 00407821
0040783F  |.  B9 10000000   MOV     ECX, 10                          ;  Case 58 ('X') of switch 00407830
00407844  |.  EB 17         JMP     SHORT 0040785D
00407846  |>  09C0          OR      EAX, EAX                         ;  Case 44 ('D') of switch 00407830
00407848  |.  79 0E         JNS     SHORT 00407858                   ;  EAX不大于80000000H,跳
0040784A  |.  F7D8          NEG     EAX                              ;  否则,求补数
0040784C  |.  E8 07000000   CALL    00407858
00407851  |.  B0 2D         MOV     AL, 2D                           ;  AL='-'(负号)
00407853  |.  41            INC     ECX                              ;  加负号后串长
00407854  |.  4E            DEC     ESI
00407855  |.  8806          MOV     [ESI], AL
00407857  |.  C3            RETN
00407858  |$  B9 0A000000   MOV     ECX, 0A                          ;  Case 55 ('U') of switch 00407830
0040785D  |>  8D75 C8       LEA     ESI, [EBP-38]
00407860  |>  31D2          /XOR     EDX, EDX
00407862  |.  F7F1          |DIV     ECX                             ;  EAX除以10
00407864  |.  80C2 30       |ADD     DL, 30
00407867  |.  80FA 3A       |CMP     DL, 3A
0040786A  |.  72 03         |JB      SHORT 0040786F                  ;  未除尽,跳
0040786C  |.  80C2 07       |ADD     DL, 7
0040786F  |>  4E            |DEC     ESI
00407870  |.  8816          |MOV     [ESI], DL                       ;  存ASCII码
00407872  |.  09C0          |OR      EAX, EAX
00407874  |.^ 75 EA         \JNZ     SHORT 00407860                  ;  依次析出各位十进数码
00407876  |.  8D4D C8       LEA     ECX, [EBP-38]
00407879  |.  29F1          SUB     ECX, ESI                         ;  ECX=串长(十进制位数)
0040787B  |.  8B55 E4       MOV     EDX, [EBP-1C]
0040787E  |.  83FA 10       CMP     EDX, 10
00407881  |.  72 01         JB      SHORT 00407884
00407883  |.  C3            RETN

//////////////////////     以上是代码     ////////////////////


   果然,程序在EAX的值大于或等于80000000H之时对它求了补码,且当负数处理。计算得知
      121*39*1398795-2*4294967296=-1989020987,而程序中显示的是-198902098,那一定是
   截去了末尾的7。串长39为奇数,所以这个输出也算符合预测。

     e) "yyyyyyyyyyyyyyyyyyyyyyyyy"——共25个y——计算得知121*25*1398795=
   4231354875,其补码为-63612421,期望输出:
   7-6361242199,结果——符合预测。

          f) "wwwwwwwwwwwwwwwwwwwwwwwww"——共25个w——计算得知119*25*1398795=
      4161415125,其补码为-133552171,期望输出:
   -13355217199,结果——符合预测。

至此,上述注册算法基本验证完毕。

   (4) 注册机:本来打算写个注册机源程序,但C语言的库函数我都忘得差不多了,没办法
了,等以后复习C的时候再写吧!


3. 感想


   软件的反向工程有很多方面的应用,解密只是其中一方面,可能还谈不上是比较主要的方
面。更为重要的是,通过一个软件的反向工程,研究它的工作原理,从而编写合适的代码,为原
来的软件增加新的功能,让它更好地服务于用户。解密只能看做学习反向工程的入门,而无法成
为一种职业。

   我本来打算用静态反汇编器来分析这个软件,因为考虑到调试器在某些场合有局限性(如
程序含恶意代码,以及网游的反外挂功能可能会封杀调试器等等),在没有弄清程序工作原理前
不宜贸然使用调试器。但硬读汇编代码实在是头痛,况且鄙人目前对操作系统的细节基本上一窍
不通。思虑再三,还是只得选用调试器。