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?"