Ben Laurie blathering

RFC 5155

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 I first ask the servers for . who the nameserver for com is. Then I ask the com nameservers where the nameservers for is, who I then ask for the nameservers for and finally ask them for the address of

But it isn’t as easy as that. In fact, the zone can contain an entry without delegating 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, doesn’t exist means showing the pair (, Note that this pair does not prove the nonexistence of 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.


  1. RFC 5155

    Ben Laurie celebrates the publication of RFC 5155. I hadn’t gotten around to blogging about it, but I’m also pretty happy that this RFC finally made it out.

    Ben says:
    It turns out that in general, to prove the nonexistence of a name usin…

    Trackback by davidb dives in — 11 Mar 2008 @ 14:29

  2. I meant to point this out earlier, but the explanation of what the various NSEC and NSEC3 records prove isn’t quite right. Ben’s explanation is about proving a particular kind of response: NXDOMAIN, which is stating that not only the record you ask for not exist, but no other record at the name exists, and no children of that name exist either.

    With NSEC (RFC 4035), one NSEC record actually proves that the name doesn’t exist and proves what the “closest encloser” is as well. The other NSEC record is there to prove that some wildcard record that could have covered the QNAME also did not exist, and thus, NXDOMAIN was the correct answer. Whew!

    In NSEC3 (RFC 5155, yay!), you need three records: one to prove that the QNAME did not exist, one to prove what the “closest encloser” is, and one to prove that the wildcard did not exist. Basically, the first NSEC record is replaced by two NSEC3 records and the second is replaced by one. Of course, we always had to say “up to three” because sometimes the same NSEC3 record would apply for more than one role — this would happen a lot for a very small zone using NSEC3.

    But, all this is pretty hard to keep straight in your head, so I forgive Ben for not getting it quite right. And I apologize in advance if I haven’t gotten it quite right either.

    Comment by davidb — 19 Mar 2008 @ 1:15

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Powered by WordPress