Password cracking: proving your login insecure (or not)

Password cracking: proving your login insecure (or not) by N. Gobbo, S. Aruch, D. Vitali {n.gobbo, s.aruch, d.vitali} “
Please, enter your username and password.” In our digital life we read this request many times a day, for example while accessing our e-mail portal, the bank account, facebook and any other web-service that, in order to deliver the tailored experience we are used to, needs to know the answer to a simple question: “who are you?”
The process of proving who you are to another entity that knows you only “partially” or, maybe, cannot meet you in person, is called authentication: this problem came up quite often in history and still poses a challenging task nowadays. If we get back in time, for example, we may have found a sentry asking the secret sentence before letting the stranger in front of him cross the bridge. Moving forth in time, we may have intercepted some treasure chests secured by a couple of padlocks or a letter sealed by a peculiar-shaped red-wax insignia. More recently, instead, you may have been asked to put your face into a wall hole in order to have your face analyzed before entering the bank vault.
Each of the examples presented shows one of the three authentication factors that has been identified in literature. You may prove your identity using:
Figure 1. Examples of the three authentication factors: Google login prompt filled with credentials, an OTP key from RSA and a human fingerprint 
The easiest to use of the just presented authentication factors is without doubts the first one: you don’t need to create any object and you don’t have to move from one place to another to prove your existence, you just need to remember a particular sentence and securely share it with the entity you are planning to authenticate with. For this reason when the information-age moved its first steps, and the electronic inventors saw their first sun, the first authentication method chosen has been knowledge based. The authentication process – also known as “logging in” – has a preliminary set-up phase where the user exchanges a secret with the server that, in turn, stores it for future use: to ease information transmission and lower disk consumption the secret is usually a string of printable characters, which took the name of password. After that, whenever a user needs access, the server prompts him with a credential form and then it has to:
  • wait for user login – i.e. the username and password couple;
  • process received data and then match it against its own database;
  • send back to the user the authentication result consisting either in an access granted message if a match has been found, or in a log in rejection otherwise.

Before digging into the password-cracking topic, however, we need answer a last question: how the server
is saving log in credentials. In early days of Internet the server usually stored that information in clear text; this posed a security problem because authentication information were available to anyone with access to
the storage position both if this person was allowed and, more problematic, if he was not, for example after a breach. For this reason instead of saving the password value as-is, servers now stores the result of processing the password with an hash-function, that is, a one-way function that besides being easy to calculate and hard to invert also always produces fixed-length outputs.

Once described the scenario we are moving in, now we try to understand how an entity may recover a password after it has been stored on the server that is, let’s wear the password-cracker hat. Password cracking is not an evil-guy only activity; in fact, every system administrator shall check their users’ password strength or, during their job, may be asked to recover lost access credentials, without the option to just reset them. So how are these people working? We should make first a distinction whether or not the cracker is able to make a credential check without invoking the authentication server that is, if an offline attack is feasible

or he has to fall back to an online one. This information is very important because it has a huge impact on the performance of the attack, usually measured in number of “tests” per second: because the online attack involves a communication with the authentication service, its time efficiency is far worse than the offline counterpart, usually from 4 to more than 8 degrees of magnitude. We now proceed to a description of both these attacks pointing out some of the common tools used in each case.

An authentication system is inherently prone to online attacks because, usually it cannot distinguish between legitimate and malicious requests. This consideration gives crackers the ability to query the server steadily, checking each time a different login, until the server accepts one of them. For this purpose exists a plethora of different tools usually specialized to probe a single server or protocol type; three of them, however, stand above the other for the number of supported protocols and/or their performance: THC-Hydra, Medusa and Ncrack.

fig2Figure 2. Example of a typical hydra run trying to find local SSH root password 

They all work by using multiple instances that hammer at the authentication server walls, using tweaked message exchanges in order to minimize the time needed to get an answer from the server. Performance here is tightly dependent on protocol definition, network bandwidth and – mostly – latency with typical values ranging from 1 to 1000 tests per seconds. Protocol definition plays also a central role in mitigating this kind of attack: for example a two-message protocol expecting a login couple and returning an accept/reject message is far more vulnerable than an iterative protocol, which asks username and password consequently, maybe requiring also the client to carry on some computation in between. Other solutions to lower crackers online attacking capacity includes Captchas when a web login is involved, otherwise forced delays between requests or temporary client blocking: all of these fixes are very effective because the server manage every single request thus taking suitable reactions when observing malicious behaviors.

fig3Figure 3. Output of oclHashcat-plus against a single IKE-PSK MD5 hash, using full-power GPU acceleration – 

