01 Jun 2018

Some guys wonder what brute force is and whether it is possible to recover the password if the password database search run has failed and the original password structure is unknown. So, we answer the question.

## So, what is brute force?

Strictly speaking, brute force is a serial search through all possible passwords of the specified length using certain symbols. In most cases, passwords consist of Latin alphanumeric characters: that is a set of characters from 0-9, a-z, A-Z. Sometimes people add to it special characters that can be typed on the keyboard: ~!@"#\$% , and others. Usually, it is a set of 90-100 characters.

During brute force attack, we first sort through all single-character passwords and then compare the received hash with the reference one to determine whether the password was found or not:

`0, 1, ... 9, a, b, ... z, A, B, …`

If no one-character password suits, then we start to search through all two-character passwords:

`00, 01, ... 09, 0 a, ..., 0z, 0A , 0B, …`

And so on till the lost password is found.

## How many variants are searched through with a brute force attack

Mathematics (or rather, combinatorics) shows us how many possible passwords we need to search through with a given set of characters and a given password length:

`C = m ^ n`

where m is the number of possible symbols, and n is the length of the password. Thus, we get the following table of possible password variants:

Password Length Number of variants (for 96 characters set)
1 96
2 96 ^ 2 = 9,216
3 96 ^ 3 = 884,736
4 96 ^ 4 = 84,934,656
5 96 ^ 5 = 8,153,726,976
6 96 ^ 6 = 782,757,789,696
7 96 ^ 7 = 75,144,747,810,816
8 96 ^ 8 = 7,213,895,789,838,336
9 96 ^ 9 = 692,533,995,824,480,256
10 96 ^ 10 = 66,483,263,599,150,104,576

As you see, the number of password variants grows exponentially, and even with the 8-character length, it becomes scary. And you know, that nowadays passwords are recommended to be of 12 or more characters…

If you don’t know the password length (as it is usually), then we have to search through all passwords starting from 1 symbol length. To get the total number of password variants of 96 characters set up to 10 characters of the maximum password length we do the following calculations:

`C = 96 + 96^2 + 96^3 + 96^4 + 96^5 + 96^6 + 96^7 + 96^8 + 96^9 + 96^10 = 67,183,087,426,509,579,360`

It is about 67 quintillion variants, just think about that number! Even in the most powerful computing center will do the search for several years! And if the password length is really no more than 10 characters and the character set is limited to 96 symbols it will brute force the lost password!

#### That is why if you don’t know the password structure Brute force is impossible!

Mind that the password could be multibyte encoded (e.g., UTF -8 using Cyrillic, Arabic alphabet or characters), so the length of an 8-symbol password may actually be up to 32 bytes.

The only way to apply a brute force attack is to know for sure in advance the password structure. For example, if you know for sure that the password has lengths of 8 characters and consists only of lowercase letters of the English alphabet and numbers from 0 to 9 then the total number of possible variants will be:

`C = 36 ^ 8 = 2,821,109,907,456`

Less than 3 trillion variants are ok, it is a completely solvable task for a powerful computer for most types of hashes.

But keep in mind, if you've made a mistake informing about the password structure, all the work will be done in vain: the password will not be found! For example, if the real password also contains symbols outside the given set, or it has a different length — we will not be able to find it within the possible given variants. So, use the brute force only if you know exactly what the password structure is!