Secrecy and the DNS flaw [LWN.net]

By Jake Edge
July 9, 2008

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:

While I'm out there, trying to get all these bugs scrubbed — old and new — please, keep the speculation off the @public forums and IRC channels. We're a curious lot, and we want to know how things break. But the public needs at least a chance to deploy this fix, and from a blatantly selfish perspective, I'd kind of like my thunder not to be completely stolen in Vegas.

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:

I wasn't contacted in advance about this, and no patch for dnsmasq has been released. Since the exact nature of the new vulnerability has not (as far as I know) been announced, I don't know if dnsmasq is vulnerable.

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".

(Log in to post comments)

Secrecy and the DNS flaw

Posted Jul 10, 2008 13:23 UTC (Thu) by tialaramex (subscriber, #21167) [Link]

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.

Secrecy and the DNS flaw

Posted Jul 10, 2008 13:17 UTC (Thu) by emk (subscriber, #1128) [Link]

I think Kaminsky steps over the line when he says, Please, keep the speculation off the @public forums and IRC channels.

At this point, we have to assume that the black hats have already puzzled out the bugor will do so very soon. As usual, the only people left in the dark will be the white hats and the working system administrators.

Im still pretty annoyed at the handling of the recent security bugs in Ruby. The Ruby developers said, Here are some security patches which you must apply right now, but we wont say why. The patches broke quite a few Ruby applications, andto make matters worsethe actual bugs had been publicly described in Ruby's source tree. Once you release patches, the bug is almost always a matter of public record, at least for anyone who cares to think about it for while. (The exception, perhaps, was the remote hole in ssh, which was first patched by privilege separation.)

In the case of the DNS bug, I could understand a weeks embargo. But for Kaminsky to request that people not discuss why their systems are vulnerable is ridiculous. As system administrators, its our job to secure our employers systems. And to do that, we need to be able to discuss security problems. And since Kaminsky specifically requests keeping speculation out of public forums, hes admitting that he expects other people to figure it out, presumably including sufficiently dedicated black hats. So what purpose is served by the embargo?

Secrecy and the DNS flaw

Posted Jul 10, 2008 15:12 UTC (Thu) by copsewood (subscriber, #199) [Link]

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.

Secrecy and the DNS flaw

Posted Jul 10, 2008 18:10 UTC (Thu) by emk (subscriber, #1128) [Link]

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.

Just to clarify my earlier remarks, Im not arguing that Kaminsky should publish exploit code. But it would be nice to know, soon, what the actual threat is. Theres a big difference between describing a problem, and actually publishing exploit code.

I once maintained an (incredibly minor) fork of a DNS implementation. It wasnt a caching resolver, so Im assuming its not affected. But I'd feel happier if I actually understood the problem.

In response to your other remarks, I really hope this isn't a weak PRNG problem. That would be pretty embarrassing.

Secrecy and the DNS flaw

Posted Jul 11, 2008 0:12 UTC (Fri) by njs (guest, #40338) [Link]

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.

Secrecy and the DNS flaw

Posted Jul 12, 2008 10:32 UTC (Sat) by copsewood (subscriber, #199) [Link]

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.

Secrecy and the DNS flaw

Posted Jul 12, 2008 20:56 UTC (Sat) by njs (guest, #40338) [Link]

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

Secrecy and the DNS flaw

Posted Jul 17, 2008 10:29 UTC (Thu) by copsewood (subscriber, #199) [Link]

Thanks for these links which are very interesting.