Since a long time, passwords have been the most popular way for authentication and proving identity. Some new biometric techniques have evolved recently and have proven great accuracy and security. However, they are not used except in very sensitive places due to their high cost. Hence, passwords are the main method of authentication used in networks. This article is about password cracking techniques, optimisations, and tools.

According to the information base that the cracker has, password cracking may be classified into two types: informed cracking and uninformed cracking. In informed cracking methods, the cracker has prior knowledge about the password. This knowledge could be the password key space (i.e. the possible combinations of the password), the password structure (for example, the fist character must be a number and the following characters must be at least 6 alpha-numeric), or the cryptographic hash (i.e. The output of a non-revisable mathematical function applied on the password).

On the other hand, in uninformed cracking, the cracker has ultimately no information about the password. It is noteworthy to mention that password cracking in this context means passing through the authentication challenge successfully regardless of knowing the original password.

Brute forcing is the most basic method for cracking a password. It can be used regardless of the cracker possession of the original hash value. If the cracker has the hash, the process will try all different possibilities and combinations of the password until the hash of the attempted trial matches the original hash value. Otherwise, in an uninformed cracking, the regular authentication procedure has to be used in trying all different possibilities along with a way to identify the successful log in attempt.

The obvious time limitation is what makes this attack almost unfeasible in its original form, given that the password is cryptographically secure enough. However, there are several variations to this attack discussed later that might be feasible to use in cracking complex passwords. A very common programme for multithreaded (parallel) password brute
forcing is THC Hydra, which has been updated recently to support advanced CPU optimisation techniques [1].

Dictionaries

A natural enhancement to the brute force approach is trying to narrow down the possible password key space. It is a common human nature to choose
understandable words for the password. This, unfortunately, eliminates a big search space of the non-readable character combinations, and simplifies the mission for crackers. A dictionary attacks against a password exploits this human vulnerability by using dictionary words as the main source of the key space.

This attack can be done on either the original hash or the authentication mechanism, in case the hash is not available. Thanks to electronic social media; the overall security awareness is in a state of continuous improvement. It is getting harder for crackers to guess passwords, because people are starting to use more complex words. Despite being complex, the words are still readable. Hence, a few optimisations are devised by crackers to improve dictionary attacks:

Customized Dictionaries:
Typically, people choose passwords relevant to their context. A slew of tools are out that analyse human profiles (Facebook accounts, blogs, Websites …etc) to generate a word list of password candidates. This word list is later used as the key space for brute forcing. This technique has been proven to be one of the most effective methods in penetration testing. Common password list generator tools include (CUPP, CeWL, and Crunch).

Hybrid Optimisations:
Another password choosing habit that can be abused is when a user slightly modifies a dictionary word to be a nondictionary, and uses it as a password. Words such as (pa$$w0rd, koolB0y, applepie …etc) are technically not  dictionary words. However, a relationship exists between those passwords and dictionary words. There are several hybrid optimisations that take advantage of this human vulnerability in order to produce a better password guessing schema. Xieve technology is devised by Passware to predict possible human readable alterations of dictionary words [5].

It uses an algorithm that mutates and combines dictionary words to produce a slightly bigger enhanced key space which are still orders of magnitude smaller than the original full key space, but way more capable of finding the correct password.

GPU Optimizations:

Another orthogonal aspect for password cracking optimisation is the hardware dimension. Modern Graphical Processing Unites (GPUs) can be used to optimise password cracking methods due to its vectorisation. They support complex vector processors that are capable of bulk vector computations. Typically, this is used for graphical processing. However, it is also very handy in password cracking due to its high parallelism. Crackers use GPU frameworks to boost password cracking by arranging password key space values into vectors with the maximum size that the GPU processor can handle at once, and process those combinations in bulks as a single trial. Obviously, the more powerful the GPU is, the more speed-up gain is achieved; one GPU processing cycle trial could include more than 10 key trials.

According to Elcomesoft, a security research company specialised in password cracking; the speedup can reach 50000% [8]. The chart below (by ElcomeSoft) shows the possible speedup gain for different GPUs.

Rainbow Tables

In informed cracking, when the cracker has a hold of the password hash, the original password cannot be inferred due to the inherent non-reversibility of password hashes. So, it is a matter of trial and error. Password cracking using rainbow tables is typical in such scenarios. It is an example of the classic time-memory trade-off. In the original brute force method, the cracker must try to hash all possible passwords to compare it with the original hash each time a cracking procedure is in place.

Rainbow tables, on the other hand, utilise pre-computed look-up tables for all the key space required to brute force. And when a given hash is required to be cracked, the problem is transformed to a search problem where the cracker is only going to look up the correct hash value in the pre-computed tables.

Rainbow tables cracking typically reduce the complexity of finding the correct password to orders of magnitude of its rival brute force methods. According to a security researcher at “the coding horror” security blog, the password “Fgpyyih804423”, which is considered a secure password, can be cracked in 160 seconds [4]. You can get the precomputed rainbow tables for most known algorithms from a number of commercial websites, such as rainbowcrack [2] and ophcrack [3].

Pass-the-hash
If the cracker already has the password hash, and the server uses the password hash only to prove the users identity (e.g. windows network authentication), the cracker then can create a custom script that just sends the saved hash to the server when requested without knowing the original password. Since the server does not know if this hash is generated on the fly or cached, it will authenticate the cracker as a benign user [6]. The figure below shows a typical authentication scenario for a user trying to access a resource on a file server. Now, what if someone tapped the line, captured the sent password hash in step 6, and replayed it later on without knowing the password? He will be granted access (under certain conditions).

Pass-the-hash is very effective in cases of repeated or static server authentication challenges such as the windows net-bios file sharing protocol. A common tool used for pass-the-hash attack is Pass-The- Hash Toolkit from security-database [7]. Also, the notorious Metasploit Framework has pass-the-hash capabilities

The Cloud
Cloud computing is “the trend” nowadays. Unless you have been hiding under a rock for the last two years, you must have heard about cloud computing. Amazon Elastic Cloud Computing (EC2), and Microsoft Azure are popular examples. With such gigantic infrastructure available on-demand, crackers are leaning towards using it for evil. Distributed computing systems can be used to divide the password trials among the working cluster, since the password cracking process is naturally divisible where each
node in the cluster would try a subset of the key space.

You can start a 100 node high computing cluster with high end GPU capabilities and use it in parallel to crack Ultra complex passwords in a matter of minutes! A German hacker recently cracked a SHA- 1 hash for 2$ according to the register security magazine [9]. Also, a security white hat, Moxie Marlinspike, created a cloud WPA cracker for 17$/password,which is able to crack any WPA password in less than 20 minutes [9].

Conclusion
It is very clear that black hats are moving towards more convoluted techniques to crack passwords. A highly technical cracker now would try to pass the hash, create a profile for the target user to infer a password key space, optimize and enhance the key space using mutation algorithms, and at the end, buy some rainbow tables online, or rent an on-demand cluster from a cloud infrastructure service, and that’s it… your password is cracked! Even worse, a bot-master who controls a herd of zombies (botnet) through Trojan horses can use the botnet capabilities to crack passwords pretty much the same way it would be done using cloud computing, only for free!. Therefore, one should be very vigilant when choosing a password, because no one knows what is lurking in the dark hallway.

References
http://freeworld.thc.org/thc-hydra/
http://project-rainbowcrack.com
http://ophcrack.sourceforge.net
http://www.codinghorror.com/blog/2007/09/rainbow-hash-cracking.html
http://www.lostpassword.com/attacks.htm#xieve
http://www.sans.org/reading_room/whitepapers/testing/crack-pass-hash_33219
http://www.security-database.com/toolswatch/Pass-The-Hash-Toolkit-v-1-4.html
http://www.elcomsoft.com/eprb.html#gpu
http://www.theregister.co.uk/2010/11/18/amazon_cloud_sha_password_hack/

About the Author:

Ahmed Saafan is a senior information security analyst and the technical team lead of Raya IT Security Services Team (RISST). Saafan, the founder of RISST’s application security division, is  specialized in software security and advanced penetration testing.