home |  contact

Brute Force

Brute force is a blanket term for using raw power to acquire secret information. It gets its barbaric name from its inelegant approach of simply guessing every possible secret until it guesses the secret it deems a match. It is often employed to guess passwords, defeat one-way hash functions, or even guess the key used to decrypt encrypted data. The effectiveness of brute force depends on three variables: how large the problem space or key space is; how quickly the brute force mechanism can attempt a guess; and the mechanism's ability to verify a correct guess. The primitiveness of brute force attacks is its strength and its weakness. As a weakness, this method must be able to rapidly execute an attempted login, calculate a one-way hash function, or decrypt data using the target encryption algorithm. As a strength, brute force is almost always successful given enough time. Our goal is to make the amount of time for a successful attack uneconomical for the attacker.

Case Study: dictionary cracking

Dictionary cracking is perhaps the eldest child of the brute force family of attacks. It is used to defeat the one-way hash mechanisms employed by the majority of network operating systems to store secret user password data. Most UNIX operating systems store password data in a passwd file or shadow file. This file includes information such as user name, preferred shell, home directory, and hashed password. The hashed password is created by taking the password given by the user and processing the password with the crypt function. This function is a variant of the Data Encryption Standard (DES) used to encrypt a string of zeroes with a key derived from the password. The result of the encryption process is the hashed password. Notice, that the function is not attempting to hide or obfuscate the string of zeroes. If a string of zeroes is used every time, than anyone knows that the original clear text was a string of zeroes so there is no need to decrypt the cipher text. To use the hashed password, the system will prompt the user for the password. The password given will then be used to encrypt an identical string of zeroes in the crypt function. If the resulting cipher text is identical to the stored hash, then there is a high level of confidence that the correct password was given.

Normal brute force cracking begins its attack by acquiring this passwd file. This may be a difficult endeavor unto itself, but it is assumed that it is easier than stealing the passwords directly. Next, the attacker sends all possible passwords through the crypt function. If any of these hashed passwords match a password found in the passwd file, the attacker now has the password of the associated user.

Exhausting the entire key space of the password problem can often be very time consuming. The key space of the problem is all possible passwords. A typical key space used by most user passwords is all upper and lower case letters, the numbers 0-9, and for this example, all the symbols available above the numbers 0-9 on a keyboard. Given an 8-character password, we can calculate the possible calculations by taking the character possibilities to the power of the number of characters in the password: (26+26+10+10)8=728=722204136308736 » 722 trillion. Hashing 722 trillion possible passwords may be unfeasible for the attacker. Fortunately for the attacker, the human mind, coincidently the storage medium for the user's password, does not work well in a 722 trillion possibilities key space. Dictionary attacks exploit the fact that most users will pick their particular password from the 722 trillion possibilities by using an English word. If this is done, the key space is drastically reduced to words found in a dictionary rather than the arbitrary combinations of 8 typed characters. If the attacker sends a dictionary through the crypt function, there will be a high likelihood of getting a "hit" on the passwd file.

The previous discussion of brute force password cracking illustrates two aspects of cryptographic hashing. The first is the utility of storing a cryptographic hash to serve as proof of knowledge of a secret without having to store the secret directly. Only someone inputting the secret password can perform the hash in the same way that the original hashing did in order to match the stored hash value. Also, knowledge of the hash value does not imply knowledge of the original secret. The second aspect is that most symmetric algorithms can be performed in a cryptographic hash "mode" by using the secret as the key and always encrypting a fixed value. The resulting cipher text is the hashed value. One limiting factor of using a certain symmetric ciphers in a hashing style is the length of the key is a limiting factor on the size of the input.

Tool: crack

This tool has probably been around as long as the technique of password hashing. In fact, crack is simply an automated way of executing the actual crypt function call over and over until matches are found. Crack is run against a normal UNIX passwd file to find all of the clear text passwords from the hashed passwords. Crock can also use a dictionary file to assist its efforts.

Tool: L0phtcrack

L0phtcrack is a Windows NT equivalent to the venerable crock tool for UNIX. The L0pht developed it, which is now the research wing of @Stake. L0phtcrack is run against a copy of the Windows NT SAM, the passwd file equivalent in Windows NT. This tool has many bells and whistles including dictionary cracking, brute force cracking, one click copying of the Windows NT SAM, cracking passwords found in a Windows NT login sniffer capture, and others.

Home

Services

Partners

About Us

Contact Us