After nearly 4 years of mind-bending minutiae of DNS (who would’ve thought it could be so complicated?), political wrangling and the able assistance of many members of the DNSSEC Working Group, particularly my co-authors, Roy Arends, Geoff Sisson and David Blacka, the Internet Draft I started in April 2004, “DNSSEC NSEC2 Owner and RDATA Format (or; avoiding zone traversal using NSEC)” now known as “DNS Security (DNSSEC) Hashed Authenticated Denial of Existence” has become RFC 5155. Not my first RFC, but my first Standards Track RFC. So proud!
Matasano Chargen explain why this RFC is needed, complete with pretty pictures. They don’t say why its complicated, though. The central problem is that although we all think of DNS as a layered system neatly corresponding to the dots in the name, it isn’t.
So, you might like to think, and it is often explained this way, that when I look up
a.b.example.com I first ask the servers for
. who the nameserver for
com is. Then I ask the
com nameservers where the nameservers for
example.com is, who I then ask for the nameservers for
b.example.com and finally ask them for the address of
But it isn’t as easy as that. In fact, the
example.com zone can contain an entry
a.b.example.com without delegating
b.example.com. This makes proving the non-existence of a name by showing the surrounding pair rather more challenging. The non-cryptographic version (NSEC) solved it by cunningly ordering the names so that names that were “lower” in the tree came immediately after their parents. Like this:
So, proving that, say,
d.example.com doesn’t exist means showing the pair (
g.example.com). Note that this pair does not prove the nonexistence of
b.example.com as you might expect from a simple lexical ordering. Unfortunately, once you’ve hashed a name, you’ve lost information about how many components there were in the name and so forth, so this cunning trick doesn’t work for NSEC3.
It turns out that in general, to prove the nonexistence of a name using NSEC you have to show at most two records, one to prove the name itself doesn’t exist, and the other to show that you didn’t delegate some parent of it. Often the same record can do both.
In NSEC3, it turns out, you have to show at most three records. And if you can understand why, then you understand DNS better than almost anyone else on the planet.