c++-STL容器逆向学习
前言
在比赛中遇到了利用stl容器嵌套的ctf题目，能力有限做不出来，只好赛后跟着大佬的wp复现，顺便学习相关知识
string
主要结构是由一个指针ptr和字符串长度string_length构成。当字符串长度小于0x10时，会在栈上分配一个长度为0x10的缓冲区用于存放字符串，且此时指针指向该缓冲区；当字符串长度大于等于0x10时，会将字符串存放到堆空间中
测试代码
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
// 15
string s1 = "aaaaaaaaaaaaaaa";
// 16
string s2 = "bbbbbbbbbbbbbbbb";
// 17
string s3 = "ccccccccccccccccc";
// 5
string s4 = "ddddd";
return 0;
}
内存布局，可以发现字符串长度小于0x10时是储存在栈上的，且始终会分配16个字节给字符串，大于等于0x10时会将字符串存在堆上。
deque
deque主要由三部分构成。第一部分是描述map的指针及map大小，第二部分是指向开头的迭代器，第三部分是指向结尾的迭代器。
首先，map用于存放指针，指向真正存放数据的空间的首地址，实现整体连续的效果。如果需要增加储存空间，便会申请一段新的内存，同时在map数组的开头或者结尾添加对应的指针。
此外，因为数据实际上存放在了多段不连续的空间，所以迭代器必须满足以下条件：
- 迭代器在遍历 deque 容器时，必须能够确认各个连续空间在 map 数组中的位置；
- 迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中。
所以，迭代器包含了4个指针，用于实现上述功能
- cur：指向当前正在遍历的元素；
- first：指向当前连续空间的首地址；
- last：指向当前连续空间的末尾地址；
- node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。
测试代码
#include <deque>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//创建10个值为5的deque
std::deque<int> d0(10,5);
std::deque<string> d1(10,"aaaaaa");
// cout << s1 << " " << s2 << " " << s3 << " " << endl;
for (auto i = d0.begin(); i < d0.end(); i++) {
cout << *i << " ";
}
cout<<endl;
for (auto i = d1.begin(); i < d1.end(); i++) {
cout << *i << " ";
}
return 0;
}
rb_tree
一般节点由颜色，parent，left，right和所存放的数据构成，其中color红色为0，黑色为1。header的末尾会有node_count来计算当前树的节点个数。
STL中的set，map都是由红黑树实现，下面以map为例进行测试
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int, string> mapTemp;
mapTemp.insert({ 5,"55555" });
mapTemp.insert({ 3, "333333"});
mapTemp.insert({ 4, "44444" });
map<int, string>::iterator it;
for (it = mapTemp.begin(); it != mapTemp.end(); it++)
{
printf("%d,%s\n", (*it).first, (*it).second.c_str());
}
return 0;
}
刚开始，树没有节点，故header的parent为0，left和right都为他本身
插入第一个节点后（即5，“55555”），parent指向根节点，left和right分别指向最左和最右的节点（此时仍为根节点）
根节点如下，且left和right都为0，数据(5,”55555”)直接存放在最后
再插入3，“333333”后，发现header和根节点的left都指向新的节点
插入（4，“4444”）后发现根节点变为了（4，“4444”），再此不做详细叙述
hashtable
哈希表是unordered_map和unordered_set的底层实现。会申请一段空间用来储存链表的头指针，储存数据的链表称之为桶。每个桶都有对应的编号，一般最开始bucket_count=13，之后如果负载因子过大，会增加桶的数量，重新进行哈希。
测试代码如下
#include<string>
#include<iostream>
#include<unordered_map>
using namespace std;
int main()
{
unordered_map<int, string> dict; // 声明unordered_map对象
dict.insert({ 30, "44444" });
dict.insert({ 13, "666" });
dict.insert({ 14, "11" });
dict.insert({ 15,"55555" });
dict.insert({ 16, "333333"});
dict.insert({ 17, "22"});
dict.insert({ 18, "7777777"});
// dict.insert({ 19, "88888888"});
// dict.insert({ 20, "999999999"});
// dict.insert({ 21, "aaa"});
// dict.insert({ 22, "bbb"});
// dict.insert({ 23, "ccc"});
// dict.insert({ 24, "ddd"});
// cout<<dict[4]<<endl;
return 0;
}
如下图，0x0D是当前桶的数量，7是当前储存的节点数量。field_1始终指向上一个插入的键值对的地址
buckets如下
当我们查看第一个桶的内容时，你以为存放的是(14，“11”)，但是实际上存放的是(13，“666”)
此外，当哈希冲突时，会在桶中利用头插法插入节点，如(30, "44444”)和(17, "22”)，都位于编号为4的桶内
cppmaster
动态调试找到输入函数，查看第二个参数如下，可以看出这是一个deque，跟进qword_55BD1608BF30，即存放的第一个元素，可以发现其中存放了两个红黑树，继续跟进可以看到数的节点存放的是一个哈希表，哈希表中有两个桶存放着deque数组……
可以推测出，我们需要输入下标，最后得到的取值要与"8850a16d-e427-446e-b4df-5f45376e20e4”相等。通过对输入函数的交叉引用可以看到，共需要我们输入28次，也就是共有28层嵌套，可以手动搜索字符串从下往上提取数据，注意搜索时按照大端序搜索十六进制字符，可以找到
之后再搜索此地址，逐层往上排查即可。
不过手动搜索的方式未免有点丢人，费时费力，寻找代替方法。看到有大佬用idapython，照搬却跑不起来，尝试选择用frida代替，脚本如下
import frida
device = frida.get_local_device()
def on_message(message, data):
global bruteforce_index
global bruteforce_success
# print(bruteforce_index)
# print(message['payload'])
# print("[%s] => %s" % (message, data))
# print(message['payload'][bruteforce_index],m[bruteforce_index])
# if((message['payload'][bruteforce_index]) == m[bruteforce_index]):
# bruteforce_success = True
print("[%s] => %s" % (message, data))
handle = open("printf.js", "r",encoding='utf-8')
script_code = handle.read()
handle.close()
moduleName = 'cppmaster'
pid = device.spawn ( './'+moduleName,stdio='pipe')
print("pid, ", pid)
session = frida.attach(pid)
script = session.create_script(script_code)
script.on('message', on_message)
script.load()
device.resume(pid)
device.input(pid,b'1111')
input()
// Find base address of current imported jvm.dll by main process fledge.exe
var moduleName = 'cppmaster'
var baseAddr = Module.findBaseAddress(moduleName);
console.log(moduleName + ' baseAddr: ' + baseAddr);
var size_table = {
'rb_tree' : 48,
'deque' : 80,
'string' : 32,
'hashtable' : 16,
}
var types_ordered = ["deque","rb_tree","hashtable","deque","rb_tree","rb_tree","hashtable",
"hashtable","rb_tree","rb_tree","hashtable","rb_tree","rb_tree","deque",
"deque","rb_tree","rb_tree","rb_tree","rb_tree","rb_tree","rb_tree",
"rb_tree","rb_tree","rb_tree","rb_tree","rb_tree","deque","deque","string"];
var monitorFuncAddr = resolveAddress('0x1e470'); // Here we use the function address as seen in our disassembler
function resolveAddress(addr) {
var idaBase = ptr('0x0'); // Enter the base address of jvm.dll as seen in your favorite disassembler (here IDA)
var offset = ptr(addr).sub(idaBase); // Calculate offset in memory from base address in IDA database
var result = baseAddr.add(offset); // Add current memory base address to offset of function to monitor
console.log('[+] New addr=' + result); // Write location of function in memory to console
console.log(Memory.readU64(ptr(parseInt(result))));
console.log(Memory.readByteArray(ptr(parseInt(result)+1),64));
return result;
}
function dump_rbtree_node(addr) {
return {
'color' : Memory.readU64(ptr(addr)),
'parent' : Memory.readU64(ptr(parseInt(addr) + 8)),
'left' : Memory.readU64(ptr(parseInt(addr) + 16)),
'right' : Memory.readU64(ptr(parseInt(addr) + 24)),
}
}
function dump_rbtree_map(addr){
var key = Memory.readU64(ptr(addr));
var node_addr = parseInt(addr) + 8;
var node_num = Memory.readU64(ptr(parseInt(addr)+40));
var result = {};
function visit(node){
var info = dump_rbtree_node(node);
var value_key = Memory.readU64(ptr(parseInt(node)+32));
var data_addr = parseInt(node) + 40;
result[value_key] = data_addr;
if(info["left"]!=0){
visit(info["left"]);
}
if(info["right"]!=0){
visit(info["right"]);
}
}
var d = dump_rbtree_node(node_addr);
visit(d['parent']);
return result;
}
function dump_deque_iterator(addr){
var a = {
'cur' : Memory.readU64(ptr(addr)),
'first' : Memory.readU64(ptr(parseInt(addr) + 8)),
'last' : Memory.readU64(ptr(parseInt(addr) + 16)),
'map' : Memory.readU64(ptr(parseInt(addr) + 24))
};
return a;
}
function dump_deque(addr,delta){
var deque_map = Memory.readU64(ptr(addr));
var map_size = Memory.readU64(ptr(parseInt(addr) + 8));
if(map_size!=8){
console.log("[+] map_size Wrong!");
}
// console.log(addr);
var start = dump_deque_iterator(parseInt(addr) + 16);
var finish = dump_deque_iterator(parseInt(addr) + 16 + 32);
var ptr1 = start['cur'];
var index = 0;
var result = {};
while(ptr1!=finish['cur']){
result[index] = ptr1;
index += 1;
ptr1 += delta;
}
return result;
}
function dump_string(addr){
var data = Memory.readU64(ptr(addr));
var length = Memory.readU64(ptr(parseInt(addr) + 8));
return Memory.readCString(ptr(data),length);
}
function dump_hashtable_map(addr){
var addrs = [];
var hash_table = Memory.readU64(ptr(addr));
var table_num = Memory.readU64(ptr(parseInt(addr) + 8));
for(var i=0;i<table_num;i++){
var link_list = Memory.readU64(ptr(parseInt(hash_table) + 8*i));
if(link_list == 0){
continue;
}
var ptr1 = Memory.readU64(ptr(link_list));
while(ptr1 != 0){
addrs.push(ptr1);
ptr1 = Memory.readU64(ptr(ptr1));
}
}
var result = {};
for(var i=0;i<addrs.length;i++){
result[Memory.readU64(ptr(parseInt(addrs[i])+8))] = parseInt(addrs[i]) + 16;
}
return result;
}
function dump_dfs(depth,addr){
var stl_type = types_ordered[depth];
var tmp = {};
if(stl_type == "rb_tree"){
tmp = dump_rbtree_map(addr);
}
else if(stl_type == "hashtable"){
tmp = dump_hashtable_map(addr);
}
else if(stl_type == "deque"){
var next_type = types_ordered[depth + 1]
tmp = dump_deque(addr, size_table[next_type]);
}
else if(stl_type == "string"){
var a = dump_string(addr);
// console.log(a);
return a;
}
var node = {};
for (var i in tmp)
{
var v = tmp[i];
node[i] = dump_dfs(depth + 1, v);
}
// console.log(node);
return node
}
Interceptor.attach(monitorFuncAddr, { // Intercept calls to our SetAesDecrypt function
// When function is called, print out its parameters
/*
其他API 用法
https://frida.re/docs/javascript-api/
*/
onEnter: function (args) {
console.log('[+] Called monitorFuncAddr' + monitorFuncAddr);
console.log('[+] Argv1: ' + args[1]); // a1
var result = dump_dfs(0, args[1]);
console.log("result:");
var str = "";
str = JSON.stringify(result);
console.log(str);
}
});
运行py结果如下
最后在得到的表中dfs即可
参考文章：
本文部分文字图片摘自下列文章，侵删
https://bbs.pediy.com/thread-275133.htm#msg_header_h1_3
https://nese.team/posts/n1ctf/
http://c.biancheng.net/view/6908.html
http://c.biancheng.net/view/7235.html
https://blog.csdn.net/tjcwt2011/article/details/127729271
[复制链接]
发表于 2022-11-30 14:08
|
发表于 2022-11-30 18:20
