首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 看雪社区
  2. 软件逆向
    3. 发新帖
[原创]PBCTF21 RE BinaryTree Beaengine+dijkstra解法
2021-10-15 21:51 4954

[原创]PBCTF21 RE BinaryTree Beaengine+dijkstra解法

wx_御史神风 活跃值
2021-10-15 21:51
4954

思路

代码是动态解密的，简单的xor，解密一块执行一块。每一块结尾会设置rbx，rbx决定下一块被解密的代码。

 

实际上每一块代码相当于一个节点，里面有一个根据输入的jz，决定下一个rbx以及一个cost，所以相当于一颗二叉树。

 

每次经过一个节点都会累加cost。

 

根节点对应的代码块会判断cost是否小于等于某个值，然后输出成功信息。

 

如果只有唯一解那么显然是找最短路。

 

解题思路是beaengine解析代码生成图，用dijkstra算法求最短路并输出路径。
事实上只有一条最短路，刚刚等于那个值。

beaengine提取图

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#include <iostream>
#include <fstream>
#include <windows.h>
#include <queue>
#include <set>
#define BEA_ENGINE_STATIC
#include "BeaEngine.h"
#pragma comment(lib,"legacy_stdio_definitions.lib")
#pragma comment(lib, "BeaEngine.lib")
 
using namespace std;
 
typedef struct Block {
    int index;
    char buf[32];
};
 
int path[25503][4] = { 0, }; // 0(path/rbx,cost) 1(path/rbx,cost)
 
queue<pair<int, Block*>> rbxs; // rbx(xor offset), lastBlock
int sa = 0x176;
BYTE* firstBlock;
int blockNum = 0;
set<int> dised;
Block xorBlock = {
    0,
    0x48, 0xc7, 0xc0, 0x01, 0x00, 0x00, 0x00, 0x48,
    0xc7, 0xc7, 0x01, 0x00, 0x00, 0x00, 0x48, 0xc7,
    0xc2, 0x05, 0x00, 0x00, 0x00, 0x49, 0x81, 0xf9,
    0xda, 0x49, 0x00, 0x00, 0x7f, 0x07, 0x4c, 0x89
};
 
Block* Xor(char* firstBlock, UInt64 offset, Block &oldBlock)
{
    Block* pB = new Block();
    pB->index = offset >> 5;
    blockNum++;
    char* xorBuf = firstBlock + offset;
    for (int i = 0; i < 32; i++) {
        pB->buf[i] = xorBuf[i] ^ oldBlock.buf[i];
    }
    return pB;
}
 
void Jmp(DISASM& infos)
{
    UINT64 nextVA = infos.Instruction.AddrValue;
    UINT64 curVA = infos.VirtualAddr;
 
    // jmp
    infos.EIP += nextVA - curVA;
    infos.VirtualAddr = nextVA;
}
 
void DisasmCode(char* stBuf, UINT64 stVA, Block* curBlock, int rbx, int branch)
{
    DISASM infos;
    size_t len;
 
    // init
    memset(&infos, 0, sizeof(DISASM));
    infos.EIP = (UINT64)stBuf;
    infos.VirtualAddr = (UINT64)stVA;
 
    while (infos.Error == 0) {
        // limit
        UInt64 offset = infos.EIP - (UINT64)curBlock->buf;
        if (offset < 0 || offset >= 32) {
            break;
        }
        if (infos.VirtualAddr == 0x400080) {// xor
            rbxs.push(make_pair(rbx, curBlock));
            break;
        }
 
 
        //disasm
        len = Disasm(&infos);
        cout << hex << infos.VirtualAddr << " " << infos.CompleteInstr << endl;
 
        // jmp
        if (infos.Instruction.BranchType == JmpType) {
            if (infos.Instruction.AddrValue == 0x400080) { // xor
                rbxs.push(make_pair(rbx, curBlock));
                break;
            }
 
            Jmp(infos);
        }
 
        // jmp
        if (infos.Instruction.BranchType) {
            // false branch
            DisasmCode((char*)(infos.EIP + len), infos.VirtualAddr + len, curBlock, rbx, 0);
            // true branch
            branch = 1;
            Jmp(infos);
            continue;
        }
 
        // if modified rbx (0x8)
        if (((infos.Operand1.AccessMode == WRITE) && (infos.Operand1.Registers.gpr & REG3))) {
            rbx += infos.Operand2.Memory.Displacement;
        }
 
        // if add r9 (0x200)
        if ((infos.Operand1.AccessMode == 3) && (infos.Operand1.Registers.gpr & 0x200)) {
            if (branch >= 0) {
                path[curBlock->index][branch * 2] = rbx >> 5;
                path[curBlock->index][branch * 2 + 1] = infos.Instruction.Immediat;
            }
        }
 
        // go on
        infos.EIP += len;
        infos.VirtualAddr += len;
    }
}
 
