【文章作者】: 月中人(yzhr)
【目标名称】: Keygenme #1 by mario
【下载地址】: http://www.crackmes.de/users/mrio_crk/keygenme1/download
【使用工具】: Ollydbg, eXescope
【难易等级】: easy 但费点脑筋，适合新手
【作者声明】: 顺便说一句，本贴发布时该网站已有Solution by Blub，不是我的啊
--------------------------------------------------------------------------------
【注册算法简析】
  1）输入序列号字串，按常见的方法两两变换成一字节，从后面分析看来字串有效长度是162字符，变换出81字节；
  2）输入Team字串用标准MD5算法加密输出16字节；
  3）循环用这16字节计算出1字节去异或由序列号变来的81字节（每轮1字节）、并用异或前的序列号该字节改变MD5值16字节（异或，影响到下一轮）；
  4）输入用户名，循环256轮根据用户名字符弄乱0到255这组字节数据，用户名可循环使用；
  5）循环每轮先交换256字节数据中的两个，再用它们的和为地址取一字节，去异或由序列号变来的81字节（每轮1字节）；
  6）然后替换81字节中指定的26个位置为指定数字。
  最后就检验经过前面变换后的81字节是不是符合下面的条件：
  首先必须全部是1到9的数字，不然就白白。接着进行三个检验，都过了不跳走就弹出正确消息。
  为方便说明我把81字节看成9横9纵的排列形式，并分为9个区块：
  第1区是第123行的第123列，第2区是第123行的第456列，第3区是第123行的第789列，
  第4区是第456行的第123列，第5区是第456行的第456列，第6区是第456行的第789列，
  第7区是第789行的第123列，第8区是第789行的第456列，第9区是第789行的第789列。
  条件是：
  1.所有区块的9个数字都不重复（即气泡排序后小到大是"123456789"）
  2.所有纵向的9个数字都不重复
  3.所有横向的9个数字都不重复
  重复与否的检验算法是，9个数字（0x31--0x39），减0x30得1-9，小到大排序后乘十累加，结果必须等于0x75BCD15(十进制123456789)。
  
  从以上分析可知，做他的注册机关键是先找到符合条件的9x9数字排列，开始以为组合数多得穷举不完，琢磨一天后想到26个确定值限制了其他位置的可能值范围，用递归函数对剩下的55个位置逐个尝试赋值并检测，出现横纵或区块内重复数字立即返回上级、不再深入(最大递归深度55)；编个程序（详见附件中的TR99.exe及其源码）不到1秒就可以完成所有尝试，实际上递归调用不到4500次，在26个值已确定的情况只找到唯一组合；如果已有一个正确的序列号也可以动态跟踪出这个数字组合。
  ******************
  39x5x2xx7
  xx4xxx2xx
  8xxxxx3xx
  6xxx14xxx
  xxx7x6xxx
  xxx28xxx6
  xx5xxxxx4
  xx2xxx8xx
  9xx8x7x23
  ******************
  391562487
  564378219
  827491365
  658914732
  249736158
  173285946
  785123694
  432659871
  916847523
  ******************
  
  //即上面提到的第3）步（前两步略过，MD5源码可以从网上下载）
  00401714  /$  60            PUSHAD
  00401715  |.  8B4C24 28     MOV ECX,DWORD PTR SS:[ESP+28]    ;外层循环次数81
  00401719  |.  8B7424 2C     MOV ESI,DWORD PTR SS:[ESP+2C]    ;Team字串的MD5值
  0040171D  |.  BF 2C464000   MOV EDI,KEYGEN.0040462C
  00401722  |.  890D 28464000 MOV DWORD PTR DS:[404628],ECX
  00401728  |.  57            PUSH EDI
  00401729  |.  B9 04000000   MOV ECX,4
  0040172E  |.  FC            CLD
  0040172F  |.  F3:A5         REP MOVS DWORD PTR ES:[EDI],DWORD PTR DS>  ;复制MD5值16字节
  00401731  |.  5E            POP ESI
  00401732  |.  8B6C24 24     MOV EBP,DWORD PTR SS:[ESP+24]     ;序列号的81字节首址
  00401736  |.  66:33FF       XOR DI,DI
  00401739  |.  66:33D2       XOR DX,DX
  0040173C  |>  33C9          /XOR ECX,ECX
  0040173E  |.  66:33C0       |XOR AX,AX
  00401741  |.  66:33DB       |XOR BX,BX
  00401744  |>  66:03D1       |/ADD DX,CX
  00401747  |.  32244E        ||XOR AH,BYTE PTR DS:[ESI+ECX*2]
  0040174A  |.  66:69D2 354E  ||IMUL DX,DX,4E35
  0040174F  |.  32444E 01     ||XOR AL,BYTE PTR DS:[ESI+ECX*2+1]
  00401753  |.  66:03D7       ||ADD DX,DI
  00401756  |.  66:69F8 5A01  ||IMUL DI,AX,15A     ; DI=AX*0x15A 注意是16位数乘积
  0040175B  |.  66:03D7       ||ADD DX,DI
  0040175E  |.  66:69C0 354E  ||IMUL AX,AX,4E35    ; AX=AX*0X4E35
  00401763  |.  66:33DA       ||XOR BX,DX
  00401766  |.  66:40         ||INC AX
  00401768  |.  41            ||INC ECX            ;内层循环的计数器++
  00401769  |.  66:33D8       ||XOR BX,AX          ;结果在BX
  0040176C  |.  83E1 07       ||AND ECX,7          ;即8轮
  0040176F  |.^ 75 D3         |\JNZ SHORT KEYGEN.00401744
  00401771  |.  8A6D 00       |MOV CH,BYTE PTR SS:[EBP]   ;从序列号81字节顺序取1字节
  00401774  |.  32DF          |XOR BL,BH           ; BL等下用
  00401776  |.  8ACD          |MOV CL,CH           ;用CH充满32位寄存器
  00401778  |.  C1C1 08       |ROL ECX,8
  0040177B  |.  8ACD          |MOV CL,CH
  0040177D  |.  C1C1 08       |ROL ECX,8
  00401780  |.  8ACD          |MOV CL,CH
  00401782  |.  310E          |XOR DWORD PTR DS:[ESI],ECX    ;改变MD5值、影响下一轮
  00401784  |.  314E 04       |XOR DWORD PTR DS:[ESI+4],ECX
  00401787  |.  314E 08       |XOR DWORD PTR DS:[ESI+8],ECX
  0040178A  |.  314E 0C       |XOR DWORD PTR DS:[ESI+C],ECX
  0040178D  |.  305D 00       |XOR BYTE PTR SS:[EBP],BL      ; BL异或序列号这个字节(CH)
  00401790  |.  45            |INC EBP
  00401791  |.  FF0D 28464000 |DEC DWORD PTR DS:[404628]     ;外层循环计数器--
  00401797  |.^ 75 A3         \JNZ SHORT KEYGEN.0040173C
  00401799  |.  BF 2C464000   MOV EDI,KEYGEN.0040462C
  0040179E  |.  8327 00       AND DWORD PTR DS:[EDI],0
  004017A1  |.  8367 04 00    AND DWORD PTR DS:[EDI+4],0
  004017A5  |.  8367 08 00    AND DWORD PTR DS:[EDI+8],0
  004017A9  |.  8367 0C 00    AND DWORD PTR DS:[EDI+C],0
  004017AD  |.  61            POPAD
  004017AE  \.  C2 0C00       RETN 0C
  这一步的逆算法只要把上面代码中“用序列号1字节改变MD5值后，再用BL异或序列号这个字节”的顺序反向，即改成“先用BL异或序列号该字节恢复它原来值，然后用它改变MD5值”的顺序就行了。
  
  //即第4）步根据用户名弄乱256字节数据（初始化）
  00401000  /$  55            PUSH EBP
  00401001  |.  8BEC          MOV EBP,ESP
  00401003  |.  60            PUSHAD
  00401004  |.  B8 FCFDFEFF   MOV EAX,FFFEFDFC
  00401009  |.  B9 40000000   MOV ECX,40
  0040100E  |>  89048D 9C4440>/MOV DWORD PTR DS:[ECX*4+40449C],EAX  ;小循环初始化赋值256字节
  00401015  |.  2D 04040404   |SUB EAX,4040404
  0040101A  |.  49            |DEC ECX
  0040101B  |.^ 75 F1         \JNZ SHORT KEYGEN.0040100E
  0040101D  |.  33C0          XOR EAX,EAX
  0040101F  |.  8B7D 08       MOV EDI,[ARG.1]       ;用户名
  00401022  |>  33DB          XOR EBX,EBX
  00401024  |.  8B75 0C       MOV ESI,[ARG.2]       ;用户名长度
  00401027  |.  EB 05         JMP SHORT KEYGEN.0040102E
  00401029  |>  FEC3          /INC BL
  0040102B  |.  4E            |DEC ESI
  0040102C  |.^ 74 F4         |JE SHORT KEYGEN.00401022
  0040102E  |>  8A91 A0444000  MOV DL,BYTE PTR DS:[ECX+4044A0]    ;顺序取初始化过256内的1字节
  00401034  |.  02043B        |ADD AL,BYTE PTR DS:[EBX+EDI]       ;加上用户名1字节
  00401037  |.  02C2          |ADD AL,DL                          ;和作为地址
  00401039  |.  8AB0 A0444000 |MOV DH,BYTE PTR DS:[EAX+4044A0]
  0040103F  |.  88B1 A0444000 |MOV BYTE PTR DS:[ECX+4044A0],DH    ;字节交换
  00401045  |.  8890 A0444000 |MOV BYTE PTR DS:[EAX+4044A0],DL
  0040104B  |.  FEC1          |INC CL
  0040104D  |.^ 75 DA         \JNZ SHORT KEYGEN.00401029
  0040104F  |.  61            POPAD
  00401050  |.  C9            LEAVE
  00401051  \.  C2 0800       RETN 8
  这步算法用C实现如下：
          BYTE username[49];        //用户名
          BYTE frname[256];        //生成数据块
          LPDWORD lpd;
          int i,len;
          DWORD dt;
          BYTE ta,tb,tc,tdh,tdl;
          dt=0xFFFEFDFC;
          lpd=(LPDWORD)frname;
          for(i=0;i<64;i++){        //初始化数据块
                  *lpd=dt;
                  dt-=0x4040404;
                  lpd++;
          }
          tc=0;
          ta=0;
  REUE:
          tb=0;
          len=strlen((char *)username);
          goto AGSM
  CHKT:
          tb++;
          len--;
          if(len==0)goto REUE;                //用户名可以循环使用
  AGSM:
          tdl=frname[tc];
          ta=ta+(BYTE)username[tb];        //逐个取用户名字节
          ta+=tdl;
          tdh=frname[ta];                        //作为地址取值
          frname[tc]=tdh;
          frname[ta]=tdl;
          tc++;
          if(tc!=0)goto CHKT;                //256次
  
  理解后简化如下：
          BYTE username[49];
          BYTE frname[256];
          int i,j,len;
          BYTE tt,tn=0;
          for(i=0;i<256;i++) frname[i]=i;
          len=strlen((char *)username);
          for(i=0,j=0;i<256;i++){
                  tn+=username[j];
                  tn+=frname[i];
                  tt=frname[i];
                  frname[i]=frname[tn];
                  frname[tn]=tt;
                  j++;
                  if(j>=len)j=0;
          }
  
  //即第5）再次变换序列号的81字节
  00401054  /$  55            PUSH EBP
  00401055  |.  8BEC          MOV EBP,ESP
  00401057  |.  60            PUSHAD
  00401058  |.  8B7D 0C       MOV EDI,[ARG.2]
  0040105B  |.  8B75 08       MOV ESI,[ARG.1]
  0040105E  |.  85FF          TEST EDI,EDI
  00401060  |.  74 41         JE SHORT KEYGEN.004010A3
  00401062  |.  33C0          XOR EAX,EAX
  00401064  |.  33DB          XOR EBX,EBX
  00401066  |.  33C9          XOR ECX,ECX
  00401068  |.  33D2          XOR EDX,EDX
  0040106A  |>  FEC3          /INC BL
  0040106C  |.  8A93 A0444000 |MOV DL,BYTE PTR DS:[EBX+4044A0]    ;顺序取256内的1字节
  00401072  |.  02C2          |ADD AL,DL                          ;累加到AL
  00401074  |.  8A88 A0444000 |MOV CL,BYTE PTR DS:[EAX+4044A0]    ;作为地址再取1字节
  0040107A  |.  888B A0444000 |MOV BYTE PTR DS:[EBX+4044A0],CL    ;两两交换
  00401080  |.  8890 A0444000 |MOV BYTE PTR DS:[EAX+4044A0],DL
  00401086  |.  02CA          |ADD CL,DL
  00401088  |.  8A89 A0444000 |MOV CL,BYTE PTR DS:[ECX+4044A0]    ;用两值之和作为地址取1字节
  0040108E  |.  300E          |XOR BYTE PTR DS:[ESI],CL           ;去异或序列号的1字节
  00401090  |.  46            |INC ESI
  00401091  |.  4F            |DEC EDI
  00401092  |.^ 75 D6         \JNZ SHORT KEYGEN.0040106A          ;循环81轮
  00401094  |.  33C0          XOR EAX,EAX
  00401096  |.  BF A0444000   MOV EDI,KEYGEN.004044A0
  0040109B  |.  B9 40000000   MOV ECX,40
  004010A0  |.  FC            CLD
  004010A1  |.  F3:AB         REP STOS DWORD PTR ES:[EDI]
  004010A3  |>  61            POPAD
  004010A4  |.  C9            LEAVE
  004010A5  \.  C2 0800       RETN 8
  这一步的逆算法与原算法完全一样
  
  //即第6）步检查前替换26个确定值
  004019A9  |.  B8 31000000   MOV EAX,31
  004019AE  |.  BF 71414000   MOV EDI,KEYGEN.00404171        ;序列号的81字节首地址
  004019B3  |.  8847 1F       MOV BYTE PTR DS:[EDI+1F],AL    ;替换位置31的值为31
  004019B6  |.  FEC0          INC AL
  ...
  00401A0A  |.  8847 01       MOV BYTE PTR DS:[EDI+1],AL
  00401A0D  |.  8847 48       MOV BYTE PTR DS:[EDI+48],AL
  
  下面检查代码的原理前面讲过了
  CALL KEYGEN.00401B64         ;按隔9字节取3字节的规律取9字节
  CALL KEYGEN.00401BAB         ;按n=9*i,i=0...8规律取9字节
  CALL KEYGEN.00401BCC         ;顺序取9字节
  上面三个CALL都有调用下面代码具体检查正确性
  00401BF3  /$  57            PUSH EDI
  00401BF4  |.  6A 09         PUSH 9
  00401BF6  |.  E8 DEFEFFFF   CALL KEYGEN.00401AD9     ;对9字节冒泡排序（从小到大）
  00401BFB  |.  B9 09000000   MOV ECX,9
  00401C00  |.  E8 FAFEFFFF   CALL KEYGEN.00401AFF     ;数字1--9 乘十累加
  00401C05  |.  3D 15CD5B07   CMP EAX,75BCD15          ;必须EAX等于0x75BCD15（即十进制123456789）
  00401C0A  \.  C3            RETN
  
  谢谢您的耐心看到这里，如果文中有疏漏欢迎指正。
  
  附件：注册机程序和源码
  
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2006年07月05日

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