Intro to John The Ripper

In this post we will present a short intro regarding the software password cracking tool named “John the Ripper” (JTR). This tool is designed to be both powerful and fast, and it combines several cracking modes in one program. It is available for many flavors of Unix, Windows, DOS, BeOS, and OpenVMS and it is the most popular available password cracking tool. The tool can be customized to mix different cracking techniques and also can auto detect password hash types.

JTR can work in three different modes: wordlist mode, single mode and incremental mode. Wordlist mode takes text string samples from a file (wordlist) containing words found in a dictionary or real passwords cracked before). Then it encrypts those words in the same format as the password being examined (including both the encryption algorithm and key), and comparing the output to the encrypted string. In addition, it can perform alternations to the data from the wordlist and compare these as well. Single mode uses login names, GECOS (information about the account or its user(s) such as their real name and phone number) and users’ home directory names as candidate passwords. This mode is faster than the wordlist mode since the used information is compared with passwords (and hashes with the same salt) for the account that is was taken from. JTR incremental mode is the most powerful mode since it can try any character combination until the password is found. However, this technique is often impractical due to the possible number of combinations that increase the computational cost (overhead). This mode actually uses trigraph frequencies tables (three letters combined together), separately for each character position and for each password length.

JTR supports two of the techniques described in the previous post, dictionary and brute force attacks. Single and wordlist modes are practically dictionary attacks, since as we explained above each one of them uses a wordlist that contains strings that can be used as a password. Of course, single mode will search in a shorter wordlist in length but nonetheless it can be classified as a dictionary attack. Moreover, JTR supports brute force attacks since the incremental mode theoretically is an implementation of this attack. As in brute force attacks, the incremental mode tries every combination of characters until the password is found. The practical difference is that incremental mode uses characters with trigraph frequency.

Information of how to install and use JTR can be found here. In the next post, we will show how to crack one million passwords from online leaked lists.

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.

Password Hashing and Cryptographic Hash Functions

According to the National Institute of Standards and Technology (NIST) [1], a hash algorithm takes binary data (message) and produces a condensed representation, called the message digest. Particularly, a hash function accepts a variable-length input and generates a unique fixed-size output (“compression property”).

The origin of the term “hash” has non-technical meaning. Hans Peter Luhn (1896 – 1964), a computer scientist for IBM, was the first that used the term “hash” to explain that hash functions “chop” the input domain into many sub-domains that get “mixed” into the output range to improve the uniformity of the key distribution. Hash functions are used for password protecting because the main purpose for this issue is to encrypt passwords in a form that is unfeasible to decrypt and also confirm if the given password is correct.

Hash function classification: Hash functions informally have the property of easy computation, i.e. given y and an input x, y(x) is easy to compute. That property implies an unkeyed hash function, but in general hash functions refer to both unkeyed and keyed hash algorithms. Two types of hash functions are the Modification Detection Codes (MDCs) and Message Authentication Codes (MACs). MDCs are a subclass of unkeyed hash functions and their purpose is to ensure the required by applications data integrity. MDCs are classified into one-way hash functions (OWHFs) and collision resistant hash functions (CRHFs). OWHFs are the functions that given an output (hashed input) is difficult to find the input (pre-specified hash value) and CRHFs are functions that given two inputs it’s difficult to find the same hash-value output. On the other hand, MACs purpose is to assure, without additional mechanisms, the source of a message and its integrity. MACs have two functionally parameters, a secret key and a message input and they belong to the class of keyed hash functions.

Figure 1: Hash function classification [1].
Figure 1: Hash function classification [2].

Cryptographic hash functions (CHFs) can be used to implement password hashing. We have to mention that although CHFs are hash functions, the term hash function per se doesn’t mean that every hash function is cryptographic as well. A cryptographic function is usable for security purposes because it offers a high degree of protection against unintentional and intentional modification. The cost for this purpose is that they are far more computationally intensive and thus slower than typically hash functions.

A cryptographic hash function must satisfy some properties depending on the application. CHFs are one way (“preimage resistance”) procedures, i.e. h is “preimage resistant” if given a hash value y it is computationally infeasible to find x such that h(x)=y. Moreover, CHFs have the requirement of “preimage resistance”, i.e. given the input x1 and its hash value h(x1), generating an input x2 with hash value h(x2)=h(x1) is computationally infeasible. Also, CHFs are “collision resistance”, i.e h is “collision resistant” if it is computationally infeasible to find any two inputs x1 and x2 such that h(x1)=h(x2). For example, if we hash the words “harrys” and “harris” the result is totally different:

hash(“harrys”) = 47682637ac38fe39739da284829b937482398ef384

hash(“harris”) = ab1738e02893829ef9312cb14c14ca452400030402

Now that we have an overview of hash functions let’s explain why we hash passwords and the properties that password hashing must have. First of all, password hashing is somehow necessary because we want to be more “secure” from attackers that maybe get access of our database. Specifically, by password hashing we are trying to make it as painful as possible for attackers to retrieve our passwords. Password hashing will not make our passwords impervious to attacks but it will perform “damage containment” in the event of a breach. Hashes have the advantages to generate quick and also are small to store. However, these advantages are also their weakness because it is simple after all to compare hashes of basic passwords with a table of precalculated hashes and then “dehash” all the passwords. Thus, password hashing requires to be fast on software, slow on hardware and have a unique salt per password. 

The solution is to hash more than just the password. This procedure is called “salting”. Not all the passwords use “salt” but when they do it boosts the security of each password so it won’t crack. The “salt” is a random value (not duplicated between passwords) appending or prepending the password before hashing. We do this process in order two passwords don’t generate the same hash value. In order to check if the password is correct we need the “salt”, hence it is stored in addition to the hash or as part of the hash string itself so that the hashed password can be reconstructed correctly for comparison. “Salting” is mostly used to prevent precomputation attacks against the digested message. Precomputation-based attack method works only for small ranges of input values, so by “salting” our password we increase the size of it and the resulting precomputation table with possible hashes would be too large even for a small subset of passwords.

Figure 2: Examples of hashed passwords [3]
Figure 2: Examples of hashed passwords [3].