Brute force and dictionary attacks in Cybersecurity - Time & Space Complexity

Time Complexity: Brute force and dictionary attacks

O(n)

Understanding Time Complexity

When analyzing brute force and dictionary attacks, we want to understand how the time to find a password grows as the number of possible passwords increases.

We ask: How does the effort change when the password list or key space gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following password guessing approach.

for password in password_list:
    if try_password(password):
        return "Password found"
return "Password not found"
    

This code tries each password from a list until it finds the correct one or runs out of options.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each password guess one by one.
• How many times: Up to the total number of passwords in the list.

How Execution Grows With Input

As the number of passwords to try grows, the time to find the correct one grows roughly the same way.

Input Size (n)	Approx. Operations
10	Up to 10 password tries
100	Up to 100 password tries
1000	Up to 1000 password tries

Pattern observation: The time grows directly with the number of passwords to test.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the password grows in a straight line as the number of guesses increases.

Common Mistake

[X] Wrong: "The attack will always find the password quickly because it tries many passwords fast."

[OK] Correct: Even if guesses are fast, the time needed grows with how many passwords there are to try, so it can still take a very long time.

Interview Connect

Understanding how brute force and dictionary attacks scale helps you explain security risks clearly and shows you can think about how attackers work in real situations.

Self-Check

"What if we used a smarter data structure to check passwords instead of a list? How would the time complexity change?"

Practice

1. What is the main difference between a brute force attack and a dictionary attack?

easy

A. Brute force uses common passwords; dictionary tries all possible combinations.

B. Brute force tries all possible passwords; dictionary uses a list of common passwords.

C. Brute force attacks only numeric passwords; dictionary attacks only words.

D. Brute force attacks are faster than dictionary attacks.

Solution

1. Step 1: Understand brute force attack method

   Brute force attacks try every possible password combination without skipping any.

2. Step 2: Understand dictionary attack method

   Dictionary attacks try passwords from a predefined list of common or likely passwords.

3. Final Answer:

   Brute force tries all possible passwords; dictionary uses a list of common passwords. -> Option B

4. Quick Check:

   Brute force = all combos, Dictionary = common list [OK]

Hint: Brute force = all combos; dictionary = common words list [OK]

Common Mistakes:

• Confusing which attack uses all combinations
• Thinking dictionary attacks try all passwords
• Assuming brute force only tries common passwords

2. Which of the following is the correct description of a dictionary attack?

easy

A. Guessing passwords based on user personal information.

B. Trying every possible password combination systematically.

C. Using a list of common passwords to guess the correct one.

D. Intercepting passwords during transmission.

Solution

1. Step 1: Identify dictionary attack method

   Dictionary attacks use a list of common or likely passwords to guess the correct one.

2. Step 2: Eliminate other options

   Trying every possible password combination systematically. describes brute force, C is social engineering, D is interception, not dictionary attack.

3. Final Answer:

   Using a list of common passwords to guess the correct one. -> Option C

4. Quick Check:

   Dictionary attack = common password list [OK]

Hint: Dictionary attack uses common password lists, not all combos [OK]

Common Mistakes:

• Mixing dictionary attack with brute force
• Confusing social engineering with dictionary attack
• Thinking dictionary attacks intercept passwords

3. Consider this scenario: An attacker uses a program that tries passwords from a list of 1000 common passwords. Which type of attack is this?

medium

A. Dictionary attack

B. Phishing attack

C. Brute force attack

D. Man-in-the-middle attack

Solution

1. Step 1: Analyze the attack method

   The attacker tries passwords from a list of common passwords, not all possible combinations.

2. Step 2: Match attack type

   Trying passwords from a list matches the definition of a dictionary attack.

3. Final Answer:

   Dictionary attack -> Option A

4. Quick Check:

   Common password list = Dictionary attack [OK]

Hint: List of common passwords means dictionary attack [OK]

Common Mistakes:

• Calling it brute force because it tries many passwords
• Confusing phishing with password guessing
• Mixing man-in-the-middle with guessing attacks

4. A security analyst notices a login system is vulnerable because it allows unlimited password attempts without delay. What is the main risk here?

medium

A. It encrypts passwords too strongly.

B. It prevents dictionary attacks from working.

C. It blocks all password guessing attempts.

D. It allows brute force attacks to try many passwords quickly.

Solution

1. Step 1: Understand unlimited attempts impact

   Allowing unlimited attempts lets attackers try many passwords fast without being blocked.

2. Step 2: Identify risk type

   This makes brute force attacks easier because they rely on trying many combinations quickly.

3. Final Answer:

   It allows brute force attacks to try many passwords quickly. -> Option D

4. Quick Check:

   Unlimited attempts = easier brute force [OK]

Hint: Unlimited tries let brute force run fast [OK]

Common Mistakes:

• Thinking it prevents dictionary attacks
• Assuming it blocks guessing attempts
• Confusing encryption strength with login attempts

5. Which of the following is the best way to protect against both brute force and dictionary attacks?

hard

A. Use strong, unique passwords and enable account lockout after failed attempts.

B. Use only numeric passwords to make guessing easier.

C. Disable password requirements to speed up login.

D. Share passwords with trusted friends.

Solution

1. Step 1: Identify effective password practices

   Strong, unique passwords are hard to guess by brute force or dictionary attacks.

2. Step 2: Understand account lockout benefits

   Locking accounts after failed attempts stops attackers from trying many passwords quickly.

3. Step 3: Evaluate other options

   Options A, B, and D weaken security and increase risk.

4. Final Answer:

   Use strong, unique passwords and enable account lockout after failed attempts. -> Option A

5. Quick Check:

   Strong passwords + lockout = best defense [OK]

Hint: Strong passwords + lockout stops guessing attacks [OK]

Common Mistakes:

• Thinking simple numeric passwords are safer
• Disabling password rules to speed login
• Sharing passwords reduces security