西湖论剑逆向之testre

qdam

附件
1904055ca752e746df2.zip (3.14 KB, 下载次数: 12)

2019-4-8 23:08 上传

点击文件名下载附件

这次抱着玩的心态参加了西湖杯，结局肯定是被打爆，不过还是有所收获的，比如这道逆向，想了很久才理解其中的算法。
先用IDA打开看一下里面的逻辑

[Asm] 纯文本查看 复制代码

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  void *ptr; // ST10_8
  __int64 v5; // [rsp+18h] [rbp-28h]
  char v6; // [rsp+20h] [rbp-20h]
  int v7; // [rsp+3Ch] [rbp-4h]

  v7 = 0;
  v5 = 256LL;
  sub_400D00((__int64)&v6, 0x11uLL);            // 读取16个字符
  ptr = malloc(0x100uLL);
  sub_400700(ptr, &v5, (__int64)&v6, 0x10uLL);  // 处理函数
  free(ptr);
  return 0LL;
}

首先是一个读取字符串的函数
然后来到了另一个函数，肯定就是最关键的处理部分，进去看一下

[Asm] 纯文本查看 复制代码

__int64 __fastcall sub_400700(void *a1, _QWORD *a2, __int64 a3, size_t a4)
{
  unsigned __int8 *v4; // rcx
  __int64 v6; // [rsp+0h] [rbp-C0h]
  int c; // [rsp+8h] [rbp-B8h]
  char v8; // [rsp+Fh] [rbp-B1h]
  int v9; // [rsp+10h] [rbp-B0h]
  bool v10; // [rsp+17h] [rbp-A9h]
  unsigned __int8 *aim; // [rsp+18h] [rbp-A8h]
  char v12; // [rsp+27h] [rbp-99h]
  int v13; // [rsp+28h] [rbp-98h]
  int v14; // [rsp+2Ch] [rbp-94h]
  unsigned __int64 i; // [rsp+30h] [rbp-90h]
  size_t n_22; // [rsp+38h] [rbp-88h]
  size_t v17; // [rsp+40h] [rbp-80h]
  size_t v18_21; // [rsp+48h] [rbp-78h]
  size_t j; // [rsp+50h] [rbp-70h]
  size_t v20; // [rsp+58h] [rbp-68h]
  int v21; // [rsp+64h] [rbp-5Ch]
  unsigned __int64 v22; // [rsp+68h] [rbp-58h]
  int v23; // [rsp+74h] [rbp-4Ch]
  __int64 *v24; // [rsp+78h] [rbp-48h]
  __int64 input; // [rsp+80h] [rbp-40h]
  void *xor_add; // [rsp+88h] [rbp-38h]
  int v27; // [rsp+94h] [rbp-2Ch]
  unsigned __int64 v28_16; // [rsp+98h] [rbp-28h]
  __int64 v29; // [rsp+A0h] [rbp-20h]
  _QWORD *v30; // [rsp+A8h] [rbp-18h]
  void *s; // [rsp+B0h] [rbp-10h]
  char v32; // [rsp+BFh] [rbp-1h]

  s = a1;
  v30 = a2;
  v29 = a3;
  v28_16 = a4;
  v27 = -559038737;
  xor_add = malloc(0x100uLL);
  input = v29;
  v24 = &v6;
  v22 = 0LL;
  v17 = 0LL;
  for ( i = 0LL; i < v28_16; ++i )
  {
    v13 = *(unsigned __int8 *)(input + i);
    *((_BYTE *)xor_add + i) = byte_400E90[i % 0x1D] ^ v13;
    *((_BYTE *)xor_add + i) += *(_BYTE *)(input + i);
  }
  while ( 1 )
  {
    v12 = 0;
    if ( v17 < v28_16 )
      v12 = ~(*(_BYTE *)(input + v17) != 0);
    if ( !(v12 & 1) )
      break;
    ++v17;
  }
  n_22 = ((unsigned __int64)(0x28F5C28F5C28F5C3LL * (unsigned __int128)(138 * (v28_16 - v17) >> 2) >> 64) >> 2) + 1;// 22
  v23 = ((unsigned __int64)(0xAAAAAAAAAAAAAAABLL * (unsigned __int128)((v17 + v28_16) << 6) >> 64) >> 5) - 1;// 不用算
  aim = (unsigned __int8 *)&v6                  // 开一段内存用于存结果
      - ((((unsigned __int64)(0x28F5C28F5C28F5C3LL * (unsigned __int128)(138 * (v28_16 - v17) >> 2) >> 64) >> 2) + 16) & 0xFFFFFFFFFFFFFFF0LL);
  memset(aim, 0, n_22);
  v20 = v17;
  v18_21 = n_22 - 1;
  while ( v20 < v28_16 )
  {
    v21 = *(unsigned __int8 *)(input + v20);
    for ( j = n_22 - 1; ; --j )
    {
      v10 = 1;
      if ( j <= v18_21 )
        v10 = v21 != 0;
      if ( !v10 )
        break;
      v22 = aim[j] << 6;                        // 没用
      v21 += aim[j] << 8;
      v9 = 64;                                  // 没用
      aim[j] = v21 % 58;
      *((_BYTE *)xor_add + j) = v22 & 0x3F;     // 没用
      v22 >>= 6;                                // 没用
      v21 /= 58;
      v27 /= v9;                                // 没用
      if ( !j )
        break;
    }
    ++v20;
    v18_21 = j;
  }
  for ( j = 0LL; ; ++j )
  {
    v8 = 0;
    if ( j < n_22 )
      v8 = ~(aim[j] != 0);
    if ( !(v8 & 1) )
      break;
  }
  if ( *v30 > n_22 + v17 - j )
  {
    if ( v17 )
    {
      c = 61;
      memset(s, 49, v17);
      memset(xor_add, c, v17);
    }
    v20 = v17;
    while ( j < n_22 )
    {
      v4 = aim;
      *((_BYTE *)s + v20) = byte_400EB0[aim[j]];
      *((_BYTE *)xor_add + v20++) = byte_400EF0[v4[j++]];
    }
    *((_BYTE *)s + v20) = 0;
    *v30 = v20 + 1;
    if ( !strncmp((const char *)s, "D9", 2uLL)
      && !strncmp((const char *)s + 20, "Mp", 2uLL)
      && !strncmp((const char *)s + 18, "MR", 2uLL)
      && !strncmp((const char *)s + 2, "cS9N", 4uLL)
      && !strncmp((const char *)s + 6, "9iHjM", 5uLL)
      && !strncmp((const char *)s + 11, "LTdA8YS", 7uLL) )
    {
      HIDWORD(v6) = puts("correct!");
    }
    v32 = 1;
    v14 = 1;
  }
  else
  {
    *v30 = n_22 + v17 - j + 1;
    v32 = 0;
    v14 = 1;
  }
  return v32 & 1;
}

