The brute force method, also known as the exhaustion method, is a method of solving problems in the fields of computer science, cryptology and game theory that are based on trial and error. of all possible (or at least many possible) cases. Both exhaustive search and full search are in use.
There are no known efficient algorithms for many problems in computer science. The most natural and simple approach to an algorithmic solution to a problem is to try all the potential solutions until the right one is found. This method is called “brute-force search”.
Brute force search is easy to implement and designed to find the correct solution. However, the amount of computational work required increases in proportion to the number of possible solutions to be tried, with the number of these possible solutions often growing exponentially as the scale of the problems increases.
---
In some cases, there are methods to optimize runtime behavior. If, for example, you want to solve a four-roller combination lock and try out the code words in natural order, you would have to move four reels when changing from code word 0999 to code word 1000. However, if you work with gray codes (0999 is followed by 1999), only one roller has to be moved per attempt.
An important area of application can be found in computer security. An often cited example of the brute force method is the breaking or colloquially “cracking” of passwords. Passwords are often encrypted using cryptographic hash functions. It is practically impossible to calculate the password directly from the hash value. However, a cracker can calculate the hash values of many passwords. If a value matches the value of the stored password, it has found the password (or another random one). Brute force here means simply trying out possible passwords. Predefined hashlists of frequently used passwords are called rainbow tables.
From the above-mentioned relationship between the scope of the problem and the number of arithmetic operations required, it can be concluded for the example of “password cracking” that as the password length increases or the number of characters that may be present in the password (alphabet without numbers, with numbers, with special characters), the effort of the brute force method increases rapidly. The method is often successful in practice, as most users use short and simple, thus insecure passwords. With the appropriate tools, millions of passwords per second can be tried out even on commercially available mid-range computers.
If the number of passwords to be tried is limited by reducing the possibilities to entries from a “dictionary” (or combinations thereof), this is also referred to as a dictionary attack. There are special word lists that contain common terms in passwords (see dictionary attack).
Due to the rapidly increasing computing power of today’s computers, they can try out more and more possibilities per unit of time. As a result, passwords that are longer and longer, or those from a larger number of characters used, are required to provide sufficient protection against the brute force method.
Countermeasures include, but are not limited to, the use of key stretching or salts. In key-stretching, iteration of a hash (PBKDF2) or complicated preparatory measures for the execution of an algorithm (bcrypt) increases the computational time to calculate the final hash value, or intensive memory use prevents execution on fast ASICs or FPGAs, both of which have negligible memory. The salt, which is concatenated with the password, is used to prevent the creation of rainbow tables by enlarging the archetype area. In other words, the key is “stretched” by certain methods, so that a password with less complexity with key-stretching still becomes computationally equivalent to a more complex password without key-stretching.
Another countermeasure is to use extremely long, randomly generated passwords that are no longer remembered, but stored in a password manager. In this way, the number of vulnerabilities susceptible to brute force is reduced to a single one, namely the master password of the password manager.
In practice, brute force attacks are also hampered by the fact that the number of attempts is limited, and after a few unsuccessful password entries, access is blocked or further attempts are only possible after a waiting period. Nevertheless, in September 2014 it became known that Apple, for example, had not implemented such simple measures in its iCloud for a long time and that at least simple brute force attacks were possible.
In cryptanalysis, i.e. the branch of cryptology that deals with the deciphering of encrypted ciphertexts, the method can be used to try out all possible keys “exhaustively”, i.e. exhaustively. This complete key search is referred to as a “brute force attack” or the “exhaustion method”.
The order of the sample keys is selected according to their probability, if necessary. However, this is not very helpful for (pseudo)randomly generated keys. Key length plays a crucial role: As the length of the key increases, the circumference of the key space, i.e. the number of all possible keys, increases exponentially. According to the rules of probability, it is to be expected that on average half of all possible keys in the key room will have to be tried out until the key used is found.
Attacks of this kind on modern encryption algorithms using sufficiently long keys are hopeless in practice, as the required computational effort (and thus time and/or cost) would be too great. Since the performance of modern hardware is increasing more and more and the time required to try out all keys of a certain length is significantly reduced, the minimum key length must be chosen sufficiently large to condemn an attack by exhaustion to failure.
In game theory, such as computer chess, the brute force method is a strategy in which the variant tree is completely searched and analyzed to a certain depth. An evaluation function for each of the positions that occurs is used to make a decision for the best move.
The effort for the brute force method grows exponentially with the maximum depth of position search used. Chess is classified as finite zero-sum games with perfect information. Theoretically, it would be possible to determine whether White or Black wins or whether the game must end in a draw if both sides play perfectly. However, since the number of possible variants is enormous, the respective performance of the hardware of this method still sets its limits.
The brute force method can be refined through different approaches, which can lead to significant improvements. One example is alpha beta search. In chess, it is taken into account whether a move at a certain search depth can be refuted by a certain counterattack. If this is recognized, then it is pointless to look for even better refutations. In this way, a lot of computing time can be saved. Another method is to only look at “forced” settlements from a certain depth. In chess, these would be chess bids or strokes.