Offline attacks, on the other side, speed up attacker’s testing capabilities to a whole new level. There are different enablers for this kind of attack and while the most common are still some form of data exfiltration like user’s table dumps or OS’ credential repositories, also weak protocol definition may be exploited forthis purpose as in the recent WPA/WPA2 crack. When an offline attack is available, the only bound in cracking capacity is given by available processing power, scaled by a suitable factor that takes into account the computational complexity of performing a single check. As well as for the online case crackers has a lot of tools at their disposal for this kind of task, with most of them being written for a specific task (try searching Google for “zip password recovery”). Some of them, however, stand out for their performance and the number of checks supported: a well-known tool is the long-time famous Jonn-The-Ripper as well as Cain&Abel, both of them, however, do not take full advantage of parallelization usually available on current architectures. The hashcat suite has made a huge step forward in this direction and, with oclHashcat-plus, has gone even further by exploiting massive parallelization offered by GPUs. To understand what this means we may compare performances advertised by developer’s sites: for oclHashcat-plus an AMD HD7970 can check more than 3 million of MD5crypt hashes each second coming from passwords up to 15 characters long; for the same test type John-the-ripper stops at barely 45 thousands checks per second per core on a Celeron E3200 overclocked at 4.00GHz. It’s however interesting to notice how impressive these results are when compared with an online attack.

fig4Figure 4. A simple run of John-The-Ripper against Kali’s shadow file: by default john leverages information inside input file and elaborate them via some basic mangling rules. In this example the password was reversed username 


From a prevention point of view, an obvious remediation is the design of authentication protocols that
does not send information exploitable by an attacker to mount the attack. Even if all protocols were secure from this point of view, however, data exfiltration will not stop any time soon, so we have to take into account possible mitigation techniques. The performance formula presented above states that the only
way to decrease the number of checks per second is increasing the time needed to make a single check.
For this reason SHA512crypt uses key stretching, a process which involves multiple iteration of a hash functions: the first iteration take as input the user password and a known random token called “salt”, all successive iterations uses as input the output of the previous run and the same salt. This way SHA512crypt computation is deliberately slower than bare SHA512 but also more cracking resistant, even if both of them are cryptographic hash functions thus having the same pre-image, second pre-image and collision resistance. Other than key stretching, also key strengthening is designed to deliberately slow down the check procedure, both for the attacker and the legitimate user. It works exactly like key stretching with the only difference that the random salt is deleted after calculation and not stored along with the hash thus forcing the trial of many different salts whenever a check is needed.

Either the cracker uses an online or offline attack, however, it has to choose which passwords to test and in which order. First of all we have to introduce the concept of “alphabet” representing the set of characters which it is possible to choose from when build a password – usually the ASCII set – and the ideal password “strength”, measured by the number of different strings it is possible to draw given an alphabet and a chosen length. A first, naive approach to password cracking may be to test every possible password combination, that is, use a brute-force attack. Nonetheless, a simple evaluation of the number of different 10-character long alphanumeric strings, that is 6210, gives more than 8 thousand years to crunch through all the combinations at hashcat rates stated above. This is clearly out of reach for current technology’s processing power and it is usually referred to as the exponential wall of password cracking.


fig5Figure 5. The exponential wall of password cracking – Rob Graham, Errata Security

Due to the presence of this unavoidable obstacle, crackers moved their attention from the power performance focusing also on the efficiency, described by Joseph Bonneau as “the ability to generate large lists of candidate passwords accurately ranked by real-world likelihood using sophisticated models.” This means that crackers try to avoid unnecessary checks exploiting the fact that users choose passwords also easy to remember, thus using only a limited subset of the password space, weakening the ideal strength. This kind

of techniques goes under the umbrella called dictionary and hybrid attacks. The basic building blocks are the wordlists filled with common words and passwords, usually coming from previous credential leaks; these lists are crunched as-is as a first step of every cracking session. Once this first sweep is complete, multiple lists can be combined together to get multi-words combination and then mangled with appropriate rules to obtain common pattern or substitution, as for the l33t alphabet. As soon as the cracker has enough “plains”

– this is the name of a recovered hash – it checks whether the source presents some bias or, for example, there seems to be a password policy forcing certain password composition rules. PACK (Password Analysis and Cracking Kit) is the tool coming into play here as it performs an analysis of a given wordlist detecting patterns, masks, rules and other characteristics. The output of this program can be used to generate new ad- hoc rules or tweak already used ones in order to increase cracking efficiency.


fig6Figure 6. An analysis of the password list leaked from Stratfor: each series represent a class of characters – Kevin Young 

The balance between brute-force, comprehensive wordlists, rule-based dictionary combination, and discovered password analysis, lead crackers to recover, in about 20 hours, the 90-percent of more than 16000-hashed entries of a leaked user database. Equally impressive are some of the recovered plains
like “momof3g8kids” or “Oscar+emmy2.”, the latter one containing both alphanumeric and common punctuations, thus giving a theoretical strength of about 8012. This fact arise an alarming question: will a password ever be strong enough? The answer roots to a fundamental tradeoff between remembering ease and guessing resilience as we usually indulge on the first one. Recent trends show an increasing switch from password to passphrases where an entire sentence is used as login: this indeed increases password strength but crackers are following shortly fueling their dictionaries with phrases contained in the Bible, Wikipedia and other common literature. For this reason, it is important to couple a personal passphrase with a peculiar string-mangling pattern, which enrich the alphabet, and is not covered by any rule. Nevertheless even following this advice the password strength is just approaching its ideal value, but, in order to reach it, we must remove the human brain memorization constraints, for example with the support of a password manager. Then we may choose a long enough and alphabet-rich true-random password, which would be unfeasible to brute-force and impossible to guess using a dictionary; even in this case, however, no one can assure you that the database isn’t storing it in clear text.



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at

Up ↑

%d bloggers like this: