AVALON Reverse Engineering 经典算法数组求和 – Duelist’s Crackme #3 后续

经典算法数组求和 – Duelist’s Crackme #3 后续

环境配置

系统 : winxp 32bit
程序 : due-cm3
要求 : 找出注册解决方案
使用工具 :ida pro

静态分析

根据之前文章的分析,可知关键代码如下:

INT_PTR __stdcall DialogFunc(HWND hDlg, UINT a2, WPARAM a3, LPARAM a4)
{
  INT_PTR result; // eax@4
  int v5; // esi@7
  int v6; // ecx@8
  UINT v7; // [sp+0h] [bp-Ch]@0

  if ( a2 == 273 )
  {
    if ( a3 == 1 )
    {
      v5 = 0;
      dword_40215E = 0;
      dword_402162 = 0;
      while ( 1 )
      {
        v6 = byte_4020FE[v5];
        if ( v6 == 77 )
          break;
        dword_40215E = byte_4020FE[v5++];
        if ( IsDlgButtonChecked(hDlg, v6) )
          dword_402162 += v5 * byte_4020FE[v5] * dword_40215E;
      }
      if ( 0x4D * dword_402162 == 0xF35466 )    // 328FE
      {
        MessageBoxA(0, Text, Caption, 0x2000u);
        result = 1;
      }
      else
      {
        MessageBoxA(0, aYourRegistrati, Caption, 0x2000u);
        result = 0;
      }
    }
    else
    {
      if ( a3 == 2 )
        goto LABEL_16;
      result = 0;
    }
  }
  else
  {
    if ( a2 != 272 )
    {
      if ( a2 != 16 )
        return 0;
LABEL_16:
      ExitProcess(v7);
    }
    SetDlgItemTextA(hDlg, 3, String);
    result = 1;
  }
  return result;
}

其中byte_4020FE数据如下:

unsigned int id_arrary[] = {0x16 ,0x49 ,0x5E ,0x15 ,0x27 ,0x26 ,0x21 ,0x25 ,0x1D ,0x59 ,0x53 ,0x37 ,0x31 ,0x48 ,0x5D ,0x0C ,0x61 ,0x52 ,0x4D };

动态调试

每个checkbox对应的值

在地址401148处下断点,然后逐一选中checkbox,断下后可以查看checkbox对应的值。按照此法得到的checkbox值示意图如下:

61h 49h 5eh 16h 25h 26h 21h 59h 53h
15h 37h 31h 48h 5dh ch  52h 27h 1dh

2*9的点阵图,一共18个元素。

求出真实数组

根据byte_4020FE的内容,我们求出参与求和的真实数组的内容:

>>> a = [0x16 ,0x49 ,0x5E ,0x15 ,0x27 ,0x26 ,0x21 ,0x25 ,0x1D ,0x59 ,0x53 ,0x37 ,0x31 ,0x48 ,0x5D ,0x0C ,0x61 ,0x52 ,0x4D] 
>>> a
[22, 73, 94, 21, 39, 38, 33, 37, 29, 89, 83, 55, 49, 72, 93, 12, 97, 82, 77]
>>> for index in range(0,len(a)-1):
...     res = a[index] * a[index+1] * (index+1)
...     print str(hex(res)),
... 
0x646 0x359c 0x1722 0xccc 0x1cf2 0x1d64 0x2163 0x2188 0x5abd 0x1208e 0xc427 0x7e54 0xb328 0x16e30 0x4164 0x48c0 0x21032 0x1bbf4

演绎推理

需要实现从长度为18的数组中取出n个数求固定sum的算法。在此例中,checkbox有两种状况,可对应0和1,即数据结构中的bit(位)。长度为18的数组可以看成18位的数据结构,只需要从1增加2^18,即可遍历所有可能的求和公式。

编写代码

按照以上推理,编写代码如下:

data_list = [0x646, 0x359c, 0x1722, 0xccc, 0x1cf2, 0x1d64, 0x2163, 0x2188, 0x5abd, 0x1208e, 0xc427, 0x7e54, 0xb328, 0x16e30, 0x4164, 0x48c0, 0x21032, 0x1bbf4]
origin_list = [0x16 ,0x49 ,0x5E ,0x15 ,0x27 ,0x26 ,0x21 ,0x25 ,0x1D ,0x59 ,0x53 ,0x37 ,0x31 ,0x48 ,0x5D ,0x0C ,0x61 ,0x52 ,0x4D]

def calSum(data_list, result):
    for index in range(1<<len(data_list)):      # search range : 2^len(data_list)
        sum = 0
        tmp = str()
        for j in range(len(data_list)):
            if index & 1 << j:
                sum = sum + data_list[j]
                tmp = str(hex(data_list[j])) if tmp == '' else tmp + ' + ' + str(hex(data_list[j]))

        if sum == result:
                print(index, bin(index))
                print(tmp + ' = 0x328FE')

calSum(data_list, 0x328FE)

# output key word : 0x359c + 0x1722 + 0xccc + 0x1cf2 + 0x1d64 + 0x2163 + 0xc427 + 0x16e30 + 0x4164
res_list = [0x359c , 0x1722 , 0xccc , 0x1cf2 , 0x1d64 , 0x2163 , 0xc427 , 0x16e30 , 0x4164]
for element in res_list:
    print hex(origin_list[data_list.index(element)]),

输出结果:

➜  playground python test.py
(25726, '0b110010001111110')
0x359c + 0x1722 + 0xccc + 0x1cf2 + 0x1d64 + 0x2163 + 0xc427 + 0x16e30 + 0x4164 = 0x328FE
0x49 0x5e 0x15 0x27 0x26 0x21 0x53 0x48 0x5d

破解成功

依据唯一的解将checkbox打上勾:

参考链接

  1. http://dreamcracker.today/2018/08/27/duelists-crackme-3-%e7%ae%97%e6%b3%95%e5%88%86%e6%9e%90/ Duelist’s Crackme #3 算法分析
  2. https://blog.csdn.net/buaa_sapphire/article/details/83417609 数组求和-从长度为n的数组里选出m个数使和为固定值sum
  3. https://blog.csdn.net/a987073381/article/details/52016960 每日一练——从长度为n的数组里选出m个数使和为固定值sum