前言

正所谓要“知己知彼”， 本题开始前先找了出题人在去年秋季赛出的最后一题，看到 “我喜欢很存粹的题目，不是靠大量的逆向量卡倒对手。所以没有使用任何的反调试、混淆手段” 。不需要重体力活的题目，好评！

（一切逻辑都摆在台面上，大气磅礴，不遮遮掩掩。就是一场阳谋，在公开战场上正面交锋，无论输赢，皆令人称勇）

逆向

main 函数初看起来有些乱。对比去年的题目，主函数是分两部分验证输入内容的：第一部分是数学验证，也是需要逆推的逻辑；第二部分是哈希验证，用来限制多解，不可逆。

对比去年题目的反编译结果和源代码，可以发现 main 函数从 0x140000979 开始是内联的魔改MD5，因此需要重点关注的是前面的部分。

sub_140000478 是核心函数，以hexdecode后的输入为参数调用了两次，然后对其返回的值有检查（0x1400008E1，0x14000090B，0x14000093B，0x140000965 共四处）。

有很多连续的内存块存储着指针和长度，在 IDA 中定义出结构体后看的更加清楚。虽然这一步花了些时间，但感觉是值得的。

sub_140000478 先调用 std::_Random_device() 得到一个 32bit 的随机数种子，然后生成了 1024 个随机数（0x140000557附近，调用了sub_140000E94），% 127 后作为一个 32x32 的矩阵（记作A）。

0x1400005E7 附近生成了 16个随机数，% 127 后与16字节的输入值构成了一个 32维的向量（记作x）。

0x14000061 附近生成了 32个随机数，每个都 & 1，构成了一个32维的向量（记作e）。

最后计算了矩阵乘法：A*x + 29*e (mod 127)，记这个结果为b。

sub_140000478 返回后，在 main 函数中，将 A 和 b 与全局常量作比较。

踩坑

（这一部分与最终题解无关，可跳过）

随机数

刚开始并没有考虑矩阵方程的问题。看到用了 Random，以及 0x6C078965 常量和经典的 624，第一反应以为本题考点是MT19937梅森旋转算法的随机数预测（只要已知连续的624个输出）……毕竟如果随机数已知，输入就可以直接求解了。
以前见过不少Python随机数预测题，都是用 randcrack 仓库做的。MT19937算法是很多编程语言的标准库随机数生成算法，准备套用到本题的C++代码时才注意到输出的随机数模了 127 ……（好吧，此路不通）

然后注意到随机数种子，发现取值空间只有 2^32。在不涉及太复杂运算的情况下，现代计算机的算力爆破32bit的开销是完全可接受的。

为了防止出题人魔改Random算法（毕竟有魔改MD5的先例）以及避免复制IDA F5伪代码可能的坑，这里直接复用原始程序的二进制字节码（主要针对sub_140000E94），遍历2^32个随机数种子，检查生成的1024个随机数是否与程序中的相等：（Linux环境（或WSL），gcc开O2优化编译）

（加了个小优化：不必每次都生成全部1024个随机数，可以边生成边比较，如果不相等立刻跳出循环）

速度上大概1秒钟能测试 0x100000 个seed，16核机器上开16个进程同时跑，几分钟就能跑完全部的2^32个seed。

跑完却没找到结果，人有点懵。
反复检查代码，修了几个问题（例如 mt_state 里面的整数至少有 1249 个，最初以为只有 624 个）后再跑还是没有结果……

调试

无奈，只好想办法调试一下看看爆破算法的输出和原始程序是否一致。

patch程序头禁用掉 DYNAMIC_BASE，x64dbg加载调试，尝试下断点看 sub_140000E94 的返回值却发现没有这个内存段？！

x64dbg给出的内存布局（部分）如下：

对比IDA给出的Segments（Shift+F7）：

很明显，.text 段在 x64dbg 中消失了。怀疑是否有奇怪的反调试，但仔细调过后发现并没有。
如果从入口点开始调试，在 0x14000317F 处（__scrt_common_main_seh -> call main），由于 main 函数位于消失的段，所以从这里开始就无法展示反汇编了，但是 F7 单步调试仍然正常，寄存器和其他内存段的值也可以正常展示。

