As the saying goes—when everything else fails try the brute force, is still the practical option today. Though regarded as an un-reliable option, a brute force attack is often tried by the hackers’ and crackers’ to crack a password or a code. In this article, we will examine the mechanisms behind a brute force attack and also various ways to prevent them.

Many systems will allow the use of weak passwords or cryptographic keys, and users will often choose easy to guess passwords, possibly found in a dictionary. Given this scenario, an attacker would cycle though the dictionary word by word, generating thousands or potentially millions of incorrect guesses searching for the valid password. When a guessed password allows access to the system, the brute force attack has been successful and the attacker is able access the account.

The same trial and error technique is also applicable to guessing encryption keys. When a website uses a weak or small key size, its possible for an attacker to guess a correct key by testing all possible keys.

The Mechanism

Brute Force Attack is the most widely known password cracking method. This attack simply tries to use every possible character combination as a password. To recover a one-character password it is enough to try 26 combinations (‘a’ to ‘z’). It is guaranteed that you will find the password, but when? How long will it take? The two-character password will require 26*26=676 combinations. The number of possible combinations and therefore required time grows rapidly as the length of the password increases and this method quickly becomes useless. Would you wait for two months while your 9-character password is cracked? What about one hundred years for an 11-character password? Besides the maximal length of the character set you should also specify the character set i.e. the list of characters that will be included in the combinations. The longer the character set is, the longer the required period of time is. Here is the problem: usually you have no idea of what characters are present in the password. On the one hand, you should specify all possible characters. On the other hand, this can slow things down very much.

Unfortunately, there are no common ways to determine what character set to use. It is more a question of luck and intuition. The only thing I can recommend is to begin with trying short passwords using the full character set. Then you can increase the length of password simultaneously decreasing the character set to keep the required time good acceptable.

Technical Definition

A brute force attack consists of trying every possible code, combination, or password until you find the right one. Technically speaking, a brute force attack is a method of defeating a cryptographic scheme by systematically trying a large number of possibilities; for example, a large number of the possible keys in a key space in order to decrypt a message. In most schemes, the theoretical possibility of a brute force attack is recognized, but it is set up in such a way that it would be computationally infeasible to carry out. Accordingly, one definition of "breaking" a cryptographic scheme is to find a method faster than a brute force attack.

The selection of an appropriate key length depends on the practical feasibility of performing a brute force attack. By obfuscating the data to be encoded, brute force attacks are made less effective as it is more difficult to determine when one has succeeded in breaking the code.

Symmetric Ciphers and Brute Force

For symmetric-key ciphers, a brute force attack typically means a brute-force search of the key space, i.e., testing all possible keys in order to recover the plaintext used to produce a particular ciphertext. In a brute force attack, the expected number of trials before the correct key is found is equal to half the size of the key space. For example, if there are 264 possible keys, a brute force attack would, on average, be expected to find a key after 263 trials.

For each trial of a candidate key the attacker needs to be able to recognize when he has found the correct key. The most straightforward way is to obtain a few corresponding plaintext and ciphertext pairs, that is, a known-plaintext attack or crib. Alternatively, a ciphertext-only attack is possible by decrypting ciphertext using each candidate key, and testing the result for similarity to plaintext language - for example, English encoded in ASCII. In general, a symmetric key cipher is considered secure if there is no method less expensive (in time, memory requirements, etc) than brute force.

Determining the Difficulty of a Brute Force Attack

The difficulty of a brute force attack depends on several factors, such as:

• How long can the key be?
• How many possible values can each component of the key have?
• How long will it take to attempt each key?
• Is there a mechanism which will lock the attacker out after a number of failed attempts?

Although a brute-force attack may be able to gain access to an account eventually, these types of attacks can take several hours, days, months, and even years to run. The amount of time it takes to complete these attacks is dependent on how complicated the password is.

As an example, imagine a system which only allows 4 digit PIN codes. This means that there are a maximum of 10,000 possible PIN combinations.

Practical Implementation

