CISCN 2021 逆向题 CISCN_gift WP

本文最后更新于:2021年7月22日

CISCN 比赛正好撞上期中考,就没去参加。事后在学长的建议下复盘了一下 CISCN_gift,感觉收获良多,记录 WP 如下。

IDA7.5 打开一看,没有任何符号表。在 Strings 面板中发现大量 fmt 开头的函数,猜测使用 Go 语言编写,故使用 IDA7.6 打开。发现能正确识别出符号表:

符号表

显然,最后 6 个函数是分析的重点所在。

先从 main_main 开始。

首先映入眼帘的就是 3 个 666 函数: main_CISCN6666666main_CISCN66666666main_CISCN666666666 。一次查看并分析,无参无返回值,直接在最后一个 main_CISCN666666666 后下断点,发现这三个函数只是在控制台输出欢迎语,略过。

继续看 main_main 。下面有个 while ,但其实就是一个 for(int i = 0; i < 32; i++) 。其中有一个 off_568230 追踪以后发现是延迟时间表 (其实不是,只是循环次数,但当时的直觉就认为这是字母延迟输出的延迟)。故整理格式后命名:

timeList

紧接着下方出现 Go 函数 runtime_makeslice 。查阅资料发现该函数构造一个 slice 对象。根据下文猜测未被正确识别的 v11 应该就是其返回值。

紧接着的又是一个被错误识别成 whilefor(int j = 1; j <= 4; j++) 。里面啥也没干,就只调用了 main_wtf 。但这个调用有些奇怪: main_wtf(0LL, j, sliced_, aTime, aTime); 。前两个看着没啥问题,后三个就挺有意思了。联想到,刚才创建的 slice 对象 sliced ,以及 slice 对象的结构:

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

推测后三个参数应该是一个结构体,故创建之。调用变为 main_wtf(0LL, j, sliceObj);

main_wtf 函数暂时先不跟进分析,先继续分析 main_mainj 循环完成后,出现语句 v6 = *(&v17 + qword_5B20E8); 。结合交叉引用中 qword_5B20E8main_wtf 更改和下文对其的大量引用,推测 qword_5B20E8main_wtf 函数的等效返回值(可以看作是返回值)。同时从上方的栈分配可知其应该小于 17。回看 v17 变量,发现其是一个 __int64 对象。但从下方语句来看,其应该为一数组。结合 qword_5B20E8 小于 17 的线索,将其类型更改为 __int8 v17[17] 。同时推测其为一 S−box

再往下的部分都是 Go 标准库的 fprintf 的部分,唯独 8 * (v6 ^ 0x66) 感觉有些蹊跷,考虑是将 S−box 的返回值与 0x66 异或后输出。

main_main 的分析到此结束,接下来看 main_wtf

首先发现递归调用。调用时有 v3 + 1 也就是参数 a1 + 1 ,故判断参数 a1 为递归深度。

if ( depth == sliced.len - 1 ) 的含义显而易见,而 else 分支的代码和 main_main 的几乎一致,发生递归调用,深度 + 1。 then 分支中调用了最后一个函数 main_goooo 。若返回值为真则对 qword_5B20E8 进行操作。由此判断 qword_5B20E8 应该是加密数值,改名为 enc

最后来分析 main_goooo 函数。在里头发现了一个奇怪的语法: *(&v3 + v2) ,考虑 v3 为一数组。看着 LOBYTE(result) 挺难受的,把函数返回类型也改一下。改完以后程序的运行逻辑一目了然。

main_goooo

至此,函数主体逻辑已经清晰。写 Python 脚本模拟:

enc = 0
timeLists = [
    1, 3, 6, 9, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0x12, 0x14,
    0x19, 0x1E, 0x28, 0x42, 0x66, 0x0A0, 0x936, 0x3D21, 0x149A7, 0x243AC,
    0x0CB5BE, 0x47DC61, 0x16C0F46, 0x262C432, 0x4ACE299, 0x10FBC92A,
    0x329ECDFD, 0x370D7470
]

def main_goooo(array):
    box = [0] * 5
    for tmp in array:
        box[tmp] ^= 1
    return box[1] == 0 and box[3] == 0

def main_wtf(depth, j, array):
    global enc
    array[depth] = j
    if depth == len(array) - 1:
        if (main_goooo(array)):
            enc = enc - 17 * (((enc + (((enc + 1) * 0xF0F0F0F0F0F0F0F1) >> 64) + 1) >> 4) - ((enc + 1) >> 63)) + 1
    else:
        for jj in [1, 2, 3, 4]:
            main_wtf(depth + 1, jj, array)

def main_main():
    global enc
    for aTime in timeLists:
        enc = 0
        for j in [1, 2, 3, 4]:
            main_wtf(0, j, [0] * aTime)
        print(enc_time)

if __name__ == "__main__":
    main_main()

但是运行后可以发现这个算法极慢且输出无规律。查阅学长们的 WP 发现可以尝试计算 enc 的运行次数,故修改代码如下:

enc = 0
enc_time = 0
timeLists = [
    1, 3, 6, 9, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0x12, 0x14,
    0x19, 0x1E, 0x28, 0x42, 0x66, 0x0A0, 0x936, 0x3D21, 0x149A7, 0x243AC,
    0x0CB5BE, 0x47DC61, 0x16C0F46, 0x262C432, 0x4ACE299, 0x10FBC92A,
    0x329ECDFD, 0x370D7470
]

