Dan Kaminsky's Blog

In case you’re curious.

As they say: “If you can’t measure it, you can’t manage it.”

There’s a serious push in the industry right now for security metrics. People really want to know what works — because this ain’t it. But where can we find hard data?

What about fuzzers — the automated, randomized testers that have been so good at finding bugs through sheer brute force?

I had a hypothesis, borne of an optimism that’s probably a bit out of place in our field: I believe, after ten years of pushing for more secure code, software quality has increased across the board — at least in things that have been under active attack. And, in conjunction with Adam Cecchetti and Mike Eddington of Deja Vu Security (and the Peach Project), we developed an experiment to try to show this.

We fuzzed Office and OpenOffice. We fuzzed Acrobat, Foxit, and GhostScript. And we fuzzed them all longitudinally — going back in time, smashing 2003, 2007, and 2010.

175,334 crashes later, we have some…interesting data.  Here’s a view of just what happened to Office — and OpenOffice — between 2003 (when the Summer of Worms hit) and 2010.

It ain’t security. Can’t say I care. Trying to fix color blindness is most fun side project evar.

[Heh! This blog post segues into a debate in the comments!]

Short Version: Zooko’s Triangle describes traits of a desirable naming system — and constrains us to two of secure, decentralized, or human readable. Aaron Swartz proposes a system intended to meet all three. While his distribution model has fundamental issues with distributed locking and cache coherency, and his use of cryptographic hashcash does not cause a significant asymmetric load for attackers vs. defenders, his use of an append-only log does have interesting properties. Effectively, this system reduces to the SSH security model in which “leaps of faith” are taken when new records are seen — but, unlike SSH, anyone can join the cloud to potentially be the first to provide malicious data, and there’s no way to recover from receiving bad (or retaining stale) key material. I find that this proposal doesn’t represent a break of Zooko’s Triangle, but it does show the construct to be more interesting than expected. Specifically, it appears there’s some room for “float” between the sides — a little less decentralization, a little more security.

Zooko’s Triangle is fairly beautiful — it, rather cleanly, describes that a naming system can offer:

1. Secure, Decentralized, Non-Human-Readable names like Z0z9dTWfhtGbQ4RoZ08e62lfUA5Db6Vk3Po3pP9Z8tM.twitter.com
2. Secure, Centralized, Human-Readable Names like http://www.twitter.com, as declared by trusted third parties (delegations from the DNS root)
3. Insecure, Decentralized, Human-Readable Names like http://www.twitter.com, as declared by untrusted third parties (consensus via a P2P cloud)

There’s quite the desire to “square Zooko’s triangle” — to achieve Secure, Decentralized, Human-Readable Names. This is driven by the desire to avoid the vulnerability point that centralization exposes, while neither making obviously impossible demands on human memory nor succumbing to the rampantly manipulatable opinion of a P2P mob.

Aaron Swartz and I have been having a very friendly disagreement about whether this is possible. I promised him that if he wrote up a scheme, I’d evaluate it. So here we are. As always, here’s the source material:

Squaring the Triangle: Secure, Decentralized, Human-Readable Names

DJB responds! Not in full — which I’m sure he’ll do eventually, and which I genuinely look forward to — but to my data regarding the increase in authoritative server load that DNSCurve will cause. Here is a link to his post:

List: djbdns Subject: dnscurve load

What’s going on is as follows: I argue that, since cache hit rates of 80-99% are seen on intermediate caches, that this will by necessity create at least 5x-100x increases in traffic to authoritative servers. This is because traffic that was once serviced out of cache, will now need to transit all the way to the authoritative server. (It’s at least, because it appears each cache miss requires multiple queries to service NS records and the like.)

DJB replies, no, DNSCurve allows there to be a local cache on each machine, so the hit rates above won’t actually expand out to the full authoritative load increase.

Problem is, there’s already massive local caching going on, and 80-99% is still the hitrate at the intermediates! Most DNS lookups come from web browsers, effectively all of which cache DNS records. Your browser does not repeatedly hammer DNS for every image it retrieves! It is in fact these very DNS caches that one needs to work around in the case of DNS Rebinding attacks (which, by the way, still work against HTTP).

But, even if the browsers weren’t caching, the operating system caches extensively as well. Here’s Windows, displaying its DNS Client cache:

