三个白帽挑战之二进制题《迷阵陷落》分析

0x00 前言


三个白帽在线挑战平台,集WEB和二进制挑战于一身,以在线挑战的形式把网络安全相关领域白帽子的技术和智慧淋漓尽致地展现出来,为白帽子们搭建了一个非常完美、和谐的在线交流平台,使得白帽子之间可以融洽地施展绝技、交流创意和想法。一次一次的挑战让白帽子们大饱眼福、乐在其中,让大家脑洞大开,并且收获满满,同时回味无穷!

由于对windows平台下二进制有过研究,本着和大家交流学习的目的,在和三个白帽平台管理沟通后,为《条条大路通罗马系列》设计了一个二进制算法题目。本文将首先从破解者角度对这个二进制题进行分析,单纯以破解者身份来逆向分析算法,解密数据,从而最终获得flag。另外将从该题设计者角度进行分析,一步步描述每步算法相对应的数据如何加密、解密的,试图达到什么样的效果,试图在哪里困住破解者。

三个白帽挑战之二进制题《迷阵陷落》分析

0x01 正向破解加密算法


首先我们按照程序的流程,一步步分析算法、破解算法。

1、和第一次二进制题一样,首先通过字符串查找,找到字符串where is flag?flag is in the beautifull spring!

2、双击字符串来到算法关键位置,相关汇编代码分析如下:

