Last time, I compared the number and size of the response messages involved in resolving a record in an unsigned zone to those involved in resolving a record in a signed zone under a signed TLD.  This time, I want to look at the actual computation involved.

This isn't really a comparison, of course, because in the case of an unsigned zone, there's no heavy computing involved:  The name server simply reads responses from the network and unmarshals their content into discrete resource records--simple!  In the case of a signed zone under a signed TLD, there's lots of work to do.

Let's start with a count of the unique records returned and their types.  We need to be a little careful here, though, since sometimes identical records are returned in more than one response.  Here's our census:

1.     6 NS RRs for org

2.     6 corresponding A RRs (the org name servers' addresses)

3.     6 corresponding AAAA RRs (the org name servers' IPv6 addresses)

4.     4 NS RRs for isc.org

5.     2 corresponding DS RRs

6.     1 RRSIG RR (covering the DS RRs)

7.     3 corresponding A RRs (the isc.org name servers' addresses)

8.     1 A RR (the answer!)

9.     2 RRSIG RRs (covering the A RR)

10.   4 NS RRs for isc.org (same as in 4.)

11.   2 RRSIG RRs (covering the NS RRs)

12.   3 corresponding A RRs (same as in 7.)

13.   1 corresponding AAAA RR

14.   8 RRSIG RRs, covering the name servers' 3 A RRs and 1 AAAA RR)

15.   4 DNSKEY RRs for isc.org

16.   4 RRSIG RRs (covering the DNSKEY RRs)

17.   4 NS RRs (same as in 4.)

18.   2 RRSIG RRs (same as in 11.)

19.   3 corresponding A RRs (same as in 12.)

20.   1 corresponding AAAA RR (same as in 13.)

21.   8 RRSIG RRs (same as in 14.)

22.   4 DNSKEY RRs for org

23.   2 RRSIG RRs (covering the DNSKEY RRs)

24.   6 NS RRs for org (same as in 1.)

25.   1 RRSIG RR (covering the NS RRs)

26.   2 corresponding A RRs (subset of 2.)

27.   2 corresponding AAAA RRs (subset of 3.)

Whew!  Now, to keep things simple, let's just say:

• Each DS RR requires one cryptographic hashing operation to check (because you run the corresponding DNSKEY RR though SHA-1 or SHA-256 to compare it to the value in the DS record)
• Each RRSIG RR requires one hashing operation and one asymmetric decryption operation to validate (because you run the RRset you're validating through SHA-1 and then decrypt the ostensible signature from the RRSIG RR and make sure they match)

That means that, in total, we'll need 22 hashing operations and an even 20 asymmetric decryption operations to completely validate www.isc.org's A RR and its chain of trust.  Yikes!  (This is actually a worst case, since it assumes that we validate all the RRSIG records, when in fact we likely don't need to.  For example, checking the signature of any one isc.org DNSKEY RR covering the full set of keys is enough to validate all four keys.)

Luckily, our name server will cache the results of the validation.  If we were to subsequently look up ftp.isc.org's A RR, the name server would only have a single hashing operation and a single decryption to do, which now doesn't seem bad at all.

This is the reason I've recommended that organizations deploying DNSSEC watch the CPU load on their recursive name servers carefully:  As the proportion of responses that are signed increases, so will the load on their recursors.

Ultimately, though, the ever-increasing speed of processors and networks will trump the burden DNSSEC adds.  Years from now - assuming DNSSEC becomes widely deployed - we'll look back at our concerns about the overhead of DNSSEC and chuckle.  I hope.