首页
社区
课程
招聘
[原创] 看雪 2022 KCTF 秋季赛 第二题 盗贼作乱
2022-11-17 03:19 7639

[原创] 看雪 2022 KCTF 秋季赛 第二题 盗贼作乱

2022-11-17 03:19
7639

(写在开头:先膜一发 tkmk [摸鱼划水打酱油]战队)

 

无混淆,好评(在程序逻辑公开的情况下设定谜题的阳谋比利用vmp之类的壳隐藏逻辑的阴谋更高一层)

 

IDA打开,观察了几个函数,感觉像大数运算

 

手动创建出下面的结构体:

1
2
3
4
struct BN {
    int len;
    char s[32];
}

其中,s是大整数的字节,低位在前;len是有效字节的个数

 

然后给各个函数改名称和类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
sub_4014D0: bn_init_str,从字符串初始化BN。每个字符在字符表里的索引是每位数值,62进制,低位在前 
sub_401630: bn_set_int,从整数初始化BN
sub_401660: bn_copy
sub_401690: bn_cmp
sub_401730: bn_add
sub_401820: bn_sub
sub_401920: bn_and
sub_401A80: bn_or
sub_401C00: bn_xor
sub_401CF0: bn_mul
sub_401F30: bn_div
sub_4021A0: bn_mod
sub_402360: do_bn_mod:计算mod,但是不修改BN
sub_4023A0: bn_shl
sub_402490: bn_shr

可以写出bn_init_str的输入字符串和BN的实际数值之间的转换:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def bn_from(s):
    table = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    tmp = [table.index(c) for c in s]
    r = 0
    for c in tmp[::-1]:
        r = r * len(table) + c
    return r
 
 
def bn_to(n):
    table = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    tmp = []
    while n:
        t = n % len(table)
        tmp.append(table[t])
        n //= len(table)
    return "".join(tmp)

标记完成后的main函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v3; // edi
  int v4; // eax
  int v6; // esi
  int v7; // eax
  char v9[64]; // [esp+8h] [ebp-40h] BYREF
 
  memset(v9, 0, sizeof(v9));
  printf("Input:");
  gets(v9);
  v3 = -1;
  v4 = 0;
  if ( !v9[0] )
    goto LABEL_20;
  do
  {
    if ( v4 >= 64 )
      break;
    if ( v9[v4] == '-' )
      v3 = v4;
  }
  while ( v9[++v4] );
  if ( v3 > 0
    && (v6 = v4 - v3, v4 - v3 > 0)
    && bn_init_str(&x, v9, v3, a0123456789abcd) > 0
    && bn_init_str(&y, &v9[v3 + 1], v6 - 1, a0123456789abcd) > 0
    && (bn_init_str(&n, aIrtzloz6iub, strlen(aIrtzloz6iub), a0123456789abcd),
        bn_set_int(&v1, 0),
        bn_set_int(&v2, 0),
        bn_cmp(&x, &y) < 0)
    && bn_cmp(&x, &n) < 0
 
    && bn_cmp(&y, &n) < 0 )
  {
    v7 = 0;
    while ( 1 )
    {
      loop_conut = v7 + 1;
      bn_add(&v1, &v1, &x);
      bn_add(&v2, &v2, &y);
      bn_mod(&v1, &v1, &n);
      bn_mod(&v2, &v2, &n);
      bn_set_int(&tmp1, 1);
      bn_sub(&tmp1, &v1, &tmp1);
      if ( !bn_cmp(&tmp1, &x) )
      {
        ++correctvar;
        bn_mul(&tmp1, &tmp1, &x);
      }
      bn_set_int(&tmp2, 1);
      bn_add(&tmp2, &v2, &tmp2);
      if ( !bn_cmp(&tmp2, &y) )
      {
        ++correctvar;
        bn_div(&tmp2, &n, &y);
      }
      if ( correctvar == 10 )
        break;
      v7 = loop_conut;
      if ( loop_conut >= 0x200000 )
        goto LABEL_20;
    }
    printf("Success!\n");
    return 0;
  }
  else
  {
LABEL_20:
    printf("Error.\n");
    return 0;
  }
}

这里的常量 n 解出后是 10000000000000000000 (10**19)

 

