我认为回答您问题的最佳方式是说：前提非常不可信，因此根本不会出现问题。

我不妨问：如果我们假设我们发现了时间旅行，是否有理由担心密码安全？当然，如果我们发现时间旅行，有人可能会回到过去，在我输入密码之前出现噗嗤，在我输入密码时回头看，然后在我注意到之前噗消失。

或者，如果我的计算机可以按需进行时间旅行，我可以将其设置为迭代以下循环：选择一个随机密码猜测，尝试查看它是否正确，如果正确则打印密码并停止；如果不正确，请及时返回到循环的开头并重新开始。如果时间旅行算法是可能的，这是一个 O(1) 时间的算法来破解任何密码，给定它的密码哈希！

但当然，这些答案是愚蠢的，因为在可预见的未来，任何人都不可能发现如何回到过去。同样，在可预见的未来，没有人发现一种算法来有效地解决所有 SAT 实例的现实前景。当然，如果有人能找到一个 SAT 解决算法，可以在 15 秒内解决每个 SAT 实例，那么他们可以在 15 秒内破解每个密码（给定密码哈希）。但我认为这在我有生之年不太可能发生。

PS我从单击您的链接中看到您可能更喜欢技术性更强的答案。我的建议是阅读 Hellman 的时空权衡和彩虹表；这将使您更好地了解适用于密码破解的最新方法。您可能还想了解为什么彩虹表不适用于加盐密码；类似的原因可能适用于您的方法。

查看链接中方法的复杂性，我发现您的方法需要 2 ^v预计算，其中v是 SAT 实例中的变量数。相比之下，Hellman 的时空权衡表和彩虹表需要 2 ⁿ的预计算，其中n是密码的位数（输入到散列函数的位数）。在密码设置中，n会比v小很多，因此彩虹表和 Hellman 的时空权衡看起来会比您的方法表现更好。换句话说，在我看来，您的方法——即使它是有效的——在密码破解方面会击败最先进的技术，或者在实践中与密码破解有很大的相关性。当然，您总是可以在一个小实验中尝试一下，并将您的方法与现有的密码破解器进行比较；那将是真正的考验。但目前，我认为没有理由期待与密码破解相关的 SAT 解决方案取得进展。

让我只引用你的两个实际问题并将SAT的事情放在一边......

如果我们假设我们可以访问某种形式的通用密码破解/破解，可以在 $O(n^{\log n})$ 时间内以某种方式找到 $n$-bit 密码，是否需要警报？

如果我们为了思想实验而假设这是真的，那么是的，我们显然有麻烦了，因为世界上任何和所有密码都将是无关紧要的。与破解密码散列相比，实际获得所述散列相对容易。并不是每个人都会立即知道其他人的密码，但这会很糟糕。

我真的想知道我们是否知道密码黑客开始变得危险的某种阈值（在速度方面）？

你的意思是“道德”黑客（不是黑客）应该在某个时候停止黑客攻击吗？就我而言，情况恰恰相反。如果人们因为担心自己离解决方案太近而停止对这些东西进行黑客攻击，那么将会有其他道德上不那么倾向的破解者不会停止。“善意”的黑客是唯一能够指出潜在危险并至少尝试提前获得任何警告的人。

这一个得到了一个非常高的问题投票。

无论如何，如果为真，则比存储密码哈希〜=存储明文密码。现在考虑存储明文密码的安全要求。

如果不是很明显，现在需要为每个站点使用完全不同的密码，这意味着使用密码管理器或写下密码。并且假设保护 SSL 的底层加密存在（它不应该存在）。

是的，准多项式时间破解或密码可能会导致安全入侵的数量大大增加。当黑客非常绝望地等待指数时间算法时，暴力破解密码已经完成。如果黑客能够在准多项式时间内破解密码，他们将破解更多密码。当然，他们需要访问密码字典，这样他们才不会因密码尝试次数而被关闭。允许的密码尝试次数通常是一个常数，因此即使是准多项式破解也会遇到块，除非黑客有字典。

原谅我，从 SAT 到解密应用程序没有标准减少吗？这似乎是文献中应该存在的减少。由于加密本身通过 NP 完全性简化为 SAT，因此破解算法也使用相同的简化。请查阅您的 CS 理论教科书，了解用于证明 NP 完整性的多时间缩减。多时间缩减当然可以用于将伪多时间 SAT 算法转换为加密密码的密码破解算法，因为多时间比伪多时间快。