KCTF 2021 秋季赛 第二题 迷失丛林

一道非常有意思的题，作者的出题思路是个数字替换的小游戏，但是实力受限，做题的时候着实看不出来。也是觉得这题非常有质量，就此分享下我的解题思路。

题目是Windows逆向，主要还是考察代码阅读能力。

找到主逻辑

能看到首先进行了长度校验的基本操作，然后就是将十六进制字符串转换成数值，同时输入限定范围0123456789ABCDEF

在这里动调时，会发现实现方式不太一样，具体表现为如下

此时我的输入是0123456789ABCDEF0123456789ABCDEF

而后程序将前8字节放入指定大小为256的sbox的首8元素处

下面分析check函数

首先这里一大段操作，很难看出些什么

往下看，能知道v21~v24类似计数，且给了第一个check点

if ( v21 == 0xA9 && v22 == 0xAC && v23 == 0xA7 && v24 > 0xC8u ){ …… }

继续往下，仔细阅读这一段代码后，知道的点：

• 一种类似于arr[i] = arr[arr[i]]的操作且循环
• sbox中的值唯一
• 值范围在0~255

由此提取出sbox[8:255]，与0~255对比，正好缺少了8个数字

rawbox = [0xA2, 0x9B, 0xF4, 0xDF, 0xAC, 0x7C, 0xA1, 0xC6, 0x16, 0xD0, 0x0F, 0xDD, 0xDC, 0x73, 0xC5, 0x6B, 0xD1, 0x96, 0x47, 0xC2, 0x26, 0x67, 0x4E, 0x41, 0x82, 0x20, 0x56, 0x9A, 0x6E, 0x33, 0x92, 0x88, 0x29, 0xB5, 0xB4, 0x71, 0xA9, 0xCE, 0xC3, 0x34, 0x50, 0x59, 0xBF, 0x2D, 0x57, 0x22, 0xA6, 0x30, 0x04, 0xB2, 0xCD, 0x36, 0xD5, 0x68, 0x4D, 0x5B, 0x45, 0x9E, 0x85, 0xCF, 0x9D, 0xCC, 0x61, 0x78, 0x32, 0x76, 0x31, 0xE3, 0x80, 0xAD, 0x39, 0x4F, 0xFA, 0x72, 0x83, 0x4C, 0x86, 0x60, 0xB7, 0xD7, 0x63, 0x0C, 0x44, 0x35, 0xB3, 0x7B, 0x19, 0xD4, 0x69, 0x08, 0x0B, 0x1F, 0x3D, 0x11, 0x79, 0xD3, 0xEE, 0x93, 0x42, 0xDE, 0x23, 0x3B, 0x5D, 0x8D, 0xA5, 0x77, 0x5F, 0x58, 0xDB, 0x97, 0xF6, 0x7A, 0x18, 0x52, 0x15, 0x74, 0x25, 0x62, 0x2C, 0x05, 0xE8, 0x0D, 0x98, 0x2A, 0x43, 0xE2, 0xEF, 0x48, 0x87, 0x49, 0x1C, 0xCA, 0x2B, 0xA7, 0x8A, 0x09, 0x81, 0xE7, 0x53, 0xAA, 0xFF, 0x6F, 0x8E, 0x91, 0xF1, 0xF0, 0xA4, 0x46, 0x3A, 0x7D, 0x54, 0xEB, 0x2F, 0xC1, 0xC0, 0x0E, 0xBD, 0xE1, 0x6C, 0x64, 0xBE, 0xE4, 0x02, 0x3C, 0x5A, 0xA8, 0x9F, 0x37, 0xAF, 0xA0, 0x13, 0xED, 0x1B, 0xEC, 0x8B, 0x3E, 0x7E, 0x27, 0x99, 0x75, 0xAB, 0xFE, 0xD9, 0x3F, 0xF3, 0xEA, 0x70, 0xF7, 0x95, 0xBA, 0x1D, 0x40, 0xB0, 0xF9, 0xE5, 0xF8, 0x06, 0xBC, 0xB6, 0x03, 0xC9, 0x10, 0x9C, 0x2E, 0x89, 0x5C, 0x7F, 0xB1, 0x1A, 0xD6, 0x90, 0xAE, 0xDA, 0xE6, 0x5E, 0xB9, 0x84, 0xE9, 0x55, 0xBB, 0xC7, 0x0A, 0xE0, 0x66, 0xF2, 0xD8, 0xCB, 0x00, 0x12, 0xB8, 0x17, 0x94, 0x6A, 0x4A, 0x01, 0x24, 0x14, 0x51, 0x07, 0x65, 0x21, 0xC8, 0x38, 0xFD, 0x8F, 0xC4, 0xF5, 0xFC]
rawbox.sort()
print(rawbox)
unknown = []
for i in range(256):
    if rawbox[i] != i:
        print("no value:", i)
        unknown.append(i)
        rawbox.insert(i, i)
