Cracking Passwords with JTR

The previous two posts covered a part of the theory behind password cracking. Now, we will show how to crack passwords of two famous leaked password hashes list: Formspring and Linkedin. If you need the lists drop me an email.

First, we started by using the single mode attack on John the Ripper (JTR). Of course we didn’t get any positive results since as we explained in the previous post single mode uses login names, GECOS and users’ home directory names as candidate passwords. In the virtual machine that we installed for the purposes of this tutorial there isn’t much information that can be used for this method:

harrys@harrys-VirtualBox:~$ john –single 
'/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:25 100% c/s: 105 trying: harrys1928 – hharrys1900 


harrys@harrys-VirtualBox:~$ john --single 
'/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:25 100% c/s: 106 trying: harrys1928 – hharrys1900

Next, we used the dictionary mode attack. Unfortunately, we didn’t manage to crack any
passwords using this method although we used a variety of password dictionary lists. Let’s see some of the results for various dictionary lists that either are included in JTR or one can find online.

a. password.lst 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist=/harrys/john/run/password.lst 
'/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:24 100% c/s: 143 trying: !@#$% - sss 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist=/harrys/john/run/password.lst '/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:35 100% c/s: 98.88 trying: !@#$% - sss 

b. common-passwords.txt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/common-passwords.txt' 
'/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:06 100% c/s: 135 trying: uucp – zmodem 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/common-passwords.txt' 
'/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:00:07 100% c/s: 116 trying: uucp - zmodem

c. Given-Names.txt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Given- 
Names.txt' '/harrys/formspring.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:01:27 100% c/s: 98.81 trying: Zainab – Zygmunt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Given- 
Names.txt' '/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:00:01:03 100% c/s: 136 trying: Zainab – Zygmunt 

d. Huge-List.txt 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Huge- 
List.txt' '/harrys/formspring.txt' 
7Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:01:43:14 100% c/s: 140 trying: gethostbyname/gethostbyaddr - Karntnerstrasse- Rotenturmstrasse 

harrys@harrys-VirtualBox:~$ sudo john -- 
wordlist='/harrys/Downloads/Huge- 
List.txt' '/harrys/SHA1.txt' 
Loaded 1 password hash (generic crypt(3) [?/64]) 
guesses: 0 time: 0:01:18:58 100% c/s: 183 trying: gethostbyname/gethostbyaddr - Karntnerstrasse- Rotenturmstrasse

We have to mention that JTR also supports hybrid attacks, i.e. attacks that check for variations of a word or a combination of dictionary words. This method like the dictionary attack didn’t help us to crack the provided password lists.

Let’s move to our approach using the brute force attack method. As we explained, it consists of systematically checking all possible keys or passwords until the correct one is found. The program goes through all the possible plaintexts, hashing each one of them and then comparing it to the input hash. JTR uses character frequency tables to try first plaintexts containing more frequently used characters. This method is useful for cracking passwords which do not appear in dictionary wordlists, but it does take a long time to run. The default incremental mode checks potential passwords up to 8 characters. Just to show how time consuming this method is, we let our computer running in this mode for 2 days but the only result we got is that the our pc got overheated.

JTR program has an option for brute force attack that can make this process quicker. If we have prior knowledge of the password format, we can make this operation faster, by using a variation in incremental mode that only checks certain formats. Specifically, if we run:

./john – format=[MODE] password_list_to_crack.txt

JTR will use the MODE that we specified.

For example, for SHA1 mode (Fig. 1) JTR achieves cracking SHA1 hashes by first guessing the password using dictionary and incremental mode, and then generates theSHA1 hash for this password. Then, it checks if the hash that was generated for the password matches a hash in our file. When JTR finds a match then we recover the password from the provided list.

Fig. 1: One iteration within SHA1 compression function [1].
Fig. 1: One iteration within SHA1 compression function [1].
Our goal at this point is to do some research and find which hash function our lists used.

Formspring list:

This list used SHA256 hash function to encrypt the data that contains. This conclusion is based on two facts. First the provided hashes in this list have the follow form:

