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?

Practice

1. What is the main goal of DNS poisoning in computer networks?

easy

A. To block access to certain websites

B. To redirect users to fake websites by giving wrong IP addresses

C. To encrypt DNS queries for security

D. To speed up the DNS lookup process

Solution

1. Step 1: Understand DNS function

   DNS translates website names into IP addresses so computers can find websites.

2. Step 2: Identify DNS poisoning effect

   DNS poisoning gives wrong IP addresses, sending users to fake sites instead of real ones.

3. Final Answer:

   To redirect users to fake websites by giving wrong IP addresses -> Option B

4. Quick Check:

   DNS poisoning = Redirect to fake sites [OK]

Hint: DNS poisoning tricks DNS to give wrong addresses [OK]

Common Mistakes:

• Thinking DNS poisoning speeds up browsing
• Confusing DNS poisoning with encryption
• Believing it blocks websites instead of redirecting

2. Which of the following is a correct way to describe DNS poisoning?

easy

A. It modifies DNS cache with false information

B. It encrypts DNS queries to protect privacy

C. It speeds up DNS resolution by caching

D. It blocks DNS requests from unknown sources

Solution

1. Step 1: Recall DNS poisoning mechanism

   DNS poisoning involves changing DNS cache entries to wrong IP addresses.

2. Step 2: Match description to options

   Only It modifies DNS cache with false information correctly states DNS poisoning modifies DNS cache with false info.

3. Final Answer:

   It modifies DNS cache with false information -> Option A

4. Quick Check:

   DNS poisoning = false DNS cache entries [OK]

Hint: DNS poisoning changes DNS cache to wrong info [OK]

Common Mistakes:

• Confusing poisoning with encryption
• Thinking it speeds up DNS
• Assuming it blocks requests

3. Consider this scenario: A user tries to visit example.com. Due to DNS poisoning, the DNS cache returns the IP 192.0.2.123 instead of the real IP 93.184.216.34. What is the likely result?

medium

A. The user is redirected to a fake website at IP 192.0.2.123

B. The DNS query fails and the website doesn't load

C. The user reaches the real example.com website safely

D. The user's browser automatically blocks the connection

Solution

1. Step 1: Understand DNS poisoning effect on IP

   The DNS cache gives a wrong IP (192.0.2.123) instead of the real one (93.184.216.34).

2. Step 2: Predict user experience

   The user is sent to the wrong IP, likely a fake website pretending to be example.com.

3. Final Answer:

   The user is redirected to a fake website at IP 192.0.2.123 -> Option A

4. Quick Check:

   Wrong IP from DNS = fake site visit [OK]

Hint: Wrong IP from DNS means fake site shown [OK]

Common Mistakes:

• Assuming user reaches real site
• Thinking DNS query fails
• Believing browser blocks automatically

4. A network admin notices users are being redirected to suspicious sites. They suspect DNS poisoning. Which action will help fix this issue?

medium

A. Turn off the internet connection temporarily

B. Disable the firewall to allow all traffic

C. Change all user passwords immediately

D. Clear the DNS cache on affected devices and servers

Solution

1. Step 1: Identify how DNS poisoning affects devices

   DNS poisoning corrupts DNS cache with wrong IP addresses causing redirection.

2. Step 2: Choose corrective action

   Clearing DNS cache removes false entries, restoring correct address resolution.

3. Final Answer:

   Clear the DNS cache on affected devices and servers -> Option D

4. Quick Check:

   Fix DNS poisoning by clearing DNS cache [OK]

Hint: Clear DNS cache to remove poisoned entries [OK]

Common Mistakes:

• Disabling firewall worsens security
• Changing passwords doesn't fix DNS
• Turning off internet is impractical

5. A company wants to protect its users from DNS poisoning attacks. Which combined approach is best to reduce risk?

hard

A. Manually edit hosts files on all user devices

B. Only use public Wi-Fi networks and disable firewalls

C. Use DNSSEC to verify DNS data and configure trusted DNS servers

D. Rely solely on antivirus software for protection

Solution

1. Step 1: Understand DNSSEC and trusted DNS servers

   DNSSEC adds digital signatures to DNS data to verify authenticity. Trusted DNS servers reduce risk of poisoning.

2. Step 2: Evaluate options for protection

   Use DNSSEC to verify DNS data and configure trusted DNS servers combines verification and trusted sources, effectively reducing DNS poisoning risk.

3. Final Answer:

   Use DNSSEC to verify DNS data and configure trusted DNS servers -> Option C

4. Quick Check:

   DNSSEC + trusted DNS = strong DNS poisoning defense [OK]

Hint: Use DNSSEC and trusted servers to stop poisoning [OK]

Common Mistakes:

• Thinking public Wi-Fi is safe
• Manually editing hosts is impractical
• Relying only on antivirus misses DNS attacks