2020网鼎杯朱雀组 Tree WP 及其思考

Tree

IDA打开，先做信息收集：无壳，有符号表，函数窗口发现了未被调用过的可疑函数outtree

string一下发现了疑似密文的一串字符串

找到main函数
main函数

checkflag规定输入的数据在‘0’~‘e’之间，并将其作为16进制数转换为4位二进制。
并且给出了flag的模板，可以知道flag长度为42

checkflag处理完之后将_root内存放的数据作为参数传给__Z5parseP4node
__Z5parseP4node接收一个名为node*的参数，猜想可能是一棵树的根节点。
动调可以发现root内的存放的数据为0x406530

函数内部逻辑很清晰，将上面函数得到的二进制串glockflag进行类似查表的操作，控制流程实际上有意义的只有‘1’和‘0’两种路径。
如果v3中的数据满足（*v3 > 96 && *v3 <= 122），就将该数据赋值给result，然后将v3还原成循环开始之前的值a1。显然，结合题目名字，这是一种二叉树查表的操作。

至于是什么二叉树，就需要将它还原出来。
好在程序预留给我们了一个现成的函数outtree，该函数和__Z5parseP4node一样需要传入一个node*参数。
简单的前序遍历二叉树代码。什么是二叉树的前序遍历这里有一张图可以很直观地表现出来。

知道了程序的逻辑和解题思路，只需要在程序运行时在适当的位置修改eip到函数内部，必要时还需要手动修改函数的参数和其它寄存器。
这里我选择的修改点是在call __Z5parseP4node的前一行代码处，执行完mov [esp], eax

跟进函数，可以发现函数的参数的并不是_root，查看汇编发现，ebp多了4个字节

把ebp从0x0061FE4C修改为0x0061FE48，函数即可正常执行。结果如下：

画出二叉树，直接写出解密脚本即可。

table={
        'y':'0000','b':'00010','q':'00011','g':'0010','f':'0011','j':'010',
       'w':'01100','p':'01101','x':'011101','d':'0111010','i':'01111011',
       'k':'01111','s':'100','z':'1010','n':'1011','c':'11000','t':'110010',
     'e':'110011','h':'1101','o':'11100','l':'1110100','u':'11101010',
       'r':'111010110','a':'111010111','m':'111011','v':'1111'
       }

ciphertext='zvzjyvosgnzkbjjjypjbjdvmsjjyvsjx'
bin_result=''
for each in ciphertext:
	bin_result+=table[each]
i=0
while(i<len(bin_result)):
    temp=bin_result[i:i+4] #每4位二进制一组
    i+=4
    result=str(hex(int(temp,2)))
    result=result[2:]   #'0xa'-->'a'
    print(result,end='')
    

得出afa41fc8574f12481a849d7f7120f89c，按照题目给出的格式写出flag即可。

flag{afa41fc8-574f-1248-1a84-9d7f7120f89c}

PS：

如果这道题没有给出outtree函数？

首先可以考虑对密文进行逐字节**，密文中每个英文字母对应着一个二进制数，那就把加密过程复现一遍，但并不意味着每4位2进制就对应了一位flag，因为尽管checkflag函数把输入的数变成了4位二进制，但是__Z5parseP4node函数在解析二进制数据查表的时候，并不是按照固定的4位二进制对应一个字符的规则来查表的，具体多少位二进对应flag中的一个字符是由二叉树本身的结构决定的。（这里有点绕，师傅们可以自己用上面的二叉树举个例子。）

第一种思路：使用idapython复现二叉树查表算法+**

root=0x00406530#根结点地址
secret='zvzjyvosgnzkbjjjypjbjdvmsjjyvsjx'

def encrypt(way):
    a=root
    result=''
    bin_s='{:010b}'.format(way) #这里设成10位二进制高位补0，起初设成8位导致a和r没有出结果
    for each in bin_s:     #模拟parse函数
        if(each=='1'):
            a=idc.Dword(a+12)
            result+='0'
        elif(each=='0'):
            a=idc.Dword(a+16)
            result+='1'
        if(idc.Dword(a)>96 and idc.Dword(a) <=122):
            return result+':'+chr(idc.Dword(a))
    return 0

L=[]
for each in range(1024):    #开爆，奥里给爆就完了
    if(encrypt(each)!=0):
        L.append(encrypt(each))
        
Table=list(set(L))
print(Table)

结果：

[‘1111:v’, ‘111011:m’, ‘011100:x’, ‘11101010:u’, ‘00010:b’, ‘11100:o’, ‘01101:p’, ‘110011:e’, ‘0000:y’, ‘1110100:l’, ‘0111010:d’, ‘110010:t’, ‘01111:k’, ‘111010111:a’, ‘1101:h’, ‘1010:z’, ‘111010110:r’, ‘0111011:i’, ‘0011:f’, ‘1011:n’, ‘01100:w’, ‘100:s’, ‘010:j’, ‘00011:q’, ‘0010:g’, ‘11000:c’]

得出
‘zvzjyvosgnzkbjjjypjbjdvmsjjyvsjx’ 对应的二进制字符串为

‘10101111101001000001111111001000010101110100111100010010010010000001101010000100100111010111111101110001001000001111100010011100’

后续方法同上，直接每4位二进制输出对应的hex可以了。

第二种思路：

个人认为这种办法比较麻烦，从根节点0x00406530开始，自己手写一个outtree把二叉树输出出来，得出二叉树后，后续步骤同上。

PPS

原来的博客因为是自己搭的，被透穿了，以后就准备在这里写东西了。
芜湖

明日计划：复盘白虎组RE题目