我们先不着急从头开始分析，先看一下最后的结果，也就是strncmp的部分

[Asm] 纯文本查看 复制代码

if ( !strncmp((const char *)s, "D9", 2uLL)
      && !strncmp((const char *)s + 20, "Mp", 2uLL)
      && !strncmp((const char *)s + 18, "MR", 2uLL)
      && !strncmp((const char *)s + 2, "cS9N", 4uLL)
      && !strncmp((const char *)s + 6, "9iHjM", 5uLL)
      && !strncmp((const char *)s + 11, "LTdA8YS", 7uLL) )
    {
      HIDWORD(v6) = puts("correct!");
    }

可以看到最后我们要实现的就是把字符串s=“D9cS9N9iHjMLTdA8YSMRMp”，这里看到s的长度是22，这对于理解上面的代码应该会有帮助，然后我们再先看一下s是怎么产生的，往上看找到赋值代码

[Asm] 纯文本查看 复制代码

 while ( j < n_22 )
    {
      v4 = aim;
      *((_BYTE *)s + v20) = byte_400EB0[aim[j]];
      *((_BYTE *)xor_add + v20++) = byte_400EF0[v4[j++]];
    }

这里aim又是另一个数组，是由输入的字符串转换得到的，然后再看一下byte_400EB0的内存

[Asm] 纯文本查看 复制代码

