KyberSlash漏洞与crystals-go库：回顾与修复技术解析

引言

本文讨论一个涉及开源库的安全事件，该库由Kudelski Security的一名硕士生在论文期间开发。该库名为crystals-go，是Go语言实现的NIST选定抗量子密码算法Kyber和Dilithium（现分别批准为ML-KEM和ML-DSA）。该库被发现存在近期发现的时序攻击漏洞KyberSlash，该漏洞影响特定Kyber实现。需强调crystals-go库已无人维护：它于2021年作为开源研究项目发布，未用于生产；Kudelski Security从未在任何商业产品或服务中使用该库。尽管如此，我们决定过度谨慎处理，因之前未正确标记库状态，不确定是否有人在实际中使用。因此，我们修补了crystals-go以防御KyberSlash，并将在本文中介绍修复过程。

KyberSlash1与KyberSlash2

Kyber（现称ML-KEM）是基于模格的关键封装机制（本质是公钥加密方案），作为NIST PQC标准化竞赛的一部分提交。存在C语言参考实现及多种其他编程语言库。该漏洞（虽非Kyber理论方案本身问题）影响许多实现，由研究人员Goutam Tamvada、Karthikeyan Bhargavan和Franziskus Kiefer发现，后于2023年底由Dan J. Bernstein教授独立发现。它是通过时序侧信道泄露秘密的经典案例。初始问题在Kyber的poly_tomsg解码过程中发现，称为“KyberSlash”；但后来，研究人员Prasanna Ravi和Matthias Kannwischer在poly_compress和polyvec_compress过程中发现相同问题。此后，经Dan Bernstein提议，命名规范变为：poly_tomsg中的特定漏洞为“KyberSlash1”，poly_compress和polyvec_compress中的问题为“KyberSlash2”（统称“KyberSlash”）。

KyberSlash的问题是可变时间除法：代码中存在除法步骤，其执行时间（CPU周期数）可能依赖（秘密）输入而变化。通过制作恶意密文并诱骗目标用户解密，可通过精确测量时间差提取完整密钥。此类攻击可能毁灭性，过去多次出现在不同安全公告中，且多数案例有实际利用。因此必须高度重视KyberSlash。

更详细地，问题出现在上述例程的步骤中，其中某些秘密值被常数除。例如：

1

t = (((t << 1) + KYBER_Q/2)/KYBER_Q) & 1;

以上代码行（取自修复前Kyber参考C实现）中，t是临时变量，存储多项式秘密系数并执行代数操作，KYBER_Q是方案相关常数，值为3329。

问题在于除以KYBER_Q。/KYBER_Q操作在每次发现KyberSlash漏洞时出现。一般而言，现代CPU架构通过单个div汇编指令实现整数除法。但div指令计算量很大（CPU周期数）；它通常是整数最慢操作，需多周期完成。更糟的是，周期数几乎总依赖输入大小，可能导致时序攻击。因此，“原生”整数除法在代码中对性能和安全都是痛点。

为避免计算开销和优化速度，现代编译器通常“足够智能”以理解除数为常数时，默认使用某些技巧加速。具体地，它们用mul（乘法）和shr（右移位）组合替换单个div指令，使得对被除数的操作结果相同（后续详述）。单个div指令在现代架构上成本高（CPU周期数），等效的mul、shr加必要mov（移动）指令组合几乎总更快。额外好处是，在多数架构上，这些简单指令有恒定周期成本，因此所得除法算法实际是常数时间。此技巧因此是性能和安全双赢：现代编译器默认一直使用它。这就是KyberSlash漏洞从未被发现的原因。

但需注意：确实存在上述情况不发生或不适用案例。例如：

（罕见）未实现shr的架构，或无法很好管理此操作的编译器；
（较常见）mul非常数时间的架构；
（更常见）优化代码大小而非速度的编译器。

事实上，查看操作码大小时，单个div指令总比多个简单指令组合占用更少空间，因此优化代码大小的编译器标志会禁用上述速度优化。

此直觉通过概念验证利用测试和验证，确认对许多实现可能发生毁灭性密钥恢复攻击。因此，KyberSlash被处理为“高”严重性漏洞，参考代码和其他受影响库通过强制显式常数时间除法技巧快速修补。

Crystals-go

我们的库因安全属性突出。在原始实现报告漏洞中，我们集成大多数对策，提供理论和实践安全的库。我们预测候选方案优化时会发布新攻击，并期望代码随库安全作为持续过程变化。

这导致几周前沟通事件，当crystals-go被发现是多个受KyberSlash影响库之一。

事件

2024年1月8日，我们获知crystals-go出现在Dan Bernstein维护的受KyberSlash影响库列表。此被某些科技新闻媒体报道[1][2]，甚至有人声称“Kudelski Security受KyberSlash影响”。我们清晨接到PR/市场部门电话…

我们立即意识到无人以暗示方式“受影响”，整个事件仅是误解。但无论如何，我们应归档项目并记录状态，因此现在必须采取行动。

