How Hackers Are Cracking Your Passwords

The previous article in this series has described why passwords which were fully compliant with the NIST recommendations from 2003 turned out to be insecure.

This article, which is the third part of the series, will describe how computers are working and what methods are used to actually crack passwords.

How computers will sort things out better than you can scramble

From the previous article it is already known that the recommendations published in Appendix A of NIST Special Publication 800-63 contained two fatal conceptual flaws.
First, they assumed that an attacker would simply brute-force his way through the password.
Second and most crucially, they did not consider that the attacker could use a method smarter than brute-force.

While there is specialized hardware that allows for extremely fast brute-force execution, that attack is very seldom used because it's stupid, and rarely effective. It is a known fact that, while additional CPU power (provided by Moore's law) can speed up computation, a much larger performance increase - sometimes of several orders of magnitude - can always be achieved with a better algorithm. Therefore, many methods are used by hackers to crack passwords, in increasing order of complexity and effectiveness.

A dictionary attack, as seen before, is already a smarter way: every word in the dictionary is a potential password, and password-cracking oriented dictionaries already include common substitutions (for example "antid0te" for "antidote") and numeric entries. It has a very low computation cost as it only requires a table look-up, and can therefore be performed at extremely high speed.

A toggle-case attack creates every possible case combination for each word in a dictionary. For example the password candidate "antidote" would also generate "Antidote", "aNtidote", "anTidote" and so on. This has a very low computation cost and completely neutralizes Burr's requirement of having both uppercase and lowercase letters in a password.

A hybrid attack is a blend of a dictionary and a brute-force attack that makes a dictionary attack stronger by placing a string of brute-force characters to the beginning or the end of the dictionary entries. For example the algorithm will quickly find "password1", as well as "password001" and "password 002" and all the progressive combinations (including "001password" and all its variants).

A combinator attack appends dictionary entries to other dictionary entries. It is an effective method because users often choose passwords that combine a few common, easy-to-remember keywords, for instance "12345qwert" (where 12345 and qwert result from the top two rows of a standard QWERTY keyboard). In this case, the combinator would try "12345qwert" and "qwert12345" as possible passwords. About the effectiveness of this attack, suffice to remember that "123qwe" ranked #25 in the Most Common Passwords List in 2019, and "abc123" ranked #11.

In a table-lookup attack each word in a dictionary generates masks for a mask attack while creating new words by consulting a table. It is effective for guessing passwords when the user replaced one or more characters with numbers or symbols (for example "antid0t&" instead of "antidote") and it is augmented with dictionaries that already include the most common substitutions. This attack neutralizes Burr's requirement to have numbers and special characters in a password when they are used to replace letters.

The most effective and sophisticated password attack method normally implemented is, at the time of writing, the rule-based attack. It’s one of the more complex types of attacks, but the possibilities are effectively endless. The rule-based attack is like a programming language designed for password candidate generation, and it uses optimizations to eliminate possibilities. It has functions to modify, cut or extend words and has conditional operators to skip some. That makes it - according to the HashCat documentation - the most flexible, accurate and efficient attack.

Going beyond rules: the PRINCE attack

A very promising method for password cracking has recently emerged: the PRINCE attack (“PRobability INfinite Chained Elements”). Presented by author Jens Steube at the 7th International Conference on Passwords (Passwords14, held in Trondheim in 2014), the PRINCE attack uses an algorithm to try the most likely password candidates with a refined combinator attack. However, rather than taking as input two different dictionaries and then outputting all the possible two word combinations, PRINCE only has one input dictionary and builds "chains" of combined words; these chains can have 1 to N words from the input dictionary concatenated together.

The real power of PRINCE is that it can run essentially autonomous for a near infinite amount of time, limited only by the provided dictionary, generating in the process password candidates, patterns and rule sets that password cracking frameworks like HashCat can use to attack a keyword. In other words, PRINCE is a tool that generates high quality input, patterns and rules to feed and optimize the (already very efficient) process of keyword cracking performed by the HashCat framework. This results in a very powerful attack that can defeat more passwords in less time:

When left on it's own, supplied with a simple dictionary, PRINCE could easily crack 75% of the LinkedIn dataset in 24 hours.

(source: NetMux)

Matt Weir of ReusableSec has written a very detailed analysis of princeprocessor, the standalone password candidate generator implementation (available on GitHub).

How long can a password resist?

By using a combination of two or more of the methods listed above, an attacker can quickly crack most passwords obtained in a data breach in a matter of hours, and the vast majority of them within days: that is fast enough to use them and compromise the accounts they belong to.

At this point it should be obvious that a strategy based on at least one upper case letter, one lower case letter, one number, and one special character is not, on its own, providing any real security and will not last very long against an determined opponent. How long exactly, can be seen in the table below:

(source: Hive Systems and Mike Halsey)

Note how the table above is referred to the time it takes a hacker to crack a password by brute-force alone: any real world scenario will make use of the other advanced attacks, which bring down the time required to a matter of few hours for the vast majority of password.
Now that Burr's rules have been demonstrated to be flawed, it is necessary to reconsider what actually constitutes a strong password, and what best practices can be implemented to create them.

(to be continued in part 4)