0.前言
1.STL逆向分析
2.Base64逆向分析
3.AES算法逆向分析
4.注册机实现

  这篇文章的内容详细的分析2018腾讯游戏安全竞赛的赛题，一开始本来只是想跟大家分享一下我是如何逆向分析STL代码的，后面突发奇想要不把整个比赛的题目分析完写出文章，经过三个月的拖延症，终于搞完了资格赛的题目，后面应该还有一篇关于决赛题的分析，所以暂且将这篇命名为（上）。

  前年腾讯游戏安全资格赛有STL，去年也是，今天还是，足以看出腾讯对STL的基础是多么看重（敲黑板，同学们，划重点了！腾讯面试也经常考STL的知识！）。今天就从STL入手，详细的讲讲竞赛中用到的STL相关知识。

  STL是Standard Template Library的简称，中文名标准模板库，从根本上说，STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL现在是C++的一部分，因此不用安装额外的库文件。（这一段摘自百度百科）

  这里只讲如何学习string和vector<T>逆向相关的内容，其他“容器”的分析方法都是一样的。当然不同编译器的STL实现可能不一样，我这边选择vs2010来说明（vs的不同版本实现应该差不太多）。

  首先，弄明白一个类的结构对逆向是非常重要的，所以我们从结构入手去学习。接着，我们看看常用的类函数被编译器编译的结果是怎么样的（对比有无调试符号2种情况）。最后，提取关键特征，方便以后使用。Let's go!

  通过查看string.h的代码，找出string的结构，提取结构如下：

  通过上面的继承关系，总结一下string的结构大体如下：

  知道了string结构，就知道string的大小，16+4+4 = 24个字节，我们用OD调试验证一下：

  接着，我们编译一个程序（源码在文末附件中），打开其源码和2个IDA进行对比分析（IDA一个加载调试符号PDB，一个不加载调试符号）。先看main函数的前2句代码：

  再来看看后面2句被ida反编译后的结果：

  我们也可以跟进testString（sub_401080）函数去看看，为了篇幅原因，这里就不再细说了，大家有需要可以自己去对比分析一下。最后我们总结一下，根据ida的分析，我们知道string的初始化情况，大约有2种：

  这就是string的初始化结构，其实这两种本质上是一样的，一个局部变量，一个是参数变量。当遇到这两种结构，那么很大可能就是一个sting变量。还有一点需要提一下，就是string有2种存储结构，所以每次取string里的字符串时，都需要判断一下最大长度 _Myres 是否大于0x10，这个也是很经典的一个特征，如下：

  其他string相关的函数大家可以直接去跟一下，反正就那么几个，这里直接给出一些总结：

  接着看看vector容器，方法还是一样，先来看看代码里面的结构，提取如下：

  这个就是vector的结构了，简化一下：

  vector<T>是一个数组，数组的元素 T 都是连续存储在一块内存空间中，其中_Myfirst 指针指向第一个元素，_Mylast 指向最后一个元素，那么很容易想到，数组元素的个数就等于 (_Mylast -_Myfirst) / sizeof(T) 。

  接下来以vector<char>、vector<int>、vector<struct>、vector<class>为例说明，先看2个例子：

  结构上跟源码基本无差，只是back()和pop_back()函数被优化了，再来看看vector<int>类型，这次用了另一种方式初始化：

  这种初始化方式会使用到vector类型的一个函数_Construct()，内部调用了insert将连续的数组插入到vector中。testVec的源码如下：

  如果IDA跟进到testVec函数里，会发现跟源代码差距非常大，原因是testVec函数里面的所有跟vector相关的函数(如begin()、push_back()、back() 等)都被优化了（库函数代码跟用户代码优化在一起了），不过细心去分析，会发现大部分代码都是在判断vector的空间是否需要重新分配，如果需要则调用reserve()函数进行调整。

  看一个动态调整大小的例子，并且看看动态调整大小的方法：

  从上面的分析可以看出，动态调整的规则是以每次增加一半来调整的，如果增加一半的大小会溢出，则每次只调整加1，这也是为何当存储量很大的时候，STL会非常慢。

  最后是vector<struct>、vector<class>这两种，本质上struct和class是一样的。分析表明，这两种类型被编译后基本上也是跟vector<int>类似的，这里只说明一下，如何确定元素struct或者class的大小。有2种方法，1)是通过循环时查看对_Myfirst增加的大小，这个大小就是元素结构的大小，例如：

  2)是找到_Uninit_copy()函数，里面包含了对整个结构的初始化，对逆向非常有帮助，例如AClass：

  从上图我们知道，这是一个类，类中有1个虚表，虚表里面有1个虚函数，类一共包括3个成员变量，类的大小一共 16 字节。

  vector差不多就分析到这里，最后给出总结：

  在开始分析题目前，我们回顾下上一节的内容，先来看看vector<string>的结构是怎么样的，例子如下：

  内存结构分析，如下：

  根据上一节的分析，string的大小是24字节，vector存储了4个string结构，系统预分配了2个结构。

  开始分析题目，首先运行程序发现是mfc所写，使用xspy工具获取按钮事件的处理函数是sub_4026F0。

  接着IDA分析这个函数：

  这里62-64行就是string初始化的经典结构，v14就是string类型，然后通过上下文可以知道，sub_402A70就是string.assign函数，赋值RegCode(v23)给v14。同样分析，v8也是string类型，保存了UserName。通过第80行的判断条件知道，sub_405510 函数返回1则显示成功，返回0则失败。接着我们来分析sub_405510 函数（这里我们需要记住传进去的参数），首先看看整体结构（只提取一些关键函数）：

  v13是该函数的返回结果，必须返回1才能通过验证，也就是说第一个if判断中的sub_404F00()函数得返回真，之后执行sub_405040()函数。下一个if判断条件也得为真，即sub_406080()为真并且( a13 || sub_403010() )为真，这里a13是外部传进来标记是普通版还是进阶版的变量，当其为0时，sub_403010()函数得为真。最后执行sub_402F20()函数将结果赋值给v13。先看sub_404F00函数：

  一开始判断了字符串的长度是否等于39，接着31-35行的典型的取string类型中字符串(char*)的标准结构，同理36-39行、41-44行也是，后面还会出现这样的结构，就不再重复了。

  这个循环是将所有的字符传递给sub_552E03函数，而该判断字符为小写字母时，将其转换为大写字母，函数内部主要的三行代码如下：

  接着往下看：

  这里出现了一个关键函数sub_404D70，然后进去分析，发现是split函数（本身STL是不包含这个函数），并且推断出v24是vector<string>结构，数组元素个数是8。sub_404D70函数的分析如下：

  回到上一个函数继续分析最后一段：

  总结一下sub_404F00函数：函数的参数是UserName（string类型），函数判断了UserName的长度是否39，将存在的小写字母转化成大写字母，并通过调用split函数将其按照 "#" 符号进行分割，保存在vector<string>结构中，分析得出是8个元素的数组，最后的判断限制了这些字符只能是 "0123456789ABCDEF" 这16个字符。通过以上分析，猜测UserName的格式是 "xxxx#xxxx#xxxx#xxxx#xxxx#xxxx#xxxx#xxxx"，x的范围为 "0123456789ABCDEFabcdef" 。

  接着分析第2个函数，sub_405040函数，这个函数参数是上面转换成大写字母后的UserName，计算结果返回5个int64的值。这个函数很长很长，但是基本结构都是差不多的，这里只分析一小段：

  这里要说一下出现的偏移24、48，包括后面出现的72、96等，都是取vector<string>数组元素的值，比如24*2=48，那么 v111[0]+48 就是取 vector<string>[2] 的值。然后这里的主要计算是在135行和146行，细心提取就OK了。

  最后使用c++将上节分析的2个函数的功能实现：

  Base64算法大家都用过，这个算法出现的主要的原因是解决有一些网络传输只支持可见字符的传输，而并不支持所有的字节的问题，base64算法能够将所有字节转换成可见字符。

  Base64的编码表如下："ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"，一共64个字符，所以只需要6位就能表示，从0-63分别对应一个字符。一般比赛中Base64算法都会修改这个编码表（有些还会修改算法），从而导致正常base64算法无法解码，加强难度。也有作者通过爆破的方式解码base64中的编码表，当然，修改了算法的话，就无法爆破了。

  一个字节是8位，base64每6位编码一次，也就是说，3个字节被base64编码后刚好等于4个字符，这对于优化计算也是非常重要的。如果不够3个字节将进行补0操作，补0中的6个0用“=”表示，这也是为什么base64编码后的字符串往往会有那么1，2个等号结尾。解码就是讲上述步骤反过来，下面看一个例子：

  上面是使用base64对字符串“1034”的编码和解码过程，编码后的结果为“MTAzNA==”。前面说了，编码时后补的6个0编码为“=”字符，不是后补的0是下标0，编码为“A”字符，如上面的红框。主要的代码实现如下：

  base64的算法就介绍到这里，接下来说说这次比赛中使用到的base64算法。

  我们进入sub_406080进行分析，F5一下。首先看下函数头：

  从该函数的外部我们知道，a1为我们输入的key字符串，那第二个参数是什么呢？不难发现，利用上一节STL的内容，通过跟踪变量，我们发现它很有可能是一个vector<T>类型的变量，其中T可能是char类型，这个vector变量保存了该函数的计算结果。

  知道了参数的意义，我们从反编译的第一行开始看起，首先有4个xmmword_xxxxxx类型的赋值语句给变量v26-v29赋值，从ida对变量的注释开始，我们知道变量v26-v29是在栈的连续空间中，__int128是16个字节，4个变量共16*4 = 64个字节，双击查看任何一个xmmword_xxxxxx变量，可以发现如下的值( 这里xmmword_5AC470没有使用 )：

  也就是说，这64个字节都是可视字符，他们排序的结果如下“ZO6Kq79L&CPWvNopzQfghDRSG@di*kAB8rsFewxlm+/u5a^2YtTJUVEn0$HI34y#”。为什么这里要分4个值赋值呢？其实是为了防止一眼看出这个是在初始化编码表。从这里我们大约已经可以猜测，这可能是一个base64的算法，并且编码表被修改了。我们接着分析：

  这里46行判断了key的长度是否是4的倍数，如果不是则返回false，前面分析已经知道了，base64编码后的字符串必须是4的倍数。接着跳转到第120的else块，分析如下：

  通过逐步分析，我们知道这个else块主要是获取key中的每一个字符并判断是否在base64的编码表中，如果存在某一个字符不在编码表中则返回flase，如果所有字符都没有问题，则跳转到LABEL_13中继续执行。细心的朋友可能会发现，如果key最后存在字符“=”不就不满足上面的循环了吗？因为“=”不在编码表中啊。确实，我也纠结了一小会，但是我们仔细看看v26初始化的那一段，会发现存在一个v30的变量，这个变量在41行被赋值为0x3d，而0x3d恰好是字符“=”的ascii码。也就是时候，在栈空间中，编码表的最后一个字符是“=”，其长度变成65。（这里OD动态调试一下就明白了）

  ida中，鼠标点一下41行的0x3d，并按键盘的R健，可以将0x3d按字符格式显示为“=”:

  继续分析 LABEL_13开始的代码。我们发现，从LABEL_13开始跟着1个大循环，大循环里面跟着4个小循环，首先我们分析小循环的代码，分析知道，每一个小循环是计算key中某一个字符在编码表中的位置，然后再通过66行的转换得到一个值，注意了，在正常的base64算法中，这个值是下标值，但是这里的算法被修改过，得到的是 index^(index >>3)。其他3个小循环的结构基本一样，唯一要注意的是63行v10相关的值，其实4个小循环分别计算key中4个字符对应的值。

  计算的4个值分别保存到v13、v15、v18、v24中，记住，虽然这4个变量是byte型（8位），但是他们的值都小于64（6位）

  我们前面分析到sub_405EB0函数是与vector相关的函数，结合上下文和参数（也可以结合OD，看vector数据的变化和数组大小的变换），我们可以确定该函数是puth_back函数（保存计算的v25值到v22中），并且v22属于vector<char>类型。

  接着我们再来看看v25的值是如何计算的，其实已经很明显了，就是base64的解码运算，通过对v13、v15、v18、v24的移位和组合，得到个3 v25的值（4字节变3字节）。