def main_goooo(array):
    box = [0] * 5
    for tmp in array:
        box[tmp] ^= 1
    return box[1] == 0 and box[3] == 0

def main_wtf(depth, j, array):
    global enc,enc_time
    array[depth] = j
    if depth == len(array) - 1:
        if (main_goooo(array)):
            enc_time += 1
            enc = enc - 17 * (((enc + ((
                (enc + 1) * 0xF0F0F0F0F0F0F0F1) >> 64) + 1) >> 4) -
                              ((enc + 1) >> 63)) + 1
    else:
        for jj in [1, 2, 3, 4]:
            main_wtf(depth + 1, jj, array)

def main_main():
    global enc, enc_time
    for aTime in timeLists:
        enc = 0
        enc_time = 0
        for j in [1, 2, 3, 4]:
            main_wtf(0, j, [0] * aTime)
        print(enc_time)

if __name__ == "__main__":
    main_main()

得数列 2, 20, 1056, 65792, 262656 。查询后得到通项公式 2 ** n + 4 ** n 。于是直接写出模拟:

for n in range(15):
    enc = 0
    for _ in range(2**n + 4**n):
        enc = enc - 17 * (((enc + ((
            (enc + 1) * 0xF0F0F0F0F0F0F0F1) >> 64) + 1) >> 4) -
                            ((enc + 1) >> 63)) + 1
    print(enc % 17, end=", ")

得数列 2, 6, 3, 4, 0, 2, -5, 5, 2, 6, 3, 4, 0, 2 。可以发现其 8 个一组循环,但是其中出现负数。考虑到 main_main 中的 sbox 长度为 17,故 -5 等价于 12 ,数列为 2, 6, 3, 4, 0, 2, 12, 5

由下述代码求得 sbox 的值:

#include "IDA.h"
#include <stdio.h>

int main(int argc, char **argv) {
    __int8 sbox[17];
    *(_QWORD *)sbox = 0x5F53055504525E54LL;
    *(_QWORD *)&sbox[8] = 0x3025156540750LL;
    sbox[16] = 87;
    for (int i = 0; i < 17; i++) {
        printf("%d, ", sbox[i]);
    }
    return 0;
}

sbox = [84, 94, 82, 4, 85, 5, 83, 95, 80, 7, 84, 86, 81, 2, 3, 0]

最终代码:

timeLists = [
    1, 3, 6, 9, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0x12, 0x14,
    0x19, 0x1E, 0x28, 0x42, 0x66, 0x0A0, 0x936, 0x3D21, 0x149A7, 0x243AC,
    0x0CB5BE, 0x47DC61, 0x16C0F46, 0x262C432, 0x4ACE299, 0x10FBC92A,
    0x329ECDFD, 0x370D7470
]
sbox = [84, 94, 82, 4, 85, 5, 83, 95, 80, 7, 84, 86, 81, 2, 3, 0]
enc_cycle = [2, 6, 3, 4, 0, 2, 12, 5]
print(''.join(chr(sbox[enc_cycle[(i - 1) % 8]] ^ 0x66) for i in timeLists))

输出 4b445b3247c45344c54c44734445452c

最终 flag: CISCN{4b445b3247c45344c54c44734445452c}

附:

exe 及 i64 文件 (请使用 IDA7.6)

所有 Python 代码:

enc = 0
enc_time = 0
timeLists = [
    1, 3, 6, 9, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0x12, 0x14,
    0x19, 0x1E, 0x28, 0x42, 0x66, 0x0A0, 0x936, 0x3D21, 0x149A7, 0x243AC,
    0x0CB5BE, 0x47DC61, 0x16C0F46, 0x262C432, 0x4ACE299, 0x10FBC92A,
    0x329ECDFD, 0x370D7470
]


def main_goooo(array):
    box = [0] * 5
    for tmp in array:
        box[tmp] ^= 1
    return box[1] == 0 and box[3] == 0


def main_wtf(depth, j, array):
    global enc, enc_time
    array[depth] = j
    if depth == len(array) - 1:
        if (main_goooo(array)):
            enc_time += 1
            enc = enc - 17 * (((enc + ((
                (enc + 1) * 0xF0F0F0F0F0F0F0F1) >> 64) + 1) >> 4) -
                              ((enc + 1) >> 63)) + 1
    else:
        for jj in [1, 2, 3, 4]:
            main_wtf(depth + 1, jj, array)


def main_main():
    global enc, enc_time
    for aTime in timeLists:
        enc = 0
        enc_time = 0
        for j in [1, 2, 3, 4]:
            main_wtf(0, j, [0] * aTime)
        print(enc_time)


def try_enc():
    for n in range(15):
        enc = 0
        for _ in range(2**n + 4**n):
            enc = enc - 17 * (((enc + ((
                (enc + 1) * 0xF0F0F0F0F0F0F0F1) >> 64) + 1) >> 4) -
                              ((enc + 1) >> 63)) + 1
        print(enc, end=", ")


def flag():
    sbox = [84, 94, 82, 4, 85, 5, 83, 95, 80, 7, 84, 86, 81, 2, 3, 0]
    enc_cycle = [2, 6, 3, 4, 0, 2, 12, 5]
    print(''.join(chr(sbox[enc_cycle[(i - 1) % 8]] ^ 0x66) for i in timeLists))


if __name__ == "__main__":
    # main_main()
    # try_enc()
    flag()

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!