odata:0000000000400EB0 byte_400EB0     db 31h                  ; DATA XREF: sub_400700+446↑r
.rodata:0000000000400EB1 a23456789abcdef db '23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz',0

是由2到z组成的字符串，我们可以把它看成对应表，因为最后aim数组中的数值对应的就是这里的字符。
那么我们又要考虑aim数组是怎么产生的，也就是说怎样才能使aim数组变成我们想要的，这就是我们的目标
现在我们从头开始分析一下
首先是第一个for循环

[Asm] 纯文本查看 复制代码

  for ( i = 0LL; i < v28_16; ++i )
  {
    v13 = *(unsigned __int8 *)(input + i);
    *((_BYTE *)xor_add + i) = byte_400E90[i % 0x1D] ^ v13;
    *((_BYTE *)xor_add + i) += *(_BYTE *)(input + i);
  }

我们看到是对输入的字符与v13做异或然后相加，所以把这个数值改名为xor_add，
然后是一个while循环

[Asm] 纯文本查看 复制代码

while ( 1 )
  {
    v12 = 0;
    if ( v17 < v28_16 )
      v12 = ~(*(_BYTE *)(input + v17) != 0);
    if ( !(v12 & 1) )
      break;
    ++v17;
  }

这里很奇怪，因为我们输入的第一个字符肯定不是ascii=0的字符，所以循环一次还没做完就break了，也就是说v17=0，这里有些疑惑，先不管看后面。

[Asm] 纯文本查看 复制代码

n_22 = ((unsigned __int64)(0x28F5C28F5C28F5C3LL * (unsigned __int128)(138 * (v28_16 - v17) >> 2) >> 64) >> 2) + 1;// 22
  v23 = ((unsigned __int64)(0xAAAAAAAAAAAAAAABLL * (unsigned __int128)((v17 + v28_16) << 6) >> 64) >> 5) - 1;// 不用算
  aim = (unsigned __int8 *)&v6                  // 开一段内存用于存结果
      - ((((unsigned __int64)(0x28F5C28F5C28F5C3LL * (unsigned __int128)(138 * (v28_16 - v17) >> 2) >> 64) >> 2) + 16) & 0xFFFFFFFFFFFFFFF0LL);
  memset(aim, 0, n_22);

这里用python跑一下就知道n_22=22，aim所开的内存大小应该也是22（好像23，这里忘记标了，反正肯定>=22，也就是字符串s的长度），然后v23这里是不用计算的，因为我们可以在后面的代码中寻找v23，发现是没有的，所以是用不到的，也就没有去算，虽然疑惑程序为什么加上这段代码。
然后来到了最关键的部分

[Asm] 纯文本查看 复制代码

v20 = v17;
  v18_21 = n_22 - 1;
  while ( v20 < v28_16 )
  {
    v21 = *(unsigned __int8 *)(input + v20);
    for ( j = n_22 - 1; ; --j )
    {
      v10 = 1;
      if ( j <= v18_21 )
        v10 = v21 != 0;
      if ( !v10 )
        break;
      v22 = aim[j] << 6;                        // 没用
      v21 += aim[j] << 8;
      v9 = 64;                                  // 没用
      aim[j] = v21 % 58;
      *((_BYTE *)xor_add + j) = v22 & 0x3F;     // 没用
      v22 >>= 6;                                // 没用
      v21 /= 58;
      v27 /= v9;                                // 没用
      if ( !j )
        break;
    }
    ++v20;
    v18_21 = j;
  }

