如何高效破解Ashley Madison网站中上百万的bcrypt哈希？

Ashley Madison数据泄露不久之后，很多组织和个人尝试破解bcrypt哈希。很多开发者使用12作为成本因数破解bcrypt哈希，所以使得这个过程的计算强度很大。我们决定使用另一个方法，并且发现了很多有趣的东西。

我们没有关于$loginkey变量的很多信息，也不知道它是如何产生大量信息的，所以我们决定从git dumps的漏洞中寻找线索。我们确定了两个有趣函数并仔细检查，发现我们可以利用这些动能，加速破解bcrypt哈希。

通过在这两个函数中观察到的两个不安全方法产生$loginkey，我们破解bcrypt哈希密码的速度会得到大幅度提升。我们没有直接慢速破解bcrypt哈希，这个方法目前是一个非常火的话题，我们采取了更有效的方式，即使用简单攻击md5(lc($username).”::”.lc($pass)) 和md5(lc($username).”::”.lc($pass).”:”.lc($email).”:73@^bhhs&#@&^@8@*$”)  token的方式代替。破解token之后，我们接下来只需要获得它所对应的bcrypt就可以了。

$loginkey变量似乎被用户自动登录，但我们没有花费很多时间进一步调查它。它是在用户创建账户的时候生成的，用户修改账户信息，包括用户名、密码、电子邮件等信息的时候再次生成。

发现1：

日期：2015-08-31

文件名：amlib_member_create.function.php

函数：amlib_member_create()

所在行数：69, 70

算法：

md5(lc($username).”::”.lc($pass))

        根据第70行的代码， $loginkey变量是通过哈希散列把小写的用户名和密码进行MD5声称的。太好了，这不就意味着我们可以通过攻击使用md5($salt.$pass)(密码加盐进行MD5) 的$loginkey来破解密码？第69行从另一方面给我们提示，因为$password是通过“encryptPassword”函数被设置为brcypt哈希的，我们想知道是否它一直是这么被设置的。一个quick git blame透露这行在2012-06-14的commit 1c833ec7被修改了。下面是区别：

 $username = !empty($Values['username_suggest']) ? $Values['username_suggest'] : $Values['username'];
+      $password = User::encryptPassword($Values['password']);
-       $password = $Values['password'];
        $loginkey = md5(strtolower($username).’::’.strtolower($password));

这意味着我们可以使用简单的加盐的MD5破解在这个日期之前被创建的账户.

同理，由于使用了strtolower()，可能的字符集被减少了26。

发现2：

日期：2015-08-31

文件名：AccountProvider.php

函数：generateLoginKey()

所在行数： 78, 79

        算法：

md5(lc($username).”::”.lc($pass).”:”.lc($email).”:73@^bhhs&#@&^@8@*$”).

这个函数使用了略有不同的方式产生$loginkey ，因为它结合使用了$username, $password, $email变量和一个名为$hash的恒定盐串，合并在一起，这些变量使用MD5进行哈希。

看起来在一个用户修改他们的账户属性（用户名、密码和电子邮件）的时候，generateLoginKey()被调用，结果是一个新的loginkey被添加道账户中。从我们的分析可以得出，看起来在馈送到generateLoginKey 之前bcrypt并不总是用于哈希密码。这就意味着这个方法可以在修改代码之前被用来回复用户的密码。

该利用的发现：

两种不同的算法被加入到MDXfind中支持这些发现。这个简单版本MD5AM实行在md5(lc($username).”::”.lc($pass))的早期代码中，MD5AM2实行了更加复杂的版本，但是是pre-bcrypt。MD5AM2使用用户名和电子邮箱记忆固定盐进行加密，形式如下：md5(lc($username).”::”.lc($pass).”:”.lc($email).”:73@^bhhs&#@&^@8@*$”)。

这两种方式需要的信息都从SQL数据库中单独提取，但合并以便解析成一个字符串。用户名电子邮箱混合是基于MDXfind进行的，它与-u交换作为一个单独的文件。

第三个优化被用户识别和排除MD5哈希散列，这个哈希散列保证使用我们的方法不会被破解。这里面的$loginkeys创建使用了安全的方法：md5(lc($usename).”::”.lc($bcrypt-string))。因为我们有用户名和bcrypt哈希，我们能够快速得到单独的哈希。

无论如何，MDXfind可以用于加载所有的哈希散列，而且由于它自身储存、查找哈希的特性，我们获得了不可忽视的因为搜索不可解哈希的罚款。这允许我们在几个小时内就找到了超过两百六十万密码，仅仅使用了单核CPU。

案例修正

虽然解决了md5 token， 然而，并不意味我们知道了原始密码。Token仅仅被用于密码中的小写值，因此第二步是确定每个字符在不同情况下的切换，以便合理的破解bcrypt散列。幸运的是，每个bcrypt散列设置是固定的，因此进需要一个盐就可以检查每个情况下的bcrypt。

一个独立运行正在证实我们这种用bcrypt对应破解taken的方法，我们实际上已经在几天而不是几年当中破解了上百万的bcrypt哈希。我们团队共计破解了11.2 million的bcrypt哈希。

更新：

来自Ars Technica的Dan Goodin写了一篇文章详尽的解释了这个过程。

更新2：

我们已经完成了后续的帖子对破解密码给出了概述。