破解咸密码哈希的时间复杂度是否大于破解未咸密码哈希的时间复杂度？

Question

假设有人试图通过暴力破解泄露的密码(即，不使用彩虹表或常用密码列表)，以下是真的吗？

O(cracking_salted_password) > O(cracking_just_password)？

如果攻击者成功地访问了我的用户数据库，显然他们在哈希我的用户密码时也使用了salt，尽管它对每个用户都是完全唯一的。我想知道，时间复杂性是否也扮演了一个角色，当有人试图破解一个盐渍密码通过蛮力。

Answer 1

由于盐渍实际上只创建特定明文散列到的一定数量的不同值(例如，将密码“密码”哈希为值X1，例如，一个16位的盐分，它可以散列的值有65536个不同的可能值)，所以盐析的效果实际上只是改变方程中的常量乘法因子。换句话说，如果您的哈希算法是O(n^2)，那么对输入进行盐析使其为k * O(n^2)，这实际上与O(n^2)相同。是的，要匹配特定密码的散列需要花费更多的时间，这取决于您的salt有多大，但是它确实不会改变O()的复杂性度量。复杂性度量不在于执行某个问题需要多长时间，而在于解决一个比最初问题大两倍的问题需要多长时间。

Answer 2

我想知道，当有人试图通过暴力破解一个盐渍密码时，时间复杂性是否起了作用。

不，单一密码的时间复杂度不会因盐而大幅度增加。盐确实为加密时间增加了一个很小的恒定值，但不足以引起问题。

这并不意味着盐渍是无用的。盐渍有两个重要原因：

1)使用相同密码的用户看起来会有所不同。如果攻击者看到多个用户拥有相同的密码，他/她将假定密码不是随机的，并首先攻击该密码。

2)使彩虹桌不实用。

在此之前，您只需要一个查找表来进行所有密码猜测。您可以离线预计算它(甚至在某些系统之间重用它！)

但是当您添加盐时，攻击者需要每个用户一张彩虹桌。这使得彩虹桌指数更大，甚至可以使它更快地使用蛮力，而不是使用彩虹桌！

因此，如果您只有一个用户，那么salt可能没有帮助，但是当您获得更多的用户时，盐是必不可少的。最好总是有盐，因为小系统往往会变成大系统。

Answer 3

如果有一个具有数十个密码作为散列的数据库，并且通过散列(大)一组可能的值来进行攻击，则工作一次可以应用于多个散列。

但是，如果密码是咸的，那么每个密码都是唯一的，每个密码都需要重复工作。