DNS poisoning in Computer Networks - Time & Space Complexity

Time Complexity: DNS poisoning

O(n)

Understanding Time Complexity

We want to understand how the effort to carry out DNS poisoning changes as the size of the network or number of DNS queries grows.

Specifically, how does the attack scale when more DNS requests happen?

Scenario Under Consideration

Analyze the time complexity of this simplified DNS poisoning attempt process.

for each DNS query in network:
    attacker sends many fake responses quickly
    if fake response arrives before real one:
        DNS cache is poisoned
    else:
        attacker tries again on next query
    

This code tries to poison DNS caches by racing real DNS replies with fake ones for each query.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Looping over each DNS query and sending multiple fake responses.
• How many times: Once per DNS query, with multiple fake responses per query.

How Execution Grows With Input

As the number of DNS queries increases, the attacker must send more fake responses.

Input Size (n)	Approx. Operations
10 queries	About 10 sets of fake responses
100 queries	About 100 sets of fake responses
1000 queries	About 1000 sets of fake responses

Pattern observation: The effort grows roughly in direct proportion to the number of DNS queries.

Final Time Complexity

Time Complexity: O(n)

This means the attack effort grows linearly with the number of DNS queries to poison.

Common Mistake

[X] Wrong: "The attack effort stays the same no matter how many DNS queries happen."

[OK] Correct: Each DNS query requires a new attempt to send fake responses, so more queries mean more work.

Interview Connect

Understanding how attack effort scales helps you think like a defender or attacker, a useful skill in network security roles.

Self-Check

What if the attacker could poison multiple DNS caches with one fake response? How would the time complexity change?