Understanding a Brute Force Attack

A brute force attack is a method used in cryptanalysis to find a password or a key. This tests, one by one, all possible combinations. This comprehensive research method can only succeed where the password searched consists of a few characters. These programs try all possibilities of passwords in random order to fool security software that prevents trying all passwords in order.

To counter this, simply choose passwords of great length or sufficiently large keys. Thus, the attacker will take a long time to find the correct password. This method is very sensitive to processing power of machines doing the algorithm.

This method is often combined with a dictionary attack and rainbow table for best results.

This method is not an attack itself because it merely defines the smallest time needed to find the secret. This method is applicable to any algorithm, giving him the title of attack means that all protocols are attacked and therefore unreliable. It is therefore an abuse of common language.

Mathematical explanation

If the password contains N characters, independence (the presence of a character does not influence another) and evenly distributed (no character is preferred), the maximum number of tests necessary amounts to:

* 26N if the password only contains letters of the alphabet completely lowercase or uppercase;

* 52N if the password only contains letters of the alphabet, with a mixture of uppercase and lowercase;

* 62N if the password mixing uppercase and lowercase and numbers.

In fact just raise the size of the alphabet used to the power N. This is an upper bound on average, two times fewer tests to find the password (if it is random). In reality, few passwords are completely random and the number of tests is well below the limits given above (with the possibility of a dictionary attack).

A personal computer is capable of testing hundreds of thousands or even millions of passwords per second. It depends on the algorithm used for protection. However, if there is a password of only 6 characters themselves from a set of 36 symbols (lowercase or uppercase letters with numbers), it does not take very long to break with such an attack.

In the case of keys used for encryption, the length is often given in bits. In this case, the number of possibilities (if the key is random) to explore is about 2N where N is the length of the key bits. A 128-bit key is already a limit impossible to achieve with current technology and the attacker must consider other solutions in cryptanalysis if they exist. But we must take into account the power of hardware which is ever-changing (due to Moore's Law).

Limitations

To avoid attacks by brute force, the best solution is:

* To extend the password or the key if possible;

* Use the widest range of possible symbols (lowercase, uppercase letters, punctuation, figures) makes it more difficult for the hackers

* To avoid having to face a dictionary attack, ensure that the password is random.

In applications, it may also introduce a delay between the introduction of the password and user evaluation. Any attacker in this case should wait any longer to submit passwords it generates. The system can also introduce a waiting time after several unsuccessful attempts, in order to slow the attack. The system passwords such as in Unix use a modified version of DES encryption. Each password is accompanied by a component called random salt whose aim is to change the internal structure of DES and thus avoid an exhaustive search using specially designed hardware for DES.

With enough time, the attacker can always (in theory) find the password, but when the time exceeds over a decade, he/she cannot expect a large profit, and the password will be changed anyway. It changes every time even if one uses the principle of "disposable masks".