Brute-force search

The brute- force method (of English brute force, brute force ') or method of brute force, even exhaustion (from the Latin exhaurire, exploit '), is a method for solving problems in the fields of computer science, cryptology and game theory, based on trying out all (or at least many ) possible cases based. Also, the term exhaustive search (English exhaustive search) is in use.

Computer science

For many problems in computer science no efficient algorithms are known. The natural and simplest approach to an algorithmic solution to a problem is to simply try out all potential solutions until the right one is found. This method is called " brute -force search " (English brute -force search).

The brute -force search is easy to implement and designed to find the correct solution. However, the amount of arithmetic operations possible solutions, where the number of possible solutions with an increasing extent, the problems frequently increases exponentially proportional to the number of ends to be sampled.

An important application is found in the computer security. An often cited example of using the brute force method here is the breaking or colloquially " crack" passwords.

Often passwords using cryptographic hash functions are encrypted. A direct calculation of the password from the hash value is not practically possible. However, Cracker can calculate the hash values ​​of many passwords. Is there a value consistent with the value of the stored password, he has ( or another random matching ) found password. Brute Force So here means simple trying out possible passwords. Predefined hash lists of frequently used passwords, called Rainbow Table.

From the above relationship between extent of the problem and required arithmetic operations can be used for the example of the " password cracking " lead to the conclusion that with increasing password length or increasing the number of which may be present in the password characters ( alphabet without numbers, with numbers, special characters ) cost of brute- force method increases rapidly. The method is often successful in practice, because most users quick and easy to make use insecure passwords. With appropriate tools can be tried out on commercial middle-class computers million passwords per second.

If the number of passwords auszuprobierenden limited by reducing the opportunities for entries from a " dictionary " ( or compositions of those ), one also speaks of a dictionary attack (english dictionary attack).

Due to the rapidly increasing computing power of today's computers, this may increasingly try more options per unit time. Thus, longer passwords or those from a wider variety of characters used for a sufficient protection against the brute- force method are always required.

Countermeasures include, among others, the use of key- stretching or Salts. When Key Stretching is by repeated iteration of a hash ( PBKDF2 ) or by complicated preparations for the execution of an algorithm ( bcrypt ) increases the computing time for the calculation of the final hash value, or by intensive memory usage to run on fast ASICs or FPGAs, both just over negligible memory feature that prevents ( Scrypt ). The Salt, which is concatenated with the password used to prevent the creation of Rainbow Tables by enlarging the original image area. The key is therefore "stretched" by certain methods, so that a password with key - stretching is still lower complexity computationally equivalent to a complex password without key - stretching.

Another countermeasure is to use extremely long, randomly generated passwords that you do not notice but is stored in a password management. In this way, you reduce the number of susceptible to brute force vulnerability to a single, namely the master password of password management.

Cryptology

In cryptanalysis, which is the branch of cryptology that deals with the deciphering of encrypted ciphertext, the method can be used to cover all possible keys " exhaustively " that is exhaustively try out. One speaks in this complete key search by a " brute force attack " (English brute force attack ) or by the " method of exhaustion ".

The order of the trial key is optionally selected according to their probability. However, this is at ( pseudo-) randomly generated keys unhelpful. The key length plays a crucial role: As the length of the key, the scope of the key space, ie the set of all possible keys increases exponentially. It is to be expected here by the rules of probability, that on average half of all possible keys of the key space must be tried until the key used is found.

Attacks of this kind on modern encryption algorithms by using sufficiently long keys are hopeless in practice because the computational effort required (and thus time and / or cost ) would be too large. Since the power of modern hardware is constantly increasing and thereby greatly reduce the time it takes to try all the keys of a certain length, the minimum key length must be chosen sufficiently large to safely condemn an attack by exhaustion to failure.

Game theory

In game theory, for example in computer chess, the brute-force method is a strategy in which the variant tree grows up to a certain depth completely searched and analyzed. An evaluation function for each of the positions occurring serves for decision making for the best train.

The cost of the brute- force method grows exponentially with the maximum depth used and the job search. This is also the appropriate performance of the hardware of this method has its limits.

The brute- force method can be refined by different approaches, yielding significant improvements can be achieved. An example is the alpha-beta search. This takes into account whether a train in a certain search depth by a particular return may be rebutted in chess. If this is detected, then it is pointless to search for even better refutations. In this way, a lot of processing time can be saved.

Another method is, from a certain depth only " forced " to look at transactions. In chess, this would be about chess bids or shock trains.