May the [Brute] Force Be with You!

October 28th, 2020 by Vladimir Katalov
Category: «General», «GPU acceleration», «Tips & Tricks»

Remember the good old times when there was a lot of applications with “snake oil” encryption? You know, the kind of “peace of mind” protection that allowed recovering or removing the original plaintext password instantly? It is still the case for a few “we-don’t-care” apps such as QuickBooks 2021, but all of the better tools can no longer be cracked that easily. Let’s review some password recovery strategies used in our software today.

Have you read Everything You Wanted to Ask About Cracking Passwords? It covers the basics on password cracking. Today we’ll dive deeper, discussing the common password recovery methods.

The brute force

Brute force attack is the oldest approach allowing to break any password in the world. The only question is the time you’ll need to complete the task.

The idea of the brute force attack is simple: we try all possible character combinations as potential passwords. The total range of passwords to be checked depends on the password length and the set of characters used. If you are good with math, you can calculate it using a simple formula: the number of possible characters in a power of password length. For example, if a password is 5 characters long and may only contain small and capital letters (English alphabet), then the total number of possible combinations is:

(26 + 26) ^ 5 = 380,204,032

The numbers increase exponentially with the length of the password. For example, for 7-character passwords of the same type, the total is:

(26 + 26) ^ 7 = 1,028,071,702,528

And once you add the numbers and special characters (all printable), the numbers become insane:

(26 + 26 + 10 + 33) ^ 7 = 69,833,729,609,375

And the worst thing is that, in most cases, password lengths and character sets are not known, so you should probably try them all or use a different approach.

But what do these numbers mean? The indicate the time you will need to break the password. Just divide the total number of passwords by the speed of attacking the given file type, and you will get the maximum recovery time. For example, if your current system can try 10 million password combinations per second, you will have to wait just half a minute to break the password from the first example (5 letters, both character cases). If the speed is 100 p/s and the password has at least 7 characters from the entire “printable” range, the time jumps to about 700 billion seconds, or ~22 thousand years.

This attack was the first and only one implemented in our first password cracker (Advanced ZIP Password Recovery) released in 1997.

Should you wear a mask?

Masks allow to dramatically reduce the number of passwords to be tried, but only if you know a part of the password. For example, let us say you have reasons to believe that a certain password starts with ‘OhMyGod’, followed by three numbers. With the brute-force approach, you will have to check a huge number of combinations:

(26 + 26 + 10) ^ 10 = 839,299,365,868,340,224

Instead, you can fix the first part and try combinations from ‘OhMyGod000’ to ‘OhMyGod999’ only, limiting the range to one thousand passwords.

Dictionary attacks

The dictionary attack is the most effective one because of the human nature. Most people select passwords they can easily memorize, like their pet names, dates of birth, football teams or whatever. William Shakespeare used a vocabulary of about 30 thousand words, while Alexander Pushkin’s vocabulary contained about 24 thousand words. Whatever the cracking speed is, it will not take too much time to check all English or Russian words.

There is a difference between a ‘dictionary’ and a ‘wordlist’. Even simple passwords are not always “words” from the dictionary, but may be also common combinations (like “qwerty”) and abbreviations (like “ROFL&SMC”). Several wordlists are usually included with password-cracking software, and of course you can use your own; you can find many collections in the Internet.

Mutations

The word ‘password’ is an extremely bad (though still popular) password. The word ‘Password’ is one bit better, but what can you say about ‘pa$$w0rd’ or ‘Password2020’?

Many people use these and similar combinations, modifying a common word in a certain way by replacing some characters, appending a number (often year) at the end, inserting delimiters, playing with characters case etc. It is often much more effective to use a small wordlist, applying various mutations to all the passwords listed in it, rather than going through a huge list collected from various sources (including password leaks). In our flagship tool Distributed Password Recovery, we have collected the most commonly used mutations, and allow you to apply them easily.

Hybrid attacks

‘maga2020!’ is a trending password, but how exactly was it discovered? In this particular case, if was probably simply guessed (just a guess!), but similar passwords can be discovered with the advanced type of attacks called hybrid attacks.

Apart from the mutations listed above, some people use more sophisticated modifications of common words. We did a solid job for you to allow making virtually any modifications with either a kind of script language (the special rules file), or with a visual editor. Here are just some of the rules that can be applied:

  • { Rotate word left: password -> asswordp
  • c Capitalize: password -> Password
  • d Duplicate the word: password -> passwordpassword
  • q Duplicate all symbols: password -> ppaasssswwoorrdd
  • r Reverse: password -> drowssap
  • V Vowels elite: password -> PaSSWoRD
  • yN  Duplicate first N characters
  • $X Add character X to the end of the word
  • ^X Insert character X at the beginning of the word
  • @X Remove all characters X from the word
  • !X Reject the word if it contains at least one character X
  • /X Reject the word if it does not contain character X

This attack is especially useful if you have an idea of what the password could be, or already recovered several passwords from the user’s other files or documents. See Ruling Out the Encryption for more information.

The workflow

The types of of attacks you are likely to use will be… “it depends”. There is no silver bullet in breaking passwords. Generally speaking, you’ll start from collecting the low hanging fruit by extracting saved passwords from various Web browsers and mail clients, local and iCloud Keychain. Once you have the list of these passwords, you’ll have a deep look at them. It’s very likely you’ll find a common pattern or several patterns that you can use to build your attacks.

Which files do you attack first? The order matters a lot. If you attack files with the weakest protection first, you are likely to break them faster. Once you have passwords from these weakly protected files, you can use them to attack files with stronger protection.

If you don’t have the handicap of the user’s existing passwords, you’ll have to resort to dictionaries with common mutations, leaked passwords and time-limited brute force.

Conclusion

If the encryption is strong and there is no backdoor or exploit, there are very few ways to go. You can make attacks faster (13 Years of GPU Acceleration) or reduce the number of passwords to try by inventing more efficient attacks.

Happy password cracking! 🙂


REFERENCES:

Elcomsoft Distributed Password Recovery

Build high-performance clusters for breaking passwords faster. Elcomsoft Distributed Password Recovery offers zero-overhead scalability and supports GPU acceleration for faster recovery. Serving forensic experts and government agencies, data recovery services and corporations, Elcomsoft Distributed Password Recovery is here to break the most complex passwords and strong encryption keys within realistic timeframes.

Elcomsoft Distributed Password Recovery official web page & downloads »