Post

FortIDCTF - toilet

Posted Updated
By 9vvert
6 min read
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

__int64 __fastcall main(int a1, char **a2, char **a3)
{
  unsigned int v3; // ebx
  __int64 v4; // rax
  __int64 v5; // rax
  _QWORD *v6; // rax
  unsigned int v7; // eax
  __int64 v8; // rax
  __int64 v9; // rax
  int v10; // r12d
  _QWORD *v11; // rax
  _QWORD *v12; // rax
  unsigned int v14; // [rsp+14h] [rbp-40Ch] BYREF
  unsigned __int64 index; // [rsp+18h] [rbp-408h] BYREF
  unsigned __int64 mask; // [rsp+20h] [rbp-400h]
  __int64 v17; // [rsp+28h] [rbp-3F8h]
  char v18[32]; // [rsp+30h] [rbp-3F0h] BYREF
  char v19[32]; // [rsp+50h] [rbp-3D0h] BYREF
  char v20[400]; // [rsp+70h] [rbp-3B0h] BYREF
  char v21[256]; // [rsp+200h] [rbp-220h] BYREF
  _QWORD v22[36]; // [rsp+300h] [rbp-120h] BYREF

  v22[33] = __readfsqword(0x28u);
  if ( a1 == 2 )
  {
    std::basic_ifstream<char,std::char_traits<char>>::basic_ifstream(v21, a2[1], 8LL);
    if ( (unsigned __int8)std::basic_ios<char,std::char_traits<char>>::operator!(v22) )
    {
      perror("open input");
      v3 = 1;
    }
    else
    {
      v6 = (_QWORD *)std::istream::operator>>(v21, &v14);
      if ( (unsigned __int8)std::basic_ios<char,std::char_traits<char>>::operator!((char *)v6 + *(_QWORD *)(*v6 - 24LL)) )
      {
        std::operator<<<std::char_traits<char>>(&std::cerr, "Error: could not read brush size\n");
        v3 = 1;
      }
      else if ( v14 && v14 <= 0x3C )
      {
        mask = (1LL << v14) - 1;
        std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string(v18);
        std::getline<char,std::char_traits<char>,std::allocator<char>>(v21, v18);
        while ( 1 )
        {
          v12 = (_QWORD *)std::getline<char,std::char_traits<char>,std::allocator<char>>(v21, v18);
          if ( !(unsigned __int8)std::basic_ios<char,std::char_traits<char>>::operator bool((char *)v12 + *(_QWORD *)(*v12 - 24LL)) )
            break;
          if ( (unsigned __int8)std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::empty(v18) )
          {
            std::operator<<<std::char_traits<char>>(&std::cout, "\n");
          }
          else
          {
            v7 = sub_2E42(16LL, 8LL);
            std::__cxx11::basic_stringstream<char,std::char_traits<char>,std::allocator<char>>::basic_stringstream(
              v20,
              v18,
              v7);
            while ( 1 )
            {
              v11 = (_QWORD *)std::istream::operator>>(v20, &index);
              if ( !(unsigned __int8)std::basic_ios<char,std::char_traits<char>>::operator bool((char *)v11 + *(_QWORD *)(*v11 - 24LL)) )
                break;
              if ( mask < index )
              {
                v8 = std::operator<<<std::char_traits<char>>(&std::cerr, "Error: k = ");
                v9 = std::ostream::operator<<(v8, index);
                std::operator<<<std::char_traits<char>>(v9, " is too large\n");
                v3 = 1;
                v10 = 0;
                goto LABEL_19;
              }
              v17 = sub_26DC(index, mask);
              sub_288B(v19, v17, v14);
              std::operator<<<char,std::char_traits<char>,std::allocator<char>>(&std::cout, v19);
              std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v19);
            }
            std::operator<<<std::char_traits<char>>(&std::cout, "\n");
            v10 = 1;
LABEL_19:
            std::__cxx11::basic_stringstream<char,std::char_traits<char>,std::allocator<char>>::~basic_stringstream(v20);
            if ( v10 != 1 )
              goto LABEL_22;
          }
        }
        v3 = 0;
LABEL_22:
        std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(v18);
      }
      else
      {
        std::operator<<<std::char_traits<char>>(&std::cerr, "Error: brush size must be between 1 and 60\n");
        v3 = 1;
      }
    }
    std::basic_ifstream<char,std::char_traits<char>>::~basic_ifstream(v21);
  }
  else
  {
    v4 = std::operator<<<std::char_traits<char>>(&std::cerr, "Usage: ");
    v5 = std::operator<<<std::char_traits<char>>(v4, *a2);
    std::operator<<<std::char_traits<char>>(v5, " input.txt\n");
    return 1;
  }
  return v3;
}