换 WinDbg (x64) 调试，发现一切正常，所以可能是x64dbg自身的问题。
查到了一些讨论：https://gitter.im/x64dbg/x64dbg?at=5d5da44c25764a3642d70f73、https://github.com/x64dbg/x64dbg/issues/2213，似乎和 VirtualProtect 有关，但并不清楚具体原因，而且应该与题目文件无关（题目文件并没有调用过VirtualProtect）。

另一方面，这暗示了题目文件的结构一定存在问题。如果用 Ghidra 加载这个文件，会得到下面的ERROR：Invalid DebugDirectory

猜测问题可能是 x64dbg 尝试解析 DebugDirectory 为调试提供辅助信息，但是过程出了错导致丢失了 .text 段，而 WinDbg 没有尝试解析这部分信息？（对 PE 文件结构不熟。希望熟悉 Windows 的人能够找出根本原因，给 x64dbg 和 Ghidra 官方提 PR）（亦或许能利用这个问题搞出一种误导人的反调试？）

（继续调试过程）在 WinDbg 中下断点到 0x1400004A3 看随机种子， 下断点到 0x140000557 看 sub_140000E94 的返回值，发现与爆破程序的计算结果完全一致。

哈希

爆破失败意味著程序中的常量根本不是按照程序中的随机数逻辑生成出来的。这也意味着 main 函数在 0x1400008E1 和 0x14000093B 两处的检查绝对不可能通过。

回头仔细梳理了一遍 main 函数，发现前面的四个检查并不是程序输出 "correct!" 的必要条件。
通过这些检查只是会跳过下面的MD5检查直接输出"correct!"，然后即使这些检查不通过，只要后面的MD5检查通过，同样会输出"correct!"。（想起来之前忽略的程序运行之初打印的一句话："real seed can get the final result. Or please break safe hash func!"，已经说明了随机数检查和MD5检查只需要通过一个即可）
（其实应该早点反应过来：因为出题要求程序首次启动输入正确的验证码必须提示成功，如果随机数检查真的是必要条件则不可能满足这个要求）

思路继续跑偏，开始怀疑出题人会不会在魔改的MD5里埋了一个后门。

仔细对比出题人去年题目的反编译伪代码以及放出的题目源代码，看了很久才确认里面没有后门，哈希不可逆。

算法

对 sub_140000478 的每次调用实际上都返回了两个数组，分别是 1024 字节的随机数，以及经过运算后的 32 字节值。之前注意力一直集中在 1024 字节的验证，现在才开始看 32 字节值的计算过程。

计算过程不复杂，核心就是一个矩阵乘法（加法和乘法都是在 mod 127 意义下的）：

其中：

• A 是 32x32 矩阵（就是返回的1024字节随机数数组），这里可以假设 main 函数中与它对比的全局常量是正确值（虽然这个检查不可能通过），是已知值
• x 是 32 维列向量，其中前 16 个字节是程序hexdecode后的输入值，后 32 个字节是随机数
• e 是 32 维列向量，每个维度只能取值 0 或 1，来源也是随机数
• v 是 32 维列向量，是计算结果，也是函数的返回值之一，在 main 函数中与全局常量有对比，是已知值

如果没有误差项 e，这就是一个普通的线性方程组。然而误差项 e 使得直接求解无法得到准确的结果。

这种带误差的模质数线性方程组的求解，在很多比赛中已经出过了，例如 2022 年春秋杯网络安全联赛春季赛的 bob's enc，以及 2021 年中科大 Hackergame 的 灯，等灯等灯 等。
题目正解是格基规约。

求解

格，个人的理解就是一组整数向量的线性组合构成的空间。（更通俗一点：已知若干个整数向量，每个向量都可以选择乘上一个整数，然后相加，这样可以得到很多新的向量）

格上的经典难题有 SVP 和 CVP：

• SVP：Shortest Vector Problem，最短向量问题，即已知一组向量，找出它们的线性组合中最短的一个向量
• CVP：Closest Vector Problem，最近向量问题，即已知一组向量，找出它们的线性组合中与一个目标向量距离最近的一个向量

这两个问题都是困难问题，但是格基规约可以把已知的一组向量转一组近似最短且正交的向量（这样通常能找到SVP问题的近似解）。常用的算法有 LLL 和 BKZ。

