曾经, 我写过一篇 肘击 Tsinghua-Secure 的文章. 里面提到, 通过字典爆破的手段, 可以拿到约 30% 的密码, 而其中 25% 左右与主密码一致. 但是呢, 我不是很满意 - 也不叫不是很满意… 这学期上课有一节对称密码分析, 讲到分析对称密码的种种手段, 于是我有点手痒痒, 总想整点活. 那么有没有一个没那么安全, 已经要弃用, 但是由于各种历史原因还在用的对称密码呢? 看过前述博客的朋友就要说了, 有啊, DES 密码就是这样的一个密码. 其只有 56bit 安全性, 已经挡不住现在的先进 ASIC 了; 但是用平常能买到的 GPU 倒还是需要一些时候才能爆破.
那么, 对 DES 的已知明文攻击是否能进一步优化呢? Hashcat 的 DES Kernel 是已知优化较好的实现, 在 4070S 上的速度大约是 60.4 GK/s. 我们选择在它的基础上进一步优化. 由于这是一个目标明确 (优化 DES Kernel 性能) 且可以检验 (可以在实际硬件上直接跑, 取得实际性能), 又存在多个方向可以尝试优化的工作, 我们注意到, 他与 AutoResearch 要解决的问题十分相似. 搜索 AutoResearch 的一般实现, 我们能看到 AKO4ALL 这样一个项目, 其与我们的需求基本一致.
基于此框架, 我使用 DeepSeek V4.1 Flash 模型慢速运行了几天, 得到了 23 个正向优化, 采用了 16 项, 优化后速度为 89.1 GK/s, 同频速度提升 44.3%, 同功率下速度提升 47.5%.
代码以 MIT 协议开源于 GitHub, 仅供学习交流使用.
AutoResearch 的设计与执行方式
对于 AutoResearch 工作而言, 最重要的可能就是其考察方式与评价指标. 传统的 AutoResearch 的架构应该是试验 --> 验证 --> 有优化保留, 无优化回滚, 而我感觉这种比较暴力的方式容易让 Agent 死循环, 而对于算子优化, 有时候会有不同的路径和方法, Agent 第一次尝试的时候不一定能把一条上限更高的路线优化得比现有的成熟路线更好. 因此, 我选用了一种更广的搜索策略: 让主 Agent 管理子 Agent 的探索方向, 对各种不同的方向的上限进行估计和赋权, 尽可能先搜索更优的方向, 而把 “最优” 的标签贴在全局最优解.
在设计上, 我让 Agent 把 hashcat 的 DES kernel 抽出来成为一个简短的可测试的程序; 然后定义好测试的脚本不可动 (相当于 OJ), 建立独立的 research 仓库以保存实验路线, 历史, 和各个检查点. 由于我只有一颗 GPU, 我要求各个子 Agent 不得在 GPU 上实际执行, 只允许使用 CUDA Toolkit 进行编译, 检查 kernel 来推定性能, 由主 Agent 统一调度在 GPU 上做性能测试.
同时, 我要求主 Agent 如果三次未能取得有效加速, 则应该对当前最佳 kernel 进行细致的 profiling, 弄清楚当前性能热点和卡点, 进而寻找新的优化方向. 如果拿不准主意, 则可以调用 codex 的 Astra 模型来给一些意见.
遇到的各种神秘问题与解决方案
GPU 测出来误差巨大
一开始的时候, 我没有给 GPU 锁频; 而我的 4070S 发热太大, 运行几秒就轻微降频了. Agent 测出来的结果忽高忽低, 干扰严重. 好在我当时看了一眼我的 claude code, 发现了这个问题. 后续, 我把我的机箱风扇拉满, 并让 Agent 在 2GHz 时钟下定频测量, 稳定性提升明显, 其多次测量误差减小至 0.3% 左右.
Subagent 停不下来
中途还发现了若干次, 看上去所有 Agent 都觉得自己干完了, 但是 Subagent 不自动退出, 主 Agent 也没有被唤醒的情况. 咋回事呢? 一看发现是有时候 Subagent 的 Shell 命令写错了, 死循环了, 导致一个 Shell 命令跑好几个小时; 然后子 Agent 又把这事情忘了, 觉得自己所有活都干完了. 于是 CC 觉得有 Shell 命令挂着所以不能退出, Shell 又不可能退出, 就永远挂在那里了. 临时的解决方案是把那些跑了几个小时的 shell 给 kill 了; 而更本质的解决方案可能是让 Agent 给所有 shell 命令加 hard timeout… 但是感觉也不本质.
Agent 想不到一些方向
这可能确实是 DeepSeek 没那么聪明导致. 有时候我看了他的研究进展之后总觉得哪里不对劲, 问他, 他就表示 “哦你说的对”. 这怎么办呢? 这也是我后来改成, 如果他觉得没货了, 就问 Astra 的原因.
AutoResearch 大致过程
本章节主要由大模型生成. 我实在是不想总结几十个 Agent 干了啥.
真正开始优化后，我先让 Agent 建立一个正确、可重复测量的基线，再分别尝试不同方向。按 Git 里实际留下的 best-cuda 版本来算，一共采用了 16 个优化版本。有些版本后来又组合到一起，所以数字不能简单相加。
最早的 W1 把两条基础路线合在了一起：一条把已知明文、密文在编译时专门化，另一条精简子密钥生成和 lane mask。两条路线单独测都有收益，合起来比基线快了 7.60%。这说明固定输入和 key schedule 都有可以省掉的工作。
接着是 R1。DES 跑到第 15 轮后，利用一个必要条件先筛掉不可能命中的密钥，避免继续做第 16 轮。这是当时最大的单项提升，快了 8.09%。N1 则观察到许多子密钥位在一批候选中是统一的 0 或 1，可以把一部分 XOR 换成 IMAD，让 ALU 和 FMA 两条管线同时工作。同频测试提升 5.69%；但在 GPU 顶到功耗墙时，提升会明显变小。
后来有几条路线继续压缩 S-box 输出附近的工作。A1 把一个输出 XOR 折进 S-box 网络，提升约 0.63%；AB2 又调整了另外两个盒子的输出，较前一版提升约 0.95%；AB4 再折叠两个输出，阶段成绩达到 65.07 Gkey/s。N1S 调整了 lane 变化位的展开方式，较前一版提升 2.59%。这些收益都不大，但都经过了实际测量，最终版本也保留了相应改动。
PRG 把第 15 轮的拒绝条件拆成逐步筛选，让大多数候选尽早退出，阶段成绩达到 64.47 Gkey/s。PRGSPEC 把这套筛选方式也用于另一条编译路线，在那条路线里提升了 4.73%。OH16 则把第 16 轮和密文比较移到 CPU 端处理，设备只报告少量幸存候选，提升约 0.92%。之后的 NOPUB 把结果发布过程并入已有计算链，收益只有约 0.13%，但实测仍略有提升，于是也留下了。
通用路线也有自己的优化。GENLAND 在不依赖编译期固定明文、密文的路径里加入第 15 轮筛选，提升约 7.01%；GENPROG 再把筛选改成逐级拒绝，提升约 5.11%。另一个方向 BUDSWEEP 调整了子密钥相关指令的组织方式，单独测得约 3.72% 的提升。最后 GENCOMB 把它和 GENPROG 组合起来，实测组合收益超过了简单相加，说明两种改动在这条路线里能互相配合。
PIPEBAL 调整关键指令的排布，让不同计算管线更好地并行，实测后作为默认版本保留。最后的 R1INV 针对已知明文对应的首轮输入做专门处理，提升约 1.03%，但只对编译时已知明文、密文的路线启用。这里的首轮输入仍然依赖运行时密钥，所以它不是把首轮计算直接删掉，而是利用固定输入条件做了专门优化。
此外，调整 CUDA block 大小也有收益：从 128 改到 256 时，设备代码本身没有变化，但实测速度提高了约 0.69%；在通用路线里提高约 2.76%。这让我意识到，除了 kernel 里的指令，启动配置本身也可能影响最终吞吐。
并不是每条路线都能带来提升。重新综合 S-box、尝试跨盒共享、使用 Tensor Core、压低寄存器数量、增加每线程处理的候选数，以及减少分支或缩小代码，都没有找到能稳定超过当前最佳值的版本。有些想法静态看起来省了指令，实际却因为额外的数据整理、寄存器压力或控制流开销而变慢。最后能留下来的，都是在同一套测量条件下确实跑得更快的实现。
试图 merge 回 hashcat
在做了这么多 AutoResearch 之后, DeepSeek, Astra 和我都觉得这个 kernel 差不多了. 是时候 merge 回 hashcat 看看了? 一看发现不对. 怎么 hashcat 还有各种掩码啊啥的输入啊, 我在 AutoResearch 的时候一直都按照 Full Keyspace Search 做隐性条件, 上面说的不少优化没办法正确并入 hashcat. 怎么办呢? (不过说实话, 我也没那么想去 contribute…) 于是我决定让 Codex 另起炉灶.
DES Search
于是就有了 DES Search 这个仓库. 我让 Codex 写了一个尽可能小的, 功能尽可能精简的程序, Codex 选择了 Python. 我让他加入了多卡支持, CUDA_VISIBLE_DEVICES, 多哈希支持; 他自己往里面填了 range support 等. 我拿这个程序在我能找到的显卡上简单测试, 得到了以下结果:
| GPU | Architecture | Cards | Total throughput (GK/s) | Speedup vs. one card |
|---|---|---|---|---|
| GTX 1660 | sm75 | 1 | 21.773 | - |
| GB10 | sm121 | 1 | ~32.4 | - |
| RTX 4070 SUPER | sm89 | 1 | 89.1 | - |
| RTX 4090 | sm89 | 1 | 201.7 | - |
| RTX 4090 | sm89 | 8 | 1572.501 | 7.80x |
同时, 由于 NetNTLMv1 的每个 MD4 会被拆成两个半 Key 用于加密同一个 Challenge (也就是 DES 的明文), 因此我们在搜索的时候, 可以在最后的 early return 处同时校验两个 Key, 而不用两个独立搜索. (是否可以认为此处加速了接近 100%?)
问了一下 GPT, 他没有搜索到更好的结果, 所以, 或许这是目前世界上最快的 DES Kernel? 在这个速度下, 8 卡 4090 可以在 12 小时遍历 56 比特的密钥空间.
虽然好像也没什么用吧 (