密码泄露后，是否存在一个Levenshtein 距离，与新派生的密码相距该距离可以认为是安全的？
我假设是的，假设例如这个词是“密码”，而新词是“drowssap”，那么距离是 8 并且我们有一个“新”（在这种情况下非常懒惰的变化肯定是不安全的）。
我想知道在有针对性的攻击中，黑客是否可以使用已经找到的密码列表（例如来自违规汇编）为单个人建立字典。
我明白 Levenshtein 距离并不是安全密码的良好指标。但是，我确实想知道，如果我知道密码是“密码”（代表任何 8 位密码）未来，我希望这个人在未来使用类似的密码，例如我有一个阿姨，我知道她会这样做，我必须给她什么作为最小距离，这样我就不能轻易计算和猜测她的新密码离线攻击中的密码，假设我能够检索密码哈希？
我知道这个问题是理论上的，但我的目标是从更大的角度来理解整个事情，例如，Levenshtein 距离是否可以在密码安全中发挥任何重要作用。
我知道通常推荐的所有良好做法。
由于 schroeder 概述的原因，作为密码强度代理的 Levenshtein 距离非常有限。而且用户体验可能很差。
但是这个问题在学术上仍然很有趣，并且可能作为某些用例的一个组件有用 - 所以它仍然值得一个彻底的答案。:D
通常，先前密码和新密码之间的最小Levenshtein 距离应该与随机生成的能够抵抗暴力破解的密码的最小长度相同（根据威胁模型进行调整）。但重要的是要注意，即使是这个最小值也常常是不够的。
我的回答基于几个因素：
首先，关于速度。
最坏的情况 - 像 MD5 这样的“快速”散列 - 许多不同类型的攻击成为可能。这将允许我们为最小 Levenshtein 距离设置一个上限。
最好的情况 - 像 bcrypt 这样的“慢”哈希 - 攻击速度显着减慢，但不像以前那么慢（更多关于下面的内容）。
二、关于用户以前的密码。
我们必须假设攻击者拥有用户以前的密码。不仅密码重用是长期存在的，而且现在，即使攻击是针对慢散列的，现代攻击堆栈也包括一种称为“相关攻击”的高效“按目标”攻击模式（由开膛手约翰的“单一”模式和稍后通过 hashcat 的 -a 9 模式）利用先前密码的知识，即使在大量泄漏时也是如此。
在关联攻击中，我们假设攻击者可以访问用户以前的密码（来自以前的泄漏，由于密码重用而来自不同的站点等）。该攻击将用户的旧密码作为“基础”，然后将一组特定的“修改规则”（附加 $、首字母大写等）应用于每个 plaintext，但仅针对该用户的 hash。对于较大批量的用户和较慢的散列，这会显着提高攻击速度 - 因为不是针对长列表中的每个散列尝试相同的候选者（就像大多数传统攻击所做的那样），相关攻击只将这些修改规则应用于该用户'.
这不仅仅是学术问题——现实世界的破解现在在很大程度上依赖于关联用户：密码或电子邮件：密码泄漏以及针对新目标的破解。所以我们必须假设攻击者拥有之前的密码。
第三，关于密码生成方法。
最坏的情况 - 密码是单个人工生成的单词，很容易在密码频率列表中找到（如“123456”）。如果一个人选择了下一个密码，那么它与该密码相似的可能性可能很高，因此即使非常低的 Levenshtein 距离也可能是相关的。
最好的情况——密码是完全随机生成的，无论是最初还是后来。在这种情况下，Levenshtein 距离不那么相关（或者更确切地说，测量两个随机生成的密码之间的 Levenshtein 距离只是衡量其随机性质量的代理）。
第四，关于作为密码强度代理的 Levenshtein 距离。
从实际密码熵的角度考虑这一点很有用- 在现实世界中攻击有多难，充分了解人类如何在心理上“分块”密码组件。（这也是香农熵在评估非随机生成密码的强度方面出了名的糟糕的原因，因为它假设蛮力 - 单词中的每个字母都是必须独立攻击的“块” - 而不是如何人类记住密码组件（“只需添加我孩子的名字”）。
最坏的情况——在最低熵级别，如上所述——如果用户只是将一个数字增加 1，或者附加一个不同的特殊字符等，Levenshtein 距离将非常低。
最好的情况 - 在最复杂的情况下 - 在字符串中的随机位置插入一个随机选择的字符可能是可以做出的最高实际熵变化（最难预测）。例如，如果我们在密码中随机注入 8 个字符，实际熵中的 delta 与生成 8 个字符的随机密码基本相同。
鉴于以上所有...
如果我们假设所有最坏的情况（人工生成的密码、糟糕的密码选择策略等），答案应该很清楚：密码的变化量本身应该足以抵御攻击——完全独立于以前的密码（好像第一个密码是空的），并且好像它是使用 MD5 之类的非常快速的哈希存储的。这降低了我们可以合理地预期随机生成的密码对于给定威胁模型用尽的速度，并且在其他地方很好地覆盖（但通常可以徘徊在 13-15 个随机字符左右）。
不幸的是，与许多测量密码强度的尝试一样，这并不容易。这是因为具有高 Levenshtein 距离的密码更改仍然可以具有非常低的实际微分熵。
例如，如果用户的第一个密码是“password”，而他们的新密码是“passwordrumpelstiltskin”，那么 15 的 Levenshtein 距离听起来很棒。但是实际的Levenshtein 距离——当人类应用它们时对初始字符串的实际变化——不是 15，而是1（“添加一个单词”）。
换句话说......就像香农熵一样，Levenshtein 距离作为密码强度度量的有用性仅在密码已经随机生成的情况下才有用。如果你这样做，你就已经拥有了保持它们强大所需的信息，而无需尝试衡量它们两者之间的差异。
甚至换句话说...非常低的Levenshtein 距离是密码更改弱点的良好代理，但高Levenshtein 距离是密码更改强度的非常差的代理。所以我的回答试图在两者之间找到平衡。
您明确想知道是否可以计算密码的“安全”Levenshtein 距离。答案是“也许”，但答案是无关紧要的。
在有针对性的攻击中，黑客是否可以使用已经找到的密码列表（例如从违规汇编中）为单个人建立字典
当然，这可能发生。但是没有攻击者会使用复杂的分析模型来为潜在的未来字符串匹配的宇宙创建概率图。他们将寻找普通人可能使用的明显模式。
因此，虽然您对数学模型感兴趣以找到可能只是在攻击者分析模型的临界边缘的“安全”密码，但“更安全”的方法不是使用密码模式，而是使用随机生成的密码字符串，而不是。攻击者不会破解他们的滑尺和神经网络来聪明地猜测未来的密码，他们只是遵循明显的模式。
拉普拉斯的日出问题在这种情况下发挥作用。当然，您可以根据可观察到的现象计算概率，但这会被人们对系统如何工作的理解所取代。您可以使用贝叶斯分析来高精度计算明天太阳升起的可能性。或者，既然你知道太阳为什么会升起，你就可以有一个更好的答案……
从安全的角度来看，这个指标是没有意义的。
首先，密码泄露通常会导致微不足道的攻击，其中攻击者将简单地攻击泄露中的所有帐户，寻找根本没有更改密码的人。这些都是唾手可得的成果，当攻击者可以拥有数百个没有更改密码的帐户时，为什么还要打扰您更改密码的帐户？
其次，Levenshtein 距离不是暴力破解工具的工作方式。即使攻击者以您为目标并希望使用涉及您的多个密码的过去密码泄漏来暴力破解您的一个帐户，也有两种可能性：
a) 您的密码遵循易于识别的模式，例如“站点名称 + 常量字符串”或“常量字符串 + 年份”或“常量字符串 + 随机字符串”或类似内容。在这种情况下，有针对性的攻击者将按照您的模式编写自定义暴力破解程序。
b) 没有可见的图案。攻击者将依赖他的标准破解工具，可能会将其调整为甚至不尝试明显超出您选择范围的密码（例如，如果您的所有密码都是 8 个以上字符，他将从该长度开始，或者如果您的密码都没有使用数字，他会排除那些）。
在 b) 的情况下，破解者所做的常见事情是字母替换，即反转字符串、切换字母（密码 => dassworp、apssword 等）和常见替换（passw0rd 等（即零））。
这些事情都与 Levenshtein 距离没有太大关系，尽管您可以为每个计算一个，但它没有说明，比如说，直到破解工具尝试这种变化的时间。
Levenshtein 距离在这里是不正确的度量。密码安全性的正确密码度量是输出密钥空间的大小（即我们的过程的图像- 可能结果的集合）。此大小的上限（但不一定等于†）取决于您执行的不同操作的数量。根据Kerckhoffs 的原则，我们假设攻击者知道我们可以在我们的系统中执行的所有可能操作，并且我们唯一的秘密信息是我们在这种自由范围内的选择。
在这个模型中，我们假设攻击者知道旧密码。假设这个密码长 16 个字符，小写字母数字（36 个字符），我们保持这种方式，只需用新字符替换 2 个字符。我们的新派生密码能有多强？
好吧，我们有 16 个选项用于替换第一个字符，15 个用于替换第二个字符，除以 2，因为顺序无关紧要。然后每个字符有 35 个选项可供替换，总输出空间为
16*15/2*35*35 = 147000 outcomes
log2(147000) ~= 17.1 bits of security
如果我们选择了一个新的随机 16 字符小写字母数字密码，我们将获得16 log2(36) ~= 82.7一些安全性。换句话说，我们派生的密码非常不安全。
如果我们添加了反转密码的可能性怎么办？这（对于大多数密码，但不是回文！）将输出空间加倍，为我们的上限增加 1 位安全性。您可以添加很多这样的操作（添加感叹号、交换大小写等），但每个操作都只会增加我们的安全上限，仅取决于我们添加的选择自由度。二进制是/否并不是很多选择。没有什么比简单地生成新密码更自由了。
† 它是一个上限而不是精确的原因是因为多个系列的操作可能会导致相同的结果，将我们的上限扩大到实际密钥空间之上。例如，如果您允许“添加字符”、“删除字符”和“替换字符”操作，那么添加/删除可以模拟替换，给我们提供比实际结果更多选择的错觉。
最后，人类是有偏见的，因此除非您编写的计算机程序可以公平地在密码的所有可能修改之间进行选择，否则您的安全性会更低，例如，您更有可能将出生年份添加到密码中，而不是随机的两位数序列。