print(unknown)

有了这八个值，想到了爆破

# -*- coding:utf-8 -*-
"""
@Author: Mas0n
@File: test23.py
@Time: 2021-11-14 16:06
@Desc: It's all about getting better.
"""


def run(flag):
    sbox = [0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0xA2, 0x9B, 0xF4, 0xDF, 0xAC, 0x7C, 0xA1, 0xC6, 0x16, 0xD0,
            0x0F, 0xDD, 0xDC, 0x73, 0xC5, 0x6B, 0xD1, 0x96, 0x47, 0xC2, 0x26, 0x67, 0x4E, 0x41, 0x82, 0x20, 0x56, 0x9A,
            0x6E, 0x33, 0x92, 0x88, 0x29, 0xB5, 0xB4, 0x71, 0xA9, 0xCE, 0xC3, 0x34, 0x50, 0x59, 0xBF, 0x2D, 0x57, 0x22,
            0xA6, 0x30, 0x04, 0xB2, 0xCD, 0x36, 0xD5, 0x68, 0x4D, 0x5B, 0x45, 0x9E, 0x85, 0xCF, 0x9D, 0xCC, 0x61, 0x78,
            0x32, 0x76, 0x31, 0xE3, 0x80, 0xAD, 0x39, 0x4F, 0xFA, 0x72, 0x83, 0x4C, 0x86, 0x60, 0xB7, 0xD7, 0x63, 0x0C,
            0x44, 0x35, 0xB3, 0x7B, 0x19, 0xD4, 0x69, 0x08, 0x0B, 0x1F, 0x3D, 0x11, 0x79, 0xD3, 0xEE, 0x93, 0x42, 0xDE,
            0x23, 0x3B, 0x5D, 0x8D, 0xA5, 0x77, 0x5F, 0x58, 0xDB, 0x97, 0xF6, 0x7A, 0x18, 0x52, 0x15, 0x74, 0x25, 0x62,
            0x2C, 0x05, 0xE8, 0x0D, 0x98, 0x2A, 0x43, 0xE2, 0xEF, 0x48, 0x87, 0x49, 0x1C, 0xCA, 0x2B, 0xA7, 0x8A, 0x09,
            0x81, 0xE7, 0x53, 0xAA, 0xFF, 0x6F, 0x8E, 0x91, 0xF1, 0xF0, 0xA4, 0x46, 0x3A, 0x7D, 0x54, 0xEB, 0x2F, 0xC1,
            0xC0, 0x0E, 0xBD, 0xE1, 0x6C, 0x64, 0xBE, 0xE4, 0x02, 0x3C, 0x5A, 0xA8, 0x9F, 0x37, 0xAF, 0xA0, 0x13, 0xED,
            0x1B, 0xEC, 0x8B, 0x3E, 0x7E, 0x27, 0x99, 0x75, 0xAB, 0xFE, 0xD9, 0x3F, 0xF3, 0xEA, 0x70, 0xF7, 0x95, 0xBA,
            0x1D, 0x40, 0xB0, 0xF9, 0xE5, 0xF8, 0x06, 0xBC, 0xB6, 0x03, 0xC9, 0x10, 0x9C, 0x2E, 0x89, 0x5C, 0x7F, 0xB1,
            0x1A, 0xD6, 0x90, 0xAE, 0xDA, 0xE6, 0x5E, 0xB9, 0x84, 0xE9, 0x55, 0xBB, 0xC7, 0x0A, 0xE0, 0x66, 0xF2, 0xD8,
            0xCB, 0x00, 0x12, 0xB8, 0x17, 0x94, 0x6A, 0x4A, 0x01, 0x24, 0x14, 0x51, 0x07, 0x65, 0x21, 0xC8, 0x38, 0xFD,
            0x8F, 0xC4, 0xF5, 0xFC]

    sb8 = int(flag, 16)
    for d, vp in enumerate(int.to_bytes(sb8, length=8, byteorder="big")):
        sbox[d] = vp
    arrs2 = [[0] * 256 for i in range(256)]
    maps = [0] * 512

    for v2 in range(256):
        m = 0
        maps[0] = sbox[v2]
        maps[1] = v2 + 1

        for i in range(2, 510, 2):
            maps[i] = sbox[maps[m] & 0xff]
            maps[i + 1] = maps[m] + 1
            m += 1

        # print(maps)
        for _ in range(0, 256):
            arrs2[v2][maps[m] & 0xff] += 1
            m += 1
        # print(arrs2)

    v21 = 0
    v22 = 0
    v23 = 0
    v24 = 0
    for i in range(256):
        if arrs2[i][0]:
            v21 += 1
        if arrs2[i][14]:
            v22 += 1
        if arrs2[i][40]:
            v23 += 1
        if arrs2[i][79]:
            v24 += 1


    # print(flag, hex(v21), hex(v22), hex(v23), hex(v24))

    if v21 == 0xA9 and v22 == 0xAC and v23 == 0xa7 and v24 > 0xc8:
        return True
    else:
        return False