注： 上图IDA中备注的高、低位只取字节的后6位（小于64）

  最后，我们总结一下这个base64的解码函数：

  解码流程写出来了，那么相应的编码函数也很简单，就是逆向解码流程，注意流程的第2点，它的逆向操作也是一样的计算，比如：result = index^(index>>3)，那么 result^(result>>3) 也就等于index。

  用c++实现base64的编码和解密函数：

  这一节的主要内容可以参考《深入浅出密码学：常用加密技术原理与应用》第4章内容，详细知识书上都有说，这里只是简单说一说整个加解密的流程：

  从上图可以看出，AES加密涉及到4个层（解密就是逆向运算）：

  分组加密方式的工作模式也可以分为好几种，wiki上面分为6种，如下：

  ECB模式指每一组明文加密都是独立的，而其他模式的加密会依赖于前后块的密文。ECB模式也是属于最弱的模型，重放攻击就是其受到的攻击之一。因此ECB模型下，相同的明文块加密后的密文也是相同的。这次比赛使用的就是ECB模型，确认方法也很简单，我们输入相同的块看AES加密后的密文是否相同就能确认。

  加密前的字节：

  加密后的字节：

  我们可以发现，在相同明文块下（2行刚好就是2块），加密的结果是一样的，那么就是ECB模式了。

  掌握以上知识，我们开始逆向分析这次的变种AES算法，这个变种函数很多流程都被修改，但是还是有一些AES的细节被保留（比如 SBox、RC数组、MixColumn矩阵等），当我们分析透彻的话，写出逆向算法还是不难的。

  首先，先分sub_403010函数的参数，根据传入的参数，我们知道改函数的结构如下：

  接着开始分析第一段，密钥拓展层：

  第269行的dword_5ABB88变量，我们点击进去看一下:

  这里其实是密钥拓展层用到的一个变量轮系数RC，但是轮系数RC的值本应该是这样的：

  也就是说，这里的轮系数是32位数组，其中每个元素的高8位保存着数值（方面AES的g()函数进行32位异或） ，但是该题用错了，拿32位跟一个byte相与，导致后面的299行的 v15&*v232 运算常为0，我们后面分析。

  270行至281行的内容是把密钥从16字节的byte型数组转换成4个4字节的int型数组，这个非常容易看出来。接着284行至307行是一个的循环，这个是密钥拓展层的主要逻辑，通过分析发现，该密钥拓展算法跟正常的密钥拓展算法只是g()函数的实现有差异，如下图：

  从上图可以看出g()函数的不同之处，首先位移的位置不同，其次经过SBox转换后，修改版还多了跟原值异或这一步，最后再进行RC相关的操作。这里RC[i]是32位，并且高8位才有数值，其它位为0，与上一个8位的数值，结果常为0，任何数与0异或都是它本身，所以相当于没有与RC操作这一步了。

  以上就是密钥拓展层，在解题的时候这一部分是不用分析的，直接从内存里抠出来利用就行，但是平时学习的话还是有必要分析一下。

  生成完密钥后，接着是对待解密的数组进行一系列的操作。首先是对待解密的字节数组进行转换，单字节转换成DWORD并且进行转置操作（下图的314行至330行），然后与密钥组进行异或（332行至343行）：

  上图变量v257所指向的空间就是计算过程中保存的结果，后面很多层都可以通过动态调试对结果的分析看出来，而不用实际去分析代码。接着进行逆向的SBox变换（iSBox）：

  接着是逆向的shift_row层（步骤8），这里进行静态分析比较麻烦，直接动态跟踪输入输出的变化就能看出来：

  shift_row层过后是MixColumn层（步骤9），因为是解密函数，所以是逆向的MixColumn层：

  这层的识别非常容易，查看dword_5ABBB0变量，发现其实就是InvMixColumn层的一个矩阵：

  而这里的矩阵乘法非常不同，不是用的乘法实现，而是对每一个字节进行判断再进行对应的操作，用了一大串switch结构，这样的实现导致代码量比较大，不过多看几遍就懂了。

  （后面的层跟前面的层代码结构类似，只要注意下输入输出就好，这里不再列举代码，有兴趣的同学可以分析分析idb ）接着再取倒数第二行的key，对key进行InvMixColumn层变换，再一次进行密钥加法层的运行。然后以上步骤从iSBox层开始循环9次。经过9次循环后，最后对结果再进行一次iSBox变换和ShiftRow层变换，并取第一行的key与结果相异或，得到的就是最终结果。

  上一节我们分析了解密函数，这一节我们需要还原加密函数，在这之前，我们再把解密流程梳理一下，整理成流程图：

  对比《深入浅出密码学：常用加密技术原理与应用》中AES算法的加密与解密流程图，我们发现这个解密函数左边的流程图跟AES的加密函数一样，而右边的密钥拓展流程图又跟解密函数的密钥流程图一样，这真是魔改版的AES啊。最后实现加密函数，我们只需要按照该解密函数反向操作就行了，这里不再说明，有兴趣的同学可以看附加中的代码，代码实现了该魔改版AES的加密和解密函数，编码过程还有一个需要注意的是，这里的SBox和iSbox都是经过变换的，跟原版的AES的Box不一样，需要从文件中dump出来。

  前面的3节分析了整个题目的90%，我们还有最后一个函数sub_402F20，现在再来看看整个分析：

  进去看看sub_402F20长啥样子：

  上面的函数参数经过了重命名，参数是8个int64类型的值（T1-T5已知，求T6,T7,T8），按照参数压栈的方式顺序命名就好了。最后将代码整理成求解的方程，如下：

  目前我们逆向完了整个校验的过程，接着考虑如何写注册机。在这之前，把整个校验过程总结如下：

  明白了整个校验过程，那么写注册机就比较简单，UserName 流程不变，RegCode通过倒推回去就能计算出来。首先，通过UserName计算出T1-T5，然后通过解方程计算出T6-T8，接着拼接T9（T9为字符串"2018\x00\x00\x00\x00"）输入到AES加密算法中，得到数据最后再进行一次Base64编码，最终的结果就是我们需要的RegCode。详情请看附件中的代码。

(上篇完)

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！