A Brute Force Attack is where software systematically generates rapid-fire input trying to guess the correct value of a password. It is a trial-and-error approach which can be used when decryption would be difficult. It is also known as an "exhaustive key search" because it searches by trying all of the keys.
The total time required for trying all of the keys depends on two main variables: the size of the search key space and the speed of each attempt.
Imagine a combination lock with three-wheels, each of which can be set to numbers 0 to 9. Ten numbers on three wheels provides 1,000 combinations (10^3). A Brute Force Attack might try "000", "001", "002", "003", and continue until it reached "999" or found the correct combination. If each attempt takes one second, then it will take 16.7 minutes to try all keys.
The time required to search the total key space can be described with an equation.
(Possibilities count ^ Key length) x Time per attemptIt is important to note that this is not the same as the actual time required to find the correct key. The key could be the first first guess, or the very last guess, or most likely somewhere in the middle. But calculating the maximum time is useful because it provides a relative measurement of the strength of a key or password.
The possibilities count and key length are the parameters which define the search key space. As these values increase, the time it takes to perform a Brute Force Attack increases, sometimes exponentially.
The time per attempt is a parameter of the mechanism performing the search. For a combination lock, that is how fast can your fingers try each number. For passwords, it is a function of how fast a computer and software can try each password and how fast the software and algorithm responds to an attempt.
As computers get faster—approximately twice as fast every 2-3 years—attempts can be submitted faster and therefore the total Brute Force time decreases. More attempts can be performed per minute if there a many computers working on the solution today such as with distributed computing or a botnet.
Calculations can also be performed faster if a GPU (Graphics Processing Unit) can be used instead of a CPU. GPUs are specialized processors which are designed for calculation speed. They are frequently used in password cracking computers. CPUs can make millions of guesses per second, while GPUs can make billions of guesses per second. Incidentally, one nice feature of bcrypt/Blowfish which does not get much attention is that it uses a lot of RAM, so much RAM that GPU optimizations are useless. The GPU is forced to take time (and take turns) accessing the system RAM so that it becomes no faster than a CPU.
Another important factor is how fast the login system responds to each attempt. In an ideal scenario, password cracking software has the encrypted hash to compare with each of its attempts. This allows it to try millions of guesses per second. A hash like bcrypt has a "cost" parameter which causes the algorithm itself to slow down calculation speeds from millions of guesses to less than 200.
However, if the encrypted hash is not known, then a Brute Force attack must make each attempt through the login software which is much slower. A typical web application which has to query the database will take 0.5-1.5 seconds to respond.
The first defense against a Brute Force attack is to choose a strong encryption algorithm. MD5 and SHA-1 are not recommended because they have collisions and are vulnerable to Rainbow Tables. bcrypt is recommended. It is a solid, well-tested algorithm with few collisions. It is slow and can be made slower by increasing its "cost" parameter, and a GPU will not increase the speed of guesses.
The next defense is to get users to pick strong passwords. Most importantly, you should require that users choose longer passwords. Remember, longer passwords exponentially increase the key space which must be searched. And by all means, never limit password length. Let the user enter a 30 character password if they want. The hash algorithm does not care, it can hash files containing several megabytes of data and still return a hash of the same length. Require that all users pick passwords which include letters, numbers, and symbols. These characters increase the key space which must be searched, and also make Dictionary Attacks less effective. Display a password strength meter which changes as a password gets longer or includes more of the required characters. Educate users in an organization about the importance of choosing strong passwords and not re-using them for other sites.
It is a good idea to encourage (or even require) that a password contains no dictionary words. Maintain a list of common passwords, like "letmein", and reject passwords if they are on the list.
Use login throttling to slow down the rate of failed attempts.
