散列常规随机数生成器的结果会产生加密安全的 PRNG 吗?
例如,是否会sha1(rand())有效地成为一个安全的 PRNG?
假设它没有,你将如何攻击它?
编辑:让我们假设通过攻击我的意思是在看到它产生的一系列值之后确定它将产生的下一个值。
注意:我应该注意我没有选择以这种方式实现 PRNG。我对分析它的属性非常感兴趣,因为我在代码中看到了类似的结构。对我来说,这看起来不是一个好主意,但我正在努力思考攻击它的最佳方法。
散列常规随机数生成器的结果会产生加密安全的 PRNG 吗?
例如,是否会sha1(rand())有效地成为一个安全的 PRNG?
假设它没有,你将如何攻击它?
编辑:让我们假设通过攻击我的意思是在看到它产生的一系列值之后确定它将产生的下一个值。
注意:我应该注意我没有选择以这种方式实现 PRNG。我对分析它的属性非常感兴趣,因为我在代码中看到了类似的结构。对我来说,这看起来不是一个好主意,但我正在努力思考攻击它的最佳方法。
对 RNG 的输出进行散列通常是制作加密安全 RNG 的一个组成部分,但这并不是魔术。它不能让一个糟糕的 RNG 突然变得安全。
加密安全 RNG 的一个关键组成部分是绝对不可预测性。如果您可以预测输出,那么您可以将该预测用作攻击的一部分。通过散列运行输出不会改变可预测性。
比如说,我的超级棒的随机数生成器在返回数字 4 和 7 之间交替。你可以说我的 RNG 很糟糕,你是对的。但是,假设您现在通过 SHA1 运行输出。所以它在返回 SHA1(4) 和 SHA1(7) 之间交替。仍然不是随机的。所以答案是否定的。
但是哈希对加密 RNG 很有用
另一方面,假设你有一个真正的熵源(例如指向一块钚的盖革计数器),它产生可证明是随机的但在我们的例子中是有偏差的结果。由于我们的采样设备,输出流是 57% 的 1 和 43% 的 0。这是随机的,因为你绝对无法预测结果,但如果你猜“1”,你会更频繁地猜对。
我们可以通过加密哈希运行输出来消除这种偏见。加密哈希的属性之一是,无论输入是什么,输出本质上都没有偏差。显然,我们必须收集足够长的输入样本块,以防止对相同的值进行两次哈希处理。但是最终输出的 1 和 0 的数量大致相等,这使得我们的加密更加安全。
散列对提高PRNG 的安全性(如rand(). 事实上,如果 PRNG 的输出大于散列函数的输出,就会降低其安全性。
sha(rand())基本上是默默无闻的安全。您假设通过使 PRNG 输出看起来更随机,它会使其更安全,这是不正确的。我不会讨论加密安全伪随机数生成器 (CSPRNG)的主题,因为我并不精通该主题。你只需要知道,如果一个任意rand()的是不安全的,那么无论你如何改变它的输出,它都会保持不安全,甚至可能会降低它的安全性。
现在,如果您谈论的是PHP/Crand(),那么重要的是要知道它远非加密安全的 PRNG。
正如CodesInChaos 所说,最大的问题rand()是它的种子来源。看php-src/ext/standard/php_rand.h,你可以清楚地看到种子是如何产生的
GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))
php_combined_lcg()归结为线性同余生成器 (LLG),不建议将这些 LLG 用于加密目的。
返回的值与可能通过生成的文件名、生成的密码、执行不良的令牌等泄露的返回值相同。一旦攻击者获得该值,剩下的就很简单了php_combined_lcg()。和uniqid()的值是相当暴力的。time()getpid()
第1部分
不,这不安全,它不会是语义安全的(因为 Random() 不安全)
我认为它不安全,因为散列函数会降低其输入的熵。换句话说,散列函数的结果与输入的映射通常小于 1:1,并且与原始输入本身相比,它与先前输入发生冲突的可能性更大。
在这种情况下,非随机输入将简单地“更长”更多位,但不会使其更随机,这是大多数加密需求的基础。(想想一个时间垫)
更好的解决方案:
将非随机输入输入“HKDF”。HKDF 允许您从一个密钥派生多个密钥,假设源密钥/PRF 不一定是随机的。HKDF 使用“提取然后扩展”范式,该范式使用随机的非秘密“盐”来增加随机性。样本HMAC(salt, yourKey)
另一种方法是将非随机输入输入到流密码(例如 AES 或 3DES)中,并将其用作一次性密码(或您打算使用它的任何内容)
你会如何攻击它?
我需要知道这是如何使用的。该攻击与对 random() 的攻击相同,但随后增加了散列延迟。这种攻击的简化版本是知道你需要暴力破解的区域远小于 2^51,这可能是不可忽略的。
在流密码示例中,这意味着 SHA1 将在不到281.5 TB的时间内导致冲突被加密,而 rand() 函数可以进一步减少这种情况。(如果有人知道如何计算这个我会很感激这个信息)
第2部分
正如您所怀疑的那样,只关注与 PRNG 无关的“散列”方面:
碰撞是不好的,因为它允许攻击者做很多事情,例如实施选择的消息攻击、存在伪造或各种其他攻击,具体取决于您在何处使用生成的哈希输出。
在散列方面,冲突最有可能发生在 2^n/2 次操作中(大致为输出空间大小的平方根)。
Name Size Attack Operations
SHA-1 160 2^80 (Insecure, don't use)
SHA-256 256 2^128
SHA-512 512 2^256
Whirlpool 512 2^256 (AES based and slowest)
上面列出的是仅基于输出中的位数的最佳抗碰撞性(理论上)。
请记住,哈希的实际安全性可能不如理论最大值安全。以 SHA-1 为例,最著名的碰撞查找器只需要 2^51 次哈希评估,理论上最好的情况是 2^80)
这完全取决于应用程序的安全要求、随机数生成器和散列函数。事实是,它可能是安全的,但回答这个问题需要仔细研究。“安全”在每种情况下并不总是意味着同样的事情。攻击者将如何尝试利用您受损的随机数生成器?当安全研究人员开发 CSPRNG 等工具时,他们试图使其满足某些要求,使其成为适用于各种应用程序的安全工具。
话虽如此,创建自己的安全解决方案通常不是一个好主意,尤其是当它们基于好的想法时,因为魔鬼在细节中,一个微妙的错误比一个明显的错误要危险得多。
我建议您花一些时间阅读 HMAC 的工作原理。乍一看,hash(message|secretkey) 似乎是一种创建消息验证码的有效方法。然而,由于散列函数的某些不可避免的弱点,以及其他原因,安全专家已经决定对输入和/或密钥进行多次散列并在其间添加垫子可以创建更安全的身份验证代码。
如果您花一些时间了解为什么 HMAC 会按照它们的方式完成,那可能会帮助您理解为什么推荐的 CSPRNG 可能会比您自己做的更好。
话虽这么说,看起来你想要做的是偷工减料。与其问,我怎样才能做一个半屁股的 CSPRNG?您可能想问一下您的随机数生成器是否真的需要加密安全。
如果你真的需要那种级别的安全性,你应该做对。如果你不需要它,半途而废只会给你一种虚假的安全感,并且难以分析和预测你的安全弱点。
如果我是一名黑客,那么一个隐藏得很好的漏洞或弱点(比如心脏出血)将比明显的东西更有价值,一旦它变得重要到值得关注,就会得到认可和修复。
我想说这是在安全性方面不发明自己的最重要原因之一。
如果您有兴趣更深入地研究您提出的方案的安全潜力,这可能是一个开始的地方。这是密码堆栈交换中的一个相关问题:
https://crypto.stackexchange.com/questions/9076/using-a-hash-as-a-secure-prng