解码 90 年代：早期软件开发中的逆向工程和密码学之旅

• elisha118
• 2023 年 2 月 1 日
• 10 分钟阅读

• 介绍
• 开始使用 - QText
• 逆向 MS-DOS 二进制文件
  • PKZip
  • int 3f - MS-DOS Overlays
• 密钥扩展函数
  • 追踪密码流程
  • 密钥派生函数
• 逆向密钥派生
  • 逆向第一阶段 - 4 字节到 4 个可打印字符
  • 逆向第二阶段 - 16 字节到 𝟦×𝟦 字节字符串
• 总结

介绍

2020 年 8 月，一位客户委托我们处理一批 90 年代中期的锁定 QText 文档，但他丢失了密码。

QText 是一款 DOS 时代的希伯来语-英语文字处理器，用 Turbo Pascal 编写，发布时间比我和 @Elisha 接触逆向工程工具早了大约 15 年。

在这篇博文中，我们将描述分析加密文档和逆向 DOS 程序的过程。

希望能深入了解以色列早期软件开发的情况，更普遍地了解早期消费者软件开发中密码学的视角和实现方式。 我们也希望帮助保存这里使用的知识和工具，其中很多都几乎没有保存到今天。

开始使用 - QText

幸运的是，我们可以访问客户提供的可用的 QText 二进制文件。 我们启动了一个 DOSBOX 模拟器实例，并开始摆弄这个文字处理器一段时间，重点是文档加密功能。

我们最初的结论包括：

• 密码很短 - 4 个字符，仅限于大写字符和数字 - 相对于现代计算能力来说，这是一个非常小的密钥空间。
• 文档通常是某种形式的纯富文本 - 但锁定的文档在它们前面加上一个 0𝑥1𝒟 标头。 具有相同密码的文档具有相同的标头（无 salt）。
• 在 0𝑥1𝒟 标头字节中 - 16 字节是可变的，并且与密码直接相关 - 密钥是否包含在文件中？
• 不熟悉的加密 - 似乎在逐行和逐列的基础上工作，这意味着相等的纯文本行将导致相等的密文行。 加密时跳过空格，这表明了逐列的特征。

具有不同密码的两个文档的第一行 - 密钥已加下划线

具有相同密码和纯文本的两个文档的 Payload - 一个文档与空格交织

因此，正如您可能预料的那样，这是一个非常基本的系统，这是在互联网并不普及的时候开发的 - 更不用说密码学最佳实践的知识了。

密钥似乎包含在文件中，但我们不知道加密机制。 我们可以尝试逆向加密函数，但暴力破解密码是可行的，而且在这种情况下要简单得多 - 如果我们有一种快速测试密码的方法。

我们相对安全地假设文件中的 16 字节密钥以某种方式从密码派生而来 - 我们可以尝试将我们的 RE 工作重点放在密钥派生算法上。 我们的第一个猜测是简单地使用当时的哈希函数对密码进行哈希处理，但不幸的是，这个方向没有奏效。

我们将目光投向了密钥派生算法，并开始拆解可执行文件。

逆向 MS-DOS 二进制文件

DOS 在 real mode 下运行，这意味着整个 16 位地址空间在所有进程之间共享，并使用 16 位 segment 选择器和一个附加的 16 位地址进行寻址 - 这些地址用于覆盖 640KB 的可用内存范围。

可执行文件不是 PE，而是 DOS MZ executables。 文件实用程序将我们的 QTtext 二进制文件识别为 PKZip 压缩的 SFX - 自解压可执行文件。

PKZip

PKWare 是我们今天所知的 ZIP 文件格式的普及者，也是 MS-DOS 时代广泛使用的可执行文件压缩器。

关于 PKZip 压缩器的可用信息并不多 - 据推测它使用了与非 SFX zip 实用程序相同的压缩算法，但我们很难找到一种可以将 SFX 正确解压缩为功能可执行文件的工具。

在未能找到有关此压缩器的其他信息，并且想要避免逆向解压缩存根的情况下 - 我们尝试使用 DOSBOX 调试器的 CPU LOG 功能来跳过解压缩器代码，在原始入口点之后 - 然后从内存中提取代码。

