G.O.S.S.I.P 阅读推荐 2025-06-04 AVX512 大整数乘法的艺术

乘法很简单，一年级的小学生都会秒算8x8等于几，但是涉及到非常大的整数的乘法，要算得又快又准，就没这么简单了。乘法运算的这种“简单的复杂性”，让它天然成为了一个 proof of work（PoW）的标尺。不过，有些人（或者硬件）天生就比别人（或者别的硬件）更会计算，那么今天我们要来看看，黑客是如何通过“算得更快”拿走五万美元奖金的（标题党，请忽略）。

在 CTF 比赛中，为了防止别有用心的选手对答案进行暴力搜索或者恶意消耗服务器资源，解题前需要进行PoW操作是一个非常常见的防护手段。而就在一周前的 Google kernelCTF（kCTF） 比赛中，一位选手的操作，让主办方做出了如下图中所示的决定（取消掉以后比赛中的PoW），这究竟是为什么呢？

先介绍一下背景，这个kCTF比赛设计了一个奇怪的提交机制，为了省钱，服务器每两周开放一次，所有选手都必须在每次开放的时候先集中求解 PoW，然后才能提交利用代码（exploit）去获取flag，最终只有第一个提交正确答案的人才能拿到奖金。我们今天这篇文章的作者（Crusaders of Rust CTF Team 的成员），他的队友之前已经搞定了一个Linux packet scheduler里面的UAF漏洞（具体代码问题见下面的commit），准备要去拿kCTF的奖金了，却担心可能因为PoW这关过不了拿不到钱，于是就找到了我们的作者，结果通过我们的作者的一点微小的贡献（原文“small but unique contribution”，原来老外也挺膜啊），最终成功拿走了奖金。让我们一起看看到底这里面有什么门道。

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=ac9fe7dd8e730a103ae4481147395cc73492d786

在这次比赛中，PoW实际上依赖的是一个叫做“树懒”（Sloth）的 verifiable delay function（VDF）函数运算（如下图），它本质上就是一个有限域的平方运算，是Arjen Lenstra和Benjamin Wesolowski在2015年的一篇论文 https://csrc.nist.gov/csrc/media/events/workshop-on-elliptic-curve-cryptography-standards/documents/papers/session1-wesolowski-paper.pdf 里面介绍的。在比赛中，PoW要求这个VDF迭代很多次，并且数据大小为1280bit。

提升VDF运算速度的第一个思路总是首先考虑使用数学上的办法进行优化。由于模数是一个梅森素数（形如 2^p - 1），所以求余操作可以简化成如下形式：

做完这一步优化之后（当然也包括用C++重写，再加上-march=native 和 静态链接等黑科技），PoW 运行时间已经从原先的 4s 左右减少到 1.4s 左右。但是作者认为还是不保险（还要卷），执意要打破这个顺序运算过程不能并行化的魔咒，并搬出了两个神器：AVX512指令集中的 vpmadd52luq 和 vpmadd52huq 指令（本质就是做8路并行的52bit乘法，并且将结果的低位/高位加到指令中的第三个操作数中）。考虑到原来 PoW 中要求的数据是 1280 bit，可以划分成 25 * 52 bit 进行运算，这样就可以用上这两个指令了。

此外，由于要实现的是平方操作，很容易想到把运算数据划分成平方项和交叉项两个部分分别运算，进而减少乘法的次数：

对于交叉项，本文的作者设计了一个巧妙的“滑动窗口法”，以此让运算结果能够在寄存器中按照正确的顺序排布，并且将重复计算的部分通过AVX512的掩码操作给去除掉。具体的实现方法就不在此赘述了，大家如果对这部分细节感兴趣，欢迎仔细阅读原文：

https://anemato.de/blog/kctf-vdf

而对于平方项，就是最直接的对应位置相乘，把得到的高位低位结果进行重新排列，最后把排列后到数据累加到对应下标位置到结果中去。最后处理完成进位数据后，根据梅森素数的特点进行取模操作。

最终在优化完毕后，在搭载 Zen5 架构、原生支持全功能 AVX512 的 AMD Ryzen 9950X 上测试，PoW 的执行时间被压缩到了令人震惊的 0.45 秒！我们不得不高喊：AMD Yes！

当然，考虑到这位作者的优化能力，我们强烈建议这位选手去参加莫队交易赛，不要来跟我们卷CTF了 顺便打个广告，如果你想体验一下全功能版本的AVX512的运算能力，当然是要去使用最新的AMD处理器，而刚好有一个叫做G.O.S.S.I.P的研究组采购了大量这类处理器（Ryzen 9600x和9700x），而且同样拥有在这方面具有丰富经验的代码优化大师，如果你感兴趣，欢迎大家来报名它家的暑期实习哦~~~

文章：https://anemato.de/blog/kctf-vdf

原文始发于微信公众号（安全研究GoSSIP）：G.O.S.S.I.P 阅读推荐 2025-06-04 AVX512 大整数乘法的艺术