int main()
{
    ifstream fin;
    ofstream fout;
    BYTE* fileBuf;
    Block* lastBlock;
    Block* pB;
 
    // read file
 
    fin.open("E:\\works\\ctf\\21pbctf\\re_BinaryTree\\main.elf", ios::in | ios::binary);
 
    fin.seekg(0, ios::end);
    size_t fileSize = fin.tellg();
    fin.seekg(0, ios::beg);
    fileBuf = (BYTE*)malloc(fileSize);
    fin.read((char*)fileBuf, fileSize);
 
    cout << "fileSize:" << dec << fileSize << endl;
    fin.close();
 
    // disasm
 
    firstBlock = fileBuf + sa;
 
    cout << "rbx:0" << endl;
    pB = Xor((char*)firstBlock, 0, xorBlock);
    dised.insert(0);
    DisasmCode(pB->buf, 0x4000AD, pB, 0, 0);
    while (!rbxs.empty()) {
        pair<int, Block*> t = rbxs.front();
        rbxs.pop();
 
        lastBlock = t.second;
 
        cout << "num:" << dec << blockNum << endl; // 0x639f * 2
 
        if (dised.insert(t.first).second) {
            // not disasm
            pB = Xor((char*)firstBlock, t.first, *lastBlock);
            // disasm
            DisasmCode(pB->buf, 0x4000AD, pB, 0, -1);
        }
    }
 
    // write file
 
    fout.open("E:\\works\\ctf\\21pbctf\\re_BinaryTree\\main_.elf", ios::out | ios::binary);
    fout.write((char*)fileBuf, fileSize);
    fout.close();
 
    // write file
 
    fout.open("E:\\works\\ctf\\21pbctf\\re_BinaryTree\\path.txt", ios::out);
    for (int i = 0; i < blockNum; i++) {
        fout << path[i][0] << " " << path[i][1] << " " << path[i][2] << " " << path[i][3] << endl;
    }
    fout.close();
 
    fout.open("E:\\works\\ctf\\21pbctf\\re_BinaryTree\\pathDij.txt", ios::out);
    int E = 0;
    for (int i = 0; i < blockNum; i++) {
        if (path[i][1]) {
            fout << i << " " << path[i][0] << " " << path[i][1] << endl;
            fout << i << " " << path[i][2] << " " << path[i][3] << endl;
            E += 2;
        }
        else {
            cout << i << ",";
        }
    }
    cout << endl;
    fout.close();
 
    cout << "N E\n";
    cout << dec << blockNum << " " << E << endl;
    // 25503 50942 0
 
    return 0;
}

dijkstra算法

自己打oi时留下的板子，忘记有没有加优化了，不过这个版本比较方便记录path

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
* 有向+无向，不能用于负权图
*/
 
#pragma warning(disable:4996)
 
#include <stdio.h>
#include <list>
#include <set>
#include <utility>
#include <iostream>
 
using namespace std;
 
typedef pair<int, int> TR;
struct Edge {
    int v;
    int w;
};
 
int roots[] = { 1225,1226,1891,1892,3929,3930,4929,4930,6295,6296,9313,9314,9813,9814,15465,15466,15713,15714,17301,17302,18767,18768,18841,18842,19145,19146,19279,19280,19927,19928,22501,22502 };
int path[50943];
int path1[50943];
 
inline bool min(int a, int b)
{
    if (a != -1 && (a < b || b == -1))
        return true;
    else
        return false;
}
 
