Lecture Summary

In this lecture, we will see:

Kaminsky Attack

In 2008, Dan Kaminsky discovered a fundamental flaw in the Domain Name System (DNS) protocol that could allow attackers to easily perform cache poisoning attacks on most nameservers.With most Internet-based applications depending on DNS to locate their peers, a wide range of attacks became feasible, including website impersonation, email interception, and authentication bypass via the "Forgot My Password" feature on many popular websites.

After discovering the problem, Kaminsky initially contacted Paul Vixie, who described the severity of the issue as meaning "everything in the digital universe was going to have to get patched." Kaminsky then alerted the Department of Homeland Security and executives at Cisco and Microsoft to work on a fix.

Landscape: poisoning the cache of a remote DNS server?

Local DNS attack: information from packing sniffing

In the last lecture, we saw how a local DNS server's cache can be poisoned.
  1. Sniff a DNS request from a local DNS server.
  2. Send a fake DNS answer
To think about how to carry the local attack to the remote one, let's first identify the useful pieces of information that the sniffed DNS request contains.

[Query] How does an attacker figure out the query?

At this moment, the DNS packets flow as the following picture:

[ID] Great challenge: figuring out the id

The most difficult part is to figure out the identifier of the DNS query that the target DNS server made in step 2. Since the attacker cannot sniff the packet, there is no way to exactly know the identifier value!

That's why the Kaminsky attack is clever!

Birthday paradox

Birthday paradox is a well-known phenomenon:
If there are 23 people, at least two will share a birthday with probability more than 50%.
Generalization of the above is stated as follows:
There are n random numbers whose range is $[m]$.

If $n = O(\sqrt m)$, at least two numbers will be the same with probability more than 50%.

In the above, $m = 365$, and n is $23 \approx \sqrt{m}$.

In our context

The random numbers are identifiers. If the possible random $m$ is $2^{16} = 65536$ since the identifier is a 16-bit field. Note that $256 = \sqrt{65536}$. Let's look at the following code: 

#!/usr/bin/python3
# collision.py

import random

n = int(input("n? "))

requests = [ random.randrange(0, 65536) for i in range(n) ]
replies = [random.randrange(0, 65536) for i in range(n) ]

print( set(requests).intersection(set(replies)) )
  Sample runs are as follows: 
n? 100
set()

n? 256
{41529}

n? 300
{49306, 33708}
As expected, when n becomes at least $\sqrt m$, there is a matching identifer in the set replies.

Attack strategy: guessing an identifier

Based on the above observation, we considr the following strategy of guessing a random id. 

#!/usr/bin/python3
# guess.py

import random

n = 500
replies = [random.randrange(0, 65536) for i in range(n) ]
trial = 0

while True:
  # This is a random id that the DNS server will choose
  id = random.randrange(0, 65536)

  # Hope that one of the fake replies will hit!
  if id in replies:
    break
  trial += 1

# How many iterations do we need for this?
print("number of trials=", trial)
  The code shown on the left emulates the scenario that we are considering. In particular:
  • Variable id represents the random identifier that the target DNS server will choose.
  • The adversary should create a fake DNS reply whose identifiers is equal to id. As the code shows, it adversary simply chooses n (=500) random identifiers and hope for the best. This means that the adversary will create and flood these n fake DNS replies. Do this job would be very quick -- 500 is really a small number for a computer.
  • Of course, the attacks will fail most of the time.
  • The adversary will never give up. It will repeat this attack until it succeeds. Variable trial represents how many trials are necessary.
According to the Birthday Paradox, we hope that trial is not really big. Well let's check it out by running the code. Sample runs are listed below: 
 number of trials= 272
 
 number of trials= 38

 number of trials= 66
 
 number of trials= 120
Yes! This is actually the case!

Complications in Repeating the Guessing Games

Problem

As shown above, the adversary would like to repeat the guessing game until it succeeds. However, there is a problem.
The query www.wikipedia.org will get an answer from the legitimate server, and the target DNS server will cache this result for quite a long time.

Now, when someone makes a query on www.wikipedia.org, the target DNS server won't send a DNS packet (hence, no DNS reply packet to spoof!). It will just reuse the cached result.

Therefore, this strategy of repeated random guessing will take too long.

Kaminsky attack: use a non-existing subdomain name

A very cute idea of Kaminsky is to use a non-existing subdomain name. The following table describe why this works.
Step 1 What is the IP address of xdalzqe.wikipedia.org?
Step 2 What is the IP address of xdalzqe.wikipedia.org?
Step 3 or 4 Fake answer: 
The IP address for xdalzqe.wikipedia.org is 6.7.8.9.
Also, the name server for *.wikipedia.org is 
 nserver.wikipedia.org with IP address 6.7.8.9.