51e9b7073797d875a8862fbba743f7febec03164db4fdf91f10987b95be1852b

That means that the output of this hash function has 64*4 = 256 bits. This narrow our options of hash functions to algorithms like HAVAL256, RIPEMD256, SHA-3-256, SHA256 and GOST. JTR supports the two last methods. We checked both of those two formats in JTR. The GOST format processing time was too long without any result. On the other hand the SHA256 algorithm format was faster and we came to the conclusion that formspring list is hashed by that function (Fig. 2). This fact is also supported by various sites.

Fig. 2. Applying SHA256 algorithm format to JTR.
Fig. 2. Applying SHA256 algorithm format to JTR.

Linkedin list:

This list used sha1 hash function to encrypt the data that contains. This conclusion is based on two facts. First the provided hashes in this list have the follow form:

37b5b1edf4f84a85d79d04d75fd8f8a1c3d2fbde

That means that the output of this hash function has 40*4 = 160 bits. This narrow our options of hash functions to algorithms like HAVAL160, RIPEMD160, SHA0, TIGER(2)-160 and SHA1. JTR supports only the last hash function and this is the function that it was used to hash the passwords. This argument is also supported by the fact that the list name is SHA1.txt and the confirmation by the LinkedIn blog after the list was leaked. The new unstable version of JTR supports a mode called raw-sha1-linkedin that is especially for this specific list that it was leaked from LinkedIn.

Before the presentation of our results, we should mention that we could use also rainbow tables with JTR although the program does not support this method per se. The idea is to create a dictionary file using JTR and another software (e.g. CowPatty) to generate rainbow tables. In this post we focus our interest onto brute force attach method which generates a hash for each password and then compare it immediately with the correct password hash.

Fig. 3. JTR results for formspring list (SHA256 format).
Fig. 3. JTR results for Formspring list (SHA256 format).
Fig. 4. JTR results for linkedin list (sha256 format).
Fig. 4. JTR results for Linkedin list (sha256 format).

All the results above were obtained through running JTR on our computer for thirteen hours (let it run more time will give more cracked passwords). The results are quite impressive. To understand what these results mean we used graphs for better representation.

Fig. 5. (a)
Fig. 5. (a) Graphical representation of the Formspring cracked list results: Cracked passwords as a function of time.
Fig. 5 (b). Graphical representation of the formspring cracked list results: Combinations per second as a function of time.
Fig. 5. (b) Graphical representation of the Formspring cracked list results: Combinations per second as a function of time.
Fig. 6. (a) Graphical representation of the linkedin cracked list results: Cracked passwords as a function of time.
Fig. 6. (a) Graphical representation of the Linkedin cracked list results: Cracked passwords as a function of time.
Fig. 6. (b) Graphical representation of the linkedin cracked list results: Combinations per second as a function of time.
Fig. 6. (b) Graphical representation of the Linkedin cracked list results: Combinations per second as a function of time.

For the Formspring list we are able to crack 1392 passwords in around nine and a half hours, whereas for the Linkedin list we cracked 1108644 passwords in around thirteen hours. For both lists the combinations per second are decreasing as the time runs and the guesses are increasing. Of course, if we were able to run the program for more time, then our results would be more impressive because we could present all the passwords from the hashed lists.

Observations

Based on the results presented in the previous paragraphs, a number of observations can be made: First, we noticed that the LinkedIn list is cracked easier than the Formspring list. That means that using the LinkedIn list we cracked faster more passwords than the Formspring list. The reason is that in the LinkedIn list passwords are stored as unsalted SHA1 hashes and thus it takes less amount of time to crack this list. Unsalted hashes are much less secure than salted hashes because the password is not merged with another combination and then hashed. So, it takes less time to recover the passwords from Linkedin list compared to the Formspring one. On the other hand, the Formspring list uses the SHA256 function to hash the password after the password is combined with a prep-ending salt. Hence, it takes more time for JTR to recover the passwords from the Formspring list. Another interesting observation is that JTR brute force attack cannot easily crack both lists after a considerable amount of time. Although JTR starts cracking password easily at the beginning, as the time is running JTR recovers less passwords than before because it checks for password with a larger length.