（这两个算法不用手写，SageMath已经自带。关于两个算法的区别，单就CVP问题而言，LLL算法复杂度更低，BKZ算法效果更好；其他区别可以参考两个算法的定义，例如这篇文章有提及）

回到最初的方程：

其中矩阵与向量的乘法可以拆分为列向量的和：

这里 和 都是向量， 和 29 是整数，等式左侧就是这33个向量的线性组合。

失败

（这一部分与最终题解无关，可跳过）

一个直观的构造方式：把这些向量转置为行向量，然后顺序排布如下（I 是单位矩阵）：

显然，这个新矩阵的第1行（即 ）乘 ，第2行乘 ，……，第32行乘 ，第33行乘 1，后面32行每行分别乘0或1（与 的具体值一致），再后面32行分别乘一个数（达到 mod 127 的效果），最后一行乘 -1，然后加在一起，结果必然每个分量都是 0。
即：新矩阵的每个行向量的线性组合中一定存在一个零向量，而零向量相对于这些行向量是更短的值，因此可以期望格规约找到这个值。

考虑到题目给了两个方程，这两个方程的 x 向量的前 16 个维度相同（都是输入值的hexdecode），可以公用 的前16行：（矩阵为空的地方都是0）

这个矩阵的行向量必然存在某个线性组合，其前32个分量都是0，后32个分量只有0或1，代表着误差项$e$的各分量取值。

尝试直接格规约（BKZ），并不能取到理想的结果。（正常现象）

格子的构造一般都需要结合格规约算法的约束条件调整数值比例、增广列数等才能提高获得理想结果的概率，可惜并不了解这么深入的概念。

赛后看到了 Zuni-W 和 全盲法师 两位大佬的题解，他们都从数学理论对上面的格子进行了调整并成功规约出了需要的结果。

（自己的背景知识不足，读两位大佬的文章比较吃力，还需要再仔细研读）

成功

既然上面直观的构造方法没出来结果，自己又不知道应该如何调整参数，不如想一想有没有其他的构造方法。

如果不存在误差项 ，则只用一个方程即可求解；如果误差项 非常小，只用一个方程构造格也可以在几乎不调整参数的情况下规约出结果。本题中误差项的影响被人为放大过（乘了 29 ），但是给了两个方程，这暗示着综合利用两个方程有可能缩小误差项带来的影响。

重新思考题目。先列出题目给的两个方程：

其中 都是已知值
未知，但每个分量只能取 0 或 1。我们希它们成为某组向量的线性组合，从而利用格规约找出它们

注意到 虽然未知，但它们的前 16 个分量是相同的（都等于hexdecode后的程序输入）。在有两个方程的情况下，可以通过消元去除掉这 16 个未知量。（虽然暂时不知道有没有用，但未知量变少了总不是坏事）

具体操作是加减消元。先两边同乘 A 的逆矩阵 （mod 127 意义下）让 向量暴露在外面：

然后相减：

其中 都是已知常量。为了简洁，分别设为 ：

（注意正负，这里统一表示为加法，方面后面构造格时候的理解）

这个式子还是不太直观，我们把向量完全展开再看：

这里展开后的向量的每个分量所在的行都代表着一个等式，一共有 32 个。
其中 的后 16 个分量，它们是未知的随机数，我们不想去关注它们。
所以对于这 32 个等式，我们抛弃掉后面 16 个，只保留前面 16 个：

这里 e1 和 e2 向量的分量并没有减少
对于 D1 和 D2 矩阵，则只剩下了前 16 行。把它们分别记作 D1' 和 D2'，简化如下：

其中 矩阵 与 向量 的乘法，可以拆分为 矩阵列向量 与 被乘向量的分量 的乘积再求和：

上面 分别表示 矩阵的 32 个列向量； 也是向量，但 都是整数。

同样，为了看起来直观一些，我们把向量都展开：

同样，每个分量所在的行都是一个方程，共 16 个

mod 127 的存在会带来麻烦（格规约要在整数空间上进行）。注意到 ，只需要再引入 16 个变量 分别表示每行的计算结果除以 127 取整的值，就可以将取模转换为向量的乘加：

