HappyTowns 30th CrackMe 算法分析及注册机

很早以前就放出来的一个CrackMe，是关于算法方面的，我比较感兴趣，所以就研究了下。
使用了Miracl大数运算库，逆向的难度不大。算法是求解二次剩余问题，有一定的难度。

用PEiD查壳，显示
Microsoft Visual C++ 6.0
经验证，确实没有加壳。

用PEiD的Krypto ANAlyzer插件检查，结果如下：
SHA1 [Compress] :: 00004C71 :: 00404C71
{Big number} :: 0000B0D4 :: 0040B0D4
{Big number} :: 0000B118 :: 0040B118

用IDA载入，并加载常用的sig。找到注册验证的关键函数，初步分析的结果如下：

.text:00401130 ; int __cdecl OnCheck(HWND hDlg)
.text:00401130 OnCheck         proc near               ; CODE XREF: DialogFunc+61p
.text:00401130
.text:00401130 ba              = dword ptr -958h
.text:00401130 bc              = dword ptr -954h
.text:00401130 be              = dword ptr -950h
.text:00401130 hash_out        = dword ptr -94Ch
.text:00401130 var_947         = dword ptr -947h
.text:00401130 var_943         = dword ptr -943h
.text:00401130 var_93F         = dword ptr -93Fh
.text:00401130 var_93B         = word ptr -93Bh
.text:00401130 var_939         = byte ptr -939h
.text:00401130 Serial          = byte ptr -938h
.text:00401130 Serial_1        = dword ptr -744h
.text:00401130 Serial_2        = dword ptr -550h
.text:00401130 Name            = byte ptr -35Ch
.text:00401130 sha_ctx         = dword ptr -168h
.text:00401130 hDlg            = dword ptr  4
.text:00401130
.text:00401130                 sub     esp, 958h
.text:00401136                 push    ebx
.text:00401137                 push    ebp
.text:00401138                 push    esi
.text:00401139                 push    edi
.text:0040113A                 mov     ecx, 124
.text:0040113F                 xor     eax, eax
.text:00401141                 lea     edi, [esp+60Dh]
.text:00401148                 mov     [esp+968h+Name], 0
.text:00401150                 rep stosd
.text:00401152                 stosw
.text:00401154                 stosb
.text:00401155                 mov     ecx, 124
.text:0040115A                 xor     eax, eax
.text:0040115C                 lea     edi, [esp+31h]
.text:00401160                 mov     [esp+968h+Serial], 0
.text:00401165                 rep stosd
.text:00401167                 stosw
.text:00401169                 stosb
.text:0040116A                 mov     ecx, 124
.text:0040116F                 xor     eax, eax
.text:00401171                 lea     edi, [esp+968h+Serial_1+1]
.text:00401178                 mov     byte ptr [esp+968h+Serial_1], 0
.text:00401180                 rep stosd
.text:00401182                 stosw
.text:00401184                 stosb
.text:00401185                 mov     ecx, 124
.text:0040118A                 xor     eax, eax
.text:0040118C                 lea     edi, [esp+968h+Serial_2+1]
.text:00401193                 mov     byte ptr [esp+968h+Serial_2], 0
.text:0040119B                 rep stosd
.text:0040119D                 stosw
.text:0040119F                 stosb
.text:004011A0                 xor     eax, eax
.text:004011A2                 push    10h
.text:004011A4                 mov     [esp+96Ch+hash_out+1], eax
.text:004011A8                 push    320h
.text:004011AD                 mov     [esp+970h+var_947], eax
.text:004011B1                 mov     byte ptr [esp+970h+hash_out], 0
.text:004011B6                 mov     [esp+970h+var_943], eax
.text:004011BA                 mov     [esp+970h+var_93F], eax
.text:004011BE                 mov     [esp+970h+var_93B], ax
.text:004011C3                 mov     [esp+970h+var_939], al

以上是初始化几个数组变量：szName[500]，szSerial[500]，szSerial1[500]，szSerial2[500]，
hash_out[20]。