int main()
{
    FILE* r = freopen("E:\\works\\ctf\\21pbctf\\re_BinaryTree\\pathDij.txt", "r", stdin);
 
    int i, j, u, v, w;
    Edge edge;
    list<Edge>::iterator it;
    TR tr;
 
    int N, E, start, iMin, nMin;
    int* flag;
    set<TR> ds;
    int* d;
    list<Edge>* es;
 
    scanf("%d %d", &N, &E);
    scanf("%d", &start);
 
    // 初始化
    flag = new int[N];
    d = new int[N];
    for (i = 0; i < N; i++) {
        flag[i] = 0;
        d[i] = -1;
        path[i] = -1;
    }
    ds.insert(make_pair(0, start));
    d[start] = 0;
 
    // 读图
    es = new list<Edge>[N];
    int boo = 1;
    for (i = 0; i < E; i++) {
        scanf("%d %d %d", &u, &v, &w);
        edge.v = v;
        edge.w = w;
        es[u].push_back(edge);
        if (boo) {
            boo = 0;
            path1[u] = v;
        }
        else {
            boo = 1;
        }
    }
 
    // dij
    while (!ds.empty()) {
        // 找最小未完成节点（确保d[iMin] != -1）
        iMin = ds.begin()->second;
        nMin = ds.begin()->first;
        ds.erase(ds.begin());
 
        // 标记完成
        u = iMin;
        flag[u] = 1;
 
        // 依次松弛
        for (it = es[u].begin(); it != es[u].end(); it++) {
            v = it->v;
            w = d[iMin] + it->w;
            if (w == d[v])
                path[v] = u;
            if (min(w, d[v])) {
                d[v] = w;
                // 加入set
                tr = make_pair(w, v);
                if (ds.find(tr) != ds.end()) ds.erase(tr);
                ds.insert(tr);
                path[v] = u;
            }
        }
    }
 
    // 输出结果
    // for (i = 0; i < N; i++)
    //    printf("%d:%d\n", i, d[i]);
    // putchar(10);
 
    cout << "\nans:\n";
    for (i = 0; i < 32; i++) {
        cout << d[roots[i]] << " ";
    }
 
    cout << "\nshortest:\n";
    for (i = 0; i < 32; i++) {
        if (d[roots[i]] <= 0x49DA) {
            cout << roots[i] << ":" << d[roots[i]] << " " << endl;
        }
    }
 
    cout << "\npath\n";
    i = 19279;
    do {
        i = path[i];
        cout << i << " ";
    } while (i);
 
    cout << "\npath\n";
    i = 19279;
    do {
        // path[i] -> i
        if (path1[path[i]] == i)
            cout << 1;
        else
            cout << 0;
        i = path[i];
    } while (i);
 
    i = 0;
    j = 0;
    while (!es[i].empty()) {
        i = es[i].begin()->v;
        j++;
    }
    cout << "\nl:" << j << endl;
 
    // 释放内存
    delete[] flag;
    delete[] es;
 
    return 0;
}

long2bytes

1
2
3
4
5
from Crypto.Util.number import long_to_bytes
 
ans = '01111101001101110110010101100101011001100110001001100001001110000011000000110110001100100110001000110001011001100011011100110001001100000011100101100011001100110011000100110101011000110110000100111000001101110011010001100001001100100011001001100010011000100011000000110011011001010011000000110011011000110011010000110111011001010101111100100001001000010110010101100100011011110110001101011111011001110110111001101001011110010110011001101001011001000110111101101101001011010110011001101100011001010111001101011111011011100110100101011111011010000111010001100001011100000101111101110100011100110110010101110100011100100110111101101000011100110101111101100101011010000111010001011111011001110110111001101001011001000110111001101001011001100010000100100001011110110110011001110100011000110110001001110000'
ans = int(ans, 2)
print(long_to_bytes(ans)[::-1])

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界

最后于 2021-10-15 21:52 被wx_御史神风编辑 ，原因：
收藏
点赞・2
打赏
分享
最新回复 (1)
默NJ
雪    币： 2037
活跃值： (4081)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
默NJ 2021-10-16 07:51
2 楼
0
不知道作者怎么写出来的
游客
登录 | 注册 方可回帖
　回帖　 表情 雪币赚取及消费
高级回复
返回