【wp】2020XCTF_逆向

前几天的XCTF最后一场终于打完了,三场比赛下来对逆向部分的大概感觉是从第一场的啥都不会做(一道lua+一道apk)到后来的终于能有参与度,至少后两场的题目都是pc逆向,虽然特殊架构但好歹能做(tcl。

本文是三场XCTF所有逆向题目的wp+复现整理。赛中拿到了7/10的flag,很多是跟着队里的大佬做出来的(tqltql),这边就试着独立复现一下,至少打完应该长长记性(

P.S. 不会的题暂时标了【TODO】,等wp出了回来填坑= =

比赛官网:XCTF高校网络安全专题挑战赛

[12.20] 华为云专场

Weird_lua【TODO】

【TODO】

lua是第一次接触,.lua文件没法反编译,估计虚拟机被魔改了

divination【TODO】

【TODO】

apk逻辑没看出来,废了废了

[12.23] 鲲鹏计算专场

mips

真·送分题,可惜当时要上课没来得及抢一血(下午2点放题绝了

老传统走迷宫

mips架构。

ida反编译以后可以看到

【wp】2020XCTF_逆向

v4是我们输入的字符串,很明显是迷宫逻辑,上下左右用wasd走,迷宫存在dword_100111F0里。

sub_10000744()这个初始函数是用来找起点用的(就是迷宫中3所在的地方,在后面可以看到3其实表示的是当前位置)。

【wp】2020XCTF_逆向

这里也可以看到应该有多个迷宫(dword_10011D10是用来表示第几个迷宫的,且<=2,一个迷宫有225个数)+一个迷宫宽为15=三个迷宫,每个迷宫为15*15。

然后就是下面的四个函数,随便挑一个出来(比如sub_10000D28())可以看到

【wp】2020XCTF_逆向

很明显是个往右走的函数,3表示当前位置,并把上一个当前位置标为1(可走路径)。并且可以看到终点是4,就是说我们要把每个迷宫从3走到4。

dump迷宫数组,写脚本打印迷宫:

aMap=[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 3, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0]
for i in range(45):
    for j in range(15):
        if aMap[i*15+j]==0:
            tmp='*'
        elif aMap[i*15+j]==1:
            tmp='.'
        elif aMap[i*15+j]==3:
            tmp='@'
        else:
            tmp='#'
        print(tmp,end='')
    print()
    if i==14 or i==29:
        print()

可以看到打印出了三个迷宫,为了看得清楚所以选用几个特定字符打印。

.....**********
.....*@*.******
.....*.*.******
.....*.*.******
.....*.*.....**
.....*.*****.**
.....*.*****.**
.....*.*****..*
.....*........*
.....********#*
...............
...............
...............
...............
...............
#sssssssddddddds

..*************
..*@*....******
..*.****.******
..*.****.******
..*..***.....**
..*..*******.**
..*..*******.**
..*..*****....*
..*..*****.**.*
..*..*****.****
..*......*.*..*
..*...........*
..***********#*
...............
...............
#ssssssssssdddddddddds

***************
*@..***********
***.*...*******
***...*.*******
****.**.*******
*..*.**.*******
**...**.*******
*******.*******
*******....****
**********.****
**********.****
**********.****
**********....*
*************.*
*************#*
#ddssddwddssssssdddssssdddss

走迷宫,然后把路径拼起来,根据提示转md5,get flag。

(有个疑惑哈,第二个迷宫理论上说就算是最短路也有多解?是题目出锅了还是我哪里看漏了= =

(再补一句,题目似乎甚至没要求最短路???神奇.jpg

【wp】2020XCTF_逆向

import hashlib
s=b"sssssssdddddddsssssssssssddddddddddsddssddwddssssssdddssssdddss"
print("flag{%s}"%hashlib.md5(s).hexdigest())

flag{999ea6aa6c365ab43eec2a0f0e5968d5}

pypy

把题目文件拖进ida,搜索字符串能看到

【wp】2020XCTF_逆向

猜测是pyinstaller打包的文件。

也就是这个题让我突然发现pyinstaller还能打包成elf的,于是比赛结束以后赶紧把之前总结的解包指南更新了:RE套路 - 关于pyinstaller打包文件的复原 | c10udlnk_Log

走流程解包,得到python源码。

【wp】2020XCTF_逆向

看到这种混淆变量名,果断替换成ida style变量名(。

放一下源码:

# uncompyle6 version 3.7.4
# Python bytecode 3.8 (3413)
# Decompiled from: Python 2.7.18 (v2.7.18:8d21aa21f2, Apr 20 2020, 13:25:05) [MSC v.1500 64 bit (AMD64)]
# Warning: this version of Python has problems handling the Python 3 "byte" type in constants properly.

# Embedded file name: main.py
# Compiled at: 1995-09-28 00:18:56
# Size of source mod 2**32: 257 bytes
import random, codecs, sys, time, pygame
from pygame.locals import *
from collections import deque
SCREEN_WIDTH = 600
SCREEN_HEIGHT = 480
SIZE = 20
LINE_WIDTH = 1
flag = 'flag{this is a fake flag}'
SCOPE_X = (0, SCREEN_WIDTH // SIZE - 1)
SCOPE_Y = (2, SCREEN_HEIGHT // SIZE - 1)
FOOD_STYLE_LIST = [(10, (255, 100, 100)), (20, (100, 255, 100)), (30, (100, 100, 255))]
LIGHT = (100, 100, 100)
DARK = (200, 200, 200)
BLACK = (0, 0, 0)
RED = (200, 30, 30)
BGCOLOR = (40, 40, 60)

def print_text(v1, v2, v3, v4, v5, fcolor=(255, 255, 255)):
    v6 = v2.render(v5, True, fcolor)
    v1.blit(v6, (v3, v4))


def init_snake():
    v7 = deque()
    v7.append((2, SCOPE_Y[0]))
    v7.append((1, SCOPE_Y[0]))
    v7.append((0, SCOPE_Y[0]))
    return v7


def create_food(v8):
    v9 = random.randint(SCOPE_X[0], SCOPE_X[1])
    v10 = random.randint(SCOPE_Y[0], SCOPE_Y[1])
    while (v9, v10) in v8:
        v9 = random.randint(SCOPE_X[0], SCOPE_X[1])
        v10 = random.randint(SCOPE_Y[0], SCOPE_Y[1])

    return (
     v9, v10)


def get_food_style():
    return FOOD_STYLE_LIST[random.randint(0, 2)]


DEFAULT_KEY = u'Y\xf3\x02\xc3%\x9a\x820\x0b\xbb%\x7f~;\xd2\xdc'

def rc4(v11, key=DEFAULT_KEY, skip=1024):
    v12 = 0
    v13 = bytearray([v14 for v14 in range(256)])
    v12 = 0
    for v15 in range(256):
        v12 = (v12 + v13[v15] + ord(key[(v15 % len(key))])) % 256
        v16 = v13[v15]
        v17 = v13[v12]
        v13[v15] = v13[v12]
        v13[v12] = v16
    else:
        v12 = 0
        v18 = 0
        v19 = []
        if skip > 0:
            for v15 in range(skip):
                v12 = (v12 + 1) % 256
                v18 = (v18 + v13[v12]) % 256
                v13[v12], v13[v18] = v13[v18], v13[v12]

        for v20 in v11:
            v12 = (v12 + 1) % 256
            v18 = (v18 + v13[v12]) % 256
            v13[v12], v13[v18] = v13[v18], v13[v12]
            v21 = v13[((v13[v12] + v13[v18]) % 256)]
            v19.append(chr(ord(v20) ^ v21))
        else:
            return ''.join(v19)


def func(v22):
    v23 = rc4(v22)
    if v23.encode('utf-8').hex() == '275b39c381c28b701ac3972338456022c2ba06c3b04f5501471c47c38ac380c29b72c3b5c38a7ec2a5c2a0':
        return 'YOU WIN'
    return 'YOU LOSE'


def main():
    pygame.init()
    v24 = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
    pygame.display.set_caption(u'\u8d2a\u5403\u86c7')
    v25 = pygame.font.SysFont('SimHei', 24)
    v26 = pygame.font.Font(None, 72)
    v27, v28 = v26.size('GAME OVER')
    v29 = True
    v30 = init_snake()
    v31 = create_food(v30)
    v32 = get_food_style()
    v33 = (1, 0)
    v34 = True
    v35 = False
    v36 = 0
    v37 = 0.5
    v38 = v37
    v39 = None
    v41 = False
    for v40 in pygame.event.get():
        if v40.type == QUIT:
            sys.exit()
        elif v40.type == KEYDOWN:
            if v40.key == K_RETURN:
                if v34:
                    v35 = True
                    v34 = False
                    v29 = True
                    v30 = init_snake()
                    v31 = create_food(v30)
                    v32 = get_food_style()
                    v33 = (1, 0)
                    v36 = 0
                    v39 = time.time()
            elif v40.key == K_SPACE:
                if not v34:
                    v41 = not v41
            elif v40.key in (K_w, K_UP):
                if v29:
                    v33 = v33[1] or (0, -1)
                    v29 = False
            elif v40.key in (K_s, K_DOWN):
                if v29:
                    v33 = v33[1] or (0, 1)
                    v29 = False
            elif v40.key in (K_a, K_LEFT):
                if v29:
                    if not v33[0]:
                        v33 = (-1, 0)
                        v29 = False
                    elif v40.key in (K_d, K_RIGHT):
                        if v29:
                            if not v33[0]:
                                v33 = (1, 0)
                                v29 = False
        else:
            v24.fill(BGCOLOR)
            for v42 in range(SIZE, SCREEN_WIDTH, SIZE):
                pygame.draw.line(v24, BLACK, (v42, SCOPE_Y[0] * SIZE), (v42, SCREEN_HEIGHT), LINE_WIDTH)
            else:
                for v43 in range(SCOPE_Y[0] * SIZE, SCREEN_HEIGHT, SIZE):
                    pygame.draw.line(v24, BLACK, (0, v43), (SCREEN_WIDTH, v43), LINE_WIDTH)
                else:
                    v44 = v34 or time.time()

            if v44 - v39 > v38 and not v41:
                v29 = True
                v39 = v44
                v45 = (v30[0][0] + v33[0], v30[0][1] + v33[1])
                if v45 == v31:
                    v30.appendleft(v45)
                    v36 += v32[0]
                    v38 = v37 - 0.03 * (v36 // 100)
                    v31 = create_food(v30)
                    v32 = get_food_style()
                else:
                    if SCOPE_X[0] <= v45[0] <= SCOPE_X[1]:
                        if SCOPE_Y[0] <= v45[1] <= SCOPE_Y[1]:
                            if v45 not in v30:
                                v30.appendleft(v45)
                                v30.pop()
                            else:
                                v34 = True
                    if not v34:
                        pygame.draw.rect(v24, v32[1], (v31[0] * SIZE, v31[1] * SIZE, SIZE, SIZE), 0)
                for v46 in v30:
                    pygame.draw.rect(v24, DARK, (v46[0] * SIZE + LINE_WIDTH, v46[1] * SIZE + LINE_WIDTH, SIZE - LINE_WIDTH * 2, SIZE - LINE_WIDTH * 2), 0)
                else:
                    print_text(v24, v25, 30, 7, f"speed: {v36 // 100}")
                    print_text(v24, v25, 450, 7, f"score: {v36}")
                    if v36 >= 5192296858534827628530496329220096:
                        v47 = flag
                        print_text(v24, v26, (SCREEN_WIDTH - v27) // 2, (SCREEN_HEIGHT - v28) // 2, func(v47), RED)
                    if v34:
                        if v35:
                            print_text(v24, v26, (SCREEN_WIDTH - v27) // 2, (SCREEN_HEIGHT - v28) // 2, 'GAME OVER', RED)
                    pygame.display.update()


if __name__ == '__main__':
    main()
# okay decompiling main.pyc

可以看到最后getflag这里(func())的程序逻辑就一个rc4加密,由rc4的特性可知加密和解密流程相同,故复用程序中的rc4()来得到flag。

uncompyle反编译出来的源码是python3,但是题目本身的源码是python2,注意编码问题。

关于编码问题,可以看:

Unicode之痛 — PyCoder's Weelky CN

关于python2中的unicode和str以及python3中的str和bytes - 明王不动心 - 博客园

这里因为反编译做了转换成python3的处理,所以脚本用python3写。

DEFAULT_KEY = u'Y\xf3\x02\xc3%\x9a\x820\x0b\xbb%\x7f~;\xd2\xdc'
def rc4(v11, key=DEFAULT_KEY, skip=1024):
    v12 = 0
    v13 = bytearray([v14 for v14 in range(256)])
    v12 = 0
    for v15 in range(256):
        v12 = (v12 + v13[v15] + ord(key[(v15 % len(key))])) % 256
        v16 = v13[v15]
        v17 = v13[v12]
        v13[v15] = v13[v12]
        v13[v12] = v16
    else:
        v12 = 0
        v18 = 0
        v19 = []
        if skip > 0:
            for v15 in range(skip):
                v12 = (v12 + 1) % 256
                v18 = (v18 + v13[v12]) % 256
                v13[v12], v13[v18] = v13[v18], v13[v12]

        for v20 in v11:
            v12 = (v12 + 1) % 256
            v18 = (v18 + v13[v12]) % 256
            v13[v12], v13[v18] = v13[v18], v13[v12]
            v21 = v13[((v13[v12] + v13[v18]) % 256)]
            v19.append(chr(ord(v20) ^ v21))
        else:
            return ''.join(v19)
# def func(v22):
#     v23 = rc4(v22)
#     if v23.encode('utf-8').hex() == '275b39c381c28b701ac3972338456022c2ba06c3b04f5501471c47c38ac380c29b72c3b5c38a7ec2a5c2a0':
#         return 'YOU WIN'
#     return 'YOU LOSE'

# -=-=-=以上所有为源码中原函数-=-=-=

cipher='275b39c381c28b701ac3972338456022c2ba06c3b04f5501471c47c38ac380c29b72c3b5c38a7ec2a5c2a0'
flag=bytes.fromhex(cipher).decode('utf-8')
print(rc4(flag))

【wp】2020XCTF_逆向

flag{snake_bao_is_really_lucky}

print【TODO】

【TODO】

这个题感觉大概知道怎么做,但就是不会啊(等wp...

贴一下当时的想法,看了看逻辑只有sprintf这种函数,除此以外没有别的可以改写内存数据的操作了。

动态调试跟了一下,猜测是sprintf格式化字符串漏洞写入?

Introduction to format string exploits

sprintf - stm32学习中 - 博客园

pwn太菜了还没搞懂要怎么往output那里写(虽然这是逆向题orz

setup函数那里有一些format的初始化,主要是loop()那里,控制input(输入的字符串,全部为可见字符且长度>11),来改变使得output!=原来的output且output-1==48('0')。

【wp】2020XCTF_逆向

[12.27] HarmonyOS和HMS专场

难得有一场ak逆向了!(虽然有大佬带着

有三道题都是卡着四血交,实惨TAT

re123

用file命令可以看到是MS Windows HtmlHelp Data文件(即.chm),查看文件头也可以知道。

【wp】2020XCTF_逆向

【wp】2020XCTF_逆向

所以添加后缀名.chm。

关于chm文件有一个常用的反编译器ChmDecompiler,可以释放CHM里面的全部源文件(包括网页、文本、图片、CHM、ZIP、EXE等全部源文件),并且完美地恢复源文件的全部目录结构 (摘抄的简介。

所以用ChmDecompiler打开re.chm,解压缩,可以看到目录下出现一个包含四个文件的文件夹(其实源文件只有三个,.hhp是ChmDecompiler自动生成的)。

【wp】2020XCTF_逆向

一个一个翻可以看到doc.htm里有一段奇怪的Item1。

【wp】2020XCTF_逆向

大概可以看到是powershell的语法?(感觉像win后门,这么多no的参数

查了一下其实就是把后面那大段进行base64解码而已,用wsl解一下base64有

【wp】2020XCTF_逆向

然后得到了一段.NET代码(白字)。

通过查微软文档可以知道,这里是把base64解码以后的字符进行Deflate解压的过程,所以用脚本把中间那段base64解码,并整理输出。

import base64
import zlib
 
def deflate(data):
    try:
        return zlib.decompress(data, -zlib.MAX_WBITS)
    except zlib.error:
        return zlib.decompress(data)

code='TY5BC4IwGIbvgv9hjB2McJhEhNChJMGTkN2qg7qvFHQT/bL575vpoV2/53n2skJJBInkQG5xwqOqhkcQXCATx7q+gkaHsvYj7kIVvCgburItVgm9MTxbVB5LATp5OlQvb6IMV0LdQvdPpu+8x66SL2eOrMl+Ck7naUA69ggND5UcoEOzI+pUc8p62G3TRZubv34K6IbLespADoGR27vv+R7HpqXzt8Q9y0IJI5N8RLCtLw=='
de_code=deflate(base64.b64decode(code)).decode()
for x in de_code.split('\r\n'):
    print(x)

【wp】2020XCTF_逆向

很明显的逻辑了,把doc.chm(应该是原来的re.chm)中"xxxxxxxx"后面的部分提取出来,还是用base64解码得到文件。

【wp】2020XCTF_逆向

把这后面的内容手动复制出来到cont.txt里,进行base64解码,最后存在theFile中。

base64 -d cont.txt > theFile

查看theFile可以猜测是exe(毕竟最开始给的就是有powershell指令的base64),把文件头补上,并改后缀名(即theFile.exe)。

【wp】2020XCTF_逆向

用ida打开,通过FindCrypt插件可以看到AES,跟过去能看到AES加密时的S盒(其实这里前两个都是S盒,第三个是逆S盒),猜测用到了AES加密。

【wp】2020XCTF_逆向

【wp】2020XCTF_逆向

往上回溯找到主函数

【wp】2020XCTF_逆向

显然,这里是AES加密过程,sub_180001100()是密钥拓展过程,sub_1800015B0()是AES加密。

关于逆向中各种常见密码的记录,指路:对称加密算法&&Hash算法 文档 | feng's blog

看了一下感觉是原装无魔改的AES,密文密钥都给了,那就直接写脚本解密。

注意这里是以整数形式给出的,别忘了小端序。

from Crypto.Cipher import AES
from binascii import *

arr=[0x16157E2B,0xA6D2AE28,0x8815F7AB,0x3C4FCF09]
key=""
for i in range(4):
    key=hex(arr[i])[2:]+key
key=unhexlify(key)[::-1] #注意小端序的问题
tmp=0x46C42084AA2A1B56E799D643453FF4B5
cipher=unhexlify(hex(tmp)[2:])[::-1]
enc=AES.new(key,AES.MODE_ECB)
print(enc.decrypt(cipher))

【wp】2020XCTF_逆向

flag{youcangues}

puzzle

mips架构。

加载进ida以后,通过字符串回溯找到主函数。

【wp】2020XCTF_逆向

【wp】2020XCTF_逆向

可以看到很明显的sub_401134()这个check,先往这里面看。

【wp】2020XCTF_逆向

看到是一个疑似maze的逻辑(

不过sub_400FA8()点进去以后可以看到是swap的功能

【wp】2020XCTF_逆向

所以应该不是maze,是一个以交换为主的逻辑。

至于dword_4A0010,可以看到是一个九个数的数组。

【wp】2020XCTF_逆向

v4和v5的出处在switch逻辑上面一点

【wp】2020XCTF_逆向

可以看到最后(v4,v5)其实表示了数组里0的位置,且数组实际可以看成是3*3。

即:

4 0 3
7 2 6
8 1 5

最后sub_400FFC()的检查逻辑:

【wp】2020XCTF_逆向

实际上就是要让这个3*3等于

1 2 3
4 5 6
7 8 0

把0看成空位的话,很容易就想到3*3的华容道了。

(或者玩算法的小伙伴可能对八数码问题这个名字更熟悉?

有本事下次出数织啊!20*20我都给你火速解出来(来自数织爱好者的吐槽)

这里实际上是求最短能得到的路径(15步),懒得想了,直接去网上抓了个现成代码下来改了改。

八数码问题的代码见:八数码问题-A*(AStar)算法实现_Broken Geeker-CSDN博客

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#define maxState 10000
#define N 3
using namespace std;

bool isEqual(int a[N][N][maxState],int b[N][N],int n){
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++){
            if(a[i][j][n] != b[i][j]) return false;
        }
    }
    return true;
}
bool isEqual(int a[N][N],int b[N][N]){
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++){
            if(a[i][j] != b[i][j]) return false;
        }
    }
    return true;
}
int evalute(int state[N][N],int target[N][N]){
    int num = 0;
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++)
            if(state[i][j] != target[i][j]) num ++;
    }
    return num;
}
void findBrack(int a[N][N],int x,int y){
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++){
            if(a[i][j] == 0) {
                x = i;y = j;return;
            }
        }
    }
}
bool move(int a[N][N],int b[N][N],int dir){
    //1 up 2 down 3 left 4 right
    int x = 0,y = 0;
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++){
            b[i][j] = a[i][j];
            if(a[i][j] == 0) {
                x = i;y = j;
            }
        }
    }
    if(x == 0 && dir == 1) return false;
    if(x == N-1 && dir == 2) return false;
    if(y == 0 && dir == 3) return false;
    if(y == N-1 && dir == 4) return false;
    if(dir == 1){b[x-1][y] = 0;b[x][y] = a[x-1][y];}
    else if(dir == 2){b[x+1][y] = 0;b[x][y] = a[x+1][y];}
    else if(dir == 3){b[x][y-1] = 0;b[x][y] = a[x][y-1];}
    else if(dir == 4){b[x][y+1] = 0;b[x][y] = a[x][y+1];}
    else return false;
    return true;
}
void statecpy(int a[N][N][maxState],int b[N][N],int n){
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++){
            a[i][j][n] = b[i][j];
        }
    }
}
void getState(int a[N][N][maxState],int b[N][N],int n){
    for(int i = 0;i < N;i ++){
        for(int j = 0;j < N;j ++){
            b[i][j] = a[i][j][n];
        }
    }
}
void statecpy(int a[N][N],int b[N][N]){
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++)
            a[i][j] = b[i][j];
    }
}
int checkAdd(int a[N][N][maxState],int b[N][N],int n){
    for(int i = 0;i < n;i ++){
        if(isEqual(a,b,i)) return i;
    }
    return -1;
}
int Astar(int a[N][N][maxState],int start[N][N],int target[N][N],int path[maxState]){
    bool visited[maxState] = {false};
    int fitness[maxState] = {0};
    int passLen[maxState] = {0};
    int curpos[N][N];
    statecpy(curpos,start);
    int id = 0,Curid = 0;
    fitness[id] = evalute(curpos,target);
    statecpy(a,start,id++);
    while(!isEqual(curpos,target)){
        for(int i = 1;i < 5;i ++){//向四周找方向
            int tmp[N][N] = {0};
            if(move(curpos,tmp,i)){
                int state = checkAdd(a,tmp,id);
                if(state == -1){//not add
                    path[id] = Curid;
                    passLen[id] = passLen[Curid] + 1;
                    fitness[id] = evalute(tmp,target) + passLen[id];
                    statecpy(a,tmp,id++);
                }else{//add
                    int len = passLen[Curid] + 1,fit = evalute(tmp,target) + len;
                    if(fit < fitness[state]){
                        path[state] = Curid;
                        passLen[state] = len;
                        fitness[state] = fit;
                        visited[state] = false;
                    }
                }
            }
        }
        visited[Curid] = true;
        //找到适应度最小的最为下一个带搜索节点
        int minCur = -1;
        for(int i = 0;i < id;i ++)
            if(!visited[i] && (minCur == -1 || fitness[i] < fitness[minCur])) minCur = i;
        Curid = minCur;
        getState(a,curpos,Curid);
        if(id == maxState) return -1;
    }
    return Curid;
}
void show(int a[N][N][maxState],int n){
    cout << "-------------------------------\n";
    for(int i = 0;i < N;i ++){
        for(int j =0;j < N;j ++){
            cout << a[i][j][n] << " ";
        }
        cout << endl;
    }
    cout << "-------------------------------\n";
}
int calDe(int a[N][N]){
    int sum = 0;
    for(int i = 0;i < N*N;i ++){
        for(int j = i+1;j < N*N;j ++){
            int m,n,c,d;
            m = i/N;n = i%N;
            c = j/N;d = j%N;
            if(a[c][d] == 0) continue;
            if(a[m][n] > a[c][d]) sum ++;
        }
    }
    return sum;
}
void autoGenerate(int a[N][N]){
    int maxMove = 50;
    srand((unsigned)time(NULL));
    int tmp[N][N];
    while(maxMove --){
        int dir = rand()%4 + 1;
        if(move(a,tmp,dir)) statecpy(a,tmp);
    }
}
int main(){
    int a[N][N][maxState] = {0};
    // int start[N][N] = {1,2,3,4,5,6,7,8,0};
    // autoGenerate(start);
    // cout << start[0][0] << start[1][1];
    int start[N][N] = {4,0,3,7,2,6,8,1,5};
    int target[N][N] = {1,2,3,4,5,6,7,8,0};
    if(!(calDe(start)%2 == calDe(target)%2)){
        cout << "无解\n";
        return 0;
    }
    int path[maxState] = {0};
    int res =  Astar(a,start,target,path);
    if(res == -1){
        cout << "达到最大搜索能力\n";
        return 0;
    }
    int shortest[maxState] = {0},j = 0;
    while(res != 0){
        shortest[j++] = res;
        res = path[res];
    }
    cout << "第 0 步\n";
    show(a,0);
    for(int i = j - 1;i >= 0;i --){
        cout << "第 " << j-i << " 步\n";
        show(a,shortest[i]);
    }
    return 0;
}

得到每一步的情况,进而根据switch写出路径。

第 0 步
-------------------------------
4 0 3
7 2 6
8 1 5
-------------------------------
第 1 步
-------------------------------
4 2 3
7 0 6
8 1 5
-------------------------------
第 2 步
-------------------------------
4 2 3
7 1 6
8 0 5
-------------------------------
第 3 步
-------------------------------
4 2 3
7 1 6
8 5 0
-------------------------------
第 4 步
-------------------------------
4 2 3
7 1 0
8 5 6
-------------------------------
第 5 步
-------------------------------
4 2 0
7 1 3
8 5 6
-------------------------------
第 6 步
-------------------------------
4 0 2
7 1 3
8 5 6
-------------------------------
第 7 步
-------------------------------
4 1 2
7 0 3
8 5 6
-------------------------------
第 8 步
-------------------------------
4 1 2
7 5 3
8 0 6
-------------------------------
第 9 步
-------------------------------
4 1 2
7 5 3
0 8 6
-------------------------------
第 10 步
-------------------------------
4 1 2
0 5 3
7 8 6
-------------------------------
第 11 步
-------------------------------
0 1 2
4 5 3
7 8 6
-------------------------------
第 12 步
-------------------------------
1 0 2
4 5 3
7 8 6
-------------------------------
第 13 步
-------------------------------
1 2 0
4 5 3
7 8 6
-------------------------------
第 14 步
-------------------------------
1 2 3
4 5 0
7 8 6
-------------------------------
第 15 步
-------------------------------
1 2 3
4 5 6
7 8 0
-------------------------------

6 左
2 上
4 右
8 下
// 884226886224488

路径为“884226886224488”。

接下来看主函数里check上面的部分,看到sub_409070()实际上是一个scanf,而dword_4A1B60是我们的输入,也就是最后的flag,中间对输入进行处理以后才得到“884226886224488”这个字符串。

在里面翻可以翻到一个sub_400B58(),猜测是base64换表编码。

【wp】2020XCTF_逆向

于是尝试写脚本编码。

import base64
b64table="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
mytable=""
offset=-18
for i in range(len(b64table)):
    mytable+=b64table[(i+offset)%len(b64table)]
text="884226886224488".encode()
cipher=base64.b64encode(text).decode().translate(str.maketrans(b64table,mytable))
print(cipher)

【wp】2020XCTF_逆向

试试能不能过check。

wsl运行:(要装qemu才能执行,毕竟特殊架构。

cp $(which qemu-mips) .
./qemu-mips -L . ./puzzle

执行mips程序,输入脚本中解出的字符串,发现成功了,get flag。

【wp】2020XCTF_逆向

flag{8xOi6R2k8xOk6R2i7xOm}

aRm

arm架构。

照例通过字符串回溯找到主函数。

【wp】2020XCTF_逆向

【wp】2020XCTF_逆向

v1是key,v9是输入的flag,对输入的限制就是长度为42且头尾是“flag{”和“}”。

动态调一下可以发现,sub_27770()这个函数实际上是把unk_723A0数组里的42个数据复制到v8里。

./qemu-arm -L ./ -g 12345 ./aRm

(Debugger选Remote GDB debugger,把端口号填上就好,其余配置具体见RE套路 - 关于使用IDA 7.0前端进行的动态调试 | c10udlnk_Log中调试elf部分。

现在我们未知的数就剩v5和v6了,v5要看sub_1714C()的输出,v6这里相当于是42条42元一次方程组(输入未知的情况下)。

而sub_105B4()是输出42个结果,于是可以知道只要输出了output.txt里的42个数就是正确的flag了。

由于前面有一个sub_169AC(key),这边又是一个无参的sub_1714C()+1,于是猜测是srand(seed)和rand()。

为了证明猜测,多次运行程序输入同一个key和相同/不同的flag,发现每一次的v5是一样的,结合rand()的伪随机性,确定这就是随机函数。

由于key只有一字节(0~255),干脆直接爆破。把output.txt的数据读入,用sympy库解方程,只要第一个解x0等于ord('f')^v8[0]=102^0xA0=198,就说明这个key有极大可能性是正确的key。

当然,在此之前,我们得先知道每一次的v5(即方程的系数)是多少。

于是hook函数,在v5生成之后复用程序原来就有的print函数及格式符,把每次生成的v5都打印出来。

还记得有个函数是可以输出八位十六进制数的吧,就是那个sub_105B4(),我们可以用这里面的printf,然后把调用这个函数的地方nop掉(目标要明确,现在是为了爆破key,没必要管程序的正常性hahah)。

本来是想自己堆个调用printf出来的,不知道为什么keypatch对LDR R0, =a08x解释不了,于是只好绕个小路了。

【wp】2020XCTF_逆向

转到汇编窗口,记一下这里的loc,等会要跳过来的。

【wp】2020XCTF_逆向

看回去原来二重循环里出v5那个地方

【wp】2020XCTF_逆向

这几条语句的意思就是f5里面的那行v5 = (unsigned __int8)(sub_1714C() + 1);,我们从再下一行开始改。

注意可以改的范围在蓝框这里,这是我们不需要的v6[j] += (unsigned __int8)v9[k] * v5;,在这个范围里可以尽情修改,剩下的nop掉。

【wp】2020XCTF_逆向

用keypatch直接输入汇编,patch后面的语句为

【wp】2020XCTF_逆向

(其实就是改了一行B loc_105D4,剩下的直接Fill with NOPs就好)

接下来去往loc_105D4,改造一下。

我们知道,现在R3寄存器里实际上存的是v5的值,我们调用printf直接输出R3的值就能达成目标。

在ARM汇编里,函数传参用R0、R1……所以我们这里给R1一个R3的值就好。

【wp】2020XCTF_逆向

这里本来就是MOV R1, R3不用改,所以直接把前面nop掉。

因为v5那里是取(unsigned __int8),所以把这里改一下,把"%08x"改成"%02x",就是出来的v5。

【wp】2020XCTF_逆向

别忘了后面还要跳回去,找到地址:

【wp】2020XCTF_逆向

patch:

【wp】2020XCTF_逆向

记得把调用sub_105B4()的地方也nop掉。

【wp】2020XCTF_逆向

最后把patch的字节保存一下。

【wp】2020XCTF_逆向

运行测试一下,有:

【wp】2020XCTF_逆向

ok,hook成功,开始爆破。

用pexpect进行批量的自动化交互见:【wp】2020ChaMd5圣诞题 | c10udlnk_Log

多亏了周五做的那个题,才有了这个题的爆破脚本(Doge。

import pexpect
from sympy import *

data=[]
with open('output.txt','r') as f:
    tmp=f.read().split('\r\n')
    data=[int(x,16) for x in tmp]
src=[0xA0, 0xE4, 0xBA, 0xFB, 0x10, 0xDD, 0xAC, 0x65, 0x8D, 0x0B, 0x57, 0x1A, 0xE4, 0x28, 0x96, 0xB3, 0x0C, 0x79, 0x4D, 0x80, 0x90, 0x99, 0x58, 0xFE, 0x50, 0xD3, 0xF9, 0x3C, 0x0F, 0xC1, 0xE3, 0xA6, 0x39, 0xC3, 0x28, 0x75, 0xF8, 0xC9, 0xC8, 0xCD, 0x78, 0x26]
flag='flag{000000000000000000000000000000000000}'

var=[]
for num in range(42):
    exec("x"+str(num)+"=Symbol('x'+str(num))")
    var.append("x"+str(num)) #创建42个变量x0~x41
for i in range(256):
    r=pexpect.spawn('./qemu-arm -L ./ ./aRm_getRand')
    r.sendline(str(i))
    r.sendline(flag)
    r.readline()
    r.readline()
    rand=[]
    for j in range(42*42):
        s=r.readline()
        rand.append(int(str(s)[2:-5],16))
    r.wait()
    exper=[]
    for j in range(42):
        anEx=""
        for k in range(42):
            anEx+=str(rand[j*42+k])+"*"+var[k]+"+"
        anEx=anEx[:-1]+"-"+str(data[j])
        exper.append(anEx)
    res=solve(exper,var)
    print(str(i)+": ")
    print(res.values())

爆破得到:

【wp】2020XCTF_逆向

可知key是82,而v9在xor以后的数组也爆出来了,简单xor得flag:

arr=[0xA0, 0xE4, 0xBA, 0xFB, 0x10, 0xDD, 0xAC, 0x65, 0x8D, 0x0B, 0x57, 0x1A, 0xE4, 0x28, 0x96, 0xB3, 0x0C, 0x79, 0x4D, 0x80, 0x90, 0x99, 0x58, 0xFE, 0x50, 0xD3, 0xF9, 0x3C, 0x0F, 0xC1, 0xE3, 0xA6, 0x39, 0xC3, 0x28, 0x75, 0xF8, 0xC9, 0xC8, 0xCD, 0x78, 0x26]
x=[198, 136, 219, 156, 107, 228, 152, 7, 239, 63, 97, 127, 134, 5, 247, 131, 109, 75, 96, 180, 241, 173, 57, 211, 49, 224, 157, 9, 34, 243, 129, 199, 1, 244, 31, 17, 157, 171, 252, 249, 64, 91]
flag=""
for i in range(42):
    flag+=chr(x[i]^arr[i])
print(flag)

【wp】2020XCTF_逆向

flag{94bb46eb-a0a2-4a4a-a3d5-2ba877deb448}

pe

arm架构,没环境调不动,只能硬看了XD。这题有好多奇怪的函数,而且通过伪代码跟的话就能看到函数套函数套函数……所以基本靠猜出来的(

继续通过字符串回溯找主函数。

【wp】2020XCTF_逆向

【wp】2020XCTF_逆向

根据参数猜测,sub_1400023C8()是strcmp()的作用,我们需要让v9="KIMLXDWRZXTHXTHQTXTXHZWC"。

再往上走,sub_1400015B0这个函数调用了v9,于是跟进去看功能。

【wp】2020XCTF_逆向

感觉是某种加密,以相邻的两字符为一组,对这两个字符做相同的操作,再做后续处理。

跟进sub_1400012B8()里看,可以看到大概是一个搜索的过程

【wp】2020XCTF_逆向

如果不等于-1就说明在表中找到了这个元素,然后返回一个索引(?

再往下看好像就看不太懂了,然后就是玄学的猜猜猜= =

回去看string可以看到一个这个,猜测是密钥表之类的?

【wp】2020XCTF_逆向

往上回溯也看不到什么线索,不过可以发现这25个数字刚好没有相同的。

现在总结一下这个古典加密算法的特点,大概是两个为一组处理+已定义的密钥表(即不是通过输入生成的)5*5+处理时用到索引。

很久很久以前想写某对cp的AU同人时想把ctf元素混进去,就看了很多简单又奇奇怪怪的编码/古典密码(现代密码太学术了XD),没想到现在有用武之地了(手动狗头。

安利一个编码/古典密码的集合:CTF中那些脑洞大开的编码和加密 - jack_Meng - 博客园

然后翻到了一个符合这个特点的密码,Playfair Cipher:

【wp】2020XCTF_逆向

不同的是密码表是直接给出的,不过加密流程再对回ida里的反编译感觉挺像的,于是果断试试。

按照Playfair Cipher的加解密流程写出脚本:

def getIndex(c):
    for i in range(len(key)):
        if key[i].find(c)!=-1:
            return i,key[i].find(c)
letter_list="ABCDEFGHJKLMNOPQRSTUVWXYZ"
key=["CREIH","TQGNU","AOVXL","DZKYM","PBWFS"]
cipher="KIMLXDWRZXTHXTHQTXTXHZWC"
text=""
for i in range(0,len(cipher),2):
    j=i+1
    x1,y1=getIndex(cipher[i])
    x2,y2=getIndex(cipher[j])
    if x1==x2:
        text+=key[x1][(y1+1)%5]+key[x2][(y2+1)%5]
    elif y1==y2:
        text+=key[(x1+1)%5][y1]+key[(x2+1)%5][y2]
    else:
        text+=key[x1][y2]+key[x2][y1]
print(text)

走一遍脚本解密可以得到:

【wp】2020XCTF_逆向

YES MAYBE YOU CAN RUN AN ARM PE

No, I can't

看起来能读的通,成功get flag。

flag{YESMAYBEYOUCANRUNANARMPE}

crash

先去肝ddl回来再补,反正就是个查md5的题(

发表评论

评论已关闭。

相关文章