.text:004011C7                 call    _mirsys
.text:004011CC                 push    0
.text:004011CE                 mov     dword ptr [eax+234h], 16
.text:004011D8                 call    _mirvar
.text:004011DD                 push    0
.text:004011DF                 mov     ebx, eax
.text:004011E1                 call    _mirvar
.text:004011E6                 push    0
.text:004011E8                 mov     [esp+97Ch+be], eax
.text:004011EC                 call    _mirvar
.text:004011F1                 push    0
.text:004011F3                 mov     ebp, eax
.text:004011F5                 call    _mirvar
.text:004011FA                 push    0
.text:004011FC                 mov     [esp+984h+bc], eax
.text:00401200                 call    _mirvar
.text:00401205                 mov     esi, [esp+984h+hDlg]
.text:0040120C                 mov     edi, ds:GetDlgItemTextA
.text:00401212                 add     esp, 1Ch
.text:00401215                 lea     ecx, [esp+968h+Name]
.text:0040121C                 mov     [esp+968h+ba], eax
.text:00401220                 push    501             ; nMaxCount
.text:00401225                 push    ecx             ; lpString
.text:00401226                 push    1000            ; nIDDlgItem
.text:0040122B                 push    esi             ; hDlg
.text:0040122C                 call    edi ; GetDlgItemTextA       ; 取用户名
.text:0040122E                 cmp     eax, 2
.text:00401231                 jb      to_exit
.text:00401237                 lea     edx, [esp+968h+Serial]
.text:0040123B                 push    501             ; nMaxCount
.text:00401240                 push    edx             ; lpString
.text:00401241                 push    1001            ; nIDDlgItem
.text:00401246                 push    esi             ; hDlg
.text:00401247                 call    edi ; GetDlgItemTextA       ; 取注册码
.text:00401249                 lea     eax, [esp+968h+Serial]
.text:0040124D                 push    '-'             ; int
.text:0040124F                 push    eax             ; char *
.text:00401250                 call    _strchr
.text:00401255                 add     esp, 8
.text:00401258                 test    eax, eax
.text:0040125A                 jz      to_exit
.text:00401260                 mov     cl, [esp+968h+Serial]
.text:00401264                 cmp     cl, '-'
.text:00401267                 jz      short loc_40127C
.text:00401269                 xor     eax, eax
.text:0040126B
.text:0040126B loc_40126B:                             ; CODE XREF: OnCheck+14Aj
.text:0040126B                 mov     byte ptr [esp+eax+968h+Serial_1], cl
.text:00401272                 mov     cl, [esp+eax+31h]
.text:00401276                 inc     eax
.text:00401277                 cmp     cl, '-'
.text:0040127A                 jnz     short loc_40126B
.text:0040127C
.text:0040127C loc_40127C:                             ; CODE XREF: OnCheck+137j
.text:0040127C                 lea     ecx, [esp+968h+Serial]
.text:00401280                 push    '-'             ; int
.text:00401282                 push    ecx             ; char *
.text:00401283                 call    _strchr
.text:00401288                 lea     edx, [esp+970h+Serial]
.text:0040128C                 add     esp, 8
.text:0040128F                 sub     eax, edx
.text:00401291                 mov     cl, [esp+eax+968h+Serial]
.text:00401295                 lea     eax, [esp+eax+968h+Serial]
.text:00401299                 test    cl, cl
.text:0040129B                 jz      short loc_4012B2
.text:0040129D                 lea     ecx, [esp+968h+Serial_2]
.text:004012A4
.text:004012A4 loc_4012A4:                             ; CODE XREF: OnCheck+180j
.text:004012A4                 mov     dl, [eax+1]
.text:004012A7                 mov     [ecx], dl
.text:004012A9                 mov     dl, [eax+1]
.text:004012AC                 inc     ecx
.text:004012AD                 inc     eax
.text:004012AE                 test    dl, dl
.text:004012B0                 jnz     short loc_4012A4
.text:004012B2
.text:004012B2 loc_4012B2:                             ; CODE XREF: OnCheck+16Bj
.text:004012B2                 lea     edi, [esp+968h+Serial_1]
.text:004012B9                 or      ecx, 0FFFFFFFFh
.text:004012BC                 xor     eax, eax
.text:004012BE                 repne scasb
.text:004012C0                 not     ecx
.text:004012C2                 dec     ecx
.text:004012C3                 jz      to_exit
.text:004012C9                 lea     edi, [esp+968h+Serial_2]
.text:004012D0                 or      ecx, 0FFFFFFFFh
.text:004012D3                 repne scasb
.text:004012D5                 not     ecx
.text:004012D7                 dec     ecx
.text:004012D8                 jz      to_exit
.text:004012DE                 mov     al, byte ptr [esp+968h+Serial_1]
.text:004012E5                 mov     edi, 1
.text:004012EA                 test    al, al
.text:004012EC                 jz      short loc_401333
.text:004012EE                 lea     esi, [esp+968h+Serial_1]
.text:004012F5
.text:004012F5 loc_4012F5:                             ; CODE XREF: OnCheck+201j
.text:004012F5                 cmp     dword_40BFD0, edi
.text:004012FB                 jle     short loc_401311
.text:004012FD                 xor     eax, eax
.text:004012FF                 push    80h             ; int
.text:00401304                 mov     al, [esi]
.text:00401306                 push    eax             ; int
.text:00401307                 call    __isctype
.text:0040130C                 add     esp, 8
.text:0040130F                 jmp     short loc_401323
.text:00401311 ; ---------------------------------------------------------------------------
.text:00401311
.text:00401311 loc_401311:                             ; CODE XREF: OnCheck+1CBj
.text:00401311                 mov     edx, off_40BDC4
.text:00401317                 xor     ecx, ecx
.text:00401319                 mov     cl, [esi]
.text:0040131B                 mov     al, [edx+ecx*2]
.text:0040131E                 and     eax, 80h
.text:00401323
.text:00401323 loc_401323:                             ; CODE XREF: OnCheck+1DFj
.text:00401323                 test    eax, eax
.text:00401325                 jz      to_exit
.text:0040132B                 mov     al, [esi+1]
.text:0040132E                 inc     esi
.text:0040132F                 test    al, al
.text:00401331                 jnz     short loc_4012F5
.text:00401333
.text:00401333 loc_401333:                             ; CODE XREF: OnCheck+1BCj
.text:00401333                 mov     al, byte ptr [esp+968h+Serial_2]
.text:0040133A                 test    al, al
.text:0040133C                 jz      short loc_401383
.text:0040133E                 lea     esi, [esp+968h+Serial_2]
.text:00401345
.text:00401345 loc_401345:                             ; CODE XREF: OnCheck+251j
.text:00401345                 cmp     dword_40BFD0, edi
.text:0040134B                 jle     short loc_401361
.text:0040134D                 xor     eax, eax
.text:0040134F                 push    80h             ; int
.text:00401354                 mov     al, [esi]
.text:00401356                 push    eax             ; int
.text:00401357                 call    __isctype
.text:0040135C                 add     esp, 8
.text:0040135F                 jmp     short loc_401373
.text:00401361 ; ---------------------------------------------------------------------------
.text:00401361
.text:00401361 loc_401361:                             ; CODE XREF: OnCheck+21Bj
.text:00401361                 mov     edx, off_40BDC4
.text:00401367                 xor     ecx, ecx
.text:00401369                 mov     cl, [esi]
.text:0040136B                 mov     al, [edx+ecx*2]
.text:0040136E                 and     eax, 80h
.text:00401373
.text:00401373 loc_401373:                             ; CODE XREF: OnCheck+22Fj
.text:00401373                 test    eax, eax
.text:00401375                 jz      to_exit
.text:0040137B                 mov     al, [esi+1]
.text:0040137E                 inc     esi
.text:0040137F                 test    al, al
.text:00401381                 jnz     short loc_401345
.text:00401383
.text:00401383 loc_401383:                             ; CODE XREF: OnCheck+20Cj
.text:00401383                 mov     edi, offset aPediy ; "&PEdiy"
.text:00401388                 or      ecx, 0FFFFFFFFh
.text:0040138B                 xor     eax, eax
.text:0040138D                 lea     edx, [esp+968h+Name]
.text:00401394                 repne scasb
.text:00401396                 not     ecx
.text:00401398                 sub     edi, ecx
.text:0040139A                 mov     esi, edi
.text:0040139C                 mov     edi, edx
.text:0040139E                 mov     edx, ecx
.text:004013A0                 or      ecx, 0FFFFFFFFh
.text:004013A3                 repne scasb
.text:004013A5                 mov     ecx, edx
.text:004013A7                 dec     edi
.text:004013A8                 shr     ecx, 2
.text:004013AB                 rep movsd
.text:004013AD                 mov     ecx, edx
.text:004013AF                 lea     eax, [esp+968h+sha_ctx]
.text:004013B6                 and     ecx, 3
.text:004013B9                 push    eax
.text:004013BA                 rep movsb
.text:004013BC                 call    _shs_init                ; SHA1初始化
.text:004013C1                 mov     al, [esp+96Ch+Name]
.text:004013C8                 add     esp, 4
.text:004013CB                 test    al, al
.text:004013CD                 jz      short loc_4013F4
.text:004013CF                 lea     esi, [esp+968h+Name]
.text:004013D6
.text:004013D6 loc_4013D6:                             ; CODE XREF: OnCheck+2C2j
.text:004013D6                 and     eax, 0FFh
.text:004013DB                 lea     ecx, [esp+968h+sha_ctx]
.text:004013E2                 push    eax
.text:004013E3                 push    ecx
.text:004013E4                 call    _shs_process
.text:004013E9                 mov     al, [esi+1]
.text:004013EC                 add     esp, 8
.text:004013EF                 inc     esi
.text:004013F0                 test    al, al
.text:004013F2                 jnz     short loc_4013D6
.text:004013F4
.text:004013F4 loc_4013F4:                             ; CODE XREF: OnCheck+29Dj
.text:004013F4                 lea     edx, [esp+968h+hash_out]
.text:004013F8                 lea     eax, [esp+968h+sha_ctx]
.text:004013FF                 push    edx
.text:00401400                 push    eax
.text:00401401                 call    _shs_hash
.text:00401406                 mov     ecx, [esp+970h+ba]
.text:0040140A                 lea     edx, [esp+970h+hash_out]
.text:0040140E                 push    ecx
.text:0040140F                 push    edx
.text:00401410                 push    10
.text:00401412                 call    _bytes_to_big
.text:00401417                 lea     eax, [esp+97Ch+Serial_1]
.text:0040141E                 push    eax
.text:0040141F                 push    ebp
.text:00401420                 call    _cinstr
.text:00401425                 mov     esi, [esp+984h+bc]
.text:00401429                 lea     ecx, [esp+984h+Serial_2]
.text:00401430                 push    ecx
.text:00401431                 push    esi
.text:00401432                 call    _cinstr
.text:00401437                 push    offset aE97e36f9426708 ; "E97E36F9426708D10516A001FC358367B8ECBB7"...
.text:0040143C                 push    ebx
.text:0040143D                 call    _cinstr
.text:00401442                 mov     edi, [esp+994h+be]
.text:00401446                 push    offset aD9bc54b68e7f0c ; "D9BC54B68E7F0CC76BD6BEB333AA09CCE9162FA"...
.text:0040144B                 push    edi
.text:0040144C                 call    _cinstr
.text:00401451                 push    ebp
.text:00401452                 push    ebp
.text:00401453                 push    2
.text:00401455                 push    ebp
.text:00401456                 call    _power
.text:0040145B                 add     esp, 44h
.text:0040145E                 push    esi
.text:0040145F                 push    esi
.text:00401460                 push    2
.text:00401462                 push    esi
.text:00401463                 call    _power
.text:00401468                 push    edi
.text:00401469                 push    edi
.text:0040146A                 call    _negify
.text:0040146F                 push    ebp
.text:00401470                 push    ebx
.text:00401471                 push    ebx
.text:00401472                 push    ebp
.text:00401473                 push    esi
.text:00401474                 push    edi
.text:00401475                 call    _mad
.text:0040147A                 push    ebp
.text:0040147B                 push    ebx
.text:0040147C                 push    ebp
.text:0040147D                 call    _add
.text:00401482                 push    ebx
.text:00401483                 push    ebx
.text:00401484                 push    ebp
.text:00401485                 call    _divide
.text:0040148A                 mov     esi, [esp+9B0h+ba]
.text:0040148E                 add     esp, 48h
.text:00401491                 push    ebx
.text:00401492                 push    ebx
.text:00401493                 push    esi
.text:00401494                 call    _divide
.text:00401499                 push    ebp
.text:0040149A                 push    esi
.text:0040149B                 call    _compare                     ; 关键比较
.text:004014A0                 add     esp, 14h
.text:004014A3                 neg     eax
.text:004014A5                 pop     edi
.text:004014A6                 pop     esi
.text:004014A7                 sbb     eax, eax
.text:004014A9                 pop     ebp
.text:004014AA                 inc     eax
.text:004014AB                 pop     ebx
.text:004014AC                 add     esp, 958h
.text:004014B2                 retn
.text:004014B3 ; ---------------------------------------------------------------------------
.text:004014B3
.text:004014B3 to_exit:                                ; CODE XREF: OnCheck+101j
.text:004014B3                                         ; OnCheck+12Aj ...
.text:004014B3                 pop     edi
.text:004014B4                 pop     esi
.text:004014B5                 pop     ebp
.text:004014B6                 xor     eax, eax
.text:004014B8                 pop     ebx
.text:004014B9                 add     esp, 958h
.text:004014BF                 retn
.text:004014BF OnCheck         endp
.text:004014BF

