djbdns/dnscache poisoning weakness

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Summary: Weaknesses in dnscache's outgoing query management and  
caching policies allow an attacker to poison arbitrary DNS records in  
far less time than previously believed possible.
Versions Effected: All current versions of djbdns (<=1.05)
Fix: Patches available at http://www.your.org/dnscache
CVE: CVS-2008-4392


Several weaknesses in djbdns's dnscache allow DNS poisoning to occur  
much more rapidly than currently believed possible. Below is an  
abbreviated and slightly non-technical description of the problem for  
people who understand the basics of what DNS is, but was written for  
ease of understanding rather than total technical accuracy. If you  
want a complete technical breakdown of the issue, see my paper at http://www.your.org/dnscache/djbdns.pdf 
  . Additionally, a much more detailed study is being presented at the  
Internet Society's NDSS Symposium on Tuesday, February 10th, modeling  
the effects of several architectural choices in DNS resolver security.  
(http://www.isoc.org/isoc/conferences/ndss/09/program.shtml#traffic3)


Background on DNS poisoning:

DNS poisoning is accomplished by asking a caching DNS server to look  
up a DNS record, then flooding the victim server with incorrect  
responses before the real server it made the request to replies. This  
type of attack can be done completely "blind" - an attacker does not  
need to intercept traffic or directly exploit any DNS servers.

Example - assuming you want to convince a DNS server that www.example.com 
  is at a different IP address than it really is:

Step 1: Pretend to be a client of a DNS server you wish to poison (the  
victim). Send a request to the victim asking for the address for www.example.com 
.
Step 2: The victim makes a request to the real server that controls  
the example.com domain, asking for the address of www.example.com. Two  
random numbers are selected by the victim (Query ID and source port)  
and are used to make the request.
Step 3: Before the real server replies, start flooding the victim with  
false replies, forged to look like they came from the real server.
Step 4: If you're able to correctly guess the two random numbers in  
any of the false replies, the victim will believe your forged reply is  
authentic. The victim will trust the answer in your forged reply,  
learning the wrong address for www.example.com
Step 5: Any users that ask the victim server the address of www.example.com 
  will be directed to the wrong IP.

The major protection that the DNS protocol has against this type of  
attack are the random numbers. There are nearly four billion  
possibilities, and the period of time between the victim's request and  
real server's reply is very short. Further protecting DNS servers from  
this type of attack is dnscache's own cache policy - once it's learned  
an answer to a question, it won't ask the same question again until  
the cache has expired. This means an attacker only gets a few  
attempts, then is forced to wait until dnscache decide to check again.  
That delay can be minutes, hours or even days.

In mid-2008, security researcher Dan Kaminsky discovered a technique  
that allows attackers to bypass the waiting period. By asking the  
victim a series of similar (but not identical) queries, the cache is  
of no benefit. The attacker asks the victim for the address of  
000001.example.com, then 000002.example.com, etc. By constantly  
changing the question being asked, the victim is forced to keep making  
requests to the real servers for example.com. The forged replies say  
"000001.example.com is at 10.182.64.86. Also, www.example.com is at  
10.182.64.86." Eventually the attacker succeeds, when a forged reply  
has the same random numbers that the victim chose. Since the forged  
reply appears to be coming from the real servers that control  
example.com, it believes all information contained in the forged reply.

Weaknesses such as these are inherent in the DNS protocol itself, with  
all DNS servers being vulnerable in roughly the same manner. Even with  
these weaknesses, DNS poisoning is very difficult to accomplish. Even  
at a very high attack speed, 15,000 queries per second (roughly  
10Mbps), it requires days to have any statistical likelihood of  
guessing the random numbers correctly. An attack of that size is also  
quite easily noticeable on all but the largest of DNS servers,  
allowing it to be blocked or traced before success.



Dnscache's weaknesses:


1) Dnscache treats "SOA" requests as uncacheable.

There are several types of DNS query types, used to ask for different  
information about a domain. The "Start of Authority" (SOA) type is  
used to ask for certain data about the management and cache policies  
for the domain. When receiving a reply from the real server about an  
SOA request, it tells the client who requested it everything it found,  
then immediately forgets the reply. This makes the "Kaminsky" attack  
(described above) much simpler, and improves its efficiency slightly.

Alone, this is not a major problem, but combined with the problems  
below it has a multiplying effect.


2) Dnscache makes no attempt to prevent simultaneous identical queries  
from going out at once.

By default, dnscache allows up to 200 queries to be "in progress" at  
once. However, it doesn't check to see if it's already waiting for a  
response for a query before asking the same question again. Using the  
SOA weakness above, the attacker can make the same SOA request over  
and over until they succeed in poisoning the server. An attacker can  
take advantage of this by requesting the same query 200 times, then  
send a flood of forged replies.

Instead of "I'm thinking of a number between 1 and 4,000,000,000 - can  
you guess it?" it now becomes "I'm thinking of 200 numbers between 1  
and 4,000,000,000". This means it takes roughly 1/200th the time to  
guess correctly. Instead of an attack taking days, it now can succeed  
in minutes. Instead of an average of 2 billion guesses needed (to have  
a 50% chance of success), it now takes around 16 million. A 10Mbps/ 
15000 queries-per-second attack now requires around 18 minutes to  
succeed.