Short Version: Dan Bernstein delivered a talk at the 27C3 about DNSSEC and his vision for authenticating and encrypting the net. While it is gratifying to see such consensus regarding both the need to fix authentication and encryption, and the usefulness of DNS to implement such a fix, much of his representation of DNSSEC — and his own replacement, DNSCurve — was plainly inaccurate. He attacks a straw man implementation of DNSSEC that must sign records offline, despite all major DNSSEC servers moving to deep automation to eliminate administrator errors, and despite the existence of Phreebird, my online DNSSEC signing proxy specifically designed to avoid the faults he identifies.

DJB complains about NSEC3’s impact on the privacy of domain names, despite the notably weak privacy guarantees on public DNS names themselves, and more importantly, the code in Phreebird that dynamically generates NSEC3 records thus completely defeating GPU hashcracking. He complains about DNSSEC as a DDoS bandwidth amplifier, while failing to mention that the amplification issues are inherited from DNS. I observe his own site, cr.yp.to, to be a 6.4x bandwidth amplifier, and the worldwide network of open recursive servers to be infinitely more exploitable even without DNSSEC. DJB appeared unaware that DNSSEC could be leveraged to offer end to end semantics, or that constructions existed to use secure offline records to authenticate protocols like HTTPS. I discuss implementations of both in Phreebird.

From here, I analyze Curve25519, and find it a remarkably interesting technology with advantages in size and security. His claims regarding instantaneous operation are a bit of an exaggeration though; initial benchmarking puts Curve25519 at about 4-8x the speed of RSA1024. I discuss the impact of DNSCurve on authoritative servers, which DJB claims to be a mere 1.15x increase in traffic. I present data from a wide variety of sources, including the 27C3 network, demonstrating that double and even triple digit traffic increases are in fact likely, particularly to TLDs. I also observe that DNSCurve has unavoidable effects on query latency, server CPU and memory, and key risk management. The argument that DNSSEC doesn’t sign enough, because a signature on.org doesn’t necessary sign all of wikipedia.org, is shown to be specious, in that any delegated namespace with unsigned children (including in particular DNSCurve) must have this characteristic.

I move on to discussing end to end protocols. CurveCP is seen as interesting and highly useful, particularly if it integrates a lossy mode. However, DJB states that CurveCP will succeed where HTTPS has failed because CurveCP’s cryptographic primitive (Curve25519) is faster. Google is cited as an organization that has not been able to deploy HTTPS because the protocol is too slow. Actual source material from Google is cited, directly refuting DJB’s assertion. It is speculated that the likely cause of Google’s sudden deployment of HTTPS on GMail was an attack by a foreign power, given that the change was deployed 24 hours after disclosure of the attack. Other causes for HTTPS’s relative rarity are cited, including the large set of servers that need to be simultaneously converted, the continuing inability to use HTTPS for virtual hosted sites, and the need for interaction with third party CA’s.

We then proceed to explore DJB’s model for key management. Although DJB has a complex system in DNSCurve for delegated key management, he finds himself unable to trust either the root or TLDs. Without these trusted third parties, his proposal devolves to the use of “Nym” URLs like http://Z0z9dTWfhtGbQ4RoZ08e62lfUA5Db6Vk3Po3pP9Z8tM.twitter.com to bootstrap key acquisition for Twitter. He suggests that perhaps we can continue to use at least the TLDs to determine IP addresses, as long as we integrate with an as-yet unknown P2P DNS system as well.

I observe this is essentially a walk of Zooko’s Triangle, and does not represent an effective or credible solution to what we’ve learned is the hardest problem at the intersection of security and cryptography: Key Management. I conclude by pointing out that DNSSEC does indeed contain a coherent, viable approach to key management across organizational boundaries, while this talk — alas — does not.

Short version:  DNS over TCP (or HTTP) is almost certainly not faster than DNS over UDP, for any definition of faster.  There was some data that supported a throughput interpretation of speed, but that data is not replicating under superior experimental conditions.  Thanks to Tom Ptacek for prodding me into re-evaluating my data.

Long version:

So one of the things I haven’t gotten a chance to write a diary entry about yet, is the fact that when implementing end-to-end DNSSEC, there will be environments in which arbitrary DNS queries just aren’t an option.  In such environments, we will need to find a way to tunnel traffic.

Inevitably, this leads us to HTTP, the erstwhile “Universal Tunneling Protocol”.

Now, I don’t want to go ahead and write up this entire concern now.  What I do want to do is discuss a particular criticism of this concern — that HTTP, being run over TCP, would necessarily be too slow in order to function as a DNS transport.