More precisely, 
;; ANSWER SECTION:
xdalzqe.wikipedia.org IN A   6.7.8.9 (or any other IP)
;; AUTHORITY SECTION:
wikipedia.org         IN NS  nserver.wikipedia.org 
;; ADDITIONAL SECTION:
nserver.wikipedia.org IN A   6.7.8.9
Real answer: 
No such name!
If none of the fake replies have the matching id, step 4 will take place, and the target server will receive the real answer. However, the real answer is about a bogus name! So, when the attacker repeats these guessing games with other random bogus names, the target DNS server will still send out DNS query packets!

If there was a match, the Authority Section will lead the target DNS server to send all the relevant queries to the adversarially controlled DNS server!

The Kaminsky attack super powerful, although source port randomization (hence more uncertaintly) will make it harder to attack the DNS servers. However, this is not an ultimate fix, because with much more trials and more fake packet flooding, the attack could work out with some chance.

Indeed, there is no effective simple fix to thwart this type of attack while still using the DNS protocol. We need a bigger change; We need to use a more secure protocol.

DNS Defense: DNSSEC

The overall idea is similar to PKI (Public-Key Infrastructure). That is, they establish the authenticity through the chain of digital signatures.

Public Keys

To use digital signatures, we need to access public keys. One can look up these public keys (called DNSKEYs) using a dig command. The following command shows the DNSKEY for the root domain.
  • ZSK (Zone Signing Key): It is used to sign the actual resource records. 
    ... DNSKEY  256 3 8 AwEAAaQ..
256: Flags ZSK
3: Protocol = Always 3
8: Algorithm RSA/SHA256
AwEAAaQ...: Actual ZSK (Verification Key)
  • KSK (Key Signing Key): It is used to sign DNSKEYs. Therefore, in this case, the RRSIG entry on the right has been generated by this key. 
    ... DNSKEY  257 3 8  AwEAAaz...
257: Flags KSK
3: Protocol = Always 3
8: Algorithm RSA/SHA256
AwEAAaz...: Actual KSK (Verification Key)
  • RRSIG: a digital signature of the entire reply. 
    8 : Algorithm RSA/SHA256
3 : Protocol 
172800: TTL
20220910000000: Signature start time
20220820000000: Signature expiration time 
20326: Key tag (with multiple keys, can be used as an id)

~$ dig +dnssec DNSKEY @a.root-servers.net .

; <<>> DiG 9.11.3 <<>> +dnssec DNSKEY @a.root-servers.net .
; (1 server found)
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 52161
;; flags: qr aa rd; QUERY: 1, ANSWER: 3, AUTHORITY: 0, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags: do; udp: 1472
;; QUESTION SECTION:
;.                              IN      DNSKEY

;; ANSWER SECTION:
.                       172800  IN      DNSKEY  256 3 8 
         AwEAAaQVKIqdmeLCaF4lq+IoKpejId9qqoIbZJ6cjB5MfyJYX3KVFXYy 
         J9rt4jKOwf4m2BoDOY66V1upRumF+eu502HXzdOdJlioRLA9YiRyLgvf 
         ...(omitted)...
         FsitupCciwE=
.                       172800  IN      DNSKEY  257 3 8 
         AwEAAaz...(omitted)...V74bU=
.                       172800  IN      RRSIG   DNSKEY 8 0 
         172800 20220910000000 20220820000000 20326 . 
         G2uHz1V7A+BdCJpR5e1lYouoB0Sk1L1fOTXA1fBAqVGDrhDbIev/Z9tZ 
         luPwkSheqpm4ns+v/TQC+DupoT/CavIb9Q38IAj3vZxN9Pk6F/rEmusV 
         ...(omitted)...
         uijebQ==

;; Query time: 13 msec
;; SERVER: 198.41.0.4#53(198.41.0.4)
;; WHEN: Tue Aug 23 06:20:00 EDT 2022
;; MSG SIZE  rcvd: 864

Chaining the digital signatures

(Source: https://security1.win.tue.nl/lib/exe/fetch.php?media=papers:noms-18-dnssec.pdf)
  • Deployment Issues. Unfortuantely, DNSSEC is not widely depolyed.

    DNS Defense: DNS over TLS (DoT) and DNS over HTTPS (DoH)

    DoT

    One way to overcome this attack is executing DNS over TLS. DoT is a network security protocol for encrypting and wrapping Domain Name System (DNS) queries and answers via the Transport Layer Security (TLS) protocol. The goal of the method is to increase user privacy and security by preventing eavesdropping and manipulation of DNS data via man-in-the-middle attacks.

    Recall that TLS provides the certificate feature that allows the client to check the authenticity of the server. A fake DNS server, without a legitimate certificate, won't be able to pass this certificate check.

    DoH

    DNS over HTTPS (DoH) is a similar protocol. It is a protocol for performing remote Domain Name System (DNS) resolution via the HTTPS protocol. By March 2018, Google and the Mozilla Foundation had started testing versions of DNS over HTTPS. In February 2020, Firefox switched to DNS over HTTPS by default for users in the United States.