One of the most practical implementation of brute force attack is the method of obtaining a user's authentication credentials. Authentication is the process of determining if a user is who he/she claims to be. It is commonly performed through the usage of usernames and passwords. Knowledge of the password is assumed to guarantee that the user is authentic. Each user initially registers (or is registered by someone else) using an assigned or self-declared password. On each subsequent use, the user must know and use the previously declared password. Using brute force, attackers attempt combinations of the accepted character set in order to find a specific combination that gains access to the authorized area.

Attackers can use brute force applications, such as password guessing tools and scripts, in order to try all the combinations of well-known usernames and passwords. Such applications may use default password databases or dictionaries that contain commonly used passwords or they may try all combinations of the accepted character set in the password field.

Compromising User Identification

User identification is not always achieved with a username and password pair. Using a brute force tool makes it easy to find a legitimate session ID that appears in a URL (Uniform Resource Locator). A session ID is an identification string used to associate specific Web pages with a specific user. The following is an example of such a session ID.

http://greetings.acme-hackme.com/view/9BA54003218827622

This is an example of a greeting card site that has a unique session ID for each greeting card. Using Brute Force applications, attackers may try thousands of session IDs embedded in a legitimate URL in an attempt to view greeting cards that they are not authorized to view.

It is relatively easy to find a legitimate key for an object id. For example, consider the URL:

http://www.acme-hackme.com/online/Displaymsg.asp?msgID=12345

In this example, the dynamic page requested by the browser is called Displaymsg.asp and the browser sends the Web server the parameter msgID with a value of 12345. An attacker may try brute force values for msgID to try and read other users' messages.

Preventing Brute Force Attacks

The brute force attack is about as uncomplicated and low-tech as web application hacking gets. The attacker simply guesses username and password combinations until he finds one that works. It may seem like a brute force is unlikely to ever succeed. After all, what are the odds of someone randomly guessing a valid username and password combination? Surprisingly, the odds for a brute force attack can be quite good if the website is not properly configured. There are several factors that work to the hacker’s advantage, the most important of which is human laziness.

1. Don’t be lazy—choose a password carefully!
Generally, people do not remember complicated passwords very well. If users are allowed to create their own passwords, they will often create very simple ones like “password”, “1234”, their spouse’s name, or their preferred personal details. Passwords like these are easy for the user to remember, but unfortunately they are also easy for someone else to guess. Furthermore, any serious hacker who attempts a brute force attack will not be sitting at a web browser, guessing at authentication credentials and typing them in. He/she will be using an automated tool for the brute force attack that can make thousands of requests per minute with credentials generated from a large list of possible values. Often this list is an actual dictionary, hence the term ‘dictionary attack.’ If a user chooses a common password, such as a dictionary word, the automated tool will eventually guess it, and the user’s account will be compromised.

Also, once the brute force attack has revealed a valid username and password combination for one website, the hacker knows that the same combination is likely to work for other websites. In a study conducted by the University of Wichita, more than half of the test subjects reported using the exact same password for multiple sites. This laziness works to the hacker’s advantage. If, for example, a hacker is able to use a dictionary attack to obtain a valid user credential for Amazon.com, then it is probable that the same credential would be valid for other popular websites, such as eBay.

2. Sidestepping a dictionary attack with username selection
Of course, a password is only half of the required login credential. A username is also required. While it is less likely that a dictionary word would be used as a username, there are still some common usernames that hackers are certain to try with a brute force attack. First among these are “admin” and “administrator”. These names are especially dangerous since they are not only easily guessed, but the accounts they represent are usually highly privileged administrative accounts. If the hacker’s dictionary attack could gain access to an administrative account, he could probably do much more damage to the system than he could if he gained access to a regular user’s account.

Administrative accounts are not the only problem: many web applications and web application frameworks create default users during installation. If the site administrator does not remove these default users or at least change their passwords, these accounts will be easy targets for a dictionary attack. Finally, when users are allowed to choose their own usernames, they often choose their email address, since it is easy to remember. Once again, the user’s laziness is a benefit to a hacker using a brute force attack. Armed with a list of email addresses (perhaps obtained from a spammer) and a dictionary of passwords (easily obtained anywhere), an attacker has an excellent chance of breaking into at least one user’s account.