Making things worse, many large dnscache users have increased its  
simultaneous query limit. If you've configured dnscache to allow 2,000  
simultaneous queries, around 1 million guesses and a little over a  
minute are needed to poison a server. Large-scale users are far more  
vulnerable than small servers, making this attack far more dangerous.


3) When dnscache hits its query limit, it silently drops the oldest  
query in progress.

As mentioned above, dnscache has a strict limit of how many queries it  
can be working on at once. If the defaults haven't been changed,  
dnscache can be looking up 200 answers to clients' questions at a  
time. If all 200 slots are full and another client asks a question,  
the query that's been waiting the longest is aborted. This makes good  
sense. If many users are trying to lookup a popular website's address,  
and that site's DNS servers are unresponsive, you don't want all 200  
slots tied up on queries that aren't going to get an answer.

However, this makes an attacker's job even easier for poisoning. By  
sending new queries fast enough that the oldest query is kicked out  
before the real server's response reaches the victim, the victim will  
never learn any answers from the real server. The scenario looks like  
this:

Step 1: Through some careful timing analysis, the attacker can  
determine how long it takes the victim to receive a reply from the  
real server. Assume the attacker determines that it takes no less than  
1/10th of a second(100ms) for the real reply to reach the victim.
Step 2: The attacker sends a flood of queries to the victim, filling  
all 200 slots.
Step 3: Due to the lack of duplicate query checking mentioned in #2  
above, the victim rushes to send the real server 200 queries.
Step 4: The attacker floods the victim with forged responses, hoping  
to guess the random numbers correctly.
Step 5: Just before the oldest query in the 200 slot window reaches  
100ms in age, the attacker sends a new query to the victim.
Step 6: The victim throws away the oldest query, and issues a brand  
new request.
Step 7: When the real reply from the real server comes in for the  
query that was just thrown away, the victim doesn't recognize it and  
discards it.
Step 8: Go back to Step 4 until success.



Impact:

Without corrective measures, all dnscache servers run the risk of  
being poisoned by customers, employees or outside attackers. A  
successfully poisoned server will redirect users to an IP under the  
attacker's control. For example, an attacker may choose to poison a  
large residential ISP's servers to redirect all users for a large  
banking site to a look-alike site that records the user's login details.


Mitigating factors:

If dnscache is configured to only accept requests from IPs that you  
control, and your network architecture allows you to block packets  
that appear to be originating from your IP space from entering your  
network externally, it is difficult (if not impossible) for an  
attacker to take advantage of any of these weaknesses. However, in the  
case of ISPs with large numbers of residential or small business  
customers, it's likely an attacker can find an exploitable host within  
the ISP's network to launch the attack from. Many networks do not or  
cannot implement spoofing protections, further expanding the range of  
this attack.

Diligent monitoring of unusual DNS activity can alert you to an attack  
in progress.


Corrective measures:

The last official version of djbdns was released in 2001, but is still  
in heavy use on the Internet.  As of 2007-12-28, djbdns has been  
placed completely in the public domain by its original creator, Daniel  
J. Bernstein. After discovering these vulnerabilities, several large- 
scale users of djbdns collaborated on creating and testing patches to  
address these issues. Respecting Mr. Bernstein’s original work,  
notification and copies of our proposed fix were made available to him  
immediately. While it’s unclear when an updated version of djbdns  
will be released, we have freely released these patches to the public  
at http://www.your.org/dnscache .

Specifically, two patches were developed by Jeff King ([email protected])  
that close the poisoning attack weaknesses discussed here. The first  
prevents duplicate identical queries from being sent at once. Multiple  
requests for the same data from one or more clients are merged  
together into a single request. Apart from the security implications,  
there are several benefits from installing this patch - a small  
bandwidth savings, and protection from a lot of users all trying to  
request the same data from an overloaded server won't make matters  
worse.

The second patch tells dnscache that SOA records are indeed cacheable  
for a short amount of time. Essentially, SOA records are treated no  
differently from other records, closing the uncacheable query weakness.

Both patches have been tested on several small and large scale  
dnscache deployments for a while now, with no reported problems or  
complaints.

The patches are available individually or as a pre-patched djbdns  
distribution at http://www.your.org/dnscache

Additionally, these patches are included in the latest version of zinq- 
djbdns (0.03) which will be released on February 10th. zinq-djbdns is  
a djbdns distribution with a modern autoconf/automake build system,  
and several well tested bug fixes already included. It is available at http://sourceforge.net/projects/zinq/

Even with a fully secure DNS server, DNS is still exploitable. Due to  
the DNS protocol's design, poisoning is possible on any DNS server.  
These risks were mentioned by dnscache's original author as far back  
as 2001(http://cr.yp.to/djbdns/forgery.html). Additional protection  
measures (such as the 0x20 bit toggling scheme) add additional  
protection now. Our goal is to return dnscache to requiring days of  
sustained brute-force attacking to succeed at poisoning. On a long  
term scale, secure authenticated DNS(such as dnscurve or DNSSEC) is  
necessary to close the poisoning window entirely.



Thanks to:

David Dagon, Adam Getchell, Dan Kaminsky, Jeff King and David Ulevitch  
and others for verification, testing and help with correcting these  
issues.



-----BEGIN PGP SIGNATURE-----

iEYEARECAAYFAkmQhvEACgkQ98o5FAzUsOlFJgCgkKpHGwr3kIXBR8ob5qPDKU42
cD8An2dpCEryLOHs5PTD6tBCfCajEA1A
=T8GQ
-----END PGP SIGNATURE-----