I decided to find out.

Several years ago, I had some fun:  I streamed live audio, and eventually video, through the DNS.

Heh.  I was young, and it worked through pretty much any firewall.  (Still does, actually.)  It wasn’t meant to be a serious transport though.  DNS was not designed to traffic large amounts of data.  It’s a bootstrapper.

But then, we do a lot of things with protocols that we weren’t “supposed” to do.  Where do we draw the line?

Obviously DNS is not going to become the next great CDN hack (though I had a great trick for that too).  But there’s a real question:  How much data should we be putting into the DNS?

Somewhere between “only IP addresses, and only a small number”, and “live streaming video”, there’s an appropriate middle ground.  Hard to know where exactly that is.

There is a legitimate question of whether anything the size of a certificate should be stored in DNS.  Here is the size of Hotmail’s certificate, at the time of writing:

You know what’s great about being a nerd?

You get to write blog posts linking TRON: Legacy to actual important things, and you get to be totally shameless about it.

So, today, lets talk a little about one of my favorite things:  Isomorphisms.

What are they, you may ask?  Well, they’re not a new species of artificial life that lives on the Grid.  Not exclusively, anyway.  The Science Dictionary defines them as:

A one-to-one correspondence between the elements of two sets such that the result of an operation on elements of one set corresponds to the result of the analogous operation on their images in the other set.

Put another way, they’re two things that appear separate and distinct, but in fact possess such deep underlying similarity that anything you can do to one, you can do to the other.  The best explanation I’ve seen for their underlying importance comes from Stephen De Beste:

Mathematics is only useful to us because of its isomorphism to various real world operations; without it, all mathematics would be nothing more than an interesting intellectual puzzle. The only pitfall is when we think we can construct the two transform functions and assume an isomorphism which isn’t there; if we’re mistaken, then math will give us the wrong answer. It’s not that the math is false, rather it’s that either the transforms were incorrect or the function we tried to use wasn’t really isomorphic to the physical reality. For example, if we try to navigate a globe using a flat map and Euclidean geometry, we’ll get lost. Plane geometry is not isomorphic to nagivation on the surface of a sphere. Spherical geometry, on the other hand, is.

Technically, isomorphisms represent perfect, if transformed relationships.  So the fact that the earth is not, in fact, perfectly spherical (it’s a little bulgy) should break the isomorphism.  But it doesn’t — once you introduce the real world, you’re allowed a bit of fuzziness.  God plays dice, as it turns out.

Well, we’ve got something that works.  So, of course we have to muck with it 🙂

The immediate architectural question is whether we should support the storage of full keying data in DNS.  See, right now, we’re just storing the hash of keying data — a nice, fixed size blob that can fit into a text record without much fuss.  There’s a fundamental assumption with this approach:  Any protocol we happen to use, will negotiate a public key (presently inside a certificate) at the application layer.  DNSSEC only needs to be used to validate the data received at that layer.

That happens to be true for most existing protocols, because most existing protocols were designed to interface with X.509.  The classic model is to connect, receive a certificate, and then interrogate that certificate against various requirements like:

• Is the subject name correct?
• Do I trust this particular Certificate Authority?
• Has this certificate expired?
• Has this certificate been revoked?
• Are there any policies embedded in this certificate that mean I should reject it despite everything else being in order?

Shockingly, this required a decent amount of expertise to be able to handle correctly.  So most programmers don’t — the amount of software out there that doesn’t even make sure it’s encrypting to the right identity is basically ‘almost everything that isn’t a browser’.  The blame isn’t only on the APIs — certificates are really expensive to deploy organizationally, so a lot of companies just throw up their hands and do what they can.  See:  The Little Black Box project, which archives fixed private keys shipped on devices.

In the new model, all the above requirements effectively get subsumed at the DNSSEC layer.  If the TXT KEY1 record resolves at all, that means:

• The name was correct
• The one root — the DNS root — has validated the record
• The record hasn’t expired
• Since the record is short lived, it doesn’t need to be revoked.  Revocation basically happens all the time, by default
• Policies in the TXT KEY1 (Secure-Transport-Security, Secure Renegotiation) are available for review

In other words, most of the complexity around certificate validation disappears; if DNSSEC reports the name was resolved securely, you’re done.  (The cost is that, unlike with certificates, you need to have network access to validate the name.)