什么是STL?
STL(Standard Template Library)是C++库为我们实现好的一系列数据结构和方法，是一些常用结构的标准实现。他们的数据结构都被定义好了，在编程的时候可以直接调用。
那么对于逆向来说，我们主要是要识别出对应的STL容器类以及对他们操作的函数功能（常见的类方法），识别相关容器的内存结构能起到很大作用。简单记录一下，其实这个没有Go这种逆向难。
本题中STL容器的内存结构和分析
参考https://www.52pojie.cn/thread-1720719-1-1.html
参考https://zhuanlan.zhihu.com/p/604288453，这篇文章写了一个LLVM PASS来分析底层结构注意，以下的结构并不是“严格”遵循的，比如本题中红黑树就有细小的差别，应该与版本等有关，重要的是识别出在干嘛然后方便我们猜测程序的功能。
String
C++的String结构包含一个指向内容的指针，一个长度和一个联合体：
1 | class.std::__cxx11::basic_string { |
如果字符串长度较小（小于8），会直接将字符串的内容和String结构放在一起，第一个字段就指向localbuf，也就是说对于局部变量字符串就会放在栈上，我们能看到。如果字符串长，字符串内容就会分配在堆上，那么这个字段就会存储堆上分配的空间大小。
对于String，结合本题来看，动调确定主流程中的输入模块之后分析参数可以看出是String，这时候可以先输入8个或以下字符跟进看一下，在栈上就大概率是了。
Vector
Vector容器看着功能多，实际上底层就三个指针，第一个存放数据开始，第二个存放数据结束，第三个存放当前vector容量的结束位置。
1 | class.std::vector<string> { |
内存中的结构就是三个相连的指针。如果vector是一直随输入变化增长的没有事先申请额外的空间（一般可能都是这样），那么finish字段的内容和end_of_storage将会指向同一个地址。如果内存中有一个开始地址，连续两个结束地址而且跟进看发现是数据，那么大概率是vector了。
rb_tree
红黑树，我并不了解红黑树相关的算法思想，这里先简单介绍一下：
红黑树就是一个自平衡的搜索二叉树，和一般二叉树不同的是，它为每个节点标注夜色（红/黑），并遵循一定的规则。根节点黑色开始，叶子结点（NIL）黑色结束。红色节点的子节点必须都是黑色，且任意节点到每个叶子结点的所有路径都包含相同数量的黑色节点。总之就是通过某些人为的染色规定，保证二叉树的相对平衡，令其在最坏情况下有O(logn)的复杂度。
我们并不关心它的算法实现，STL为我们实现好了，我们关心的是他的内存视图。他的内存视图有两种，header和node。header是一个代表一整颗树的变量，node是真正的结点。
header
对于一个header，它应该包含以下信息（本题中一个header占6个机器字长）
1 | class.std::map<string,string> { |
简单说，第一个字段不重要（也没懂是干嘛的），后面包含color，parent,left,right的三个指针，以及一个节点总数。对于rbtree，color只取0和1，0黑1红。
header的这三个指针，在树为空的时候parent为0，left和right指向自己，树初始化后，paretn指向根节点，left和right则指向这个树最左边和最右边的结点。同时header和真正的根节点root他们的parent互相是对方。
node
一个节点存储的信息就好说了，只有color（0和1，int32），parent，left，right三个指针，以及一个存储真正数据的element data域。
总之，红黑树的关键就是那个color，识别到有这种0和1的color域就可能是红黑树。
Others
STL容器还有很多，deque，基于红黑树的map等等，这里不再细说，了解这三种足够我们做这道题了。
题目分析
拿到手IDA打开，主函数很清晰，输入正确会显示flag
1 | v18 = sub_4E0940; |
这里用了STL容器但是把符号全扣了，我们先来找一下输入函数，动调单步，输入函数看不懂太复杂，确定输入是这个a1，而且输入8个字符放在栈上，结构也符合，a1应该是一个String类来接受我们的输入。确定是String类后根据String的结构还原一下结构体，也就找到了getlenth的函数，可以看到我们要输入36个字符。
中间的ssm和m128i这种代表用了simd指令集，用到了那个128位的xmm寄存器，操作这个寄存器可以按64,32位去放数据。允许两个机器字长。
加密逻辑就是主函数的循环，一次跑4个字节，跑9轮到长度就退出。还原结构体后可以看到中间是按i去从String内容里按下标取出字符，然后调用一个位运算操作：
1 | char *__fastcall String_get_idx(String_class *a1, __int64 a2) |
最关键的，就是这个左移右移处理过后的字符传入的这个函数4b7d90，我们可以看到最后是将4个字节拼凑成一个然后做了一些操作，那么这个4b7d90的加密就很重要。
关键函数分析
开始入手的时候试图分析这个函数，但是跟进发现一拖史，调用套调用最后看不懂，而且相当多功能简单（直接返回，返回arg+8）的函数没有复用都是新的符号：
1 | __int64 __fastcall sub_4B7D90(struct my_rbtree_header *rb_tree, char *enc_byte) |
看不懂在干嘛，看STL相关结构的同时决定动调。
我们能看到这个函数接收了两个参数，这第一个参数就很重要。回到主函数的开头，这个变量参与了这样一个函数（当然名字是做出来之后才有的）：
1 | tree_create(&rb_tree, ssm00.m128i_i64, (__int64)&v31, (__int64)&v32); |
这个函数的内容我们也看不懂，但是不重要，它接受的第二个参数很有意思，在前面的初始化过程中，它存储的是一段神秘数据的指针。检查的时候这段数据是从0-FF依次对应另一个字节，
1 | memcpy(ascii_db0, ascii_db, sizeof(ascii_db0)); |
这个东西程序一拿到手就修了，但是不知道在哪用的。但是很重要的是，我们的输入函数还在靠后的位置，前面初始化的这些东西都和输入无关，代表他们都是死的，动调到输入之前看看初始化的都是什么，如果是一些加密用的东西直接dump出来就不用分析函数了。抱着这个心态，发现了红黑树：
动调之后函数一过：
1 | Stack[00006BA8]:000000000071FA20 dq offset unk_A31E80 |
6个指针，跟进去看结构，
1 | debug030:0000000000B54690 dword_B54690 dd 1 ; DATA XREF: Stack[00006BA8]:000000000071FA30↑o |
parent指向header，左右指针，红黑树是八九不离十了。这时候我们就可以猜测这个函数是建立了一棵树，结合我们前面看到的那个下标-字符数组，我们就可以大胆猜测是按照那个数组建立的，加密函数是按照某种逻辑（对应下标）从这个树上搜一个值出来。
黑盒测试，前面经过动调已经知道输入特定字符加密过后是不变的了，这时候我们去看那个数组的0x61看是不是a加密后的3a，发现不是。动调之后再猜测，这棵树是一个S盒，我们是把加密后的那个字符输入然后返回一个代换字符，确定不了，把这个数组dump出来转成S盒还原一下加密逻辑，结果和动调获得的一致，加密逻辑就分析出来了：按照索引建立一个红黑树，本质上是一个S盒代换
最后就是将4个字节拼起来放在一个vector里（动调看内存确定的）。前面栈上那9个初始化的32位变量就是被放进了vector，最后的比较也是传两个vector，那么最后肯定是我们的输入加密后和那个初始化的比较了
1 | //vector |
exp
逆向s盒不会写，按字节也就256个，按字节爆破和结果比对出flag就行。
1 | # a(0x61)-0x3a b-0x4e c-0xa7 d-0x88 连在一起 |
1 | PS D:\学校相关文件\逆向工程\stl> .\stl.exe |
总结
函数还是太简单了，只要分析一个STL的数据结构就行，没有控制流的难度很多功能太好猜，扣符号真的恶心。感觉可以改改之后放l3h招新（纯粹数据结构还原）。