两个 RNG 输出的异或会比其中一个更安全吗?

信息安全 随机的
2021-08-24 09:55:10

假设我怀疑一个或多个(伪)随机数生成器存在密码缺陷,甚至可能是故意后门的。在这种情况下,RNG 可能是 PRNG 算法、硬件随机数生成器或某些 OS 提供的原语,其来源可能是其中之一。

通过使用其输出的异或和其他一些 RNG 的输出来“加盐”RNG 会是一件坏事吗?后一个 RNG 的质量可能要低得多,但不太可能被同一个攻击者破坏 - 例如,您的硬件制造商可能已经破坏了您的硬件 RNG,但他们也不太可能将标准委员会引导到DUAL_EC_DRBG或贿赂您的操作系统供应商,让其将漏洞潜入加密原语

鉴于对篡改加密标准委员会的持续披露,开始使用多个随机源的异或似乎是谨慎的,其中至少一个是“高质量”并且至少其他一个具有非常低的“攻击”相关”与之相关。

2个回答

有细节。

这取决于您的两个 RNG 有多么不同,或者更恰当地说,是不相关的概念。让我们用密码学的眼睛来看它。

“破坏”RNG 意味着观察n位输出,然后以远高于1/2的成功概率预测n+1位。加密安全的 RNG 在实践中将是加密安全的 PRNG,它将内部状态确定性地扩展到所请求的尽可能多的位。我们假设攻击者知道代码(如果只是通过逆向工程,或者通过向开发人员支付啤酒);因此,RNG 输出与 RNG 的内部状态完全一样未知。通用攻击是对状态值的穷举攻击,如果可能的状态值空间很大(例如超过 128 位),这将过于昂贵。PRNG 是加密安全的如果最著名的攻击是通用攻击并且该攻击确实不可行。

正式的设置是给攻击者n位的 RNG 输出(我们称之为r 1),并挑战预测n+1位。现在假设“两个 RNG 的 XOR”结果很弱,这意味着给定r 1 XOR r 2(一个n位序列),攻击者可以以高于1/的概率计算该序列的n+1位2 . 那么攻击者只需......自己产生r 2他构建了第二个 RNG 并运行它,输出r 2他完全知道,异或r 2用给定的r 1然后,他对 XOR 结果应用“攻击 XOR”,这会产生r 1 XOR r 2的n+1但是攻击者以 100% 的可靠性知道r 2的n+1(他自己生成),因此他可以计算r 1的n+1

这个论点表明,两个 RNG 的 XOR 不能比单独的 RNG 弱……只要上面的正式设置是对现实的正确描述。

实际上,这里的隐含假设是两个 RNG 彼此足够无关,以至于正式攻击者可以从外部构建第二个 RNG 的适当仿真,而无需对第一个 RNG 有任何了解。这不是给定的。实际上,在给定的机器上,每个好的 RNG 都会根据“硬件事件”(例如硬件中断发生的时间,具有时钟周期精度)的度量来计算其内部状态的初始值;并且两个RNG同时运行在相同的硬件上,所以他们看到相同的事件......这意味着上面的正式描述与实际情况不匹配,这使得数学论证无效。

一个人为的例子将突出我的观点。假设 RNG1 采用初始种子S并将其用作 CTR 模式下的 AES 密钥(使用 AES 对计数器的连续值进行加密,从 0 开始)。这是一个很好的、强大的 RNG,密码学家不会回避。现在将 RNG2 也定义为 CTR 模式下的 AES,但要使每个输出位反转(值 0 的位变为 1,反之亦然)。种子 RNG2 具有相同的S单独来看,RNG2 很容易被证明在密码学上与 RNG1 一样强。密码学家很容易在其强度上赌一品脱吉尼斯啤酒。但是,假设您将 RNG1 和 RNG2 的输出异或在一起;然后你会得到……一长串的 1,而不是一个 0。这非常弱,因为n+1 然后可以以 100% 的可靠性预测 bit 为 1。

然而,毫无疑问,RNG1 和 RNG2 是“不同的”。它们不会产生相同的位序列。这表明“不同的输出”在这里不是一个好概念。我们想要的是不相关的 RNG,形式化为:攻击者可以在不知道第一个 RNG 内部状态的情况下构建第二个 RNG 的仿真。如果两个 RNG 都是从同一个硬件播种的,那么不能盲目地假设这两个 RNG 是“不相关的”。


结论:在同一硬件上运行的两个 RNG 的 XOR在实践中可能比单独的 RNG 弱。XOR 是否强大取决于 PRNG 的加密内容“如何”隐藏一个共同的种子。另一方面,如果你可以安排不相关的播种(你用种子S 1播种 RNG1 ,然后用另一个种子S 2播种 RNG2 ,并且你有充分的理由相信S 2与S 1无关),那么,在这种情况下,两个 RNG 的 XOR 不能弱于单独的 RNG。

我建议你不要沉迷于此类游戏。仅当您对它们的播种方式有足够的了解,以便您可以确定其中任何一个单独是否强大时,将两个 RNG 异或在一起才能为您提供一些安全保证。如果你知道一个RNG很强,那就用它吧。如果两个 RNG 都很弱,那么两者的 XOR 很可能会同样弱。对两个 RNG 进行异或唯一确定的事情是,它增加了计算成本,更重要的是,增加了复杂性复杂性不利于安全。

如果你做对了,你需要确保一个 RNG 不知道另一个 RNG。

这是重点。即使你推出自己的 RNG 并且做得很糟糕,你也无法通过对两者进行异或来削弱现有的 CSPRNG。什么都不知道意味着没有关于所用熵的信息,并且在两者进行异或之前无法访问现有 CSPRNG 的输出。

因此,您可以使用这种策略来获得两全其美,一个不能被削弱的 DIY 实现,以及一个经过测试并受到很多关注的知名生成器。这也是美白的好方法。