虽然这确实有效，但它只占代码的一小部分 - 可执行文件的大小为 24K（已压缩）。

回想起破解 crackme 的早期（虽然没有这个程序那么早），我们开始寻找通用的可执行文件解压缩工具，这些工具过去在破解站点上很常见。

比一些开源趋势早了十多年，它们的内部运作通常很神秘，但大多数时候它们都能完成工作。 最终，我们找到了 以下 ssokolow 博客文章，该文章引导我们找到了一个神话般的逆向工程遗物 - exetools。

解压缩器页面有一个巨大的解压缩器列表，我们假设其中很多都可以完成工作 - 因为 PKZip 相当常见。 我们首先尝试了名为 PKUNLITE 的那个，当它没有工作（但看起来很有希望）时 - 我们使用 DISLITE v1.15 找到了成功。

int 3f - MS-DOS Overlays

在 IDA Free 5.0 中加载二进制文件（幸运的是，该文件仍然在分发中 - 托管在 ScummVM 网站上）显示可执行文件使用了类似 Turbo Pascal 的内存 overlays。

由于我们在 real mode 下运行，因此无法进行分页/交换内存，而 overlays 是解决有限内存空间的解决方案。

overlay 机制本质上是用户空间中页面交换的实现：可执行文件包含不可移动内存的根段，并附带一个 .ovr 文件，该文件包含其他代码（在本例中，是大量的其他代码）。

根代码（源自 .exe 文件）始终映射到内存中，而 overlay 段被选择性地映射到内存中并按需交换。

overlays（和根段）之间的调用通过跳转表发生，如果 overlay 已经映射到内存中，则跳转表存根会“链接”到其当前在内存中的位置。

否则，它会导致（在本例中）一个 int 3f 指令，以及与其一起的 overlay 元数据。

overlay 元数据包含 - 除其他外 - 相关代码段的文件偏移量。

然后，中断处理程序会将相关的 overlay 映射到内存中，以取代另一个 overlay，并修复存根，然后再恢复执行。

未链接存根的示例。 请注意上面的 overlay 元数据。

相同的存根，现在在其 overlay 加载到内存后已链接。

IDA 在展平和静态链接存根方面做得非常好，因此我们可以完整地逆向程序。

然而，这给我们在动态调试代码方面带来了挑战，因为虽然根段始终加载到相同的内存区域中，但 overlays 会非常频繁地更改位置，这使得我们无法正确地放置断点。

挖掘有关 Turbo Pascal overlay 系统的信息非常困难，而 DOSBOX 调试器并不方便地支持跳出中断。

我们很可能已经逆向了中断处理程序，并找到了一个在恢复新加载的 overlay 中的程序执行之前放置断点的地方，但我们最终选择了一个更简单的解决方案 - 找到一个我们可以中断的 overlay-to-root 调用，然后跳出到新加载的 overlay 中。

从 overlay 到根段的调用的示例。overlay-to-root.PNG

在上面的示例中，pascal_strncpy 位于根段中，其地址是固定的且可预测的。 要中断 overlay 73 中的调用函数，我们将改为在 pascal_strncpy 处放置一个断点，然后跳出到调用函数中。

这有点费力，但对于手头相当短的任务来说，它可以工作，而且我们有足够的 overlay-to-root 调用可以中断，因为根段托管了许多 Turbo Pascal 标准函数。

密钥扩展函数

追踪密码流程

找到密钥扩展函数需要一些逆向和大量的追踪。 我们最初的想法是通过使用 DOSBOX 的 CPU LOG 命令来追踪执行，同时反复使锁定文档上的密码检查失败，从而执行热点分析。

最终，我们采取了一种更直接的方法，只是在 int 21 中断处理程序上放置一个断点，以捕获打开和读取调用。

DOSBOX 调试器在打开的中断调用处。 请求的路径在数据概述中可见。

我们通过文档路径上的打开和 0𝑥1𝒟 字节的读取进行跟踪 - 这与我们在锁定文档中看到的标头大小完全相同。 继续进行动态调试，我们确定了一个将输入的密码字符串和 0𝑥1𝒟 标头作为参数的函数。