该CrackMe使用了Miracl大数库，除大数运算以外，还使用了其中的SHA1算法。

注册验证过程：
1、对用户名和注册码进行检查，用户名长度至少2个字符，注册码必须是这样的：
xxxxxx-xxxxxxx，它是用'-'连起来的字符串，前后两个子串都必须由16进制字符组成，
且长度都不能为0。
2、将注册码中'-'前的子串转化为大数s1，将后面的子串转化为大数s2。将用户名与字符串
"&PEdiy"连接起来，进行SHA1运算，将结果的前10个字节转化为大数h。
3、另给定了两个大数：
n = E97E36F9426708D10516A001FC358367B8ECBB7210388B971C886AA4A44845F1
d = D9BC54B68E7F0CC76BD6BEB333AA09CCE9162FA9DF22989EC049D5BCD34981FE
4、验证 h ?= s1^2 - d * s2^2 mod n ，如果相等则注册成功，否则失败。

为生成注册码，需要求解方程 h = s1^2 - d * s2^2 mod n。该方程还有两个未知数s1和s2，
因此是一个不定方程。我们给以将该方程改写为这样：
s1^2 = h + d * s2^2 mod n
其中s2可以任意给定（取一个随机数即可），然后关于s1的方程就变成了一个二次剩余方程。
由于大数n可以分解为两个大数的乘积: n = p * q
p = EB8D197C10BA775BA2A785085C44A0C3
q = FDC35FF9D4A7BBCAD7577E99D8C8533B
故由定理可知，在有限域Zn*内大约2^-2=1/4的元素都是模n的二次剩余。这个比例还是很大的。
任取随机数s2，验证 a = h + d * s2^2 mod n 是否是模n的二次剩余，如果不是则重新选择s2。
经过多次重复以后，总可以得到一个模n的二次剩余 a 。
然后求解二次剩余方程 s1^2 = a mod n，这个可以用中国剩余定理来求。

故生成注册码的过程：
1、将用户名与字符串"&PEdiy"连接起来，进行SHA1运算，将结果的前10个字节转化为大数h。
2、另给定了两个大数：
n = E97E36F9426708D10516A001FC358367B8ECBB7210388B971C886AA4A44845F1
d = D9BC54B68E7F0CC76BD6BEB333AA09CCE9162FA9DF22989EC049D5BCD34981FE
其中 n = p * q
p = EB8D197C10BA775BA2A785085C44A0C3
q = FDC35FF9D4A7BBCAD7577E99D8C8533B
3、取随机数s2，计算 a = h + d * s2^2 mod n ，并验证a是否是模n的二次剩余，
如果不是则重新选择s2，直到a是模n的二次剩余为止。
4、用中国剩余定理求解二次剩余方程 s1^2 = a mod n，得到大数s1。
5、将s1和s2转化成字符串，并用字符'-'连接起来，即为注册码。

感谢jB,bLaCk_eYe等人的精彩教程！

源码及keygen见附件。

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