上面的等式表明这 32+32+1+16=81 个向量的存在一个线性组合，其结果是短向量 ，并且这个线性组合中各个向量的乘数分别是

这就是最短向量SVP问题，新格子的雏形已经出现了，即：这 81 个列向量转置为行向量，再顺次排布形成的矩阵：

直接在这个矩阵上应用 LLL 或 BKZ 格规约算法，得到的结果中确实有一个全为 0 的行，但是不知道每行的乘数具体是多少。

获得每行乘数的方法通常是在格矩阵右边补上一些列，这些列的某一行设为1。当乘数乘到这一行时1也会被乘到并带到最终结果中，这样就能从结果中获知得到该结果行的线性组合中对应于该原始行的乘数是多少。

我们期望获得的全 0 结果行对应原始行的线性组合乘数分别是
对于求解原始的带误差模质数方程组，知道 的值不会带来任何帮助，但知道 就可以直接求解。另外 的取值只会是 0 或 1，即使把它作为乘数保留到 结果行 中，结果行 的向量长度仍然很小，因此格规约仍然有很大概率能找出此行。

具体增补方案就是在前 65 行右侧补一个单位矩阵，即：

分块表示：

虽然乘数分别为 时确实可以得到一个前 16 列都为 0 的行，但这不是唯一的解（因为如果只看前16列，向量的个数远超于 16 个），所以需要在增补的部分进行过滤筛选。

注意到误差项 $e$ 的各个分量一定是 0 或 1，且 $d$ 向量作为常量项系数也一定是 1，因此可以用这两个条件筛选格规约后的结果行。
（另外，CVP 问题对最短向量的方向没有限制，因此有一半概率找到的最短向量是反方向的，此时增补部分的乘数都是负数，但仍然是合理答案）

具体的，格规约后的结果行需要满足：

1. 前 16 列都是 0
2. 第 81 列必须是 1 （或 -1）
3. 第 17-80 列只能是 0 或 1 （如果第 81 列是 -1，则第 17-80 列只能是 0 或 -1）

对上面的格直接应用 LLL 或 BKZ 算法，发现并不能找到同时满足三个条件的结果行。

原因主要是 LLL 或 BKZ 算法只能找到近似的最短向量。这里构成的格的 81 个向量本身都不是很大，因此直接格规约找到的近似解不一定是最短解。

通常，只有在原始向量很大且线性组合的最短向量很小时， LLL 或 BKZ 算法才能获得较好的效果。
注意到筛选条件有一个是前 16 列都是 0，因此可以给格矩阵的前 16 列都乘上一个很大的常量，从而在放大了原始向量的同时不影响期望得到的 结果行 向量。

这里随手取了 magnification = 100000，然后应用 BKZ 算法（实测 LLL 算法还是不行），成功找到了唯一符合三个条件的结果行。

现在误差项 都已知了，只需代回原始方程即可解出 ，并且可以验证它们的前 16 个分量确实相等。

取前 16 个分量组合为 bytes 再 hexencode 得到一个字符串，输入到程序后成功通过了检查。

sage代码：

由于程序中的矩阵乘法是在 mod 127 意义下的，而输入字符的取值范围是完整 0-255，理论上需要爆破 16 个字符每个 2-3 种可能的取值。出题人没有在这里增加复杂度，所以原始解直接通过了魔改MD5的检查。
但是，即使是通过验证的答案，对两次调用 sub_140000478 得到的返回值的四处检查也是无法通过的，即：程序中对答案是否正确唯一生效的检查只有魔改MD5。这一点感觉不是很好，建议还是让程序中的关键线索（即矩阵乘法）也进入最终检查输入是否正确的关键路径中，对于正确的输入，程序中能够明确检查矩阵运算结果与预设值相等。（万一有人真的破解了魔改MD5，题目的核心逻辑不就完全无用了么）

另外，对于单个矩阵方程，误差量 $e$ 只有 32 位长，而 $2^{32}$ 是完全可以尝试爆破的。要避免爆破，感觉至少也要 64bit 起步更稳妥。

后记

附件是做了部分标记的IDA数据库文件（需要 7.7 或更高版本），供参考。

（咕了一星期，总算写完了）

（P.S：不支持LaTeX公式太难受了）

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课