深入研究，我们看到了密码如何传递到内部函数，并将结果与标头进行比较。

密码检查流程的一部分 - 如果密码有效，则此函数返回 1。

据推测，memcmp 之前的函数调用执行密钥扩展，然后将结果与文件头进行比较。

密钥派生函数

密码首先通过一个排列函数，该函数以迭代方式将密码的每个字节递增字符串中所有字节的总和。 在继续处理下一个位置的字节之前，通过使用结果字节的值作为静态位图的索引来测试某个谓词 - 其中每个位表示该字节值是否有效 (1) 或无效 (0)。 在 CFG 中可以找到使用这种位图的更现代的示例。

此函数用于在多个位置检查字节值与位图。

在每个字节排列后，都会测试字节值。 如果该值无效 - 则将其递增 0𝑥22。 在我们不可变的位图的情况下 - 这种“更正”总是足以将其推入有效值范围 - 这意味着每个字节只能发生一次。

排列函数中使用的位图。

24_# Taken from binary
_25 BITMAP **=** b"\xff\xff\xff\xff\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80"
 ... 
 28**def is_valid_char**(c):
 29_# Can be simplified as 0x20 < c < 0x100
_30**assert**type(c) **is**int31**assert** c **<=**0xFF32   upper_idx **=** c **>>**3_# upper 5 bits
_33   lower_idx **=** c **&** 0b111 _# Lower 3 bits
_34**return not**bool((BITMAP[upper_idx] **>>** lower_idx) **&**1)

摘自 qtext_cracker.py - 在 python 中重新创建的谓词

具体来说，这可以通过简单地检查 0𝑥22 < value < 0𝑥100 来表示🤷

排列函数 𝑃(𝑥) 很简单 - 它以迭代方式将每个字节递增该点处整个字符串的总和：

37**def key_transform**(input_key, modifier**=**0x22):
 38**assert**type(input_key) **is**bytearray39   key **=**bytearray(input_key) _# copy
_40**for** i **in**range(len(key)):
 41**for** j **in**range(len(key)):
 42       key[i] **=** (key[i] **+** key[j]) **&**0xFF43**while not** is_valid_char(key[i]):
 44       key[i] **=** (key[i] **+** modifier) **&**0xFF45**return** key

摘自 qtext_cracker.py - 在 python 中重新创建的排列函数

之后，字符串被连接到自身（在适当的位置）3 次，并再次通过排列函数。 结果确实是密钥，因为它出现在标头中。

因此，密钥派生函数 𝐾(passcode) 是：

𝐾(passcode) = 𝑃(𝑃(passcode) |𝑃(passcode) |𝑃(passcode) |𝑃(*passcode))_

现在我们可以非常快速地暴力破解密码，密码的输入空间非常小。 但是，凭借我们新发现的密钥派生函数知识，我们可以尝试对其进行逆向，以获得更快的解决方案。

逆向密钥派生

让我们首先检查一个简单的案例 - 排列一个简单的双字符字符串 - '00' 的结果：

长度为 2 的字符串的排列过程也可以描述为：

排列只涉及我们输入值的组合 - 因此它是线性的，但它不是严格线性的 - 我们在任何溢出 0𝑥𝐹𝐹 的操作中都会丢失进位位

假设我们想要逆向排列 - 从最后一个字节开始。 我们知道 𝟸𝑎₁＋𝑎₂ 的值为 0x90，所以我们可以替换它：

但是现在，由于我们必须除以 2（在此字段中不可逆）- 有两种可能的解决方案：

我们碰巧知道这里正确的值是 0𝑥30，但一般来说，当尝试反转排列函数时，我们将不得不叠加两个结果。 简而言之 - 在分解过程的每个步骤中，我们“分裂”成两个分支 - 每个结果一个分支。

此外，对于某个范围的值，会发生另一次分裂 - 在每次字节排列结束时，如果字节落入一组特定的值 (0𝑥20 < 𝑏 < 0𝑥100) 中，则将其递增 0𝑥22。

