使用PBKDF2对密码进行散列

Question

如果攻击者想黑2^{10}用户的密码。所有这些用户都从2^{50}密码**的空间中生成一个密码，并且每个密码都使用PBKDF2来使用2^{10}迭代**。

在最坏的情况下，攻击者需要做多少散列才能获得所有密码？

我认为这将是2^{10} \cdot 2^{50} \cdot 2^{10} = 2^{70}，因为在本例中，每个密码都将使用2^{10}迭代进行散列。

Answer 1

我想对这个计算提出三项反对意见：

1. 当用户从2^50个密码的空间中选择密码时(空格一词适合于密钥，而不是密码，参见2)，他们实际上从不在空间的“外部边界”选择密码，而是在“内部边界”选择密码:一些用户选择密码"123"，绝大多数用户选择最多8个字母的密码。这意味着几乎从不需要搜索整个空间，但只需要搜索其中的一小部分。
2. 如果你破解密码，你不会尝试所有的可能性，而是按密码频率顺序排列的密码列表，经过几次尝试，你会发现很多密码。
3. 即使还有2^40次迭代，这听起来比在实际中更好，因为1.密码可以并行破解，2.对巨大的破坏来说，只破解了最容易的60%。

Answer 2

你是怎么到达2^{10} \cdot 2^{50} \cdot 2^{10}的？据推测，它的目的是代表如下内容：

For each user u
    For each password p
        Compute PBKDF2(p) and compare with u.hashed_password

它提供对PBKDF的2^{10} \cdot 2^{50}调用，每个调用都是2^{10}哈希函数调用。但考虑一下这一做法：

For each password p
    For each user u
        Compute PBKDF2(p) and compare with u.hashed_password

注意，没有必要计算循环中的PBKDF，您可以这样做：

For each password p
    Compute h = PBKDF2(p)
    For each user u
        compare h with u.hashed_password

这给出了对散列函数的总共2^{10} \cdot 2^{50}调用。因此，实际上，用户数量并不会影响所需的哈希调用数。防止这种优化恰恰是盐的目的。这意味着PBKDF的输入依赖于用户的属性，因此不能将哈希计算从内部循环中吊起。