朋友不会让朋友复用随机数 - Trail of Bits博客

如果您接触过密码学软件，很可能听说过"永远不要两次使用同一个随机数"的建议——事实上，这就是"随机数"（一次性使用的数字）这个词的由来。根据所使用的密码学方案，重复使用随机数可能泄露加密消息，甚至泄露您的密钥！但常识可能无法覆盖所有意外复用随机数的可能方式。有时，本应防止随机数复用的技术存在细微缺陷。

加密通道的构建原理

加密消息——即使第三方能够完全访问消息内容，也能隐藏消息含义——可能是我们认可的最古老的"密码学"活动。当今消息加密的核心结构至少可以追溯到16世纪的多字母替换密码，基本流程如下：

加密过程：

1. 将秘密消息分割成规则大小的区块，每个区块的数据被视为单个"符号"
2. 根据密钥、消息位置以及可能的前序符号，将每个符号替换为不同的符号
3. 发送加密后的消息

解密过程：

1. 接收加密消息并分割成区块
2. 使用加密过程的逆操作替换每个符号，同样基于密钥、位置和前序符号
3. 读取解密后的消息

该方案的安全性依赖于第三方无法仅通过观察加密数据来推断符号替换过程的信息。

历史上，许多密码通过观察单个加密消息中的模式被破解（艾伦·图灵破解纳粹海军Enigma加密的Banburismus技术就是著名例子）。

现代密码在设计上如果正确使用，可以完全消除这些模式。首先，我们的替换字母表要大得多——两种常用的流密码AES-CTR和ChaCha20分别使用128位和256位的块大小，这意味着字母表分别有2^128和2^256个符号。其次，有规则确保消息中的每个符号都获得不同的替换表。如果以相同方式处理每个符号，您可能会暴露底层消息的模式，就像经典的ECB企鹅问题！

最重要的是，您需要确保每条消息都被不同处理——这就是随机数的作用所在。

随机数：一次性使用的数字

AES-CTR和ChaCha20流密码都是"计数器模式"流密码。计数器模式密码使用非常简单的替换表类型：将第i个块的值x_i映射到x_i XOR F(i)，其中F是从密钥派生的所谓"伪随机函数"。

如果我们不小心，可能会泄露太多信息。当我们对两条使用相同噪声加密的消息进行XOR操作时，原始内容会重新出现！问题在于我们在每条加密消息中使用了完全相同的噪声。

在实际加密通道中，用于生成噪声的伪随机函数F会获得一个额外参数，称为"随机数"。顾名思义，该数字对每条消息应该是唯一的。如果您重复使用随机数，看到两条加密消息的第三方可以了解明文的XOR值。然而，只要您从不重复使用随机数，良好的伪随机函数将在给定两个不同随机数时生成完全不同的噪声。

漏洞详情

我们的客户正在实现一个阈值签名方案。阈值签名方案中的签名过程需要在所有参与方之间进行大量通信。有些通信是广播的，有些是点对点的。出于安全考虑，点对点通信需要既私密又防篡改，因此实现使用了名为ChaCha20-Poly1305的认证加密方案，该方案结合了ChaCha20流密码和Poly1305多项式消息认证码。

考虑一个包含Alice、Bob和Carol的三方示例。为了创建她的点对点通道，Alice分别通过Diffie-Hellman密钥交换与Bob和Carol建立两个不同的共享秘密s_B和s_C。然后，Alice设置一个全局"随机数计数器"：每次Alice发送消息时，她使用计数器的当前值发送消息，然后递增计数器。这样她绝对永远不会发送两条具有相同随机数的消息，即使在不同通道上！

不幸的是，所有参与方都将计数器初始化为相同的值（0），以相同的速率递增，并按相同的顺序发送消息。因此在第一步中，当Alice向Bob发送消息，而Bob向Alice发送消息时，他们都使用秘密s_B和随机数0！因此拦截这两条消息的窃听者可以了解它们的XOR内容。同样，Bob和Carol将使用随机数1相互发送消息，然后在下一轮中Alice和Bob都将使用随机数2。

在实际发生此漏洞的系统中，使用相同随机数的消息恰好具有高度结构性，被XOR的重要字段本身是伪随机的。这意味着窃听者无法利用这些消息进行直接攻击。然而，这种特定的随机数复用确实泄露了消息认证密钥，并允许中间人篡改某些消息，导致其他参与方将诚实方视为潜在恶意方。

修复方案

当您有通信通道时，正确管理涉及的随机数以确保从不重复使用任何随机数至关重要。一个快速但不够完善的方法是在参与方之间划分随机数空间。在上述示例中，Alice和Carol巧合地总是具有不同的随机数奇偶性，您可以有意这样做：在每个通道中，您有某种方式将一方指定为"奇数"方，另一方为"偶数"方，然后要使用随机数n发送消息时，如果您是偶数方实际使用2n，如果是奇数方使用2n+1。

然而，更好的方案是为每个方向使用完全独立的密钥：换句话说，Alice使用秘密s_AB加密发送给Bob的消息，使用s_BA解密来自Bob的消息。同样，Bob使用s_BA加密，使用s_AB解密。这就是[Noise协议框架]所做的，它要求您为发送和接收使用不同的CipherState对象。有几种不同的方法可以从单个共享秘密派生这些"方向密钥"，但通常我们建议使用经过充分验证的现有实现。

不要重复使用随机数！

归根结底，重要的是仔细评估密码系统的每个假设和限制，并确保您的所有缓解措施真正解决了威胁。“不要重复使用随机数"的一个简单心理简化是"不要发送两条具有相同随机数的消息”——在该简化模型中，全局随机数计数器是有效的！然而，随机数复用的实际威胁并不关心谁发送消息——如果任何人使用相同的密钥和随机数发送消息，您就面临风险。

大多数著名的加密通道库都能安全处理此问题，但如果您发现需要实现类似解决方案，请考虑联系我们进行密码学审查。