这意味着，如果我们当前正在查看的字节介于 0𝑥20 ＋ 0𝑥22 ≡ 0𝑥24 和 0𝑥100 ＋ 0𝑥22 ≡ 0𝑥22 之间，我们需要考虑一种可能将其递增到该值的情况，而不是自然地到达该值。

值得庆幸的是，更正考虑了整个“禁止”值的跨度，因此它只能发生一次 - 因此只占一个额外的分支。

总结一下 - 在密钥分解的每个阶段，我们都会在一次和两次之间进行分支。 以下是使用递归的分解算法的实现：

48**def recursive_decomposition**(input_key, decomposed_part**=**None, stop_at**=**4):
 49**assert**type(input_key) **is**bytearray50   key **=**bytearray(input_key) _# copy
_51**if** decomposed_part **is**None:
 52     decomposed_part **=**bytearray()
 5354**if**len(key) **==**0:
 55_# Stopping condition
_56**return** [
 57       decomposed_part,
 58     ]
 5960**if** stop_at **is not**None:
 61**if**len(decomposed_part) **>=** stop_at:
 62**return** [
 63         decomposed_part,
 64       ]
 6566   results **=** []
 67   value **=** key.pop()
 68**if not** is_valid_char((value **-**0x22) **%**0x100):
 69_# We have an additional case to process
_70     new_key **=**bytearray(key) _# copy
_71     new_key.append((value **-**0x22) **%**0x100)
 72_# Where to save this?
_73     results.extend(recursive_decomposition(new_key, decomposed_part, stop_at))
 7475   value **=** (value **-**sum(decomposed_part)) **%**0x10076_# Subtract trailing (decomposed) characters
_77_# Compute two candidates
_78   candidate_1 **=** ((value **//**2) **-**sum(key)) **%**0x10079   candidate_2 **=** (((0x100**+** value) **//**2) **-**sum(key)) **%**0x10080   new_decomposed_left **=**bytearray([candidate_1,]) **+** decomposed_part
 81   new_decomposed_right **=**bytearray([candidate_2,]) **+** decomposed_part
 8283   results.extend(recursive_decomposition(key, new_decomposed_left, stop_at))
 84   results.extend(recursive_decomposition(key, new_decomposed_right, stop_at))
 8586**return** results

摘自 qtext_cracker.py - 分解函数

考虑到 16 字节的密钥，这意味着在 2¹⁶ 和 2¹⁷ 个分支之间，这还不错，但幸运的是，有一些约束可以帮助我们大大减少搜索空间。

逆向第一阶段 - 4 字节到 4 个可打印字符

第一个约束非常简单 - 任何分解的字节最初都是密码字节 - 意味着一个大写字母或数字。

考虑到我们之前的示例 - 显然我们只能选择可打印的值 - 0𝑥30。

逆向第二阶段 - 16 字节到 𝟦×𝟦 字节字符串

第二个约束并不那么简单，但仍然很简单 - 第二次排列之前的 16 字节密钥的格式是一个 4 字节序列，重复 4 次。 这意味着我们只需要分解一个 4 字节的后缀 - 然后通过将其提供给排列函数并检查结果是否为原始密钥来测试该 4 字节后缀。

这会将我们的搜索空间缩小到每个步骤 2⁵ 个 - 或总共 2⁶ 个。 如果你有耐心，你实际上可以在一张纸上破解这个加密！

总结

所以 - 从从文档中提取的 16 字节密钥 (𝑘) 开始：

1. 通过分解函数运行 𝑘，累积所有可能的 4 字节后缀。
2. 将后缀反馈回排列函数以找到正确的后缀。
3. 再次通过分解函数运行结果后缀，再次累积所有结果。
4. 将结果缩小到与密码输入空间匹配的结果，以得出原始密码。

完整的 qtext cracker 脚本可以在 这里 找到。

联系我们

最近的文章

查看所有

Hacking eBPF & LLVM for Fun and Profit

Unraveling the Bluetooth Enigma: Extracting the Flag from BSides TLV 2022 CTF 'Handsfree'