The big security news of Summer 2008 has been Dan Kaminsky's discovery of a serious vulnerability in DNS. This vulnerability could allow an attacker to redirect network clients to alternate servers of his own choosing, presumably for ill ends.
Table of Contents This all led to a mad dash to patch DNS servers worldwide, and though there have been many writeups of just how the vulnerability manifests itself, we felt the need for one in far more detail. Hence, one of our Illustrated Guides.
This paper covers how DNS works: first at a high level, then by picking apart an individual packet exchange field by field. Next, we'll use this knowledge to see how weaknesses in common implementations can lead to cache poisoning.
By fully understanding the issues at play, the reader may be better equipped to mitigate the risks in his or her own environment.
We hope everybody who runs a DNS server patches soon.
With a few key terms defined, we'll review how a simple recursive query works in the absence of any bugs or shenanigans; this forms the background of where the exploits can later be applied.
Though the DNS packet itself has many fields (each of which is important), we're omitting that detail for now in order to understand the high level flow of a full query, from top to bottom. Visualizing how delegation bounces requests from one server to another is vital to understanding the vulnerability will be exploited later.
We can't really tell by looking at the query itself what prompted the query in the first place. In the logo of this section, we see that the user attempted to ping our webserver, and the ping program asked the nameserver to perform this name-to-IP lookup.
But it could have just as easily been a user entering http://www.unixwiz.net in a browser address bar. But it's not important to know why the name's being looked up, only to know how it looks up.
This procedure goes on under the hood trillions of time every day over the internet. DNS is quite fast, so the eight-packet handshake (for this particular query) routinely completes in just a split second.
This reveals the distributed nature of DNS: no one machine knows everything, but they do know how to find each other via delegation.
As a side note, nothing prevents any nameserver from hosting any zone, including those it doesn't really own. A bad guy could set up a nameserver and configure an authoritative zone for BankOfSteve.com, but it has no effect because no higher-level nameserver ever delegates to it.
The illustration on the right shows the overall structure of a single packet of DNS data, and it can reflect a question packet or an answer packet. We've highlighted some of the fields that are most related to this exploit.
Ultimately, DNS is a kind of distributed database, and each query or response includes a name, a type, and (for a response) a value. The resource types represent different purposes, and no understanding of DNS is complete without knowing about them.
There are dozens of resource record types, though only a few are in common usage. The rest are experimental, obsolete, or serve obscure purposes that rarely come up in practice.
It's generally (but not universally) allowed that one name can have multiple resource records, even more than one of the same type. A common example would be a machine having multiple IP addresses, both of which are entered in DNS:
We'll note that the IN token means the INternet class, and this is virtually the only class you'll ever see in practice. Others (such as Chaos or Hesiod) are defined but are for specialized and mostly obsolete purposes.
Recalling our query exchange above, we're going to study steps 4 through 7 in some detail: they are most representative of the DNS name-resolution process without adding duplicative steps.
Ultimately, DNS is a kind of distributed database, and it can look up much more than just an IP address: there are multiple resource record types involved in a query, and one can't understand the packet structure without knowing their distinctions.
We'll note that not every detail is predictable even when the protocol is fully understood: nameservers have some latitude in how they accomplish a resolution, so a few alternatives are available. We're just choosing one common path through this process.
In this example, we're using the nameserver of our own ISP — dnsr1.sbcglobal.net — (referred to as dnsr1) as the local recursive nameserver, and we'll find a few things in common for all of them.
As noted previously, these transactions typically occur very rapidly across the internet, and the user is normally unaware that so much is going on under the hood on his behalf.
But local performance is further enhanced by use of a local cache in the recursive nameservers: this is an important part of the domain-name system, and gets us one step closer to our security issue.
In the DNS lookups we've seen so far, the ISP's resolving nameserver has gone out and fully resolved each name from scratch, relying on no prior knowledge except the built-in root hints.
But in practice this full road trip is not necessary: once we get an authoritative answer for a given name, we can save it in a local cache to use to satisfy future queries directly.
The more clients serviced by a nameserver, the more benefit of the cache: the work of the full name resolutions is spread out over the whole client base. It may well require quite a bit of memory in the nameserver, but the amounts of RAM required are peanuts compared with the benefits.
Fortunately, the recursive nameserver doesn't have the burden of guessing how long to cache things: the administrator of the zone specifies this information for every resource record. This is known as a Time To Live (TTL), and it's a lifetime measured in seconds.
A TTL can be a short as a few minutes, or as long as a week or more: this is entirely determined by the administrator of the zone.
In our final Step-7 answer above (with snippet to the right), we see the TTL of one hour for the A record in www.unixwiz.net. All client requests for this resource record in the next hour will be satisfied immediately, from the cache. But once it expires, it's removed from cache and the next request will force a full lookup from scratch.
But it's not just the A record that's cached; all the other authority data (the NS data plus associated glue A records) arrive with their own TTLs, and are also cached. This means that a full lookup for a single resource record could well fill the cache with a half dozen associated records or more.
It's not so simple as just sending random DNS packets to a nameserver, as DNS only accepts responses to pending queries; unexpected responses are simply ignored.
How does a nameserver know that any response packet is "expected"?
But if the bad guy can predict and forge a DNS response packet that's just right, he can cause all kinds of shenanigans for the victims.
The bad guy normally first chooses his victim by finding a nameserver he believes vulnerable to poisoning: all of the clients of that DNS server get to unwittingly ride the victim train as well.
Then he finds a target domain, one he wishes to take over. His intent is to fool the victims into visiting his own malicious website instead of the real deal: by getting www.goodsite.com to resolve to the bad guy's IP address, the user's traffic visits the bad guy's website instead of the good one.
We noted that unexpected packets were simply dropped, so a bad guy need not get everything right every time: sending many packets attempting to guess some of the key parameters is likely to prove fruitful with enough attempts.
We probably can't directly ask the nameserver for its query ID, but we can provoke it into telling us:
But the thoughtful might wonder: so what? This hasn't poisoned anything yet, and there's no need to engage in DNS shenanigans for badguy.com anyway. After all, the bad guy is already authoritative for his own zone.
True enough, but this was only the first step: the next one engages in DNS shenanigans for other domains.
In this illustration, we'll attempt to poison a particular nameserver with a fraudulent IP for a legitimate banking website, www.BankOfSteve.com. The bad guy's intention is to get all of the ISP's customers to visit his own malicious site instead of the real one operated by the Bank.
And because that satisfies the request, the real answer that arrives later is dropped, because the query is no longer pending.
In any case, once the bad guy gets the answer from the victim's nameserver, the matter is closed, and he can stop flooding the victim.
We'll note that even though this illustrates trying to beat just the reply from ns1.bankofsteve.com, our forged DNS traffic could actually match the query ID of any of the prior steps.
This includes matching an earlier reply from the root server or the GTLD (.com) server: if the query ID matches, our fake authoritative wins, and pollutes the cache. This is a race, but only the attacker knows it's playing.
With sequential Query IDs, the bad guy has a fairly limited range of guesses required once he observes a single current Query ID. If he sees QID=999, then he may flood with QIDs 1000-1029 in an attempt to make at least one match.
Experience has shown this is an easy window to beat.
But if the nameserver chooses random Query IDs, then the attacker has the full 16-bit pool to choose from — that's 64k values — and this is a much harder target to hit in the narrow window of time while the victim is going through the routine resolution steps.
Though forging 20 packets in routine name-resolution time is straightforward enough, doing so with thousands of packets is a much more substantial challenge.
So true randomization of Query IDs raises the bar quite a bit.
Dan Kaminsky found an approach that's dramatically more effective than this, and it caused quite a furor in the security community. The general approach is the same as the simple approach shown above, but the key difference is the nature of the forged payload.
In the simple example, our intention was to poison the final answer, the A record with the IP address, but what Dan discovered is that we can go up one level and hijack the authority records instead.
Before undertaking the attack, the bad guy configures a nameserver that's authoritative for the bankofsteve.com zone, including whatever resource records he likes: A records, MX for email, etc.
There's nothing stopping anybody from configuring his own nameserver to be authoritative for any domain, but it's pointless because the root servers won't point to it: it's got answers, but nobody ever asks it a question.
The bad guy will typically set a very high TTL in the poisoning responses so that the victim will keep the bogus data in cache as long as possible.
Instead, the bad guy issues a flurry of queries, each for a different random name under the main domain. The first request caused the nameserver to perform the usual root-first resolution, but it eventually caches the valid ns1.bankofsteve.com values. Subsequent queries within this domain go directly to that nameserver, skipping the root steps.
But the next request for a different random name (which certainly won't be in cache) causes an immediate query to the valid ns1 server. The bad guy then throws a flood of forged data at the victim about that second random name, though the odds here are still pretty long.
Just for the sake of discussion, let's assume that the bad guy can generate 50 forged replies for each random name query before the real reply arrives from the real nameserver. This appears to be a very small chance, but when repeated over and over — and run from automated tools — success by the bad guy is likely.
It's been reported that success can commonly be achieved in 10 seconds.
By poisoning the Authority records for .COM and the like, the victim nameserver will route all DNS lookups to the bad guy's nameservers. This effectively hijacks all names under that top level, including domains he didn't actually request. This gives a great deal of flexibility even though it may well require substantial computing and network resources to serve the flood of requests that this hijacking must generate.
As has been alluded to several times, it's the small space — just 16 bits — of the Query ID that makes this attack possible. Though certainly one might wish to increase that ID to something larger (perhaps 32 bits), it's simply not possible do that in the short term because it would break DNS on the internet: the fields are what they are, and they can't be changed casually.
But an additional source of randomness is required nevertheless, and that's been done by randomizing the source port. Rather than use just a single UDP port, which is trivial to discover, a much larger range of ports is allocated by the nameserver and then used randomly when making outbound queries.
As one would imagine, the nameserver would keep track of which source port was used for each query: replies arriving on the wrong port would be discarded just as if the Query ID failed to match.
Microsoft's updated DNS server is said to preallocate 2,500 UDP ports to use for these random queries, and for discussion we'll round this down to an even power of two: 2 11 = 2,048. This yields this much larger transaction space:
Increasing the search space from 64k to 134M provides far better odds for the good guys.
We presume that each nameserver provides a way of setting how large of a pool to use for these source ports, as well as a way of excluding certain port numbers known to be required for other purposes.
There is far more detail about this vulnerability than we can present here, and we'll urge the reader to consult other resources (especially Dan's presentation).
But we can include a few (ahem) random notes about this matter that didn't seem to fit in elsewhere, and seem important and/or interesting enough to include in this paper.
Reference: http://unixwiz.net/techtips/iguide-kaminsky-dns-vuln.html
This paper covers how DNS works: first at a high level, then by picking apart an individual packet exchange field by field. Next, we'll use this knowledge to see how weaknesses in common implementations can lead to cache poisoning.
By fully understanding the issues at play, the reader may be better equipped to mitigate the risks in his or her own environment.
We hope everybody who runs a DNS server patches soon.
Terminology
Before we see how DNS operates, we need to define a few terms to know who the players are, software-wise. This will be review for many, and in some cases we leave out side details that an expert would find fault with. Omitted details won't matter for an understanding of this issue.- zone
- Think of this as a "domain": a collection of hostnames/IP pairs all managed together.
- Our servers operate unixwiz.net, and all the DNS records that go with it — www.unixwiz.net, mvp.unixwiz.net, cs.unixwiz.net, etc. — are all part of the unixwiz.net zone.
- The subtle distinction comes with subdomains: sometimes they are part of the main zone, sometimes they are a separate zone, but none of that matters for this paper.
- Nameserver
- This is server software that answers DNS questions, such as "What is the IP address for www.unixwiz.net?". Sometimes a nameserver knows the answer directly (if it's "authoritative" for the zone), other times it has to go out to the internet and ask around to find the answer (if it's a recursive nameserver).
- There is wide variety of software that performs this service: BIND, PowerDNS, djbdns, and many others. They all answer the same questions more or less the same way, though the minor differences matter some for this paper.
- Authoritative Nameserver
- For every zone, somebody has to maintain a file of the hostnames and IP address associations ("linux.unixwiz.net is 64.170.162.98", and so on). This is generally an administrative function performed by a human, and in most cases one machine has this file. It's the zone master.
- Zones with multiple public nameservers make administrative arrangements to transfer the zone data automatically to additional slave nameservers, all of which are authoritative as far as the outside world is concerned. The distinction between master and slave is unimportant for this paper.
- Resolver
- This is the client part of the DNS client/server system: it asks the questions about hostnames. The resolver is usually a small library compiled into each program that requires DNS services, and it knows just enough to send questions to a nearby nameserver.
- On Linux/UNIX systems, the location of the servers-to-ask is found in the file /etc/resolv.conf, and on Windows it's part of the Network Connections setup in the control panel. This usually consists of a list of IP addresses, each of which expects to find a nameserver on the other end.
- Resolvers are usually very small and dumb, relying on the servers to do the heavy lifting.
- Recursive Nameserver
- This is a nameserver that's willing to go out on the internet and find the results for zones it's not authoritative for, as a service to its clients. Not all nameservers are configured to provide recursive service, or are limited to just trusted clients (say, an ISP may provide nameservice only to its customers).
- Resource Record
- Though most think of DNS as providing hostname-to-IP mapping, there are actually other kinds of questions we can ask of a nameserver, and this highlights the notion that DNS is really a database of "resource records".
- The most common type is an IP Address (an "A" record), but other records exist too: NS (nameserver), MX (mail exchanger), SOA (Start of Authority), and so on.
- Delegation
- When a nameserver doesn't have the contents of a zone, but knows how to find the owner, it's said to delegate service of that zone to another nameserver. Informally, it's a pass-the-buck mechanism: "I know the zone you're asking about, go ask (hostname) for the details".
Following a simple DNS query
With a few key terms defined, we'll review how a simple recursive query works in the absence of any bugs or shenanigans; this forms the background of where the exploits can later be applied. Though the DNS packet itself has many fields (each of which is important), we're omitting that detail for now in order to understand the high level flow of a full query, from top to bottom. Visualizing how delegation bounces requests from one server to another is vital to understanding the vulnerability will be exploited later.
We can't really tell by looking at the query itself what prompted the query in the first place. In the logo of this section, we see that the user attempted to ping our webserver, and the ping program asked the nameserver to perform this name-to-IP lookup.
But it could have just as easily been a user entering http://www.unixwiz.net in a browser address bar. But it's not important to know why the name's being looked up, only to know how it looks up.
| 1 | The client (noted as "User's PC") makes a request for www.unixwiz.net, and it's routed to the nameserver provided by the user's ISP. It requests the A record, which represents an IP address. The ISP's nameserver knows that it's not authoritative for unixwiz.net, so it can't look it up in its local zone database. It also doesn't find the name it its cache of recently-seen data, so it knows it has to go out to the internet to find it for us. |  |
| 2 | All recursive nameservers are preconfigured with a list of 13 root servers, a selection of which looks like: Root hints A.ROOT-SERVERS.NET. IN A 198.41.0.4 B.ROOT-SERVERS.NET. IN A 192.228.79.201 C.ROOT-SERVERS.NET. IN A 192.33.4.12 ... M.ROOT-SERVERS.NET. IN A 202.12.27.33Thankfully these IP addresses don't change very often. The nameserver picks one at random and sends off the query for the A record of www.unixwiz.net; here it's going to b.root-servers.net |  |
| 3 | The root server doesn't know anything about unixwiz.net, but is happy to send me the way of the Global Top Level Domain (GTLD) servers responsible for the .net domain. This is in the form of NS records of servers more qualified to answer our query: "Go ask these guys - here's a list". .NET referrals /* Authority section */
NET. IN NS A.GTLD-SERVERS.NET.
IN NS B.GTLD-SERVERS.NET.
IN NS C.GTLD-SERVERS.NET.
...
IN NS M.GTLD-SERVERS.NET.
/* Additional section - "glue" records */
A.GTLD-SERVERS.net. IN A 192.5.6.30
B.GTLD-SERVERS.net. IN A 192.33.14.30
C.GTLD-SERVERS.net. IN A 192.26.92.30
...
M.GTLD-SERVERS.net. IN A 192.55.83.30Though technically we asked only for the NS records, the root servers also give us the IP address of each: this is known as "glue" and is provided to save us from having to look it up. | |
| 4 | With the helpful referral from the root servers, this nameserver chooses one of the authoritative servers at random — here, c.gtld-servers.net — and sends off the same query: "I was told to ask you: what's the A record for www.unixwiz.net?". |  |
| 5 | The GTLD server doesn't know the specific answer to our query, but it does know how to get us closer. Like the root servers, it sends back a referral (a set of NS records) that are likely to have what we seek. unixwiz.net referral /* Authority section */
unixwiz.net. IN NS cs.unixwiz.net.
IN NS linux.unixwiz.net.
/* Additional section - "glue" records */
cs.unixwiz.net. IN A 8.7.25.94
linux.unixwiz.net. IN A 64.170.162.98 | |
| 6 | Once again the recursive nameserver is following a chain of referrals on the client's behalf, and it picks one of the nameservers at random and sends off a third query (the same as the other two). |  |
| 7 | Unlike the other answers, that merely passed the buck onto other nameservers, this one actually has what we were looking for: it provides the A record for www.unixwiz.net. In addition, the response includes a flag saying "This is an authoritative response", indicating it came from the source of truth for this domain. | |
| 8 | Now with answer in hand, the ISP's recursive nameserver hands that answer back to the client, and that satisfies the entire query. The recursive nameserver also files away this answer into its own cache in case this or some other client makes the same query later. But we'll note that the reply to the client doesn't include the "authoritative" indicator. Even though it received one from cs.unixwiz.net, the recursive nameserver can't pretend to the client that it's actually the source of authority, so it's considered a non-authoritative answer. |  |
This reveals the distributed nature of DNS: no one machine knows everything, but they do know how to find each other via delegation.
As a side note, nothing prevents any nameserver from hosting any zone, including those it doesn't really own. A bad guy could set up a nameserver and configure an authoritative zone for BankOfSteve.com, but it has no effect because no higher-level nameserver ever delegates to it.
What's in a DNS packet?
With a grasp of the high-level exchanges we dig a bit deeper into what's inside a DNS packet: the details are required to understand cache poisoning and this recent vulnerability. There's a lot of detail here, but fortunately many of the fields aren't important for an understanding of these issues.The illustration on the right shows the overall structure of a single packet of DNS data, and it can reflect a question packet or an answer packet. We've highlighted some of the fields that are most related to this exploit.
- Source / Destination IP address
- These reflect the IP addresses of the machines that sent and should receive the packet. It's possible to forge the source address, but pointless to forge the destination.
- Analog in the real world: on an envelope sent in the US Mail, you can put anything you want as the return address — the source address — but if you lie about the recipient, it's not going to go where you want.
- Source / Destination port numbers
- DNS servers listen on port 53/udp for queries from the outside world, so the first packet of any exchange always includes 53 as the UDP destination port.
- The source port varies considerably (though not enough, as we'll find shortly): sometimes it's also port 53/udp, sometimes it's a fixed port chosen at random by the operating system, and sometimes it's just a random port that changes every time.
- As far as DNS functionality is concerned, the source port doesn't really matter as long as the replies get routed to it properly. But this turns out to be the crux of the problem at hand.
- Query ID
- This is a unique identifier created in the query packet that's left intact by the server sending the reply: it allows the server making the request to associate the answer with the question.
- A nameserver might have many queries outstanding at one time — even multiple queries to the same server — so this Query ID helps match the answers with the awaiting questions.
- This is also sometimes called the Transaction ID (TXID).
- QR (Query / Response)
- Set to 0 for a query by a client, 1 for a response from a server.
- Opcode
- Set by client to 0 for a standard query; the other types aren't used in our examples.
- AA (Authoritative Answer)
- Set to 1 in a server response if this answer is Authoritative, 0 if not.
- TC (Truncated)
- Set to 1 in a server response if the answer can't fit in the 512-byte limit of a UDP packet response; this means the client will need to try again with a TCP query, which doesn't have the same limits.
- RD (Recursion Desired)
- The client sets this to 1 if it wishes that the server will perform the entire lookup of the name recursively, or 0 if it just wants the best information the server has and the client will continue with the iterative query on its own. Not all nameservers will honor a recursive request (root servers, for instance, won't ever perform recursive queries).
- RA (Recursion Available)
- The server sets this to indicate that it will (1) or won't (0) support recursion.
- Z — reserved
- This is reserved and must be zero
- rcode
- Response code from the server: indicates success or failure
- Question record count
- The client fills in the next section with a single "question" record that specifies what it's looking for: it includes the name (www.unixwiz.net), the type (A, NS, MX, etc.), and the class (virtually always IN=Internet).
- The server repeats the question in the response packet, so the question count is almost always 1.
- Answer/authority/additional record count
- Set by the server, these provide various kinds of answers to the query from the client: we'll dig into these answers shortly.
- DNS Question/Answer data
- This is the area that holds the question/answer data referenced by the count fields above. These will be discussed in great detail later.
Resource Record Types
Ultimately, DNS is a kind of distributed database, and each query or response includes a name, a type, and (for a response) a value. The resource types represent different purposes, and no understanding of DNS is complete without knowing about them. There are dozens of resource record types, though only a few are in common usage. The rest are experimental, obsolete, or serve obscure purposes that rarely come up in practice.
| Type | Description |
|---|---|
| A | This is an IP Address record, and is the most obvious type of data supported by DNS. Indeed; many users have no idea that DNS deals with anything other than IP addresses. |
| NS | This describes a Nameserver record responsible for the domain asked about. |
| MX | The MX record encodes the name of a Mail Exchanger, a system responsible for handling email for the given domain. Multiple MX records can be provided for a domain (they included way to specify priority). Email server software is the main consumer of MX resource records. Curiously, the mail exchanger for a domain doesn't have to be part of that domain; it's common for the mailserver at a large hosting operation to be primary MX for thousands of customer domains. |
| SOA | The Start of Authorities record describes some key data about the zone as defined by the zone administrator (on the domain master machine). It includes things such as the contact address for the admin, and the amount of time that slave nameservers should hang onto the zone in case the master is unreachable. |
| CNAME | The Canonical Name, more commonly known as an Alias, this allows providing an alternate name for a resource. |
| TXT | A generic Text record that provides descriptive data about domain. These are essentially comments, though some applications (such as SPF) use them for programmatic purposes. |
www.example.com. IN A 192.168.1.3 www.example.com. IN A 192.168.7.149Here, the name www.example.com has two IP address records associated with it, and both will be returned in answer to an A query for this name. Note that the order of the addresses as they appear in the file are not maintained in the responses: they're usually shuffled.
We'll note that the IN token means the INternet class, and this is virtually the only class you'll ever see in practice. Others (such as Chaos or Hesiod) are defined but are for specialized and mostly obsolete purposes.
Drilling down to a real query
Recalling our query exchange above, we're going to study steps 4 through 7 in some detail: they are most representative of the DNS name-resolution process without adding duplicative steps. Ultimately, DNS is a kind of distributed database, and it can look up much more than just an IP address: there are multiple resource record types involved in a query, and one can't understand the packet structure without knowing their distinctions.
We'll note that not every detail is predictable even when the protocol is fully understood: nameservers have some latitude in how they accomplish a resolution, so a few alternatives are available. We're just choosing one common path through this process.
In this example, we're using the nameserver of our own ISP — dnsr1.sbcglobal.net — (referred to as dnsr1) as the local recursive nameserver, and we'll find a few things in common for all of them.
- In every case, the Question section is the same: "What is the A record for www.unixwiz.net?". This question is also repeated in the answer — mainly as a convenience — so it's seen in common in every packet we look at.
- The ISP's nameserver usually sets the RD=1 flag (Recursion Desired) on the odd chance that the other end is willing to do the heavy lifting and go find this answer for us. Most top-level nameservers are unwilling to do this, so they give us the best information they have and set RA=0 flag (Recursion Unavailable) to let us know that we have to do the work ourselves.
- In this example, the source UDP port number for all queries from our ISP's nameserver is the same. It's a common practice for nameserver software to request a random port from the operating system at startup, then use it for every query.
- We observe that the Query ID increments by one each time it sends a new query.
| 2&3 | In this step our ISP's nameserver queried a root server for www.unixwiz.net, and it replied with a list of global top-level domain servers that knew about the .net hierarchy. From this delegation, the ISP's nameserver chose one at random (c.gtld-servers.net), as shown in step 4. | (not illustrated) |
| 4 client to server | The dnsr1 server at our ISP grabs one of the GTLD nameservers received from a root server (in step 3) and fires off a second query. This is essentially the same as the first; the Question is about the A record www.unixwiz.net. Because this is a query — not a response — the answer/authorities/additional records fields are blank (as shown with a count of zero). The Query ID value was taken as the next ID available from this server's internal counter. |  |
| 5 server to client | The GTLD server we asked doesn't know the specific answer to our question, but it knows where to ask: it responds with a series of NS records that should know how to handle our request. They show up in the Authorities section as cs.unixwiz.net and linux.unixwiz.net. We're given hostnames of the nameservers we ought to contact, but real network connections are only made by IP address: how do we look these up? Avoiding what would clearly be a chicken-and-egg problem, the GTLD nameserver provides not only the hostnames of the authoritative servers, but their IP addresses too. These are provided as A records in the "Additional Records" section, and are known as "glue data". Because this nameserver can't give us the final answer, it sets the AA=0 flag (Authoritative Answer) to zero, indicating that somebody else knows the real story and we have to keep asking around. But a related note: dnsr1 is a very busy nameserver, having perhaps hundreds of queries outstanding every second. How does it know that this reply packet is a response to that specific pending request? The answer is: by matching on the Query ID. Inbound DNS packets that don't have a waiting Query ID are ignored. The TTL is a Time To Live, discussed later. |  |
| 6 client to server | In step 5 we received two nameservers that are purported to know more about the unixwiz.net domain, so one more query is created that asks the same question — again! — of these just-learned nameservers. This request is really no different from the previous queries, though it does increment the Query ID by one before sending it off. The idea is that we keep following these delegations until we actually get a real answer, not a referral. |  |
| 7 server to client | And at last the answer comes! Unlike the previous replies, this one has answer count=1, and it carries an A record with the IP address to satisfy our query. In addition, this response has the AA=1 flag set, which indicates that it's an authoritative answer (aka "from the horse's mouth"). If an answer is provided but with AA=0, we assume it's from the server's cache. The answer also includes the authority and glue information, but this time all we're really interested in is the answer itself. And the nameserver used the Query ID of 43562 to match this reply to the pending request. |  |
But local performance is further enhanced by use of a local cache in the recursive nameservers: this is an important part of the domain-name system, and gets us one step closer to our security issue.
What's in the cache?
In the DNS lookups we've seen so far, the ISP's resolving nameserver has gone out and fully resolved each name from scratch, relying on no prior knowledge except the built-in root hints. But in practice this full road trip is not necessary: once we get an authoritative answer for a given name, we can save it in a local cache to use to satisfy future queries directly.
The more clients serviced by a nameserver, the more benefit of the cache: the work of the full name resolutions is spread out over the whole client base. It may well require quite a bit of memory in the nameserver, but the amounts of RAM required are peanuts compared with the benefits.
The Time-To-Live
When a DNS answer is stored in the local cache, it can't keep it forever: this could lead to terribly stale data that effectively breaks the domains involved. Fortunately, the recursive nameserver doesn't have the burden of guessing how long to cache things: the administrator of the zone specifies this information for every resource record. This is known as a Time To Live (TTL), and it's a lifetime measured in seconds. A TTL can be a short as a few minutes, or as long as a week or more: this is entirely determined by the administrator of the zone.
In our final Step-7 answer above (with snippet to the right), we see the TTL of one hour for the A record in www.unixwiz.net. All client requests for this resource record in the next hour will be satisfied immediately, from the cache. But once it expires, it's removed from cache and the next request will force a full lookup from scratch.
But it's not just the A record that's cached; all the other authority data (the NS data plus associated glue A records) arrive with their own TTLs, and are also cached. This means that a full lookup for a single resource record could well fill the cache with a half dozen associated records or more. Poisoning the cache
With a good understanding of a properly-functioning DNS, it's time to see where things break. Cache poisoning is where the bad guy manages to inject bogus data into a recursive nameserver's cache, causing it to give out that bad information to unsuspecting local clients.It's not so simple as just sending random DNS packets to a nameserver, as DNS only accepts responses to pending queries; unexpected responses are simply ignored.
How does a nameserver know that any response packet is "expected"?
- The response arrives on the same UDP port we sent it from: otherwise the network stack would not deliver it to the waiting nameserver process (it's dropped instead).
- The Question section (which is duplicated in the reply) matches the Question in the pending query.
- The Query ID matches the pending query
- The Authority and Additional sections represent names that are within the same domain as the question: this is known as "bailiwick checking".
This prevents ns.unixwiz.net from replying with not only the IP address of www.unixwiz.net, but also fraudulent information about (say) BankOfSteve.com.
But if the bad guy can predict and forge a DNS response packet that's just right, he can cause all kinds of shenanigans for the victims.
The bad guy normally first chooses his victim by finding a nameserver he believes vulnerable to poisoning: all of the clients of that DNS server get to unwittingly ride the victim train as well.
Then he finds a target domain, one he wishes to take over. His intent is to fool the victims into visiting his own malicious website instead of the real deal: by getting www.goodsite.com to resolve to the bad guy's IP address, the user's traffic visits the bad guy's website instead of the good one.
We noted that unexpected packets were simply dropped, so a bad guy need not get everything right every time: sending many packets attempting to guess some of the key parameters is likely to prove fruitful with enough attempts.
Guessing the Query ID
In old nameservers (and in our detailed packet trace example), the Query ID simply increments by one on each outgoing request, and this makes it easy to guess what the next one will be as long as an interloper can see a single query. We probably can't directly ask the nameserver for its query ID, but we can provoke it into telling us: - Bad guy asks the victim nameserver to look up a name in a zone for a nameserver he controls (perhaps test.badguy.com).
He might query the server directly, if it permits recursion from his location, or he might convince a user to lookup a name — perhaps by including the test hostname on a web page.
- Victim nameserver receives the request and makes the usual rounds to resolve the name starting at the root servers. Here, we've put the root and GTLD servers in the same category to separate them from the bad guy's nameserver.
- Eventually, the victim nameserver will be directed to the bad guy's nameserver: after all, it's authoritative for badguy.com.
- Bad guy monitors this lookup of test.badguy.com by sniffing the IP traffic going to his own machine, or perhaps even with a custom modification to the nameserver software, and from this discovers the source port and Query ID used.
Aha!
But the thoughtful might wonder: so what? This hasn't poisoned anything yet, and there's no need to engage in DNS shenanigans for badguy.com anyway. After all, the bad guy is already authoritative for his own zone.
True enough, but this was only the first step: the next one engages in DNS shenanigans for other domains.
Shenanigans, Version 1
With the ability to easily predict a query ID, and since our victim nameserver always sends queries from the same UDP port, it should be easy enough to cause some trouble.In this illustration, we'll attempt to poison a particular nameserver with a fraudulent IP for a legitimate banking website, www.BankOfSteve.com. The bad guy's intention is to get all of the ISP's customers to visit his own malicious site instead of the real one operated by the Bank.
- Step 1 — Bad guy sends a DNS query to the victim nameserver for the hostname it wishes to hijack. This example assumes that the victim nameserver allows recursive queries from the outside world.
- Step 2a — Knowing that the victim will shortly be asking ns1.bankofsteve.com (as directed from the root/GTLD servers) for an IP address, the bad guy starts flooding the victim with forged DNS reply packets. All purport to be from ns1.bankofsteve.com, but include the answer with the IP of badguy's fraudulent webserver.
- Steps 2b & 3 — Root/GTLD servers provide referral to ns1.bankofsteve.com. This may be multiple queries, but we're showing just one for simplicity.
- Step 4 — victim nameserver asks ns1.bankofsteve.com for the IP address of www.bankofsteve.com, and it uses query ID 1001 (one higher than the previous query).
- Step 5 — the real nameserver provides a legitimate response to this query, with QID=1001. But if the bad guy has successfully matched the query ID in the step 2a flood, this legal reply arrives too late and is ignored. Oops.
- Step 6 — With the bogus IP address (of the bad guy's webserver) in cache it provides this poisoned answer to the requesting DNS client. Boom.
- Step 7 (not illustrated) — future DNS clients asking for www.bankofsteve.com will receive the same fraudulent answer.
And because that satisfies the request, the real answer that arrives later is dropped, because the query is no longer pending.
In any case, once the bad guy gets the answer from the victim's nameserver, the matter is closed, and he can stop flooding the victim.
We'll note that even though this illustrates trying to beat just the reply from ns1.bankofsteve.com, our forged DNS traffic could actually match the query ID of any of the prior steps.
This includes matching an earlier reply from the root server or the GTLD (.com) server: if the query ID matches, our fake authoritative wins, and pollutes the cache. This is a race, but only the attacker knows it's playing.
- The name can't already be in the cache
- If www.bankofsteve.com is already in the victim nameserver's cache, all of the external queries are avoided, and there's simply no way to poison it in this manner.
- If the bad guy still wants to poison that particular hostname, he has to wait for it to expire from cache (as determined by the TTL).
- The bad guy has to guess the query ID
- This is made easy with (now-obsolete) nameservers that increment the Query ID by one each time — even a busy nameserver has a fairly small range to guess from.
- The bad guy has to be faster than the real nameserver
- If the victim nameserver and the real nameserver are topologically close (network wise), then the steps 2/3 and 4/5 may complete so quickly that the bad guy has a too-small window to exploit.
Mitigations
An obvious mitigation here is to randomize the Query ID.With sequential Query IDs, the bad guy has a fairly limited range of guesses required once he observes a single current Query ID. If he sees QID=999, then he may flood with QIDs 1000-1029 in an attempt to make at least one match.
Experience has shown this is an easy window to beat.
But if the nameserver chooses random Query IDs, then the attacker has the full 16-bit pool to choose from — that's 64k values — and this is a much harder target to hit in the narrow window of time while the victim is going through the routine resolution steps.
Though forging 20 packets in routine name-resolution time is straightforward enough, doing so with thousands of packets is a much more substantial challenge.
So true randomization of Query IDs raises the bar quite a bit.
Dan's Shenanigans
So far we've seen how to poison a single record, but this has less impact than expected: it's just one record, and many properties require multiple hostnames to operate, and it's harder to hack them all.Dan Kaminsky found an approach that's dramatically more effective than this, and it caused quite a furor in the security community. The general approach is the same as the simple approach shown above, but the key difference is the nature of the forged payload.
In the simple example, our intention was to poison the final answer, the A record with the IP address, but what Dan discovered is that we can go up one level and hijack the authority records instead. Before undertaking the attack, the bad guy configures a nameserver that's authoritative for the bankofsteve.com zone, including whatever resource records he likes: A records, MX for email, etc.
There's nothing stopping anybody from configuring his own nameserver to be authoritative for any domain, but it's pointless because the root servers won't point to it: it's got answers, but nobody ever asks it a question.
- Step 1 — bad guy client requests a random name within the target domain (www12345678.bankofsteve.com), something unlikely to be in cache even if other lookups for this domain have been done recently.
- Step 2a — As before, the bad guy sends a stream of forged packets to the victim, but instead of A records as part of an Answer, it instead delegates to another nameserver via Authority records. "I don't know the answer, but you can ask over there".
The authority data may well contain the "real" bankofsteve.com nameserver hostnames, but the glue points those nameservers at badguy IPs. This is the crucial poisoning, because a Query ID match means that the victim believes that badguy's nameservers are authoritative for bankofsteve.com.
The bad guy now owns the entire zone.
- Curiously, the rest of the steps don't matter: the point of this process was to fake out the victim into thinking that badguy runs the domain in question, and that would have been successful in this step.
Once one of the victim's queries has been poisoned — it could be any in the chain — all the rest are directed to badguy's servers.
The bad guy will typically set a very high TTL in the poisoning responses so that the victim will keep the bogus data in cache as long as possible.
Flurry of queries
Our example has shown a single query being hijacked, but this is unlikely to be successful: because of Query ID randomization, it's not likely that that the bad guy will manage to get a hit in the short time required to match on 64k IDs.Instead, the bad guy issues a flurry of queries, each for a different random name under the main domain. The first request caused the nameserver to perform the usual root-first resolution, but it eventually caches the valid ns1.bankofsteve.com values. Subsequent queries within this domain go directly to that nameserver, skipping the root steps.
But the next request for a different random name (which certainly won't be in cache) causes an immediate query to the valid ns1 server. The bad guy then throws a flood of forged data at the victim about that second random name, though the odds here are still pretty long.
Just for the sake of discussion, let's assume that the bad guy can generate 50 forged replies for each random name query before the real reply arrives from the real nameserver. This appears to be a very small chance, but when repeated over and over — and run from automated tools — success by the bad guy is likely.
It's been reported that success can commonly be achieved in 10 seconds.
Going for the top
Our examples have all focused on hijacking an end domain, but the same techniques can do the same thing up a level: taking over .COM, .NET, or the like.By poisoning the Authority records for .COM and the like, the victim nameserver will route all DNS lookups to the bad guy's nameservers. This effectively hijacks all names under that top level, including domains he didn't actually request. This gives a great deal of flexibility even though it may well require substantial computing and network resources to serve the flood of requests that this hijacking must generate.
What's the fix?
This all sounds awful: how does one fix this?As has been alluded to several times, it's the small space — just 16 bits — of the Query ID that makes this attack possible. Though certainly one might wish to increase that ID to something larger (perhaps 32 bits), it's simply not possible do that in the short term because it would break DNS on the internet: the fields are what they are, and they can't be changed casually.
But an additional source of randomness is required nevertheless, and that's been done by randomizing the source port. Rather than use just a single UDP port, which is trivial to discover, a much larger range of ports is allocated by the nameserver and then used randomly when making outbound queries.
As one would imagine, the nameserver would keep track of which source port was used for each query: replies arriving on the wrong port would be discarded just as if the Query ID failed to match.
Microsoft's updated DNS server is said to preallocate 2,500 UDP ports to use for these random queries, and for discussion we'll round this down to an even power of two: 2 11 = 2,048. This yields this much larger transaction space:
Increasing the search space from 64k to 134M provides far better odds for the good guys. We presume that each nameserver provides a way of setting how large of a pool to use for these source ports, as well as a way of excluding certain port numbers known to be required for other purposes.
Summary
This has been an exceptionally serious vulnerability because it undermines the very faith in DNS: this is at the core of the internet. Most experts believe that if you can't trust DNS, all else is lost, and we're of this same mind.There is far more detail about this vulnerability than we can present here, and we'll urge the reader to consult other resources (especially Dan's presentation).
But we can include a few (ahem) random notes about this matter that didn't seem to fit in elsewhere, and seem important and/or interesting enough to include in this paper.
- Patch your servers: Tools exist to make exploit-in-a-box available to even low-skilled bad guys.
- Authoritative-only nameservers are not vulnerable because they have no cache to poison, but we'd be surprised if no small number of "auth only" nameservers actually provided recursive service to at least some clients.
- A nameserver need not be directly visible to the Internet to be exploitable. By convincing a user to visit a particular web page, it can trigger a chain of events that reliably lead to poisoning.
- Even patched servers may still be vulnerable if an intervening firewall performs Port Address Translation in a way that un-randomizes the source ports.
- It's been suggested that DNSSEC or IPv6 are solutions to this problem, but this is only in theory. Both of these technologies have to be fully rolled out to be effective, and this is likely years away, at best.
- The Secure Sockets Layer (SSL) is only a partial protection against being redirected to malicious websites. Putting up a fake BankOfSteve.com website will have the wrong SSL certificate name (which is a warning to the user who's paying attention), but the great majority of users skip right through those warnings.
- But the bad guy can subvert even SSL: since many Certificate Authorities validate a user's control over a domain by sending email, hijacking a mailserver by attacking the cert vendor's resolving DNS, this may well mean that an attacker can obtain a fully-valid certificate for the target domain.
This is very scary.
References
- Dan Kaminsky's Black Hat presentation (PowerPoint) — Excellent reading.
- DNS and BIND, O'Reilly — The definitive book on DNS.
- TCP/IP Illustrated, Volume 1: The Protocols, W. Richard Stevens — the definitive book on TCP/IP.
- BIND (Berkeley Internet Name Domain) — The most popular nameserver, with a long history of security issues.
- DJBDNS nameserver — Always an attitude, but never a security vulnerability.
- Mind Of Root podcast #63 — interviewed regarding the DNS vulnerability
- DNS Cache Poisoning at Wikipedia
-
Adobe Illustrator CS3™ — the excellent software used to make the all the diagrams in this paper. Yes, this took a long time to write.
Reference: http://unixwiz.net/techtips/iguide-kaminsky-dns-vuln.html
