评估 PRNG 中的熵收集

信息安全 密码学 随机的
2021-08-19 21:03:15

我正在查看嵌入式设备上的随机数生成器(预计具有加密质量)。我的观点是操作系统和加密库实现者。我特别关心熵收集。我已经确定了要查看的几点:

  • PRNG的初始状态是如何产生的?
  • PRNG 什么时候应该拒绝交付,直到它获得更多的熵?
  • 有一个 API 调用来注入更多熵,它如何将新熵与现有状态混合?

(在我的例子中,有一个硬件 RNG,速度太慢,无法系统地使用,但我们可以从中获取熵。)

如果我的实现很好,这些问题的答案应该是什么样的?我还应该尝试回答哪些其他问题?

2个回答

“熵”是对某些数据元素可能是什么的度量。我们说我们在一堆比特中有n比特的熵,如果这些比特可以共同假设2 n 个具有统一概率的不同值(有很多复杂性隐藏在“统一”术语下)。要制作加密安全的 PRNG,您必须:

  1. 从随机来源收集足够的数据,以达到至少 128 位的熵。这个想法是,对于攻击者来说,“尝试” 2 n 个可能的内部状态空间中不可忽略的部分是不可行的。n=80曾经是它的传统值,但鉴于 80 年代以来的技术进步,我们现在更喜欢n=128,它是 2 的幂,因此受到众神的祝福。
  2. 在适当的类流密码函数中使用充满熵的种子:这是一个基于初始密钥输出伪随机位的函数;在这里,密钥将通过具有固定长度输出的单向函数(即散列函数)从种子中导出。您在此处寻找的安全特征是,在给定一系列连续输出位的情况下,不可能以远高于 0.5 的成功概率猜测任何其他过去或未来的输出位。请注意“未来位”部分:这并不像您想象的那么直接。

第二点并不容易。作为基本规则,如果类流密码函数不是已在某些标准中精确描述并由数十位密码学家分析的已发布构造,那么您应该认为 PRNG 的质量可疑。自制的 PRNG 与自制的分组密码一样糟糕:它可能很强大,但许多自制的 PRNG并不强大,而且没有确定的密码强度测试。

NIST 发布了一些“已批准”的 PRNG的完整描述。如果您使用的 PRNG 是其中之一,那很好。否则,你真的应该提出警告标志。

至于你的确切问题:

  • 初始 PRNG 状态应该从“良好的 alea 源”收集,这意味着源不仅应该产生“变化”的数据,而且还应该以一种攻击者无法观察到变化的方式。例如,向外部网络主机发送“ping”请求,并测量返回响应所需的时间,这不是一个好的来源:它看起来确实是随机的,但必须假设攻击者可以观察到你的传出ICMP 请求和相应的答案,从而获得相同的计时措施。有关此类问题的更详细处理,请查看此答案(是的,我在引用自己的话)。

  • 额外熵的注入与初始状态的注入非常相似:用作种子的“随机数据”通常很庞大,因此应该有一些混合步骤来产生高熵、序列。这里的工具是任何安全散列函数。为了简单起见,注入应该是这样的:我们获取当前的内部状态,我们连接额外的“熵”,然后我们散列整个事情;哈希输出是新状态。当心:这种事情依赖于不完全正确的安全属性保证任何给定的哈希函数。我在这里的意思是,这种用法的安全性并不是抗碰撞或抗原像的结果。因此,在为此使用散列函数时会有一种信念的飞跃(尽管您可能会比使用 SHA-256 做得更糟)。在 NIST PRNG 中,我建议好好看看 HMAC-DRBG,它使用HMAC来完成这类工作。HMAC 是一种消息认证代码,它使用底层散列函数以允许更好的“安全证明”,原因类似。

  • PRNG 在获得更多熵之前拒绝提供更多数据的想法有点像巫毒仪式:只有你相信它才重要。如果你用足够随机的初始种子初始化你的 PRNG,然后使用适当的数据生成函数,那么从它生成 PB 级的伪 alea 应该没有安全问题。然而,这让一些人感到紧张,因此许多 PRNG 实现包括阻塞行为,其中 PRNG 将拒绝输出超过 1 MB 的数据,例如来自 128 位初始熵的数据。在实践中,阻塞 PRNG(除了初始化——有必要阻塞直到足够的初始熵已被收集)导致部署问题(例如,在生成 SSH 密钥时,Linux 操作系统自动安装在服务器上阻塞,因为没有键盘或鼠标从用户那里收集熵)。作为一项规则:

一个。按照 PRNG 标准规定进行操作(参见NIST SP 800-90);

湾。除非标准另有明确规定,否则不要阻塞,只要你有一个完整的初始种子。

请注意,Linux/dev/random/dev/urandom两者都失败了:/dev/random会经常阻塞,而且/dev/urandom根本不会阻塞,即使它没有得到一个好的初始种子。幸运的是,任何体面的 Linux 发行版都将确保/dev/urandom使用足够好的种子作为引导脚本的一部分进行初始化(包括将随机种子保存在隐藏文件中,在上次关闭时生成)。FreeBSD 的/dev/urandom行为方式与我描述的一样,这很好。

主要问题已经回答了,所以我只是扩展了答案的一部分。

熵收集虽然一些熵源可能被窃听甚至完全被攻击者控制,但要正确地做这件事有点棘手。估计收集到的熵的数量很可能注定要失败。

解决这些问题的一个很好的实现是Fortuna它是由 Bruce Schneier 等人设计的。