看雪论坛
发新帖
1

[翻译]使用有序马尔可夫链和用户信息加快密码破解速度

flamepeak 2017-3-1 10:05 800



我一直在寻找加快密码破解的速度的方法。有很多关于这个话题的研究,但是有一个团队在这方面已经做了一些了不起的工作。这里有一篇论文 OMEN: Faster Password Guessing Using an Ordered Markov Enumerator,就是我写这篇文章的灵感来源。虽然这篇文章的想法来自上面的论文,但是所有的工作都是我手动完成的,没有复制代码和其它任何东西。让我们开始吧!


使用有序马尔可夫链和用户信息加快密码破解速度

比John the ripper 的马尔可夫和增强模式提高22.5%的准确性


阅读完上面提到的论文后,我想要一个类似的工具,但是这些家伙制作的工具已经不可用了。因此,我花了几天时间编写代码来实现这个工具,它足够灵活,使用一个破解的密码列表来实现基于n-gram和马尔可夫链的密码生成。我想修改并编写我自己的工具给了我这样做的自由。这个工具仍处于开发阶段,一旦完成,我将会把它分享出来。

编写脚本后,我想看看我们是否可以利用用户信息来加快密码破解速度。这里有一个Fling泄漏的数据,Fling是一个成人交友网站。他们泄漏的数据库可以公开获取到,我下载了这个数据并进行了一些分析。让我们来看看吧。


用户在其密码中使用个人信息


通过一个简单的查询,我们可以看到用户密码与他们邮箱/用户名/用户代码/昵称有相同的前三个字母的用户占多大比例。在Fling泄漏的数据库中共有4993276个密码。让我们看看有相同起始三元组的占多大比例。


总密码的8% 意味着大约有386894个密码。这是一个很大的数字。

让我们看看1-grams。


17%的用户的密码与其邮箱、用户名、昵称有相同的首字母。

让我们玩玩生日和加入网站日期。我想看看有多少用户在他们密码结尾使用他们的生日。查询显示2%的用户这样做。下面是一些结果。


在做了一些非常基础的分析之后,我们已经知道大约有20%的用户在他们密码中使用其非常基本的信息。

如果这还不够,我还有另一个泄漏的数据(ClixSense),包含更多的用户信息,例如用户名、名字、姓氏、电子邮件、国家、城市、生日、加入日期、安全问题等。我精心编写了一个查询,来看看有多少密码的前`n-grams`同样出现在他们的社交信息中。结果令人惊讶,让我们看看它们。

使用2-grams和更多的社交信息例如生日,我们发现32.5%的用户在密码中使用他们的社交信息。下面是这个查询:

select count(password) from users where lower(substring(password,1,2)) = lower(substring(username,1,2))
or substring(password,1,2) = substring(first_name,1,2)
or substring(password,1,2) = substring(email,1,2)
or substring(password,1,2) = substring(last_name,1,2)
or substring(password,1,2) = substring(city,1,2)
or substring(password,1,2) = substring(security_answer,1,2)
or substring(password,1,2) = substring(address1,1,2)
or substring(password,1,2) = substring(security_answer,1,2)
or substring(password,1,2) = substring(zip,1,2)
or substring(password,1,2) = substring(payable_to,1,2)
or lower(substring(password,1,2)) = lower(substring(country,1,2))
or substring(password,length(password)-3,4) = substring(date_of_birth,1,4)
or substring(password,length(password)-4,4) = substring(date_of_birth,1,4)
or substring(password,length(password)-3,4) = substring(register_date,1,4)
or substring(password,length(password)-3,2) = substring(username,length(username)-3,2)
or substring(password,length(password)-2,1) = substring(username,length(username)-2,1)


结果是在200万密码中有65万密码使用社交信息。

我们可以使用这个来加速密码破解吗?是的,我们可以。让我们深入了解马尔可夫链(Markov Chain)。


马尔可夫链(Markov Chains)

简单来说,马尔可夫链所做的是,告诉我们一个字母在一个n-gram之后出现的概率。假设,我们有一个4-gram 的 'ilov',马尔可夫链只会告诉我们下个字母出现的概率。在这个例子中,大部分时间,出现最高概率的字母是'e',使它成为'ilove'。这就是你需要知道的关于马尔可夫链的所有知识。如果我们对这些概率进行排序,我们按照从最高到最低概率的顺序排列密码,故名有序马尔可夫链(ordered markov chains)。

