How to Test for Brute-force Vulnerabilities

Summary

Key brute force attacks focus at defeating a cryptographic algorithm by attempting to predict a valid key from a large number of possibilities. During this attack, an attacker produces a large number of keys by performing an exhaustive search over the key space (all possible keys) and uses each of the predicted keys in an attempt of decrypting a cipher text.  Attackers will often take this attack route when they discover weak cryptographic systems, such as systems using a small key length, wherein predicting a valid key is feasible. Actually, in cryptographic terms, the choice of a secure key length depends on the possibility of executing a key brute force attack in a reasonable amount of time.

Follow these steps to test for key brute force bugs:

• Step 1: Understand attack scenarios
• Step 2: Analyze causes and countermeasures
• Step 3: Execute test cases

Step 1: Understand Attack Scenarios

The first step in testing for key brute force attacks is to understand the details of the different attack scenarios involved:

• Breaking encryption
• Breaking authentication

Scenario 1: Breaking encryption

For simplicity, this article will refer to any data before encryption as plaintext and to the encrypted data as ciphertext.

During this scenario, the attacker’s goal is to recover a cryptographic key in order to decrypt an encrypted message. First the attacker must possess a ciphertext that was produced using the target key.  The attacker might also possess the plaintext that was used to create this ciphertext (known-plaintext attack). Then the attacker starts trying all possible key values. For each produced key, the attacker attempts to decrypt the ciphertext and produce a readable plaintext (or the known plaintext in known-plaintext attacks). The attack succeeds when the attacker is able to recover the encryption key.

In detail:

1. The attacker discovers a cipher text and the encryption algorithm used to produce it.
2. The attacker produces a key value by iterating over all possible key values in the key space.
3. The attacker attempts to decrypt the ciphertext using the key value predicted in the previous step.
4. The attacker repeats steps 2 and 3 until a readable plaintext is produced (in known plaintext attacks the attacker checks the decrypted value against the known plaintext).

It is important to note that this scenario flows different depending on whether the plain text is known or not. If the plain text is known, the attacker knows what plain text to verify on step 4. In that case the attacker’s goal is to recover a valid key to use for decrypting other unknown plaintexts. If the attacker doesn’t possess the plaintext then step 4 must be done looking for any form of readable plaintext (ciphertext-only attack).

Scenario 2: Breaking authentication

Applications can also use keys for authentication purposes such as when signing messages or allowing clients to log into the application. During this scenario, the attacker executes the key brute force attack to find a valid authentication key.  

In detail:

1. The attacker discovers an application functionality that performs authentication based on a key value.
2. The attacker produces a key value by iterating over all possible key values in the key space.
3. The attacker attempts to authenticate using the key value predicted in the previous step.

For more information on credential brute force attacks refer to Team Mentor’s article How to Test for Credential Brute Force Bugs.

Step 2: Analyze Causes and Countermeasures

During this step you must analyze what causes key brute force attacks and how to protect against them.

Key lengths

Any application that implements cryptography must choose a key size to encrypt and decrypt messages. Key lengths are measure in bits. For instance, a 64-bit key has 2<SUP> 64 </SUP>possible key combinations. However, in cryptography the expected number of tries to recover a valid key is of half the key space (2<SUP> 63</SUP>). The larger the key the more time it takes to brute force.  Symmetric block ciphers such as DES have fallen victims to this attack. DES uses a 56-bit key that was broken using brute force attack in 1998 [i]. To countermeasure key brute force attacks, it is recommended to use a key size of at least 128 bits.

Authentication brute force attacks

For key brute force attacks that focus at breaking authentication, , developers can take additional measures. For instance, they can implement an account lockout policy that locks out the account that is trying to be brute forced. However, attackers can use lockout policies to execute denial-of-service attacks on legitimate clients. For more information on counter measuring authentication brute force attacks refer to Team Mentor’s articles How to Test for Credential Brute Force Bugs and How to Test for Account Lockout Bugs.  

Step 3: Execute Test Cases

Now that you’ve reviewed the theoretical aspects of key brute force attacks, it is necessary to execute the following test cases to check if your application is vulnerable.

Test for key brute force using a known-plaintext attack

Follow these steps to test for key brute force using a known-plain text attack:

1. Discover a plaintext message P and its correspondent ciphertext C encrypted using key K (C = Encrypt(P, K)).
2. Iterate though all possible key values on the key space of K.  
   • For each predicted value K’, execute the decryption algorithm using the ciphertext from step 1 to produce its equivalent plaintext (P’ = Decrypt (C, K’)).
   • Check if the produced plaintext P’ equals the initial known plaintext (P = P’?).  

Expected results: the application is vulnerable if it is possible to recover a valid key in a reasonable amount of time.

Test for key brute force using a ciphertext-only attack

Follow these steps to test for key brute force using a ciphertext-only attack:

1. Discover a ciphertext message C that was encrypted using key K (C = Encrypt(P, K)). Note that plaintext P is unknown.
2. Iterate though all possible key values on the key space of K.
   • For each predicted value K’, execute the decryption algorithm using the ciphertext from step 1 to produce its equivalent plaintext (P’ = Decrypt(C, K’)).
   • Check if the produced plaintext P’ is readable.

Expected results: the application is vulnerable if it is possible to recover a valid key in a reasonable amount of time.

Test for key brute force attacks to bypass authentication

Follow these steps to test for key brute to bypass authentication:

1. Discover an application functionality that uses a cryptographic key K to authenticate its users.
2. Iterate though all possible key values on the key space of K.
   • For each predicted value K’, execute the application functionality in step 1 using K’.
   • Check if authentication is possible using K’.

Expected results: the application is vulnerable if it is possible to recover a valid key for authentication in a reasonable amount of time.

Conclusion

Key brute force attacks focus at discovering a valid key by trying a large amount of possible combinations. Once attackers discover a valid key they can use it to decipher encrypted data or to break an authentication scheme. This vulnerability is avoided by using an industry-standard algorithm with a large enough key of at least 128 bits, thus making the key space so large that is impossible to cover it in a reasonable amount of time.

Testing for key brute force attacks is done by executing different test cases. To test for key brute force attacks on encryption keys it is necessary to execute two different test cases, depending on whether the plaintext that produced the ciphertext is known or not. To test for key brute force attacks on authentication keys it is necessary to find an application functionality that performs authentication and that is accessible to outside users such as a login packet and perform the brute force attack.