004026E0  |.  57            push    edi                            ;  这里开始了一个非常初级的数独游戏
004026E1  |.  8D4C24 10     lea     ecx, dword ptr [esp+10]
004026E5  |.  897424 18     mov     dword ptr [esp+18], esi
004026E9  |.  E8 68080000   call    <jmp.&MFC42.#CString::CString_>
004026EE  |.  33DB          xor     ebx, ebx
004026F0  |.  68 60564000   push    00405660                       ;  where is flag?flag is in the beautifull spring!
004026F5  |.  8D4C24 14     lea     ecx, dword ptr [esp+14]
004026F9  |.  C78424 D00000>mov     dword ptr [esp+D0], 1
00402704  |.  895C24 18     mov     dword ptr [esp+18], ebx
00402708  |.  E8 43080000   call    <jmp.&MFC42.#CString::operator>
0040270D  |.  8BAC24 D80000>mov     ebp, dword ptr [esp+D8]
00402714  |.  83C9 FF       or      ecx, FFFFFFFF
00402717  |.  8BFD          mov     edi, ebp
00402719  |.  33C0          xor     eax, eax
0040271B  |.  F2:AE         repne   scas byte ptr es:[edi]
0040271D  |.  F7D1          not     ecx
0040271F  |.  49            dec     ecx
00402720  |.  83E9 0C       sub     ecx, 0C
00402723  |.  74 5A         je      short 0040277F
00402725  |>  BF 54564000   /mov     edi, 00405654                 ;  adf438ghi
0040272A  |.  83C9 FF       |or      ecx, FFFFFFFF
0040272D  |.  33C0          |xor     eax, eax
0040272F  |.  33D2          |xor     edx, edx
00402731  |.  F2:AE         |repne   scas byte ptr es:[edi]
00402733  |.  F7D1          |not     ecx
00402735  |.  49            |dec     ecx
00402736  |.  74 23         |je      short 0040275B
00402738  |.  8A1C2E        |mov     bl, byte ptr [esi+ebp]        ;  单个取输入的字符
0040273B  |>  3A9A 54564000 |/cmp     bl, byte ptr [edx+405654]    ;  判断取出来的字符是否在adf438ghi中
00402741  |.  74 14         ||je      short 00402757               ;  如果是就跳出循环
00402743  |.  BF 54564000   ||mov     edi, 00405654                ;  adf438ghi
00402748  |.  83C9 FF       ||or      ecx, FFFFFFFF
0040274B  |.  33C0          ||xor     eax, eax
0040274D  |.  42            ||inc     edx
0040274E  |.  F2:AE         ||repne   scas byte ptr es:[edi]
00402750  |.  F7D1          ||not     ecx                          ;  取字符串adf438ghi的长度
00402752  |.  49            ||dec     ecx
00402753  |.  3BD1          ||cmp     edx, ecx
00402755  |.^ 72 E4         |jb      short 0040273B
00402757  |>  8B5C24 14     |mov     ebx, dword ptr [esp+14]
0040275B  |>  BF 54564000   |mov     edi, 00405654                 ;  adf438ghi
00402760  |.  83C9 FF       |or      ecx, FFFFFFFF
00402763  |.  33C0          |xor     eax, eax
00402765  |.  F2:AE         |repne   scas byte ptr es:[edi]
00402767  |.  F7D1          |not     ecx
00402769  |.  49            |dec     ecx
0040276A  |.  3BD1          |cmp     edx, ecx
0040276C  |.  74 3F         |je      short 004027AD                ;  如果上面循环次数等于adf438ghi的长度说明判断失败,跳到结束
0040276E  |.  8BFD          |mov     edi, ebp
00402770  |.  83C9 FF       |or      ecx, FFFFFFFF
00402773  |.  46            |inc     esi
00402774  |.  F2:AE         |repne   scas byte ptr es:[edi]
00402776  |.  F7D1          |not     ecx
00402778  |.  83C1 F3       |add     ecx, -0D                      ;  这个是循环次数 取输入的字符串的长度减去13
0040277B  |.  3BF1          |cmp     esi, ecx
0040277D  |.^ 72 A6         jb      short 00402725                ;  跳回去,循环判断下一个输入的字符
0040277F  |>  B9 14000000   mov     ecx, 14
00402784  |.  BE 00564000   mov     esi, 00405600                  ;  g8azfzzd3f3zzzhazgzdzzzgzf4zzizz8fghzzfdgi3zz3gzfzzizdai3g8zzzzhfd4zzg8z84gzazd3z
00402789  |.  8D7C24 70     lea     edi, dword ptr [esp+70]
0040278D  |.  33D2          xor     edx, edx
0040278F  |.  F3:A5         rep     movs dword ptr es:[edi], dword>
00402791  |.  A4            movs    byte ptr es:[edi], byte ptr [e>
00402792  |>  33C0          xor     eax, eax
00402794  |.  8D7414 70     lea     esi, dword ptr [esp+edx+70]
00402798  |>  8A0C06        mov     cl, byte ptr [esi+eax]
0040279B  |.  8D3C02        lea     edi, dword ptr [edx+eax]
0040279E  |.  80F9 7A       cmp     cl, 7A                         ;  循环判断405600地址的字符串的字符是否为z
004027A1  |.  75 2A         jnz     short 004027CD
004027A3  |.  8A0C2B        mov     cl, byte ptr [ebx+ebp]
004027A6  |.  43            inc     ebx
004027A7  |.  884C3C 1C     mov     byte ptr [esp+edi+1C], cl      ;  如果是z就把输入的字符依次替换掉z
004027AB  |.  EB 24         jmp     short 004027D1
004027AD  |>  8BB424 D40000>mov     esi, dword ptr [esp+D4]
004027B4  |.  8D4424 10     lea     eax, dword ptr [esp+10]
004027B8  |.  50            push    eax
004027B9  |.  8BCE          mov     ecx, esi
004027BB  |.  E8 EA070000   call    <jmp.&MFC42.#CString::CString_>
004027C0  |.  C74424 18 010>mov     dword ptr [esp+18], 1
004027C8  |.  E9 A4000000   jmp     00402871
004027CD  |>  884C3C 1C     mov     byte ptr [esp+edi+1C], cl
004027D1  |>  40            inc     eax
004027D2  |.  83F8 09       cmp     eax, 9
004027D5  |.^ 7C C1         jl      short 00402798                 ;  跳回去判断下一个字符
004027D7  |.  83C2 09       add     edx, 9
004027DA  |.  83FA 51       cmp     edx, 51                        ;  要分9组每组9次循环81次
004027DD  |.^ 7C B3         jl      short 00402792                 ;  跳回去继续判断下一组
004027DF  |.  C74424 14 000>mov     dword ptr [esp+14], 0
004027E7  |.  8D5C24 1C     lea     ebx, dword ptr [esp+1C]
004027EB  |.  8D4C24 1C     lea     ecx, dword ptr [esp+1C]
004027EF  |>  33C0          /xor     eax, eax                      ;  这里有3层循环是用来检查数独结果是否正确
004027F1  |.  8BEB          |mov     ebp, ebx
004027F3  |>  8A1401        |/mov     dl, byte ptr [ecx+eax]       ;  最里面一层的第一个循环以行为单位进行检查
004027F6  |.  C60401 77     ||mov     byte ptr [ecx+eax], 77       ;  具体方法就是取出当前要检查的字符,替换为0x77即w
004027FA  |.  33F6          ||xor     esi, esi
004027FC  |>  3A1431        ||/cmp     dl, byte ptr [ecx+esi]      ;  然后对该行所有的字符进行判断是否和取出的那个字符重复
004027FF  |.  0F84 9A000000 |||je      0040289F                    ;  如果存在重复就跳没了
00402805  |.  46            |||inc     esi
00402806  |.  83FE 09       |||cmp     esi, 9
00402809  |.^ 7C F1         ||jl      short 004027FC
0040280B  |.  881401        ||mov     byte ptr [ecx+eax], dl
0040280E  |.  8A55 00       ||mov     dl, byte ptr [ebp]
00402811  |.  C645 00 79    ||mov     byte ptr [ebp], 79           ;  这里以列为单位 取出当前字符替换为字符y,然后判断该列所有字符是否与取出的字符有重复
00402815  |.  33F6          ||xor     esi, esi
00402817  |.  8BFB          ||mov     edi, ebx
00402819  |>  3A17          ||/cmp     dl, byte ptr [edi]
0040281B  |.  0F84 85000000 |||je      004028A6                    ;  如果存在 就跳没了
00402821  |.  46            |||inc     esi
00402822  |.  83C7 09       |||add     edi, 9
00402825  |.  83FE 09       |||cmp     esi, 9
00402828  |.^ 7C EF         ||jl      short 00402819
0040282A  |.  8855 00       ||mov     byte ptr [ebp], dl
0040282D  |.  40            ||inc     eax
0040282E  |.  83C5 09       ||add     ebp, 9
00402831  |.  83F8 09       ||cmp     eax, 9
00402834  |.^ 7C BD         |jl      short 004027F3               ;  外边两层循环,行判断时分别控制行标和列标;列判断时分别控制列标和行标
00402836  |.  8B4424 14     |mov     eax, dword ptr [esp+14]
0040283A  |.  83C1 09       |add     ecx, 9
0040283D  |.  40            |inc     eax
0040283E  |.  43            |inc     ebx
0040283F  |.  83F8 09       |cmp     eax, 9
00402842  |.  894424 14     |mov     dword ptr [esp+14], eax
00402846  |.^ 7C A7         jl      short 004027EF
00402848  |.  68 E0554000   push    004055E0                       ;  good !flag is waving to you!

3、根据上面分析的结果,整理如下:

首先撇开后12个字符不管,判断前面的字符串(以s命名)中的字符是否都是字符串adf438ghi中的字符,内存地址405600处字符串(以f命名)为g8azfzzd3f3zzzhazgzdzzzgzf4zzizz8fghzzfdgi3zz3gzfzzizdai3g8zzzzhfd4zzg8z84gzazd3z,把s依次替换f中的z字符,替换后依次9个字符为一行检查是否有重复字符,同时9个字符为一列检查是否有重复字符。把f转为列表形式如下:

g8azfzzd3
f3zzzhazg
zdzzzgzf4
zzizz8fgh
zzfdgi3zz
3gzfzzizd
ai3g8zzzz
hfd4zzg8z
84gzazd3z

那么很明显这是一个9X9的数独算法,输入的字符就是数独算法的解。为了使数独更加直观,我们来用数字代替字母。把字符adf438ghi作以下对应:

a d f 4 3 8 g h i
1 2 3 4 5 6 7 8 9

同时根据算法z其实就是数独算法里的空字符,这个时候列表变为:

三个白帽挑战之二进制题《迷阵陷落》分析

这是个很简单的难度系数为1的数独游戏,大家有兴趣可以手动完成这个数独游戏,数独游戏结果如下:

761934825
354628197
928157634
219546378
483279516
576381942
195762483
832495761
647813259

抽出我们填充的数字:9484629981562154481668142483951839,根据前面设定的对应关系,其对应的字符串为:i4h48diiha38da344ha88ha4d4hfi3ahfi。这里就得到了算法的第一部分的字符串。把断点设置在该算法函数尾部,单步走,等到该函数返回后我们就来到了下面的算法部分。

0x02 逆向追踪算法


跟踪到后面我们发现其实第二部分是对我们输入的后12个字符进行解密运算,然后把运算结果作为key来加密第一部分得到的结果,那么我们需要根据解密流程,逆向加密KEY来获得正确的输入字符串。具体分析如下:

1、相关算法汇编代码分析如下:

004029B6   .  8BF0          mov     esi, eax
004029B8   .  8B06          mov     eax, dword ptr [esi]
004029BA   .  894424 30     mov     dword ptr [esp+30], eax
004029BE   .  8B4E 04       mov     ecx, dword ptr [esi+4]
004029C1   .  894C24 34     mov     dword ptr [esp+34], ecx
004029C5   .  8B56 14       mov     edx, dword ptr [esi+14]
004029C8   .  8B0B          mov     ecx, dword ptr [ebx]
004029CA   .  895424 24     mov     dword ptr [esp+24], edx
004029CE   .  8B46 18       mov     eax, dword ptr [esi+18]
004029D1   .  894424 28     mov     dword ptr [esp+28], eax
004029D5   .  8B69 F8       mov     ebp, dword ptr [ecx-8]
004029D8   .  83C5 DE       add     ebp, -22                          移动长度34
004029DB   .  55            push    ebp                       ; /size
004029DC   .  FF15 34424000 call    dword ptr [<&MSVCRT.mallo>; malloc
004029E2   .  8BCD          mov     ecx, ebp
004029E4   .  8BF8          mov     edi, eax
004029E6   .  8BD1          mov     edx, ecx
004029E8   .  33C0          xor     eax, eax
004029EA   .  C1E9 02       shr     ecx, 2
004029ED   .  897C24 1C     mov     dword ptr [esp+1C], edi
004029F1   .  F3:AB         rep     stos dword ptr es:[edi]
004029F3   .  8BCA          mov     ecx, edx
004029F5   .  83E1 03       and     ecx, 3
004029F8   .  F3:AA         rep     stos byte ptr es:[edi]
004029FA   .  8B4C24 1C     mov     ecx, dword ptr [esp+1C]
004029FE   .  8D46 22       lea     eax, dword ptr [esi+22]
00402A01   .  8B56 22       mov     edx, dword ptr [esi+22]
00402A04   .  8911          mov     dword ptr [ecx], edx
00402A06   .  8B50 04       mov     edx, dword ptr [eax+4]
00402A09   .  8951 04       mov     dword ptr [ecx+4], edx
00402A0C   .  8B40 08       mov     eax, dword ptr [eax+8]
00402A0F   .  8941 08       mov     dword ptr [ecx+8], eax
00402A12   .  8BC5          mov     eax, ebp
00402A14   .  99            cdq
00402A15   .  83E2 03       and     edx, 3
00402A18   .  03C2          add     eax, edx
00402A1A   .  C1F8 02       sar     eax, 2
00402A1D   .  8D4440 0A     lea     eax, dword ptr [eax+eax*2>
00402A21   .  50            push    eax                       ; /size
00402A22   .  FF15 34424000 call    dword ptr [<&MSVCRT.mallo>; malloc
00402A28   .  8B4C24 20     mov     ecx, dword ptr [esp+20]
00402A2C   .  8BF8          mov     edi, eax
00402A2E   .  57            push    edi
00402A2F   .  55            push    ebp
00402A30   .  51            push    ecx
00402A31   .  E8 CAE5FFFF   call    00401000                  ;  从输入串第35个字符开始取剩下的字符串进行BASE64解密
00402A36   .  C60438 00     mov     byte ptr [eax+edi], 0     ;  解密结果最后加上0结束符
00402A3A   .  8D5424 38     lea     edx, dword ptr [esp+38]   ;  取输入串第21个开始的8个字符
00402A3E   .  6A 01         push    1
00402A40   .  8D4424 48     lea     eax, dword ptr [esp+48]   ;  取输入串前8个字符
00402A44   .  52            push    edx
00402A45   .  50            push    eax
00402A46   .  57            push    edi
00402A47   .  E8 94ECFFFF   call    004016E0                  ;  把上面取出的两组字符作为密钥进行3DES解密
00402A4C   .  8A0E          mov     cl, byte ptr [esi]
00402A4E   .  83C4 24       add     esp, 24
00402A51   .  33C0          xor     eax, eax
00402A53   .  84C9          test    cl, cl
00402A55   .  74 49         je      short 00402AA0
00402A57   >  8B0B          mov     ecx, dword ptr [ebx]
00402A59   .  8B49 F8       mov     ecx, dword ptr [ecx-8]
00402A5C   .  83C1 F4       add     ecx, -0C                  ;  取输入字符串长度减去12
00402A5F   .  3BC1          cmp     eax, ecx                  ;  大于这个长度就跳出循环
00402A61   .  7D 3D         jge     short 00402AA0
00402A63   .  8BD0          mov     edx, eax                  ;  下面实际上是除以8取余操作,3DES解密后数据长度为8,每8次加法后,又从第一个字节开始取加数
00402A65   .  81E2 07000080 and     edx, 80000007
00402A6B   .  79 05         jns     short 00402A72
00402A6D   .  4A            dec     edx
00402A6E   .  83CA F8       or      edx, FFFFFFF8
00402A71   .  42            inc     edx
00402A72   >  8A0C3A        mov     cl, byte ptr [edx+edi]    ;  依次取上面3DES解密后字节,长度超过8时 从第一个开始取
00402A75   .  8D2C3A        lea     ebp, dword ptr [edx+edi]
00402A78   .  8A1430        mov     dl, byte ptr [eax+esi]    ;  取输入的字符
00402A7B   .  02D1          add     dl, cl                    ;  两者相加
00402A7D   .  8ACA          mov     cl, dl
00402A7F   .  881430        mov     byte ptr [eax+esi], dl    ;  保存相加后的结果
00402A82   .  80F9 3E       cmp     cl, 3E                    ;  这里依次判断相加后的结果是否是字符> ? ;中的一个
00402A85   .  74 0A         je      short 00402A91
00402A87   .  80F9 3F       cmp     cl, 3F
00402A8A   .  74 05         je      short 00402A91
00402A8C   .  80F9 3B       cmp     cl, 3B
00402A8F   .  75 06         jnz     short 00402A97
00402A91   >  024D 00       add     cl, byte ptr [ebp]        ;  如果是的话 就再加一次cl
00402A94   .  880C30        mov     byte ptr [eax+esi], cl
00402A97   >  8A4C30 01     mov     cl, byte ptr [eax+esi+1]
00402A9B   .  40            inc     eax
00402A9C   .  84C9          test    cl, cl
00402A9