我们本可归档仓库并停止，但觉有责任修补当前代码问题，因不知是否有人生产中使用此库（仅知我们未用），或更广影响可能是什么。

修补KyberSlash

我们从修补KyberSlash1开始。这容易，基本从C参考实现修补复制粘贴。

对于KyberSlash2，情况不直接。原因是crystals-go基于旧版参考代码构建，某些内容略有不同。最重要的是，crystals-go支持Kyber方案某些早期参数，后从标准移除，特别是d（压缩多项式数组时每系数位数），在crystals-go中可取值3、4、5、6、10或11（而当前参考实现支持集合更小）。

因此，首先必须决定如何继续。一选项是实际移除未用参数，然后从参考实现复制粘贴KyberSlash2修补。这会更优雅，但我们反对此选项，原因有二：

对废弃项目花费时间过多。crystals-go结构不同于当前C参考，某些函数在不同文件，其他函数合并为一…我们将不得不重度重构代码，因此首先必须非常熟悉它。过度。
最重要的是，我们不能确定是否有人因支持这些传统参数而使用crystals-go库进行研究或任何目的。

因此我们决定为所有参数修补KyberSlash2，甚至那些参考实现当前不支持的参数。但这需要很好理解修复背后的数学和工程，而非仅复制粘贴。

基本地，为修补问题，我们需要在代码中强制编译器在“正常”条件下应做之事：即，用等效常数时间操作序列替换/KYBER_Q除法。让我们从看KyberSlash1开始。回顾KYBER_Q是常数（3329），再看参考C实现中原始易受攻击代码片段：

1

t = (((t << 1) + KYBER_Q/2)/KYBER_Q) & 1;

这被官方修补为：

1
2
3
4
5


t <<= 1;
t += 1665;
t *= 80635;
t >>= 28;
t &= 1;

这里发生什么？那些其他常数从何而来？1665似乎是KYBER_Q/2的上取整（ceil），但其他呢？

类似修补也出现在参考实现中易受KyberSlash2攻击代码。例如，在polyvec_compress中，易受攻击行：

1

t[k] = ((((uint32_t)t[k] << 11) + KYBER_Q/2)/KYBER_Q) & 0x7ff;

被替换为：

1
2
3
4
5
6


d0 = t[k];
d0 <<= 11;
d0 += 1664;
d0 *= 645084;
d0 >>= 31;
t[k] = d0 & 0x7ff;

但现在常数不同，甚至KYBER_Q/2的舍入是下取整（floor）而非上取整。如何解释？

嗯，工作原理如下：总可将除法x/y视为x * (1/y)。处理整数时，当然无法表示1/y，但可近似1/y结果为z / 2^s对某些值z和s，因为除以2^s仅是shr（右移）s位，也写作» s。换言之，可通过计算(x*z) » s近似x/y，其中z是尽可能接近(2^s)/y的整数。当除数是常数时可预计算和硬编码，这正是此处发生：在我们案例中，所有那些常数如80635和645084是形式round(2^s/KYBER_Q)对某个s（且s正是后续右移值，即上述两例中28和31）。

但如何选择好s？为何它们案例不同？嗯，记住如果需要正确（整数）结果则需要好近似，因此理想地想用给出最佳可能近似的s，且容易看出，通常s越大，近似越好。但用太大s会导致乘法后变量溢出，这意味着将丢失结果某些位，从最高有效位开始。在我们案例中，多项式系数压缩期间，我们只对除法结果的d个最低有效位感兴趣（注意最后指令&是与所需长度全位掩码的逻辑AND布尔运算符，返回最后d有效位）。因此想用最大s允许在» s操作后保留d位。这依赖变量大小：如果变量适配32位寄存器，则s = 32 - d，这是KyberSlash1中poly_tomsg和KyberSlash2中d=3,4,5,6的polyvec_compress案例。在d=10,11案例中，我们使用64位变量，因此理论上可承担更好近似，但过度，且保持操作数32位值加速计算，因此我们坚持最大s=32。

仍需理解为何KYBER_Q/2有时近似为1664，其他时候1665。这是为“补偿”来自除法的其他舍入：如果我们用下舍入常数（如首例80635），则通过上舍入KYBER_Q/2为1665补偿，否则（如第二例645084）下舍入为1664。

理解此允许我们为这些传统参数修补crystals-go对抗KyberSlash。

状态与结论

修补crystals-go后，我们发布安全公告并归档crystals-go仓库，提醒所有人不应生产中使用该库。此后，我们通知上述科技新闻媒体，它们非常专业地更新文章。我们还联系NIST PQC社区，Dan Bernstein及时更新易受攻击库跟踪页面。我们再次确认crystals-go从未用于Kudelski Security任何商业服务或产品。项目现从我们侧未维护，因想聚焦其他项目，但欢迎分叉，这是开源力量！

最后，我们正实施内部过程以减少未来类似事件可能性。