Secrecy and the DNS flaw

By now, most folks will have seen reports of the design flaw discovered in DNS as it has seen fairly widespread coverage, even in the non-technical press. It is rare to see such a coordinated disclosure and security update amongst that many of the big players in the computer industry. While fixes abound, the actual problem has yet to be disclosed, which has both positives and negatives.

Responsible disclosure policies dictate that vulnerabilities be kept secret until all affected vendors can create an update. Because this flaw is in the design of DNS, most implementations were affected. This still doesn't quite explain the roughly six months between the discovery of the problem and the release of the fix. Evidently it took a meeting of the minds at the Microsoft campus in March to decide upon the right course of action. Once the fixes were done, presumably they were released on the next "patch Tuesday"—Microsoft's monthly security update day.

Normally, once fixes are available, information about the vulnerability is released. But, for a number of reasons, that has not happened in this case. One of the main reasons is that DNS is an essential internet service and it will take time for affected users to patch their systems. In addition, there have been no reports of this flaw being exploited "in the wild", reducing the pressure to divulge it.

Security researcher Dan Kaminsky discovered the flaw and he has yet another, "blatantly selfish" reason for keeping it quiet as he would like to be able to announce it at Black Hat in Las Vegas in early August:

None of these seem like horrible reasons to keep the vulnerability quiet for a time (roughly 30 days), but they do leave some DNS implementations and worried administrators without the information they need to evaluate the situation. Administrators do not know what traffic patterns or other symptoms to look for to determine if exploits are being attempted. Smaller, less prominent DNS implementations were not included in the collaboration, thus they don't have enough information to decide whether they are vulnerable or not.

A perfect example is Dnsmasq, a lightweight DNS server for smaller networks. Dnsmasq is often used in embedded Linux distributions targeted for home wireless routers. Simon Kelley, Dnsmasq developer, was asked about the vulnerability; his response speaks volumes:

Kelley has since released a patched version, but it is still unknown whether it is needed or, really, if it even fixes the problem. It is difficult to know for sure that a security hole has been closed if information about the hole is not available. This points to the problems that can come from withholding vulnerability information.

Based on the patches and some information from Kaminsky and others, it is clear that this is a cache poisoning vulnerability. Since source port randomization is the change that was applied to alleviate, but not eliminate, the flaw, we can surmise that Kaminsky found a way to reduce the number of spoofed replies that need to be sent to something tractable. According Internet Systems Consortium, developers of the BIND DNS server, the only true solution is DNSSEC, which implies that the current fixes only make cache poisoning less likely, not impossible.

Source port randomization is a technique that has been advocated by Daniel J. Bernstein (i.e. djb) for many years. He implemented it in his djbdns name server long ago. Essentially, it chooses a random source UDP port for each query that the name server makes, which has the effect of increasing the randomness that an attacker needs to be able to predict before being able to poison the cache.

While the market share of Dnsmasq may be miniscule, there are certainly other DNS implementations that are also concerned. In addition, we are relying on those who are "in the know" to be on the lookout for suspicious traffic that might indicate the vulnerability being exploited. Kaminsky is certainly under no obligation to reveal anything, but one wonders if the safest course would have been for him to provide details now, even at the expense of his "thunder".

The CERT release document also mentioned that some of the vulnerable
DNS cache servers would issue a new request for every query they
received whilst waiting for an answer to fill their cache (rather than
just sending a single request to the next DNS server and taking note of
all the clients that require a response).

Hence an attacker could issue X simultaneous queries for the same
record to a DNS cache (each with a unique transaction ID), and
then send back X simultaneous spoofed responses shortly there after
in the time window between the DNS cache sending a request to the next
DNS server and the DNS cache receiving the reply.

This would increase the chance of the cache poisoining attack succeeding
from 1/2^16 (as transaction IDs are 16 bit) to X/2^16.

Actually if transaction IDs are random (which they must be to avoid various already known
exploits) and the server has this sub-optimal behaviour you get a situation similar to the
birthday paradox.

Sending A identical queries, followed by B purported answers with arbitrary sequential
transaction IDs to the query gives you a much better chance of spoofing the target server than
sending A+B queries and one answer, or one query and A+B answers.

According to a quick back of the envelope calculation, just 128 queries and 128 spoof answers
gives you about 25% chance of success, equivalent to sending many thousands of spoof answers
ordinarily. Doubling the number of packets sent (256 queries and 256 answers) improves this to
more than 60%.

However this can't be the totality of the new discovery (in the sense that it's new at all)
since it supposedly also threatens direct queries which aren't directly instigated by an
attacker and are usually cached, e.g. those from the libc stub resolvers in many operating
systems.

I think we have to assume that DNSSEC is the way out of this quagmire and that either we have
to solve the political problems or work around them. That could mean shipping DNS
implementations with a set of keys for the major TLDs and leaving the root unsigned.