其中sub_288B函数会将一个int64数字按照0/1比特转换成 ‘ ’ 和 ‘*’相间的字符串 关键函数：

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

__int64 __fastcall sub_26DC(unsigned __int64 a1, __int64 a2)
{
  __int64 v2; // rbx
  __int64 v4; // [rsp+0h] [rbp-90h] BYREF
  unsigned __int64 v5; // [rsp+8h] [rbp-88h]
  __int64 v6; // [rsp+10h] [rbp-80h] BYREF
  unsigned __int64 i; // [rsp+18h] [rbp-78h]
  char v8[32]; // [rsp+20h] [rbp-70h] BYREF
  char v9[56]; // [rsp+40h] [rbp-50h] BYREF
  unsigned __int64 v10; // [rsp+78h] [rbp-18h]

  v5 = a1;
  v4 = a2;
  v10 = __readfsqword(0x28u);
  if ( a1 == 1 )
    return 1LL;
  sub_2F32(v9);
  sub_2FB2(v8);
  v6 = 1LL;
  sub_33BC(v9, &v6);
  v6 = 1LL;
  sub_3440(v8, &v6);
  sub_3476(v9, &v4);
  sub_34EE(v8, &v4);
  if ( v5 == 2 )
  {
    v2 = v4;
  }
  else
  {
    v6 = 0LL;
    for ( i = 3LL; i <= v5; ++i )
    {
      v6 = sub_2589(v9, v8, v4);
      sub_3476(v9, &v6);
      sub_34EE(v8, &v6);
    }
    v2 = v6;
  }
  sub_3374(v8);
  sub_2F52(v9);
  return v2;
}

通过动态调试猜测出了其功能，静态分析比较难，不知道有没有什么好的静态方法。 执行逻辑是：传入一个index和mask，其中index为1时返回1,为2时返回mask,其它的情况会遍历所有的点，然后计算和所有已知点的距离，如果是其中最小的就返回。

程序固有的算法效率实在太低，不可能算完。我们很容易找出其中的通项公式，然后用frida hook替换目标函数，改成我们自己的逻辑。

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

function convert(num: bigint, mask: bigint) {
	if (num == 0n)
		return 0n;
	if (num == 1n)
		return 1n;
	if (num == 2n)
		return mask;
	if (num == 3n)
		return (1n + mask) / 2n;
	// find group (2^r+1)
	var grp_num: bigint = 0n;
	while (1) {
		var x = 2n ** grp_num + 1n;
		if (num <= x) {
			break;
		}
		grp_num++;
	}
	grp_num--;
	var remain: bigint = num - 2n ** grp_num - 1n;
	var mid: bigint = (1n + mask) / 2n;
	var cellNum: bigint = 2n ** grp_num;
	var cellSize: bigint = (1n + mask) / cellNum;


	if (remain == cellNum - 1n) {
		return cellSize / 2n;
	} else if (remain == cellNum) {
		return mid + cellSize / 2n - 1n;
	} else if (remain <= (cellNum - 2n) / 2n) {
		return cellSize / 2n + cellSize * remain;
	} else if (remain <= cellNum - 2n) {
		return cellSize / 2n + cellSize * (remain + 1n) - 1n;
	} else {
		console.log("error", num, remain);
		return 1n;
	}

}

const proc = Process.findModuleByName("chal");
if (proc) {

	const baseAddr = proc.base;
	const targetAddr = baseAddr.add(0x26DC)

	var cal_result: bigint | undefined;
	Interceptor.attach(targetAddr, {
		onEnter: function(args) {
			const num: bigint = BigInt("0x" + args[0].toString(16));
			const mask: bigint = BigInt("0x" + args[1].toString(16));
			cal_result = convert(num, mask);
			args[0] = ptr(1);

		},

		onLeave: function(retval) {
			if (cal_result) {
				retval.replace(ptr("0x" + cal_result.toString(16)));
			}

		}
	});
}
else {
	console.log("Cannot find main module.");
}

（中间用字符串来构造ptr,以及提取int64参数，避免默认的number截断）

但是这一题有些数据似乎是超过mask范围的？

[TODO]

ctf2025, FortIDCTF
reverse hook algorithm
This post is licensed under CC BY 4.0 by the author.