Brute Force algorithm is a typical problem-solving technique where the possible solution for a problem is uncovered by checking each answer one by one, by determining whether the result satisfies the statement of a problem or not. It is used when the problem size is limited since its various tries are equally proportional to a solution’s candidates.
What is a Brute Force Algorithm?
In Computer Science, Brute Force is a trial and error methodology, which is used by attackers to break into any website’s data or systems. They try to steal information by generating every possible combination of the password-protected information. Brute Force relies on the computational power of the machine to try every possible combination to achieve the target.
It is also known as Exhaustive Search or Generate and Test that yields all possible solution of the problem. It is a simple problem solving technique that is easy to implement and will always come up with a solution if exists. The computational cost of Brute Force algorithm is directly proportional to the number of candidate solutions, i.e. it grows as quickly as the problem size increases. Therefore, it is ideal to use when the problem size is limited and small and does not have complex and large problem sets.
What is the use of a Brute Force Algorithm
Brute Force algorithm is used when there is no other algorithm available to speed up the process and the one has to check each possible solution for the problem to solve it. For example, let us take a scenario in which you need to search a particular word “test” in the dictionary using Brute Force algorithm. You need to iterate through each word to reach to your targeted word. The time complexity would be equal to O (n) since it takes the steps, which are equal to the words in the dictionary. You can use Binary Search method to reach to your work quickly i.e. split the dictionary into two equal lists and get the middle point. If the word comes before the middle point, you will take the first portion and discard the other half. This will repeat until you find out your word. In such case, the complicity would be O (log (n)).
You may use such techniques to speed up the performance, but what if you have unsorted input dictionary, and then you would need to go through each word to find out your target word.
Performance of Brute Force Algorithms
You can improve the Brute Force algorithms by reducing the search criteria as it directly proportional to the given input. It can also be improved by using different heuristic approach for each problem, which results in the optimal solution of a problem. Brute Force relies on trial and error approach which is a fundamental methodology in problem solving. In this methodology, the program continues to make attempts until it gets success in the problem.
For example, you have a challenge of finding all the integers between 1 and 100,000,000 that are divisible by 511. If you take a simple approach, Brute Force algorithm would generate all the integers that are in the range. You can reduce the search criteria and make it more efficient by starting with 511 and repeatedly adding the same number until the number exceeds the given limit. Thus, you can save the possible trials by performing analysis in some cases.
Brute force approach
A brute force approach seeks to find all possible solutions in order to solve a problem. The brute force algorithm explores all possible solutions until a satisfactory solution is found.
This algorithm can be one of two types:
- Optimizing: This is where the best solution is found.It may find the best possible solution by looking at all options. If the value of the best solution has been established, it will stop searching until the best solution has been found. Example: The best way to solve the problem of a travelling salesman. This best path should allow you to travel in all cities at a minimal cost.
- Satisfying: Once the satisfactory solution has been found, it stops searching for the solution.For example, finding the travelling salesman path which is within 10% of optimal.
Many times, Brute force algorithms take exponential time. There are many optimization and heuristic options:
- Heuristic: A method that allows you to determine which options should be looked at first.
- Optimization: Some possibilities can be eliminated without exploring all.
Advantages of brute-force algorithms
These are some of the benefits of brute-force:
- This algorithm will find all possible solutions and guarantee that it will solve the problem correctly.
- This algorithm can be applied to many domains.
- It is used primarily to solve small and simpler problems.
- It is a benchmark that can be used to compare solutions to simple problems and doesn’t require domain knowledge.
Disadvantages of brute-force algorithms
These are the drawbacks of the brute force algorithm:
- This algorithm is inefficient as it must solve every state.
- This algorithm is slow to find the right solution because it solves every state without considering whether or not the solution is possible.
- The brute force algorithm does not produce any creative or constructive results when compared to other algorithms.
How to make a Brute Force Algorithm?
Brute Force can be applied to a wide variety of problems. It is used for trial and error problems, searching a number, performing some sort of sorting on the given input unsorted lists, find the integers between some ranges given any condition, find out the largest number and so on. It is extremely useful in solving small-size problems.
Sorting
Let us take an example of sorting. You have a list of n items and you need to arrange them in ascending order. This straightforward problem can be solved by using either selection sort algorithm or bubble sort.
In selection sort algorithm, the program will scan the entire list to find its smallest element and put that smallest element in its final position. Then second step starts with scanning the second element to find the smallest among the n-1 elements. The sorted list will look like this
X0 < X1 < X2 < X3 < X4 < …………….. < Xi -1 Xi, ………………. , Xn-1
Algorithm
Problem: To sort a given array X by using selection sort algorithm
Selection Sort (X [0, 1, 2 …… n – 1])
Input: An ordered list of array X [0, 1, 2 …… n – 1] in descending order
Output: An ordered list of array X [0, 1, 2…… n – 1] in ascending order
For a <- 0 to n – 2 do
Min <- a
For b <- a + 1 to n – 1 do
If X [b] < X [min] min <- b
Swap X [a] and X [min]
Example
You have a list X having elements 84, 43, 66, 94, 28, 31, 11. The following iterations are made on the list
84 43 66 94 28 31 11
11 43 66 94 28 31 84
11 28 66 94 43 31 84
11 28 31 94 43 66 84
11 28 31 43 94 66 84
11 28 31 43 66 94 84
11 28 31 43 66 84 94
Famous Security Attacks using a Brute Force Algorithm
The Brute Force algorithms are popular among the attackers to steal confidential information. When an attacker uses a set of possible candidate to attack on some targeted information or leaked data, this phenomenon is called as a brute force attack. Attacker continues the trials until there is any success. If the input size is bigger, the longer it will take, but there is a good probability of achieving the target.
The most common attack is stealing the password information of users. In the dictionary attack, an attacker uses a password dictionary that has billions of words that can be used as a password by normal users. The process executes one by one password from the dictionary attack to authenticate the credentials of users. If the user set the password, which is a part of a dictionary attack, then there is a high risk of obtaining the password.
In the past era, attackers used to try a combination of letters and alphabets to generate a closest password of a user. This is still used by some attackers and is useful when the password is not long enough and does not have a combination of special characters. Therefore, it is always recommended to use a strong password having long length and must have special characters in it. This makes hard enough to crack a password easily for attackers. Attacker also tries to find hidden pages in the website by trying multiple hidden requests to the server, if the server has the response it will show 200 response else server will show the 404 page not found message. This is another way to find hidden pages.
Brute Force Attack is mainly used for cracking passwords or stealing confidential information of the users. You can use them in any software or website which does not take appropriate actions on multiple failed login attempts on user account. Some tools available that are used with any protocol to crack the passwords:
Aircrack-ng
Aircrack-ng is the most popular tool available in the market to crack Wi-Fi password. A freeware brute force attack software uses dictionary attack. The success is heavily relies on the dictionary of passwords so the more strong the dictionary is, the more chances are to crack the password. It is supported on Windows, Linux, Android and iOS platforms.
John the Ripper
John the ripper is another a favorite choice of attackers for cracking the passwords. Initially, it was developed for Linux platform, but later it was made available for other fifteen platforms like Unix, Windows, DOS and etc. It detects the hashing done on the password and thus making it easy to crack against any password.
Rainbow Crack
Rainbow Crack is also the popular brute-force attacking tool used by the attackers to crack passwords by generating rainbow tables during the process. It uses less time than other conventional brute forcing tools by using the precomputed rainbow tables. Rainbow tables are available online and can easily be downloaded and used in the program to speed up the brute force attack. The major platforms i.e. Windows and Linux support this brute force tool.
L0phtCrack
The L0phtCrack is famous for breaking windows passwords. It uses multiple combinations of typical dictionary attacks, brute force attacks, rainbow tables and hybrid attacks. This tool is used to steal the passwords of windows systems.
Ophcrack
Ophcrack is also used to crack the passwords of windows systems by using LM hashes through rainbow tables. It is available free for the attackers and it usually cracks the password within few minutes having less than 14 length.
Hashcat
Hashcat is one of the fastest CPU-based brute-force attacking tool supported by Windows, Linux and MAC OS. This algorithm supports various hashing algorithms including LM Hashes, MD4, MD5, SHA-family etc. It can be used in the various attacks such as hybrid attacks, dictionary attacks, brute force attacks etc.
DaveGrohl
DaveGrohl is also popular brute-force attacking tool for Mac OS. It supports almost all the versions of Mac OS X, which are available until now. It supports both incremental attacks and dictionary attacks. It has a distributed mode that enables developers to perform attacks from multiple distributed computers to attack on the single password hash. This tool is also open-soruce and can easily be downloaded to be used.
Ncrack
Ncrack is a famous network password-cracking tool in networking systems. It supports various protocols including RDP, SSH, HTTP(S), SMB, POP3(S), VNC, FTP and Telnet. It also supports different attacks including brute-forcing attacks. It is supported on various platforms including Linux, BSD, Windows and Mac OS X.
THC Hydra
The THC Hydra is also famous for cracking passwords of network system by performing brute force attacks. It performs dictionary attacks against more than 30 protocols including Telnet, FTP, HTTP, HTTPS, SMB and more. It is available for various platforms including Linux, Windows/Cygwin, Solaris 11, FreeBSD 8.1, OpenBSD, OSX and QNX/Blackberry.
Final Thoughts
The brute force algorithm is most common approach used by the attackers in stealing the user’s sensitive information with a predefined set of values to achieve the target. The success depends on how effective and strong the values are. The processing time is directly proportional to the given input size, but it can be optimized by analyzing the criteria and using some of the heuristic approaches. Traditionally, the attackers used to combine the letters and alphabets to crack a password but in the modern era, brute force attacking tools are made available for them to crack a password by selecting the relevant tool. These tools are powerful enough to crack a weak password very easily by using various brute force attacks such as dictionary attacks, predefined rainbow tables, LM Hashes, popular hash algorithms etc. Therefore, it is recommended to not to use common passwords which are easily available in common dictionary and one must use long and complex password having a combination of numbers, alphabets and special characters to prevent such brute force attacks. Reverse brute force attack is basically the reverse of this approach in which the attacker uses one password and find the matching usernames. In this way, user information may get leaked easily. This brute force attacking can easily be implemented with any protocol. It is also recommended to lock the account after invalid login attempts to save the information of a user.
