Brute force method
The brute force method (from English brute force 'raw violence') or method of brute force , also exhaustion method ( exhaustion from Latin exhaurire for short ), is a solution method for problems in the fields of computer science , cryptology and game theory , which is based on trying out all possible (or at least many possible) cases. The concept exhaustive search (Engl. Exhaustive search ) is in use.
Computer science
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 potential solutions until the right one is found. This method is called "brute-force search" ( English brute-force search ).
Brute force search is easy to implement and designed to find the correct solution. However, the complexity of arithmetic operations increases proportionally to the number of possible solutions to be tried, the number of these possible solutions often growing exponentially rapidly as the scope of the problems increases .
An important area of application can be found in computer security . A frequently cited application example for the brute force method is the breaking or colloquially “cracking” of passwords .
Passwords are often encrypted with the help of cryptographic hash functions . A direct calculation of the password from the hash value is practically impossible. 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 (or another, randomly matching) password. 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, the conclusion can be drawn for the example of "password cracking" that the longer the password length 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 passwords that are therefore unsafe. With the appropriate tools, millions of passwords per second can be tried out on standard mid-range computers.
If the number of auszuprobierenden passwords by reducing the opportunities to entries from a "Dictionary" restricted (or compositions of those), it is also called a dictionary attack (English dictionary attack ). There are special word lists that contain common terms in passwords.
Due to the rapidly increasing computing power of today's computers, they can increasingly try out more options per unit of time. This means that ever longer passwords or those made up of a large number of characters are required for adequate protection against the brute force method.
Countermeasures include the use of key stretching or salts . With key stretching, iteration of a hash ( PBKDF2 ) or complicated preparatory measures for the execution of an algorithm ( bcrypt ) increase the computing time for calculating the final hash value, or intensive memory use increases the execution on fast ASICs or FPGAs , both of which only have negligible memory prevent (scrypt). The salt that is concatenated with the password is used to prevent the creation of rainbow tables by enlarging the original image area. The key is "stretched" using certain methods so that a password with less complexity with key stretching is still computationally equivalent to a more complex password without key stretching.
Another countermeasure is the use of extremely long, randomly generated passwords that are no longer memorized but are stored in a password manager . This reduces the number of vulnerabilities prone to brute force to a single one, namely the main password for password management.
In practice, brute force attacks are made more difficult by the fact that the number of attempts is limited and access is blocked after a few unsuccessful password entries or further attempts are only possible after a waiting period. Nevertheless, in September 2014 it became known that z. B. Apple had not implemented such simple measures in its iCloud for a long time and at least simple brute force attacks were possible.
Cryptology
In cryptanalysis , the branch of cryptology that deals with the deciphering of encrypted ciphertexts , the method can be used to "exhaustively" test all possible keys . One speaks in this complete key search of a "brute force attack" (English. Brute force attack ) or from the "exhaustion".
The order of the trial keys is selected , if necessary, according to their probability . However, this is of little help with (pseudo) randomly generated keys. The key length plays a decisive role: as the key length increases, the size of the key space , i.e. the set of all possible keys, increases exponentially. According to the rules of probability, it is to be expected here that on average half of all possible keys in the key space must be tried before the key used is found.
Attacks of this type on modern encryption algorithms when using sufficiently long keys are futile in practice, since the required computing effort (and thus time and / or cost) would be too great. As the performance of modern hardware increases more and more and the time required to try out all keys of a certain length is reduced considerably, the minimum key length must be chosen to be sufficiently large to ensure that an exhaustion attack will fail.
Game theory
In game theory , for example in 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 arise is used to make decisions about the best move.
The effort for the brute force method grows exponentially with the maximum depth of the position search used. Chess is assigned to the finite zero-sum games with perfect information. Theoretically, one could determine whether white or black wins or the game has to end in a draw if both sides play perfectly. However, since the number of possible variants is extremely high, the respective performance of the hardware of this method is currently still limited.
The brute force method can be refined by different approaches, whereby considerable improvements can be achieved. One example is alpha-beta search . This takes into account whether a move in a certain search depth can be refuted by a certain counter move when playing chess. 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 consider “forced” developments from a certain depth. In chess , these would be chess rules or moves.
Web links
- Relationship between brute force attacks and password lengths. ( Memento of May 21, 2013 in the Internet Archive ).
- Dennis Yurichev: How to create FPGA-based Oracle RDBMS cracker that works in average 30–40 times faster than password crackers on Intel Core Duo 2.
Individual evidence
- ^ The scrypt key derivation function and encryption utility. At: tarsnap.com.
- ↑ Kevin D. Mitnick, William Simon: The Art of Deception . mitp / bhv, July 10, 2012, ISBN 978-3-8266-8689-4 , p. 343.
- ↑ Apple warned of iCloud brute-force vulnerability 6 months before Celebgate. At: dailydot.com.
- ↑ Apple has known about the iCloud vulnerability for months. At: golem.de.