Thursday, September 10, 2015

How we cracked millions of Ashley Madison bcrypt hashes efficiently




Not long after the release of the Ashley Madison leaks, many groups and individuals attempted to crack the bcrypt hashes. Since the developers used a cost factor of 12 for the bcrypt hash, this made the process an extremely compute intensive task. We decided to take a different approach and made some rather interesting discoveries.

Without much information about the $loginkey variable and how it was generated, we decided to dive into the second leak of git dumps. We identified two functions of interest and upon closer inspection, discovered that we could exploit these functions as helpers in accelerating the cracking of the bcrypt hashes.

Through the two insecure methods of $logkinkey generation observed in two different functions, we were able to gain enormous speed boosts in cracking the bcrypt hashed passwords. Instead of cracking the slow bcrypt hashes directly, which is the hot topic at the moment, we took a more efficient approach and simply attacked the md5(lc($username).”::”.lc($pass)) and md5(lc($username).”::”.lc($pass).”:”.lc($email).”:73@^bhhs&#@&^@8@*$”)  tokens instead. Having cracked the token, we simply then had to case correct it against its bcrypt counterpart.

The $loginkey variable seemed to be used for automatic login, but we didn’t spend much time investigating further. It was generated upon user account creation and was re-generated when the user modified their account details including username, password and email address.

Discovery 1
Date: 31/08/2015
Filename: amlib_member_create.function.php
Function: amlib_member_create()
Lines of interest: 69, 70
Algorithm: md5(lc($username).”::”.lc($pass))  
According to line 70 of the code, the $loginkey variable was generated by hashing the lowercased username and password with MD5. Great, did this mean that we could crack the password by attacking the loginkey with md5($salt.$pass)? Line 69 would suggest otherwise, since $password was set to the bcrypt hash by the “encryptPassword” function. We wondered if it had always been this way, and a quick git blame revealed that this line was changed on 2012-06-14 with commit 1c833ec7. Here’s the difference:
       $username = !empty($Values['username_suggest']) ? $Values['username_suggest'] : $Values['username'];
+       $password = User::encryptPassword($Values['password']);
-       $password = $Values['password'];
       $loginkey = md5(strtolower($username).'::'.strtolower($password));

This meant that we could crack accounts created prior to this date with simple salted MD5.
Also, the possible charset was reduced by 26 due to the use of strtolower(). 

Discovery 2
Date: 31/08/2015
Filename: AccountProvider.php
Function: generateLoginKey()
Lines of interest: 78, 79
Algorithm: md5(lc($username).”::”.lc($pass).”:”.lc($email).”:73@^bhhs&#@&^@8@*$”). 
This function used a slightly different routine to generate the $loginkey as it incorporated the use of $username, $password, $email variables along with a constant salt string called $hash; and together, these variables were  hashed with the MD5 algorithm.
It appeared that generateLoginKey() was invoked when a user modified their account attributes (username, password and email) and as a result of this, a new loginkey was issued for that account. From our understanding, it appeared that bcrypt was not always used to hash the password prior to it being fed to the generateLoginKey function. This meant that this method could be used to recover passwords of accounts which had been modified prior to this code change.

Exploiting the discoveries

Two different algorithms were added to MDXfind to support these discoveries.  The simple version, MD5AM, implements the earlier code of md5(lc($username).”::”.lc($pass)); while MD5AM2 implements the more complex version, but pre-bcrypt.  MD5AM2 uses both the username and the email address, as well as a fixed salt, in the form of md5(lc($username).”::”.lc($pass).”:”.lc($email).”:73@^bhhs&#@&^@8@*$”).

Both required this information to be extracted from separate SQL database entries, but were combined for ease of parsing into one string.  The username/email combination was supplied to MDXfind with the -u switch as a separate file.  

A third optimization was performed to identify and exclude MD5 hashes that could not be cracked using our discovered methods. These were $loginkeys created using the secure methods of md5(lc($usename).”::”.lc($bcrypt-string)). Since we had the username, and the bcrypt hash, we were able to isolate these hashes quickly.

Regardless, MDXfind was able to load all of the hashes, and because of the manner in which it stores and searches the hashes, we incurred negligible penalty from the search overhead of the “unsolvable” hashes.  This allowed us to find more than 2.6 million passwords in just a few hours, using just *one* CPU box only.

Alternatively

The hashes from the the dump were also converted into an appropriate format suitable for loading as md5($salt.$pass) into any existing CPU/GPU crackers (only for Discovery 1).

Case Correction

Having the solved md5 tokens however, did not mean that we “knew” the original password.  The token used only the lowercase value of the password and thus a secondary step to toggle the case of each character generating each variant was necessary, in order to properly crack the bcrypt hashes.  Fortunately, this was a fixed-set problem with each bcrypt hash, thus only one salt needed to be checked for each bcrypt against the case variants.

A separate run correcting our cracked tokens against the bcrypt counterpart validated that we had in fact solved millions of bcrypt hashes...in days, not years. As of posting our team has successfully cracked over 11.2 million of the bcrypt hashes. 

Update:
Dan Goodin from Ars Technica has also written an article which gives a thorough explanation of the process.
Update 2:
We have done a follow up post giving an overview of the cracked passwords.

#FOLLOW_US #JOIN_US #LOVE_US #HATE_US #CONTACT_US @CynoPrime
Twitter: @CynoPrime 
Blog: cynosureprime.blogspot.com
Email: cynosureprime@gmail.com
 
  

52 comments:

  1. Awesome work! I really hope that the people had changed their passwords already, otherwise lot's of cheaters will suffer. :)

    ReplyDelete
    Replies
    1. I think you didn't understand why Cynosure Prime did it ...

      Delete
  2. Good job, just point me to the pass list when you guys upload it ;)

    ReplyDelete
  3. Ah! That moment when you realize that you've been immensely outsmarted.
    Great job!

    ReplyDelete
  4. Check out the big brain on Brad ! Have fun sorting out the bots from the humans.

    ReplyDelete
  5. Awesome, I hope you do some analysis of the passwords as far as a Uniques & Count and post it somewhere. Could be useful to strip out the top 100 and drop the bottom 30% and add to a dictionary.

    ReplyDelete
  6. Awesome, I hope you do some analysis of the passwords as far as a Uniques & Count and post it somewhere. Could be useful to strip out the top 100 and drop the bottom 30% and add to a dictionary.

    ReplyDelete
  7. I'm more curious how this got into their code in the first place. What an enormous mistake in security design. They do the right thing and use bcrypt to store the main password hash with a high complexity. Then completely screw up and use md5 for some secondary hash of the password and even worse, remove case sensitivity. Why?

    ReplyDelete
  8. I'm more curious how this got into their code in the first place. What an enormous mistake in security design. They do the right thing and use bcrypt to store the main password hash with a high complexity. Then completely screw up and use md5 for some secondary hash of the password and even worse, remove case sensitivity. Why?

    ReplyDelete
    Replies
    1. Maybe as an efficiency measure as that much data/traffic MD5 is quicker? on login and they never thought anyone would get access to the source code to see how the MD5 hash was generated... who knows.

      Delete
  9. This comment has been removed by the author.

    ReplyDelete
  10. I'm no expert, but wouldn't all of the old username/password combinations have to be reencrypted with the same approach after it is made more secure on 2012-06-14? Otherwise you would have a set of encrypted keys using two different approaches. How could you validate against that, short of having two different methods based on when the passwords were created?

    ReplyDelete
    Replies
    1. Sounds like the loginkey was some kinda auto login, maybe it was set as a cookie or something along those lines and they simply didnt set the cookie on login if ye account was that old.. so those users would login normally. no idea really just speculating

      Delete
    2. Upon adding a new way of hashing passwords, you add a field "password_type" for the user entity... you initially set it to e.g. "legacy" and then when the user changes his password the field gets updated to the current algorithm. In the "password is valid" procedure, you have a simple case statement on that field and use the proper validator...

      Delete
    3. The recommended approach is to store the algorithm along with the hash e.g. MD5:hash:salt or bcrypt12:hash:salt. This allows you to easily identify what algorithm to use on a per-user basis. When you deem an encryption strategy obsolete you can still protect your existing users by wrapping their existing hash in a new algorithm; in this case that would be bcrypt-ing the existing md5 hashes and storing something like md52bcrypt:hash:salt.

      This strategy is further explained in this article: https://medium.com/@uther_bendragon/sustainable-password-hashing-8c6bd5de3844

      Delete
    4. They didn't have access to the unencrypted passwords so they couldn't just re-encrypt them. They could have wrapped the insecure encrypted strings with another layer.

      Delete
    5. You can also re-encrypt the password at their next login, where you have the password, but that will not help users who have churned out.

      Delete
    6. You can also re-encrypt the password at their next login, where you have the password, but that will not help users who have churned out.

      Delete
    7. Thanks all for the input. This is something many developers don't plan for: handling the next generation of security and making current designs future-proof. I understand the "double wrapper" approach now. Thanks for the details.

      Delete
  11. Ok. That makes sense if you are going to force all the less-secure people to update their details, which suggests that the easier to Crack passwords came from people who never logged back into the site for the last 3 years...

    ReplyDelete
  12. Ok. That makes sense if you are going to force all the less-secure people to update their details, which suggests that the easier to Crack passwords came from people who never logged back into the site for the last 3 years...

    ReplyDelete
    Replies
    1. NO excuse for keeping MD5 hashes in your database. Better to smear/delete the hashes and make the user employ the "forgot password" function, or use a composite algorithm as mentioned above.

      Delete
    2. Using a composite algorithm is most user friendly. I think AM is just like most sites. Only have very few tech people to keep their tech current. The company was launched back in 2001; but still quite a few year after AES was created. So there is no excuse not to have a much more secure model.

      Delete
    3. Using a composite algorithm is most user friendly. I think AM is just like most sites. Only have very few tech people to keep their tech current. The company was launched back in 2001; but still quite a few year after AES was created. So there is no excuse not to have a much more secure model.

      Delete
  13. Would anyone be interested in making a detailed tutorial outlining this process? I have an IT consulting company and I'm looking for material to present to clients from a security and weak password perspective. Would be willing to pay for a couple of hours of time.

    ReplyDelete
    Replies
    1. You might want to look at here.
      http://nelenkov.blogspot.com/2012/04/using-password-based-encryption-on.html

      Delete
    2. You might want to look at here.
      http://nelenkov.blogspot.com/2012/04/using-password-based-encryption-on.html

      Delete
  14. Don't understand why they had to store the pass hash to begin with as it can be computed every time the user logs onto the site. Also don't understand why users' emails addresses and credit information are stored on the site either. The user profiles shouldn't linked to those information.

    ReplyDelete
  15. Don't understand why they had to store the pass hash to begin with as it can be computed every time the user logs onto the site. Also don't understand why users' emails addresses and credit information are stored on the site either. The user profiles shouldn't linked to those information.

    ReplyDelete
  16. Success is never ending failure is never final

    ReplyDelete
  17. Thank you very much for this nice article. It will help the new bloggers like me. Really appreciate your effort.
    THANKS

    ReplyDelete
  18. This comment has been removed by a blog administrator.

    ReplyDelete
  19. http://priceinbdindia.com i want to add

    ReplyDelete
  20. Bonjour, à tous j'offre et partage des codes Free Wifi Code Orange et SFR chaque semaine pour vous connecté a internet dans toutes la france

    Mon site de partage ▄︻̷̿┻̿═━一 http://caribbeansunshine.co/


    free wifi identifiant gratuit

    ReplyDelete
  21. Thanks for the info. Check out quality parts inspection system parts from www.e3view.com/eng/

    ReplyDelete
  22. BN+ Brute force hash attacker-md5 cracker
    http://bicombusiness.blogspot.com/2016/01/bn-brute-force-hash-attacker-md5-cracker.html

    ReplyDelete
  23. thank you for such a nic article, check here my site Symphony Mobile

    ReplyDelete
  24. Instagram asking me for a security code and they didn't send me?
    encrypted messenger

    ReplyDelete
  25. I really like this post. Highly recommend to everyone. Thank you.
    Password breaking

    ReplyDelete
  26. nice article . your article help me very much . thanks for
    Sharing

    ReplyDelete
  27. I have learn some excellent stuff here. Certainly worth bookmarking for revisiting, Thank you
    Password breaking

    ReplyDelete
  28. This comment has been removed by a blog administrator.

    ReplyDelete
  29. This comment has been removed by a blog administrator.

    ReplyDelete
  30. This comment has been removed by a blog administrator.

    ReplyDelete
  31. This comment has been removed by a blog administrator.

    ReplyDelete
  32. Thanks for share kind information .

    All kind of free net follow this

    Robi Free Net Android

    ReplyDelete
  33. I use PasswordWrench. I switch my important passwords every 30-60 days, and make them long, but I can none remember them and ended up using variations of the same password over and over, which is not safe. This way they help me originate my own personal system for managing my passwords.

    ReplyDelete