两个密码之间的距离

信息安全 密码 攻击
2021-09-09 04:49:18

众所周知,人们在不同的网站上重复使用他们的密码。重用可以通过两种方式完成:

  1. 对两个不同的站点使用完全相同的密码,
  2. 稍微修改一个站点的密码并在另一个站点上使用它。我们称它们为相似密码。

对于案例1。比较密码直接揭示密码重用。

对于情况 2。没有明确的方法来测量两个字符串之间的距离。最流行的度量是 Levenshtein 或编辑距离。例如“password”和“password1”之间的编辑距离只有1对应于字母'1'的插入

然而,Levenshtein 距离并不总是很好。例如,如果某个站点的密码x.com是“monday”,而站点的密码y.com是“wednesday”,则编辑距离为5。假设攻击者知道x.com即“monday”的密码以及编辑所在的位置已为 site 制作y.com,应尝试至少 26^5 种密码 monday 变体。

但从概念上讲,“星期一”被另一个工作日所取代。除了“星期一”之外,还有 6 个工作日。所以在这种情况下,聪明的攻击者只需要尝试 6 个不同的工作日,而不是“星期一”的 26^5 个变体。

测量两个密码之间距离的好方法应该是什么?

2个回答

没有什么好办法。你说的,实际上是我们心中密码距离 度量。显然不可能有直接的方法来做到这一点。

第二件事,你想要测量的东西,很大程度上取决于人,并且通常只包含他已知的信息。例如,您的一位同事可以在不同的公司服务器上使用其孩子的名字。不可能建立一个软件解决方案来找到这个,但是一些黑客/同事可以拥有这些信息并使用它们来破解他的帐户。

你能做的,是进入 NSA 的轨道:虽然你不能直接窥探人们的思想,但你可以使用大数据来模拟一些非常相似的东西。

你需要什么:网络上公开的信息。例如:

  1. 词库
  2. Wikipedia(虽然没有简单的方法来衡量两个关键字的链接距离,但它的数据库可以简单地下载,您可以构建一个脚本来分析其链接连通性)。
  3. 或者简单地说,您可以使用google search api进行自动 google 搜索,并获得第一个、第二个密码和双重查询之间的命中率(例如,如果第一个密码是“apple”,第二个是“orange” ",则Hits("apple")*Hits("orange")/Hits("apple", "orange")^2必须低于您设定的实验限制)。

但请注意:不要在不受信任的公共云中执行包含密码的查询,这是非常严重的安全漏洞!当然,这仅取决于您的观点/考虑/责任,您信任哪个公共云。对我来说,没有。

在你的地方,我做了以下事情:

  1. 我有一个维基百科镜像(他们有简单的 mysql 数据库,可公开下载)
  2. 创建了一个链接距离图(它非常简单,虽然它可能很大)
  3. 我为这两个密码创建了与他们最近的维基百科文章标题进行比较(它可能需要大量的 levenshtein 比较,所以你需要很多 cpu)
  4. 最后我使用了以下公式:D("pwd1", "pwd2") = Levensheiten("pwd1", Lev_nearest("pwd1")) + Wiki_Link_Distance(Lev_nearest("pwd1"), Lev_nearest("pwd2"))+ Levensheiten ("pwd2", Lev_nearest("pwd2"))

扩展:wiki 包含大约 100 万条文本条目,这使得最短的搜索方式几乎是不可能的。您肯定已经将其实现为 C++,并使用了非常优化的算法。因此,这将是困难的。作为替代方案,您可以只使用维基百科中最常用的词(可以通过获取它们的使用统计信息来找到)。尽管英语维基有大约几百万篇文章,但以英语为母语的人只知道大约一万篇文章。

真的应该有人写这个,它是 github 某处的一个很棒的开源恶魔 :-)

你很幸运,有一个很好的方法来规范化公开信息:WolframAlpha可用于将字符串减少为可比较的逻辑组件,并产生更准确的 Levenshtein 比较。

“星期一”的示例

一旦将字符串“分解”为所有可能的含义(星期几、拼字游戏值等),您就可以将这些元素用作新的比较值。

对于私有信息,例如兄弟名称,您将需要遵循类似的方法为您的专有存储重新构建 Wolfram 的结构。Wolfram有一个可用的 API ,可以将结果导出为 JSON,并且可以帮助您将想法与创建此类私有存储库所需的内容保持一致。