向更多受众解释Dual EC DRBG的弱点？

#1 楼

我不会尝试解释后门的数学原理。只需解释一下，国家安全局就在其中隐藏了一个秘密后门。

，我建议重点关注历史和背景。例如，您可以解释Crypto.AG，他们如何增加RNG来帮助NSA监视客户。您可以解释一下随机数生成器是密码学中的经典弱点的原因，因为RNG已被后门攻击，任何人都知道后门可以恢复您的所有密钥。您还可以解释一下这是很难检测到的：由于RNG应当输出看似随机的比特，因此如果NSA可以预测到它实际上是伪随机比特，而其他人则不能（如果这些比特实际上来自PRNG， NSA知道种子，但没有其他人知道），这很难通过黑盒测试或通过检查所谓的随机位来检测。

如果您愿意，可以解释一下在2006年，密码学家发现了允许后门的数学结构，但是却避免提出任何指控，因为，嘿，美国国家安全局（NSA）肯定不会这样做-那真是太可怕了，很难想象实际上包含一个后门。现在情况发生了变化：似乎难以想象的事实实际上是现实。因此，您可以解释一下这对于密码学界是如何大开眼界的，以及它将如何改变我们对未来政府标准和系统设计的看法。

然后，您可以解释其影响。您可以解释一下这种影响被认为是相对较小的，因为大多数人从2007年开始就听从Bruce Schneier的警告，并且没有使用Dual_EC_DRBG。但是，您可能会解释，由于不清楚的原因，至少有一个主要的加密库（RSA的BSAFE）确实使用了它，因此这可能会对未知数量的已部署产品产生未知影响。您可以解释一下此后门可能如何仅允许NSA解密流量，而不允许其他人解密流量。最后，您可以解释最大的影响是什么：对密码标准和美国公司失去信任的可能性。我不确定我们是否已经看到公众已经失去信任-我认为人们仍然相信Google以及Apple和Amazon会得到他们的支持-但是如果发生这种情况，可能很难恢复。


我看到你想解释数学。好的，这是一个解释。我要攻击的是Dual_EC_DRBG的简化版本，但是这种简化并不会改变攻击的本质。

算法规范指定了一个椭圆曲线，它基本上只是一个有限循环（因此是Abelian）组$ G $。该算法还指定两个组元素$ P，Q $。它没有说他们是如何选择的；我们所知道的是，它们是由NSA的一名雇员选择的。在简化算法中，PRNG在时间$ t $处的状态为某个整数$ s $。为了使PRNG向前运行，请执行以下操作：


我们计算$ sP $（回想一下，我们使用加法组表示法；如果$ P ^ s $，则与$ P ^ s $相同）您更喜欢乘法表示法），将其转换为整数，然后将其命名为$ r $。
我们计算$ rP $，将其转换为整数，然后将其命名为$ s'$（这将成为下一步）。
我们计算$ rQ $并将其作为PRNG的这一步输出输出。 （好的，从技术上讲，我们以特定方式将其转换为位串，但是您可以忽略它。）

现在是观察结果：对于某些整数$ e $，我们几乎可以保证$ P = eQ $。我们不知道$ e $是什么，而且我们很难找到它（这需要解决椭圆曲线上的离散对数问题，因此这可能很难）。但是，由于NSA选择了值$ P，Q $，因此可以通过随机选择$ Q $，随机选择$ e $和设置$ P = eQ $来选择它们。特别是，NSA可能会选择它们，以便他们知道$ e $。

这里的数字$ e $是让您破坏PRNG的后门。假设NSA可以观察到PRNG的一个输出，即$ rQ $。他们可以将此乘以$ e $，以获得$ erQ $。现在注意$ erQ = r（eQ）= rP = s'$。因此，他们可以推断出PRNG的下一个状态。这意味着他们了解您的PRNG状态！这确实很糟糕-在仅观察PRNG的一项输出之后，他们几乎无需做任何工作就可以预测PRNG的所有未来输出。这与PRNG的中断几乎一样严重。

当然，只有知道$ e $的人才能破坏PRNG。因此，这是一种特殊的后门：NSA可能知道如何破解Dual_EC_DRBG，但其他人不太可能知道如何破解它。即使我们现在知道后门存在，也很难恢复秘密的后门$ e $，因为这需要解决离散日志问题。


嗯。也许这仍然太复杂了，因为它需要了解加法器组以及有关椭圆曲线的一些知识，等等。好。因此，让我与您分享一个类似的例子：PRNG就像Dual_EC_PRNG一样，只不过它使用整数而不是椭圆曲线。特别是，从概念上讲，一切都将基本相同-后门将相同，PRNG将相同-如果没有椭圆曲线密码学的任何背景，这将更容易理解。希望这可以使直觉更好。


PRNG。该算法指定素数$ p $和两个均小于$ p $的整数$ g，h $。该算法告诉您，PRNG在每个时间点的状态都是满足$ 1 \ le s

后门。后门是一个秘密数字$ e $，这样$ g = h ^ e \ bmod p $。创建算法规范的NSA通过随机选择$ h $，随机选择$ e $，设置$ g = h ^ e \ bmod p $然后发布$ g，h，p $来选择$ g，h $ （但要保留$ e $的机密性，因为$ e $是后门）。

违反了PRNG。 NSA可以打破PRNG。假设他们观察到PRNG的一个输出$ t $。他们计算$ t ^ e \ bmod p $。请注意，

$$ t ^ e =（h ^ r）^ e = h ^ {re} =（h ^ e）^ r = g ^ r = s'\ pmod p。$$

这意味着他们能够计算PRs的下一个状态$ s'$。因此，在仅观察PRNG的一个输出之后，他们可以推断PRNG的下一个状态，从而预测PRNG将来的所有输出。

例如，假设您生成一个随机IV使用此生成器（并以明文形式发送），然后使用此生成器生成会话密钥，然后使用该会话密钥对内容进行加密。 NSA（正在窃听您的通信，因此可以看到IV）知道IV是从此PRNG输出的，可以使用其后门推断PRNG的状态并预测其将来的输出-因此他们可以预测会话密钥并解密所有后续流量。您已经拥有了！


我希望这能带来直觉。 Dual_EC_DRBG的问题与我刚刚描述的虚拟PRNG的问题完全相同。希望这很容易遵循：如果您了解Diffie-Hellman的工作原理，那么您就可以理解为什么会这样。