散列SHA-512 1000次

Question

SageMathCloud安全性(http://goo.gl/dCujW1)如下：

服务器只存储密码的散列，服务器使用sha-512哈希函数的1000次迭代，盐分长度为32。

虽然这听起来像一个不错的盐，我有点怀疑1000-迭代的想法。虽然这确实使蛮力攻击速度慢了1000倍，但每一次额外的迭代都会使你的碰撞几率减小，这不是吗？

Answer 1

在基于密码的密钥派生中，使用适度次数的迭代是一种标准方法(例如，请参见http://en.wikipedia.org/wiki/PBKDF2、RCF 2898 https://www.rfc-editor.org/rfc/rfc2898)。它也可以用在所描述的sceanrio。在这种情况下，如果攻击者能够访问您的密码数据库，那么它应该将攻击者的速度降低到迭代次数的线性。

您所讨论的冲突问题实际上并不是一个关注的问题。我猜您的意思是，如果我进行q (不同的)散列计算，那么我发生冲突的概率(即M和M'这样的H(M) = H(M') )小于q^2 \cdot 2^{-s-1} (假设函数或多或少是随机的)，其中s是哈希函数的输出长度。如果是沙-512，我们有s=512。这个概率很小。例如，即使对于一个大型数据库，比如10^6 (100万个)密码，碰撞的概率也是10^{18} \cdot 2^{-513} < 2^{-453}，如果没有1000迭代，这个概率就是\approx 2^{-473}。换句话说，额外的1000迭代在碰撞概率中弥补了2^{20}因子的损失。

在任何情况下，这都不是一个问题，因为在同一个迭代中不发生的冲突(@fgrieu，谢谢您指出了这一点)不会导致相同的密码。