main函数的明逻辑很简单:给出两个小于n且不相等的整数x和y,统计 (x*loop_count - 1) % n == x(y*loop_count + 1) % n == y 的次数,要求随着loop_count增大至少满足10次。

 

这两个等式稍微变形即可得到 x*(loop_count-1) = k1 * n + 1y * (loop_count+1) = k1*n - 1,因此 x 和 y 都要与 n 互质
如果想找到两个不同的 loop_count 满足同一个等式,即 x*(loop_count1-1) == 1 (mod n)x*(loop_count2-1) == 1 (mod n),相减后得到 x * (loop_count2 - loop_count1) == 0 (mod n),即 n 整除 x * (loop_count2 - loop_count1)
由于 x 与 n 互质,所以只能是 n 整除 loop_count2 - loop_count1,这意味着在满足一次等式条件后,需要至少再累加 n 次 x 才能再次满足等式,显然超过了限制,因此仅从表面逻辑看,题目似乎是无解的。

 

其实很多bn_函数内部都有一些奇怪的操作,例如很多无用的对tmp1和tmp2的操作;但是值得注意的是 bn_mul 和 bn_div 中有对 n 的引用,摘抄如下:

1
2
3
4
5
6
7
8
9
10
bn_set_int(&tmp1, 4);                       // now tmp1 == 4
bn_shl(&tmp2, &tmp1, 3);                    // now tmp2 == 32
if ( correctvar > 0 && *(_DWORD *)&n.s[tmp2.s[0]] == tmp2.s[0] )// check if loop_count == 32
{
  bn_add(&tmp1, &tmp1, &tmp2);              // now tmp1 == 36
  v13 = do_bn_mod(&tmp1, loop_conut);
  n.s[tmp1.s[0]] += 4;                      // correctvar += 4
  bn_shl(&tmp1, &tmp1, v13);
  bn_sub(&tmp2, &tmp1, &tmp2);
}

把常量运算带入到下面,发现玄机在于 n.s[tmp2.s[0]]n.s[tmp1.s[0]] 两处的索引都越界了。看一下全局变量的地址:

1
2
3
4
5
6
7
.data:0040A9D0 ; struct bn n
.data:0040A9D0 n               bn <0>                  ; DATA XREF: bn_sub+AD↑o
.data:0040A9D0                                         ; bn_or+FF↑o ...
.data:0040A9F4 loop_conut      dd 0                    ; DATA XREF: bn_cmp:loc_4016D0↑r
.data:0040A9F4                                         ; bn_cmp+65↑r ...
.data:0040A9F8 correctvar      dd 0                    ; DATA XREF: bn_cmp+7B↑r
.data:0040A9F8                                         ; bn_add+D0↑r ...

这里 n.s[tmp2.s[0]] 访问的是 n.s[32],即 0x40A9D0+4+32 = 0x40A9F4,是 loop_count 变量;n.s[tmp1.s[0]] 访问的是 n.s[36],即 0x40A9D0+4+36 = 0x40A9F4,是 correctvar 变量。

 

所以,如果通过了 main 函数里明逻辑的等式使得 correctvar 加 1 时的 loop_count 等于 32,这部分暗逻辑会把 correctvar 再加上 4,所以才有可能达到明逻辑里 correctvar 等于 10 的最终要求。

 

如果限定 loop_count == 32,则等式约束变为了 x*(32-1) = k1*n + 1y*(32+1) = k2*n - 1。稍微遍历一下 k1 和 k2 的值使得 31 整除 k1*n + 1 和 33 整除 k2*n - 1,得到 k1 = 12,k2 = 18,从而 x = 3870967741935483871,y = 6129032258064516129,且满足 x < y < n 的约束。
重新编码回去,得到程序正确的输入为 ZSxZerX4xb4-jyvP7x12lI7

 

(p.s. 利用越界写隐藏暗逻辑的思路很新颖,而且确实不太容易被发现。这种难度在往年估计都是中后段的题目了,今年竟然才到第二题)
(再p.s. 下一道题,看到出题战队是ArmVMP就很劝退)


[培训]《安卓高级研修班(网课)》月薪三万计划,掌握调试、分析还原ollvm、vmp的方法,定制art虚拟机自动化脱壳的方法

收藏
点赞2
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回