I think enough has been published concerning the flaw so that white hats should by now know
enough about the nature of it to remediate the vulnerability, without specific attack code
having to be published before they have a chance to do so. It's not as if the source code for
the patches is kept secret, and if you don't know enough about how DNS works this information
isn't a secret either. The problem seems to be that weak and pseudo-randomisation of source
ports and transaction IDs isn't good enough for PRNGs whose source code or algorithm is
available. This is because we can deduce that the Kaminsky attack, when it is published, will
be based on determining the internal state of the PRNG by carrying out some DNS enquiries
possibly in connection with an attacker enticing a victim to resolve an attacker chosen-domain
name. I would guess, without having read the patches, that the internal state of the PRNG has
to be more heavily disguised, or possibly the PRNG having to be more frequently reseeded using
genuine entropy or even a multi-threaded DNS caching server having per-thread state
independent PRNGs. 

Assuming the attack involves discovering the internal state of the PRNG then subsequent source
ports and transaction IDs in a sequence can be guessed based on knowledge of previous ones.
You don't really need to know yet how the internal PRNG state can be discovered to take
reasonable steps to prevent this information from being discovered. For the most part admins
will just apply the patches as usual. Those who really need to know more will be those who are
developing and running less popular DNS caching recursive resolvers who were not party to the
prior restricted disclosure, and which are not easily replaceable using standard DNS programs
for some reason. In connection with those who have to run non-standard and unpatchable DNS
client libraries and who also can't trust their upstream ISP connection to their ISPs DNS
resolving server not to be sniffed with MITM UDP packet injection capability attacks, they
would do well either to use VPNs to an ISP network with more trusted properties or a local and
trusted DNS resolver. This could happen over an insecure wireless network, but for those
operating such networks, attacks against unpatchable DNS clients are not likely to be amongst
their greatest worries.

It seems unlikely that the problem is really a PRNG flaw, because we know how to build good
PRNGs.  Not every implementation might *use* such a PRNG, but if it were a PRNG flaw then it
would only affect those implementations that were using poor PRNGs, not every implementation.

What do you mean by a "good" PRNG ? I think what we understand to be good here might have to
change. It's one thing for a PRNG to generate a sequence of numbers with good statistical
properties and which doesn't repeat its inherently predictable sequence until a very large
integer number space is exhausted. It's entirely another to have a PRNG with a published
algorithm and an attacker able to obtain prior information relevant to its internal state but
provably unable to predict the subsequent sequence of numbers generated. The P here means
pseudo, because the randomness isn't randomness at all - it means that the sequence of numbers
is generated using an algorithm and not a noise source. Certainly the developer and
administrator can attempt to reseed such an algorithm periodically and cryptically. The issue
is how much can an attacker learn by knowing previous numbers in the sequence in order to
predict subsequent numbers in the sequence.

One solution for the paranoid is to use /dev/random instead of /dev/urandom as the entropy
source. This is a good idea when generating cryptographic keys intended for medium-long term
use, but running a DNS recursive resolving server which needs to generate thousands of
unpredictable source port numbers and transaction IDs a second is going to need a faster
entropy source than /dev/random hence the need for a PRNG in the first place.

Indeed, the study of PRNGs splits into two parts: scientific PRNGs, where the emphasis is on
provable uniformity, provably large period, and speed, versus cryptographic PRNGs, where the
emphasis is on resistance to prediction, judicious incorporation of true entropy, and speed.
As you suggest, since DNS port randomization is effectively using the source port as part of a
secret key, it's important that the the source ports be generated by a cryptographic PRNG.

Fortunately, these days we can build very good PRNGs of both types.  For cPRNGs, the
constructions usually involve using some other crypto algorithm as part of the generation
process (e.g., a strong hash or cipher like SHA-256 or AES).  This is exactly what /dev/random
and /dev/urandom do, and it's what good-quality DNS server implementations will do too.  In
practice, attacking such a PRNG is about as easy as inverting SHA or AES -- not gonna happen.
(And yes, I know that SHA-1 has been recently weakened.)

If you want to know more about these issues, then I can recommend Schneier's paper on
yarrow[1] for a great discussion of the issues faced by such a design, and [2] for a fun and
famous discussion of exploiting such flaws in TCP sequence numbers (with pretty pictures!).

[1] http://www.schneier.com/yarrow.html
[2] http://lcamtuf.coredump.cx/oldtcp/tcpseq.html

Thanks for these links which are very interesting.

The market share of DNSmasq isn't trivial; it's in every SnapGear router I've ever shipped.
Wonder how long it will take SecureComputing to trickle Simon's release down...

And it's in openwrt. 

And probably in vast numbers of default loads on routers that will never get fixed.

Exactly - unless people are clueful enough to turn off dnsmasq, or more likely to find a
firmware update for their routers, there will be a lot of broadband routers cracked in a month
or two...

> And it's in openwrt.

If anyone is struggling to update their OpenWRT router, I've just posted this description of
what I did:

http://forum.openwrt.org/viewtopic.php?pid=72220#p72220

The solution is apparently to start used random selected UDP source 
ports on the nameserver when answering to DNS requests. Well the new 
problem has with this solution already been created : "Vulnerability in 
IANA root servers, servers go down after UDP port storm." 
 
The only sensible solution is to create a hierarchical slaves.conf 
access list. WHO are allowed recursive access to higher up bind 
servers?  Besides selection using ip-numbers, one can also be awarded 
with a valid DNS SEC hmac-md5 key. Ok I know this is Big Brother style 
stuff. But i don't know of any DNS hackers who like to leave their 
identity inside nameserver logs.