逆向工程 - 挑战变长整数编码 - 吾爱随笔录

挑战变长整数编码

逆向工程二元分析文件格式二进制格式

2021-06-14 04:31:04

我有一段要调查的二进制数据。我的猜测是它应该是简单的类似文件系统的索引的一部分。文件中有 2 个部分。第一部分有一个非常简单的格式：

第一部分的字节数
许多看起来像文件名的以零结尾的字符串（其中 1256 个）

自然地，我希望稍后会找到指向一些以这些字符串命名的文件的指针。但是，文件的其余部分长 0x5c47 字节，看起来它有许多记录（int32，little endian = 0x4e0），然后是一系列记录本身。然而，诀窍在于显然记录长度不是恒定的：(0x5c47 - 4) / 0x4e0 ~ 18.9254807。我在这里看到了某种模式，让我演示一下：

E0 04 00 00

正如我所说，它以记录数开始，0x4e0 = 1248。请注意，1248 条记录与我之前找到的字符串数（1256）相当接近，但并不完全匹配。然后我看到一些 14 字节长的记录：

90 00   |90 0D|90 16 02 90 22 90 2A 90 39|00
90 46   |90 0D|90 16 02 90 22 90 2A 90 39|01
90 53   |90 0D|90 16 02 90 22 90 2A 90 39|02
90 61   |90 0D|90 16 02 90 22 90 2A 90 39|03
90 6E   |90 0D|90 16 02 90 22 90 2A 90 39|04

最后一个字节似乎是记录号计数器。至于其他人，到目前为止，只有第二个字节发生了变化。但是，接下来我们会看到一些 15 字节长的记录：

91 82 00|90 0D|90 16 02 90 22 90 2A 90 39|05
91 97 00|90 0D|90 16 02 90 22 90 2A 90 39|06
91 A4 00|90 0D|90 16 02 90 22 90 2A 90 39|07
...
91 14 01|90 0D|90 16 02 90 22 90 2A 90 39|0E

似乎涉及到一些可变长度的整数，即记录的第一个值以90 00,开头90 46，然后它最终溢出并变为91 82 00, 91 97 00, ...91 26 01等。但是，这不是正常的（BER，AKA VLQ，AKA Base128，等）编码我曾经使用过的可变长度整数。让我们检查一下记录的内容在变成 16 字节长的记录后如何扩展：

91 26 01|90 0D|90 16 02 90 22 90 2A 90 39|0F
91 39 01|90 0D|90 16 02 90 22 90 2A 90 39|80 10
91 4E 01|90 0D|90 16 02 90 22 90 2A 90 39|80 11
91 6C 01|90 0D|90 16 02 90 22 90 2A 90 39|80 12
91 8B 01|90 0D|90 16 02 90 22 90 2A 90 39|80 13
...

哇，它只是05, 06, 07, ... 0E, 0F（大概编码记录#0..15），然后它跳到80 10指定记录#16。第一个字段似乎继续是 3 字节整数。接下来切换到 17 字节长的记录看起来像这样：

...
91 7C 08|90 0D|90 16 02 90 22 90 2A 90 39|80 7D
91 8A 08|90 0D|90 16 02 90 22 90 2A 90 39|80 7E
91 98 08|90 0D|90 16 02 90 22 90 2A 90 39|81 7F 00
91 A6 08|90 0D|90 16 02 90 22 90 2A 90 39|81 80 00
91 B4 08|90 0D|90 16 02 90 22 90 2A 90 39|81 81 00
91 C2 08|90 0D|90 16 02 90 22 90 2A 90 39|81 82 00
...

与我们之前看到的90变成的技巧有一些模糊的相似之处91：这里80变成81可能指定从#126 = 0x7e（编码为80 7E）到#127 = 0x7f（编码为81 7F 00）的切换。

进一步在文件中，似乎有一个 18 字节长记录的主要格式切换，我猜它有点像这样排列：

...
91 5D 14|90 0D   |90 16   |02|90 22|90 2A   |90 39|81 5C 01
91 6A 14|90 0D   |90 16   |02|90 22|90 2A   |90 39|81 5D 01
91 77 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|00
91 AA 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|01
91 B5 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|02
91 C0 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|03
91 CB 14|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|04
...

此更改扩展了许多字段（实际上使其在某种程度上清除了字段边界）并将最后一个字段重置为 0。

与我们之前看到的90变成的技巧有一些模糊的相似之处91：这里80变成81可能指定从#126 = 0x7e（编码为80 7E）到#127 = 0x7f（编码为81 7F 00）的切换。文件末尾的记录长 20 个字节，如下所示：

...
91 32 34|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|81 7F 03
91 3B 34|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|81 80 03
91 44 34|91 86 14|91 8F 14|02|90 22|91 9B 14|90 39|81 81 03

我最好的选择是，许多中间值已经增加并90 xx变成91 xx yy.

总结到目前为止我学到的东西，看起来这些记录使用可变长度编码的整数，编码方案是这样的：

0x0 = 00=0000_0000
0x1 = 01=0000_0001
...
0xf = 0F=0000_1111
0x10 = 80 10=1000_0000|0001_0000
0x11 = 80 11=1000_0000|0001_0001
...
0x7e = 80 7E=1000_0000|0111_1110
0x7f = 81 7F 00=1000_0001|0111_1111|0000_0000
0x80 = 81 80 00=1000_0001|1000_0000|0000_0000
...
0x15d = 81 5D 01=1000_0001|0101_1101|0000_0001

有谁知道任何看起来像这样的标准格式/编码方案？关于如何正确解码90 xx和91 xx yy值的任何想法？

1个回答

记录中的八个字段中的每一个都有一个一字节的标头。

在标题中，高 nybble8表示未签名，高 nybble9表示已签名（或者可能反过来，无法确定）；低 nybble 是编码数字所需的字节数（不包括头字节），减一。
如果标题的高 nybble 是0，那是非常小的无符号数（更准确地说：与相同类型的非常小的数字8）的特殊代码，在这种情况下，低 nybble 是整个数字。

现在，使这变得困难的棘手的事情是（对于类型8和9）数字的其余部分是使用一种方法编码的，该方法自行表示编码长度，完全没有意识到标头已经告诉我们将有多少字节编码所需。我的猜测是，在已经决定了这种内部编码之后，为此应用程序“发明了”标头字节。

对于正整数，内部编码与 VLQ 非常相似（感谢删除名称，我不知道它们）：将数字的最低 7 位输出为单个字节，并将该字节的 MSB 设置为 1，如果后面还有更多字节，如果没有，则为 0；继续接下来的 7 位，等等
。与 VLQ 的区别在于位序列7F被视为非终止，这可能是编码器中的 Obi-Wan 错误，或者某种我不知道的真正设计决策真的懂（这不能表明数字不应该被符号扩展为负数，因为那样同样适用于40- 7e。）

从末尾看到第 4 条记录会很有趣 - 它应该以值 0x1fe 结尾，我希望它会被编码为81 FE 03（注意 0x1ff 被编码为81 7f 03，这意味着这种编码永远不会在FF任何地方使用该值。）

我们在您的样本中没有负数示例，因此我们无法确定它们将如何编码。

其它你可能感兴趣的问题

上一篇从 PANDA 跟踪获取操作码列表下一篇识别switch语句的跳转表

挑战变长整数编​​码

挑战变长整数编码