# print(v21 == 0xA9 && v22 == 0xAC && v23 == 0xA7 && v24 > 0xC8u)
tables = "0123456789ABCDEFF"
import itertools
arr = [hex(s)[2:].zfill(2).upper() for s in [30, 40, 75, 109, 140, 163, 210, 251]]
print(arr)
for _, v in enumerate(itertools.permutations(arr, 8)):
    if run("".join(v)):
        print("".join([ch[::-1] for ch in v]))
        print("!!!!!ok")

能够爆破出前十六位serials：B4D682C8BF2DE13A

回到之后的执行代码

简单的ascii和位操作，把sbox dump下来，偷懒用z3了。

from z3 import *

flag2 = [BitVec(f"flag2[{i}]", 8) for i in range(8)]

rsbox = [0xC1, 0x9B, 0x7F, 0x58, 0x64, 0xD5, 0x77, 0x21, 0x74, 0xEB, 0x14, 0xBF, 0xDF, 0x25, 0x5A, 0x37, 0x85, 0x2C, 0xAF, 0x8C, 0xDA, 0x26, 0xE2, 0x7A, 0x87, 0x4C, 0x60, 0x99, 0x54, 0x3C, 0x95, 0xC0, 0xB9, 0x0C, 0xBC, 0x0E, 0xE7, 0x2D, 0x86, 0xBE, 0x67, 0xD3, 0xD8, 0xFC, 0x30, 0xB6, 0xC8, 0x57, 0x1E, 0x62, 0x3E, 0xCE, 0xA0, 0xCD, 0xF5, 0xEE, 0xA7, 0xCF, 0x45, 0xFE, 0xD0, 0x80, 0x05, 0xAD, 0x13, 0xF3, 0xB7, 0x6B, 0x22, 0x2B, 0xBD, 0x69, 0x42, 0x4B, 0xA5, 0xEA, 0xA6, 0xD2, 0x6F, 0x4F, 0x4E, 0x07, 0xE1, 0x36, 0x01, 0xB5, 0xAA, 0xB1, 0x94, 0x0B, 0x35, 0x3A, 0xC7, 0x49, 0x53, 0x82, 0xC3, 0x7B, 0x32, 0xFF, 0x19, 0xC4, 0xF1, 0xC9, 0xE8, 0xF7, 0x56, 0x15, 0xA3, 0x46, 0x89, 0x43, 0x9D, 0x8F, 0x20, 0xEF, 0xBB, 0x2A, 0xCB, 0x09, 0x93, 0x4A, 0x1C, 0xE3, 0x33, 0xD1, 0xE0, 0x1D, 0x72, 0x7C, 0x27, 0xE9, 0x17, 0x28, 0x6D, 0x6A, 0xD9, 0x00, 0x9A, 0xE5, 0x63, 0xDE, 0x23, 0x9F, 0x0D, 0x47, 0x3B, 0x65, 0x08, 0x84, 0x6C, 0x1A, 0x88, 0x12, 0xA1, 0xA4, 0xB3, 0x18, 0x24, 0x1B, 0xD7, 0x44, 0xDB, 0xAC, 0x6E, 0x7D, 0x51, 0x5E, 0xED, 0x50, 0xD6, 0x11, 0x5B, 0x9C, 0xB4, 0x68, 0x3D, 0x2F, 0x03, 0x40, 0xBA, 0x2E, 0xCA, 0x02, 0xE6, 0xA8, 0xEC, 0x83, 0x06, 0x5D, 0xB8, 0x4D, 0x97, 0x66, 0xF0, 0xFB, 0x8A, 0x55, 0xAB, 0xB2, 0x04, 0xFA, 0x0A, 0x31, 0x71, 0xCC, 0x8B, 0x73, 0xA9, 0x48, 0x5C, 0xF9, 0x98, 0xE4, 0xC6, 0x34, 0xC5, 0x7E, 0x81, 0x75, 0x90, 0x1F, 0x92, 0x3F, 0x9E, 0x10, 0x29, 0x52, 0x39, 0xF4, 0x41, 0x78, 0x5F, 0x16, 0x79, 0xC2, 0xB0, 0xDD, 0xF2, 0x61, 0x0F, 0x70, 0xD4, 0x91, 0xDC, 0xF6, 0xF8, 0xFD, 0x59, 0x38, 0x8D, 0x96, 0xAE, 0x8E, 0x76, 0xA2]
sbox = Array("sbox", BitVecSort(8), BitVecSort(8))
sol = Solver()

for i, v in enumerate(rsbox):
    sol.add(sbox[i] == v)
input8 = flag2
for v17 in range(9):
    for i in range(8):
        if v17 >= 8:
            if i == 0 or i == 7:
                code[i] -= 1
        else:

            v19 = If(input8[i] & 1 != 0, code[i] + 1, Select(sbox, 0xff & code[i]))
            code[i] = v19
            input8[i] = (input8[i] >> 1) & 0xff


good = list(b"GoodJob~")

for i in range(8):
    sol.add(good[i] == code[i])

assert sol.check() == sat
mol = sol.model()
print(mol)

拼接即可

flag2 = [0] * 8
flag2[2] = 234
flag2[5] = 8
flag2[7] = 34
flag2[6] = 188
flag2[0] = 157
flag2[3] = 47
flag2[1] = 107
flag2[4] = 164

for i in flag2:
    flag += hex(i)[2:].zfill(2)[::-1].upper()

print(flag)

后记

不知道后面还能不能做出题来，先膜一波大佬们吧。

自己还是比较缺乏算法方面的知识，分析代码的速度也比较慢。解题的过程虽然枯燥，但同时也是一种对探索未知的享受吧。