3. Countering a brute force attack with a strong password policy
The primary protection against a brute force attack must be enforcement of a strong password policy. As mentioned earlier, dictionary words make poor passwords. Password size is also important: the longer the password, the more difficult it will be to force. While there is no strict definition of a strong password that will be harder to determine via a dictionary attack, some good guidelines would be:

• Minimum length of at least seven characters;
• Must include both upper and lower case characters;
• Must include numeric characters;
• Must include punctuation.

These guidelines may seem overly strict, but there is little chance that a password created with these restrictions will be found with a brute force attack. There are almost 70 trillion combinations of characters that can be seven digits long and can include upper case characters, lower case characters, numbers, and punctuation. Even a dictionary attack tool that could make one hundred requests per second would still take over 11,000 years before it would be statistically likely to guess the password.

Obviously, most websites will want to block a dictionary attack much sooner than 11,000 years into the attack. Many organizations use an intrusion detection system (IDS) to detect an abnormally high number of requests coming from a single user. This is a good idea, but it is not sufficient to prevent the brute force attack. A clever hacker will simply reduce the bandwidth used by his automated tool until it falls under the alert threshold of the IDS.

4. Other defensive strategies—and why they don’t work
Another common defensive strategy against a dictionary attack is to automatically disable an account after a certain number of failed login attempts. For example, if the server detects that the user “john” has provided an incorrect password three times since his last login, the server might decide that the “john” account is the subject of a brute force attack and will disable it. The account may automatically reactivate after 30 minutes, or the user might have to contact the site administrator to have the account reactivated. In either case, automatically disabling user accounts is a poor security mechanism to fight a dictionary attack. In the first place, by disabling accounts the system has traded an authentication evasion vulnerability for a denial of service vulnerability. If an attacker can disable an account by incorrectly guessing its password three times every 30 minutes, he/she can effectively prevent that user from ever accessing the system. Imagine how damaging a dictionary attack could be if it were used against an administrative account.

5. A better strategy: incremental delay
A better strategy for blocking any brute force attack is to incrementally delay the page response after failed login attempts. After the first failed login attempt, for example, the response would be delayed by one second. After the second failed attempt, the response would be delayed by two seconds, and so on. A one-, two-, or even six-second delay is probably not going to bother a human user too seriously. Certainly he/she will find it less irritating than having to wait 30 minutes for his account to reactivate because he/she accidentally left the caps lock key on. On the other hand, an incrementing delay can completely defeat an automated tool being used for a brute force attack. Assuming the tool could normally make ten requests per second, the time it would take to make one thousand requests would jump from two minutes to five days. This pretty much renders the brute force attack tool useless. An incrementing delay also solves the problem of the attacker holding the password constant and varying the username. Since the system tracks failed login attempts on a user session basis and not an authentication credential basis, the delay logic cannot be bypassed this way.

Limitations of Brute Force

While brute force techniques are highly popular and often successful, they can take hours, weeks or years to complete. Hence it is an unreliable option and attempted as a last resort by most hackers and code crackers.

Technically, certain types of encryption, by their mathematical properties, cannot be defeated by brute force. An example of this is one-time pad cryptography, where every cleartext bit has a corresponding key bit. One-time pads rely on the ability to generate a truly random sequence of key bits. A brute force attack would eventually reveal the correct decoding, but also every other possible combination of bits, and would have no way of distinguishing one from the other. A small, 100-byte, one-time-pad–encoded string subjected to a brute force attack would eventually reveal every 100-byte string possible, including the correct answer, but mostly nonsense. Of all the answers given, there is no way of knowing which is the correct one. Nevertheless, the system can be defeated if not implemented correctly, for example if one-time pads are re-used.

—By:R. Manoj. The author is an Assistant Editor at Fanatic Media, Bangalore.