两个循环语句，先对输入的每一个字符从前往后循环，然后里面再嵌一个对aim数组的循环，这里是从后往前的
然后再循环体内我发现了很多无关的语句，也就是和这个程序没有关系的运算，我上面做了注释，因为这些变量，包括数组对于最后我们产生的aim数组没有一点影响，所以我们先不考虑这些无关的代码
可看到算法是对每一个字符 ch， 先进行ch=ch+aim[j]<<8, 然后aim[j]=ch%58（这里58是对应表的长度），然后ch=ch/58， 然后 j-- ，直到j==0或者ch==0跳出内部循环，再对下一个字符处理。
最后每一个字符都循环完以后，aim数组就产生了，而且也不再修改了。后面的代码就不讲了，感觉有很多无关代码，这里只要是和 s ，aim无关的代码都是不用看的。
现在我们知道的是，最后aim数组里面的值，也就是字符串s中每一个字符在对应表中的下标。
然后我要通过aim数组去逆出我们输入的字符。这就是问题最关键的部分。
为了简化问题，我们先考虑一下一种16进制转10进制的运算
假设我们有16进制数0xabcd，那么怎么转化为10进制数呢，我们采取这样的做法，每次取出16进制数中的两位，从头开始取（假设位数一个为奇数位，最前位添0，如0xabc ->0x0abc），假设取出的值为a，然后先对前两位对10取余，得到的结果放在数组Y的最后，然后a=a/10，再把a%10的结果放在最后位的前一位，知道a=0。做完这次循环后，我们可以算出0xab所对应的10进制结果，对吧，这里记为d0。然后我们同样可以算出0xcd对应的10进制结果d1。但是我们知道0xab在这里其实不是真的0xab，而是0xab00，也就是我们需要把我们刚刚算出的d0*256+d1，这才是真正的十进制数。而在实际过程时，当我们对一个新的16进制数操作时，我们需要把a加上留在数组Y中的每一位数<<8（*256）的结果，然后再对10取与，把Y数组中当前位的值更新为余数，然后a=a/10循环。最后得到10进制数（感觉没讲明白，5555，不知道怎么讲了。）
举个例子 0xabcd，取出0xab 后计算得到 Y数组中的值位  1 7 1 （0xab对应的10进制数），然后取出0xcd，d=0xab 先加上1<<8,也就是d=d+256，对10取与得到1，所以Y当前位更新为1，然后d=d/10=46， 然后d=d+7<<8=1838 ,对10取余， 更新Y相应位=8， d=d/10=183， 然后d=d+1<<256=439 , 取余 ，更新 Y，d=d/10 =43,此时Y=  9 8 1 （Y数组中其它的值都为0）,由于d>0，继续操作，d=d+0<<8=43,  取余，更新Y，d=d/10， 继续， 取余，更新Y， d=d/10，由于d==0，所以不再循环，这个时候 Y数组里面的值为 4 3 9 8 1，是不是就是0xabcd呢。
讲了半天，回来看这道题，你会发现这就是把16进制数转化为58进制的数，是不是呢？每次先加上数值中左移8位的值，然后对58取余，再除以58，直到为0。
于是就很简单，我们只要把58进制的数转为16进制不就好了吗？
附上脚本

[Asm] 纯文本查看 复制代码

from Crypto.Util.number import long_to_bytes
cipher='D9cS9N9iHjMLTdA8YSMRMp'
all='123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
flag=0
for i in range(len(cipher)):
  flag=flag*58+all.index(cipher[i])
out=long_to_bytes(flag)
print("hex(flag)={}".format(hex(flag)))
print("ascii(flag)={}".format(str(out,encoding="utf8")))

运行结果

[Asm] 纯文本查看 复制代码

hex(flag)=0x6261736535385f69735f626f72696e67
ascii(flag)=base58_is_boring

qdam

瑟瑟发抖小菜虾 发表于 2019-4-8 23:31
楼主有 这个比赛 其它 逆向或者 pwn的题嘛   想去做一下，谢谢！！！

pwn的话我没有做，不过逆向的话还有一道easycpp
https://pan.baidu.com/s/1XC9IMccYyAvGlEHvKKxkSA
提取码：hsnz

瑟瑟发抖小菜虾

楼主有 这个比赛 其它 逆向或者 pwn的题嘛   想去做一下，谢谢！！！

wangzhenuen

学习一下！！

姚小宝

辗转相除法，base58

helica

感觉就是把移位过的数据用58进制存起来了

Bayerischen

这玩意儿就是base58的算法，找个在线的就能解出来，真是绝了

蜗~牛

n不是23吗楼主

qdam

蜗~牛 发表于 2019-4-9 19:32
n不是23吗楼主

嗯，对的，应该是23

chenjin056

谢谢分享希望论坛越办越好