首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. CTF对抗
    3. 发新帖
[原创] 看雪 2022 KCTF 秋季赛 第二题 盗贼作乱
2022-11-17 03:19 7684

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

mb_mgodlfyn 活跃值
12
2022-11-17 03:19
7684

（写在开头：先膜一发 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 + 1 和 y * (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 + 1 和 y*(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就很劝退）


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

收藏
点赞・2
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回