What is unique on those two password lists?

The cracked passwords from the Formspring list show that the formula that it was used to hash these data was SHA256(“00-99”+”password”), i.e. each password was hashed after a number with range from 00 to 99 (salt) prep-ends the password. For example the password named “harrys” was hashed using the SHA256 hash algorithm after mixed with a random number from 00 to 99, i.e. SHA256(“58”+”harrys”). This hash weak method is quite easy to be cracked since the used salt has a range of 100 possibilities.

A view at the LinkedIn list reveals that many of the hashes contain five zeros at the beginning. That is something impossible for passwords that are hashed with the SHA1 hash function. We assumed that someone replaced the first five digits of some hashes with zeros so we would not be able to crack them. We removed these lines starting with “00000” as they are obfuscated hashes. This technique can be done using the “grep” command, i.e. “grep -v ‘^00000′” which will exclude all the lines from Linkedin file containing the “00000” string. We can get the same result using the raw-sha1-linkedin format mode in JTR that works with the same way.

Advertisements

Password Cracking Techniques

There are a lot of different ways to crack a password. The figure below shows some scenarios attempts that can occur. If the attacker has access to a machine and consequently to the password hashes then he can use any password cracking technique of the follow:

Figure 1: The flow of password attacking possibilities [1].
Dictionary attack

Dictionary attack uses a wordlist that contains words, phrases, common passwords and other strings that can used as a password. The password is cracked after comparing every word in the wordlist (after hashed) to the password hash. Dictionary files are created by extracting words from large bodies of text and even from real databases of passwords. These files are also containing words with appending numbers to the end of them (e.g. “harrys123”) and with their leet speak equivalent (“harrys” becomes ”h4rry5”). This method is popular because many people use common words as passwords. We have to mention that dictionary wordlists are also available for technical and foreign languages. Although, dictionary attacks have a fairly high speed, are ineffective against passwords that are not based on a dictionary word. For instance, the password “#!d^3m4&0z” is improbable to be found by a dictionary attack. Moreover, by “salting” the password, the attacker would need to precompute hashes for each password coupled with each possible “salt”. This can be a huge restraint for the attacker, especially if the salt is large enough.

Brute Force Attack

Brute force attacks can be used in cases that dictionary attacks were unable to recover a password. The reason is that brute force attacks try every combination of characters up to a given length until the password is found. For instance, given a length of 6 characters in a password, brute force attack will follow a sequence of “aaaaaa”, ”aaaaab”, ”aaaaac” and so on. It is obvious that this attack is the slowest method of password crack attacks, very computationally expensive and the least efficient in terms of cracked hashes per processor time. Nevertheless, brute force attack will always eventually find the password and can be very successful on short and simple passwords.

Rainbow table attack

Rainbow table attack is an implementation of the time-memory trade-off method developed by Philippe Oechslin. It is called like that because it consumes time to be created, but after that password recovery it is very quick.The idea behind rainbow tables attacks is lookup tables*. The previous attacks, i.e dictionary and brute force, generate the hash for each password and then compare this hashed password to the correct password hash. On the other hand, rainbow tables compute hashes for words taken from a dictionary, store all these values into a table, retrieve the hash of the password to be cracked and do a comparison between the real password hash and the password hash from the created table. The difference however between these lookup tables is that rainbow tables sacrifice hash cracking speed to make lookup tables smaller. Thus, rainbow tables are more effective compared to simple lookup tables because the same amount of space is used to store more cracked password hashes. However, these tables are also quite large. For example for passwords up to 7 characters the MD5 rainbow table is 64GB [2]. These tables can crack non-dictionary based words very fast but due to the nature of this attack not all passwords can be found. Like dictionary attacks, rainbow table attacks can be prevented by “salting” the passwords before storing them.

Figure 2: The spectrum of possibilities for password cracking attacks [3].
Figure 2: The spectrum of possibilities for password cracking attacks [1].
*lookup tables are data structures containing pre-computed hashes of the passwords in a password dictionary and also their corresponding password.