WriteUp:QCTF asong

发表于 更新于 分类于 ，

题目描述

QCTF 的 asong 题目。

题目本体见这里

这道题解压出来有三个文件。

其中 that_girl 是一首歌的歌词。

稍微有点奇怪的是所有空格换成了下划线。

然后 out 是一个二进制文件。

看起来也没什么特别的。

最后 asong 就是 ELF64 文件了，也就是接下来要逆向的东西。

程序输入

把 asong 拖进 IDA 直接跳到 main 函数 F5 可以看到主体逻辑非常简单。

当然这里的标注（包括后面的各种符号名）是我已经看过每个函数后才有的，这才是 Interactive 嘛。

接下来就先简单看下前三个函数。

initialize

点进去后可以看到只有三条语句。

跟解题毫无关系，一边凉快去。

readinput

点进去后可以看到代码如下。

具体逻辑非常清晰，就是造了一个低配版的 getline 轮子，用于读取一行输入。

cutstring

点进去后可以看到代码如下。

逻辑同样很简单，首先判定前 5 个字符是不是 QCTF{，然后如果最后一个字符是 } 就用 0 截断，最后取出两个大括号之间的内容。

that_girl 读取

跟踪进入 convert_that_girl 可以看到

这里如果直接看反编译结果的话会一头雾水，因为 e_wtf 这个局部变量没有初始化就被直接使用了，甚至还被用来当指针，这程序难道不崩溃？

看了一个小时百思不得其解后，我决定直接去看汇编，发现这里竟然是 IDA 自己的一个 bug，这段函数对应的汇编如下。

可以看到这里很明显根据 x86_64 的 calling convention，函数的第二个参数 wtf 在 rsi 里传递进来后存入了局部变量 e_wtf 中，也就是说应该有一句 e_wtf = wtf，但是 IDA 反编译结果并没有。

避开这个坑后我们再看这段函数的逻辑。它打开了 that_girl 文件，然后逐字节读进来映射为一个偏移，最后让 wtf 数组中相应偏移的值加一。

这里有一个映射函数 convert_that_girl_char 如下

并没有什么特别的，也不用刻意去理解逻辑，反正到时候复用就好了。

decode 函数

读取完 that_girl 之后就进入了解码函数。

这里我们看到最后一个函数调用中出现了 out，也就是题目三个文件中的那个二进制文件，很可能与 flag 有关系，所以我们先看它。

writeout

点进去后可以看到代码如下

乍一看没什么特别的，但是这里有一点非常重要，那就是 out 中写入的字节数目等于 flag 去掉首尾的长度，所以我们通过 writeout 首先确定 flag 的长度为 38 + 6 = 44。

同时我们已经有了 out 的内容，也就是说到这里我们才明白题意是根据 out 来倒推 flag。

roundshift

接下来我们倒着看解码过程，首先是 roudshift。

和之前的 babymips 有点类似，这里是一个循环移位，直观来讲：

原来数组是

1
2
1 0 1 0 1 0 | 1 0 1 0 1 0 1 0 | 1 0 1 0 1 0 1 0 | 1 0 1 0 1 0 1 0 | 1 0 1 0 1
     ...    |    mixed[-1]    |    mixed[0]     |     mixed[1]    |    ...

那么经过这个函数移位后得到的 out 就是

1
2
1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1 0 1 0 1 0 1 | 0 1
  |     out[-1]     |      out[0]     |      out[1]     |     out[2]      |

可以理解为整个数组首尾相连然后逆时针左移了 3 位。

所以我们很容易可以从 out 逆推出这个函数的输入，也就是说这个变换是可逆的。

index_round

接着我们再看 index_round 函数。

这里很不幸的是我又踩到了 IDA 的坑，就是上面 v[4] = 0 这句，我们直接看汇编。

显然正确的语句应该是 v[1] = 0，绕过这个坑后我们再看逻辑。

这里中间一个循环看似很复杂，但是我们先看 index_table

就是个 int 数组嘛。

然后再结合每次循环后的 v[1] = index_table[v[1]]，也就是说是一个指针按照 index_table 的规则在数组 mixed 上跳跃直到回到数组开头。

同时还有一句是 v[1] = index_table[v[1]] 也就是说在指针跳跃的同时，数组本身随之错位。

所以这个函数的作用就是按照 index_table 的规则让数组自身错位，由于经过后来的验证这个过程中并没有发生元素的覆盖，因此这个变换也是可逆的。

