可以使用迭代哈希从强随机种子创建加密安全的随机数据吗?

信息安全 加密 哈希 随机的
2021-08-29 07:00:30

我想知道从随机种子生成顺序哈希是否可以被认为是“足够随机”以用于加密操作?

通过顺序哈希,我的意思是:

首先,我们使用例如 SHA512 从一个强随机种子数创建一个散列 -> 我们得到第一个散列。然后我们使用先前计算的哈希计算下一个哈希,然后从该哈希计算下一个哈希,依此类推......

如果初始种子是随机的,那么以这种方式生成的数据是否可以被认为足够“随机”以用于需要强随机性的加密操作?

4个回答

不,这在密码学上是完全不安全的

这种结构违反了加密安全 PRNG 的一个非常重要的属性,即知道 PRNG 输出的一部分并不能帮助攻击者预测输出的任何其他部分。但是,在您的构造中,知道一个输出块可以让攻击者准确预测所有后续输出块。

考虑输出的第一个块被泄露给攻击者的情况。知道流的前 512 个字节意味着他们知道SHA512(seed). 他们现在可以在这 512 位上计算 SHA512 并派生SHA512(SHA512(seed)),这是第二个输出块。然后他们可以在第二个块上计算 SHA512 的另一次迭代,并派生SHA512(SHA512(SHA512(seed))),这是第三个块,依此类推。


有些人似乎正在尝试改进此方案以消除此漏洞。除非您纯粹是为了思想实验而这样做,否则请停止。Hash-DRBG/HMAC-DRBG 已经存在。虽然你的改进可能会堵住这个特殊的漏洞,但密码学是一个非常困难的学科,除非你是专业的密码学家,否则你无法判断你是否还在你的方案中引入了其他微妙的弱点。记住施奈尔定律:

任何人,从最无知的业余爱好者到最好的密码学家,都可以创建一个他自己无法破解的算法。这甚至不难。困难的是创建一种其他人都无法破解的算法,即使经过多年的分析。

不,散列函数通常不能直接用于创建加密安全的随机数据,即使来自强随机种子也是如此。话虽如此,可能存在也具有此属性的散列函数。

散列函数定义中固有的问题是,散列函数首先不需要输出是伪随机的。加密哈希函数必须仅满足以下属性:

  • 原像抗性
  • 第二原像电阻
  • 碰撞阻力

这些属性不足以创建伪随机数生成器。使用散列函数 h 可以创建散列函数 g,例如:g(x) = 0^64 || h(x)where||表示连接。

函数 g 也将被视为散列函数,因为这三个属性都已满足,但前 64 位不是随机的。

此外,正如没有人提到的那样,知道流的前 512 位将允许攻击者计算数据流的所有位,而不是您想要的伪随机数生成器的属性。

其他人已经涵盖了您提出的解决方案中的缺陷,以及为什么您不应该推出自己的加密货币,所以我不会重复。

如果您决定不自己动手,而是使用现有算法,NIST SP 800-90A Rev. 1中的 Hash_DRBG是一个经过严格审查的确定性随机位生成器,它基于 SHA 系列散列函数。如果您想要一个基于散列的随机位生成器,请使用它。

使用现有的实现(例如/dev/urandom)是比使用现有算法更好的主意。Hash_DRBG 的现有实现也存在,但我对它们不够熟悉,无法推荐一个。

对提议的加密 PRNG 安全性的关键测试是下一位测试这意味着,给定 PRNG 的一些输出,某人应该不可能以优于 1/2 的概率(也就是说,比仅仅猜测)来确定输出的下一位。

在您的情况下,如果我们看到了 512 位的输出,我们可以以概率 1 猜测下一位:它们将是我们看到的位的 SHA-512 哈希。

有两种使用安全加密哈希函数的常见设计,它们在 NIST 的 SP 800-90A Rev 1 中进行了概述。它们是 HMAC DRBG 和 Hash DRBG。

我将向您推荐完整实现的文档,但大致而言,哈希 DRBG 的工作方式如下:

  1. 从输入中派生一个种子,并将 V 设置为种子。从 V 派生一个变量 C,前面有一个零字节。将重新种子计数器设置为 1。
  2. 要生成数据,请将 D 设置为 V。散列 D 并将其放入输出中。然后将一个添加到 D,并再次对下一个输出块进行哈希处理,直到您产生所需的输出量为止。
  3. 为了更新状态,哈希 V 前面有一个值为 3 的字节,并将其称为 H。将 V 设置为 V + H + C + 重新种子计数器。增加种子计数器。

请注意,在这种方法中,攻击者永远不会看到 D,因此他们无法从先前的数据中确定下一个输出数据。这最终是“散列的散列”,但不同之处在于 D 是秘密的,而不是我们输出给攻击者的东西。

还有 HMAC DRBG,在我看来它更容易实现,因为它使用带有 HMAC 的哈希函数并且不需要 bignum 算法,这很容易出错并且可能不是常数时间。它在同一文档中进行了描述。它还在 RFC 6979 中用作确定性 DSA 和 ECDSA 的一部分,并且被广泛认为是强大的。

不过,一般情况下,您应该根据需要使用系统的 CSPRNG:getentropygetrandomarc4random/dev/urandomRtlGenRandom这几乎总是正确的选择并且是安全的。只有当您确定不能使用它或有其他要求时,您才应该自己实现这些算法之一。