累积测试向量
我喜欢测试。我特别喜欢可重用的测试向量库。有时测试向量是精心手工制作的，针对的是晦涩的边缘情况。这些向量属于Wycheproof或上游规范。但有时向量是通过纯粹的暴力产生的。枚举每个可能的输入并检查输出。尝试一百万个随机输入，看看会发生什么。组合每个参数的所有可能输入大小。制作一个非常非常大的输入。
这些向量可能非常有效，并且不需要事先了解你正在寻找的错误。如果你运行30万次随机测试，你有99%的机会遇到任何2⁻¹⁶的边缘情况。¹
例如，你可以通过生成随机密钥对，将公钥传递给Encapsulate，将生成的密文传递给Decapsulate，然后确保密钥、密文和共享秘密符合预期，来很好地覆盖新的后量子算法ML-KEM的内部结构。² 参考实现提供了一个程序来生成包含10,000个这些已知答案测试的语料库。
问题是——除非结果明显正确³——你需要实际在某处检查输入和预期输出。那些ML-KEM向量即使压缩后也会达到几十兆字节。检查参考实现也不理想，因为它具有不小的体积、不兼容的构建系统以及不同的支持环境。
这里有一个我称之为累积测试向量的技巧：定义一个测试，从确定性源⁴（如可扩展输出函数SHAKE128）中抽取随机输入；将输出累积到哈希函数中；并检查预期的最终哈希。这是一个简单的想法，可能被多次重新开发，但我之前没有看到过文档记录。
以下是运行10,000个随机ML-KEM测试所需的所有内容，相当于参考实现中的测试：
使用空输入实例化SHAKE128，称之为r。实例化另一个SHAKE128，称之为a。从r中抽取一个ML-KEM-768种子，将其传递给KeyGen_internal。将ek写入a。从r中抽取一个消息，将其传递给Encaps_internal。将ct和k写入a。运行Decaps并检查k是否匹配。从r中抽取一个无效密文，将其传递给Decaps。将拒绝的k写入a。总共重复10,000次。从a中抽取16字节，它们应匹配8a518cc63da366322a8e7a818c7a0d63。
与几十兆字节的JSON相比，这真是天壤之别！
这种方法也随着可用CPU时间而良好扩展。在Go中，我们在-short模式下运行100次迭代（在预提交检查中），默认运行10,000次（在CI中花费几秒钟），并根据需求运行1,000,000次（用于开发）。最后一个将需要超过千兆字节的向量，而我们只检查三个哈希值。
与JSON向量一样，累积向量在实现之间可重用，只要生成器和累加器足够简单且广泛可用。ML-KEM向量可在CCTV上获得。
除了纯随机输入外，还可以定义累积测试来系统地探索大范围的输入参数和大小。例如，我们有一个累积的cSHAKE128测试，它遍历N大小0到200、S大小0到200以及输入大小100、168、200的组合（以覆盖低于、匹配和高于“速率”或块大小的值）。这同时测试了多个连接点：长度前缀编码、输入分块和填充。它被编写为一个通用测试，旨在覆盖特定错误，但在重构期间立即发现了一个不相关的问题。
最后，你可以做类似的事情来“压缩”单个大向量。例如，我们现在通过从SHAKE128中抽取并检查预期输出来测试大于512MiB的cSHAKE个性化字符串（其大小以位计会溢出uint32）。使用确定性源使我们能够轻松地将结果与其他实现进行比较，尽管尝试了几次，因为我们尝试的第一个实现也有一个错误。
累积向量的主要缺点是如果测试失败，它不提供调试的洞察力。我认为这被其优点所充分证明，并且在常见场景中大多得到缓解：在首次开发实现时，中间值比测试向量更有用，而在进行更改时，你通常知道你接触了什么并可能破坏了什么。许多密码学工程仅依赖于二进制结果代码盲目寻找错误！这是乐趣的一部分。
如果你读到这里，你可能还想在Bluesky上关注我@filippo.abyssdomain.expert或在Mastodon上关注我@filippo@abyssdomain.expert。
图片
罗马我最喜欢的地方之一：台伯岛，位于河流中央。占据一半的建筑是一家拥有急诊室的活跃医院。⁵ 海岸是长时间电话通话的绝佳踱步轨道。
我有点惊讶我还没有发布这张罗马照片。到现在我肯定已经拍了一百个变体：白天、夜晚、日落、阳光明媚、暴风雨、洪水、候鸟。我喜欢水、对称性以及随时间的变化。
我的维护工作由出色的Geomys客户资助：Interchain、Smallstep、Ava Labs、Teleport、SandboxAQ、Charm和Tailscale。通过我们的保留合同，他们确保了我们开源维护工作的可持续性和可靠性，并获得了直接接触我和其他Geomys维护者专业知识的渠道。（在Geomys公告中了解更多。）
以下是其中一些客户的几句话！
Teleport — 在过去的五年中，攻击和入侵已经从传统的恶意软件和安全漏洞转向通过社会工程、凭据盗窃或网络钓鱼来识别和入侵有效用户账户和凭据。Teleport Identity旨在通过访问监控消除弱访问模式，通过访问请求最小化攻击面，并通过强制访问审查清除未使用的权限。
Ava Labs — 我们Ava Labs，作为AvalancheGo（最广泛使用的与Avalanche网络交互的客户端）的维护者，相信开源密码协议的可维护性和开发对于区块链技术的广泛采用至关重要。我们很自豪通过持续赞助Filippo及其团队来支持这项必要且有影响力的工作。
SandboxAQ — SandboxAQ的AQtive Guard是一个统一的密码管理软件平台，有助于保护敏感数据并确保符合当局和客户的要求。它提供全面的能力以实现密码敏捷性，作为一个基本的密码库存和数据聚合平台，应用当前和未来标准化组织的授权。AQtive Guard自动分析和报告你的密码安全状况和策略管理，使你的团队能够部署和执行新协议，包括抗量子密码学，而无需重写代码或修改IT基础设施。
Charm — 如果你是一个终端爱好者，加入俱乐部。Charm为命令行构建工具和库。从使用Lip Gloss设计终端应用程序到使用Gum使你的Shell脚本交互式的一切。Charm使用Go构建库以增强CLI应用程序，同时使用这些库构建以提供基于CLI和TUI的应用程序。
¹ 我坚信，在一个设计良好的密码组件中，边缘情况应该是可测试的或完全不可达的（即< 2⁻¹²⁰几率）。任何随机几率> 2⁻⁴⁰的我们可以通过暴力方式达到，但理想情况下它们都应该有随机几率> 2⁻¹⁶，以便可以在不针对的情况下有机地进行测试。↩
² 这只覆盖成功的计算。你还需要负面测试向量，例如被拒绝的封装密钥。那些更适合手工制作。↩
³ 如果你可以从结果中判断它是否正确，而无需与已知答案进行比较，你可以更简单地应用带有不变量的模糊测试，也称为属性测试。↩
⁴ 当算法提供可测试的去随机化接口而不使用天空中的随机性时，确定性地定义如何抽取输入是最容易的。↩
⁵ 去年我在那里作为救护车送达的支援EMT，看到这个我经常走过的地方在如此不同的光线下，有点奇怪。↩