偏移

再往前看就到了最关键的一个循环了。

之所以我一开始的时候把解密数组的名字起为 mixed 就是因为在这里它是由我们的输入 input 和 that_girl 读入后产生的数组 wtf 混合而成，同时也是解密的关键。

这一行中我们很容易正向推出右边的 wtf，同时根据之前的分析我们可以反向推出左边的 mixed，那么我们只要根据二者的偏移就可以算出 input 了，也就是 flag。

到这里这道题基本上就没问题了，完全不用爆破，只要逆向走一遍算法就行了。

计算脚本

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import struct

def convert_that_girl_char(c: str)->int:
    c = ord(c)
    result = c - 10
    if c == 10:
        result = c + 35
    elif 32 <= c <= 34:
        result = c + 10
    elif c == 39:
        result = c + 2
    elif c == 44:
        result = c - 4
    elif c == 46:
        result = c - 7
    elif 58 <= c <= 59:
        result = c - 21
    elif c == 63:
        result = c - 27
    elif c == 95:
        result = c - 49
    else:
        if c <= 47 or c > 57:
            if c <= 64 or c > 90:
                if c > 96 and c <= 122:
                    result = c - 87
            else:
                result = c - 55
        else:
            result = c -48
    return result

# 计算 convert_that_girl_char 反向映射
char_mapping = {}

for i in range(256):
    char_mapping[convert_that_girl_char(chr(i))] = chr(i)

# 加密后下标 加密前下标
# v    index_table[v]
# 0    <=   22
# 22   <=   20
# 20   <=   19
# 19   <=   14
# 14   <=   17
# 17   <=   4
# 4    <=   30
# 30   <=   29
# 29   <=   28
# 28   <=   27
# 27   <=   36
# 36   <=   34
# 34   <=   33
# 33   <=   32
# 32   <=   31
# 31   <=   37
# 37   <=   35
# 35   <=   26
# 26   <=   25
# 25   <=   5
# 5    <=   24
# 24   <=   15
# 15   <=   23
# 23   <=   16
# 16   <=   13
# 13   <=   12
# 12   <=   8
# 8    <=   21
# 21   <=   11
# 11   <=   10
# 10   <=   18
# 18   <=   3
# 3    <=   2
# 2    <=   6
# 6    <=   9
# 9    <=   7
# 7    <=   1
# 1    <=   0
# 两边没有重复

# 计算 index_table 反向映射
with open('./index_table', 'rb') as table:
    index_table = struct.unpack('<' + "".join(( 'i' for i in range(38))), table.read())  # 懒癌

index_mapping = {}

v = 0

while index_table[v] != 0:
    index_mapping[index_table[v]] = v
    v = index_table[v]

index_mapping[0] = 1

# 从 out 反推循环移位之前的 mixed
with open('./out', 'rb') as outf:
    out = struct.unpack(''.join([ 'B' for i in range(38)]), outf.read())  # 懒癌++

mixed = []

mixed.append(((out[-1] << 5) | (out[0] >> 3)) & 0xFF)

mixed.extend([((out[i] << 5 ) | (out[i + 1] >> 3)) & 0xFF for i in range(len(out) - 1)])

# 从循环移位之前的 mixed 反推要计算偏移时的 mixed
new_mixed = [ 0 for i in range(38)]

for origin, encoded in index_mapping.items():
    new_mixed[origin] = mixed[encoded]

mixed = list(map(chr, new_mixed))

# 计算正向 wtf 数组
wtf = [0 for i in range(0xbc)]

with open('./that_girl', 'r+') as f:
    for c in f.read():
        wtf[convert_that_girl_char(str(c))*4] += 1

wtf = list(map(chr, wtf))

# 打印所有非 0 字符和 mixed 数组，更加清晰的看出对应关系（用于Debug）
print(list(filter(lambda x: x != '\x00', wtf)))

print(mixed)

offset = [ wtf.index(byte) // 4 for byte in mixed]

inner = "".join(map(lambda x: char_mapping[x], offset))

flag = f'QCTF{{{inner}}}' # wtf！ hexo 解析这一行还要加 raw 标签

print(flag)

后记

相当好的一道 RE 题目，构思很精巧。一开始总以为是要爆破，结果仔细分析逻辑后才发现都是可逆的，很轻松就可以拿到 flag。

唯一让我感觉很不爽的是被 IDA 坑了两次，远程调试还崩了好几次。

参考资料