John the ripper 使用未排序的马尔可夫链,从某种意义上来说,它完全遍历一个'n-grams'之后才到下一个'n-grams'。我的脚本的做法是,使用线程同时遍历所有高概率的'n-grams'。我希望已经解释清楚,如果没有的话,请在评论中提出任何问题。你也可以阅读文章开头给出的OMEN论文。


破解密码

一旦脚本完成,我将会分享这个处理数据的脚本。现在,我只是把结果和数据公布出来。


数据集

我破解所使用的数据来自于 MuslimMatch 数据库泄漏的数据。密码使用MD5加密存储,同时泄漏的数据库中还有用户名、用户代码、用户邮箱和用户国家。我现在忽略了用户国家,只是使用用户名、用户代码和用户邮箱。大约有77000个哈希值需要破解。


John the ripper 增强模式

每种模式我想尝试1亿个长度在6-12位之间的密码。第一种模式是增强模式,结果是15000个哈希值被破解,占总数的20%。


John the ripper 马尔可夫模式

这次我依然尝试了1亿个密码,同时设置`level=210`并保持密码长度不变。结果是有20000个哈希值被破解,占总数的25%。


用户信息的前三个字母作为`n-grams`的有序马尔可夫链

在这里,我从用户信息中获取 tri-grams, tetra-grams, penta-grams and hexagrams,并把它们作为密码的起始字母。接下来的字母使用了可以公开获取的mate1密码列表。我只使用了500万个泄漏的密码数据,为了证明这种方法即使使用了更少的密码也可以执行的更好,因为John the ripper 的马尔可夫模型是基于1300万的rockyou密码训练而成的。这样,我使用一个的密码列表(mate1)进行训练,另一个不同的密码列表(muslimmatch)进行测试。

我使用n-grams用户信息方法生成了6000万个密码,使用简单的有序Markov链方法并使用mate1密码作为训练列表生成了4000万个密码。

结果是25000个哈希值被破解。 这大约是32%,多于增强模式和马尔可夫模式。


结论

为什么它会发挥作用?它之所以起作用,是因为大量用户在密码中使用他们邮箱、用户名或其它详细信息;如果我们首先检查以部分用户名、用户邮箱开始的n-grams密码,我们可以直观的加快准确性,而这个实验证明了这种直觉是正确的。准确性提高的另一个原因是:我使用了相同类别的单词训练列表,都是成人社交网站。这两个因素是准确性提高的主要原因。

为什么这样做是有意义的?在我的笔记本电脑上,John the ripper 在不到2分钟时间内就产生了1亿个密码,如果我们能够在不到2分钟内破解32%的密码,这是很棒的事情,不是吗?


PS:我还做了一些试验,在密码结尾添加生日,而且结果是非常理想的。

这就是我所做的工作。我希望这个想法可以被你们进一步的拓展,让我们看到一些令人惊讶的结果。出于隐私的原因,我不能上传整理后的泄漏数据。


注意:这绝不意味着我已经打破了john the ripper的速度和准确性记录。John the ripper是一些了不起的人开发的一个伟大的工具。我只是认为,使用用户社交信息作为`n-grams`的增强马尔可夫模型可以显著提高密码破解速度。欢迎批评指正。


数据: https://github.com/faizann24/Using-Ordered-Markov-Chains-and-User-Information-to-Speed-up-Password-Cracking



原文链接:Using Ordered Markov Chains and User Information to speed up  Password Cracking 

本文由看雪翻译小组 FlamePeak 编译

LinkMe:FlamePeak.com


本主题帖已收到 0 次赞赏,累计¥0.00
最新回复 (3)
1
flamepeak 2017-3-1 10:39
2


如果想了解更多马尔可夫链,请参考:

如何用简单易懂的例子解释隐马尔可夫模型?

Markov Chain




哆啦咪 2017-3-3 10:49
3
chonhuang 2017-7-8 17:00
5
不错  支持
返回



©2000-2017 看雪学院 | Based on Xiuno BBS | 知道创宇带宽支持 | 微信公众号:ikanxue
Time: 0.012, SQL: 9 / 京ICP备10040895号-17