DNS Workshop

Friday Dec 30, 2011

Take your DNSSEC with a grain of salt

Authenticated denial of existence

It requires some 'out of the box' thinking to understand how DNSSEC can prove things that do not exist. The solution is to list all the things (DNS Names and Resource Records) that do exist, and secure that list. If that list can be proven, then everything not listed must not exist. This property of DNSSEC prevents an attacker from sending fake negative DNS responses, like 'google.com -> NXDOMAIN', which could be used for denial of service attacks.

This list of things that do exist in a DNS zone is created by the NSEC (or NSEC3) records. These records build a linked-list from every domain name in a DNS zone, listing all resource record types for each name. Lets have a look at an example, the simple DNS zone 'myzone.example.com.'. Here is the plain DNS zone-file, without DNSSEC:

myzone.example.com.     3600 IN SOA  dns1.myinfrastructure.org.  hostmaster.myinfrastructure.org. (
              2011123001
              2h
              1h
              1000h
              1h )
myzone.example.com.     3600 IN NS dns1.myinfrastructure.org.
myzone.example.com.     3600 IN NS dns2.myinfrastructure.org.
myzone.example.com.     3600 IN MX 10 mail.myinfrastructure.org.
www.myzone.example.com. 3600 IN A 192.0.2.100
www.myzone.example.com. 3600 IN AAAA 2001:db6:100::80

The zone including the NSEC records will look like this (I'm omitting all RRSIG signature-records and DNSSEC key records here, because the focus is on the NSEC records):

myzone.example.com.     3600    IN SOA  dns1.myinfrastructure.org. hostmaster.myinfrastructure.org. (
                                        2011123001 ; serial
                                        7200       ; refresh (2 hours)
                                        3600       ; retry (1 hour)
                                        3600000    ; expire (5 weeks 6 days 16 hours)
                                        3600       ; minimum (1 hour)
                                        )

                        3600    NS      dns1.myinfrastructure.org.
                        3600    NS      dns2.myinfrastructure.org.
                        3600    MX      10 mail.myinfrastructure.org.
                        3600    NSEC    www.myzone.example.com. NS SOA MX NSEC
www.myzone.example.com. 3600    IN A    192.0.2.100
                        3600    AAAA    2001:db6:100::80
                        3600    NSEC    myzone.example.com. A AAAA NSEC

In this simple zone, we have two domain names (myzone.example.com. and www.myzone.example.com.), and each domain name owns one NSEC record, listing all the resource record types that exist for that name, and pointing to the next domain name in the zone (in lexicographical order). The last NSEC record wraps around and points to the very first domain name in the zone.

Walking a DNS zone

Using NSEC is relatively simple, but it has a nasty side-effect: it allows anyone to list the zone content by following the linked list of NSEC records. This is called 'zone walking'. The 'ldns' library contains an tool called 'ldns-walk' that can be used to list all records inside a DNSSEC signed zone that uses NSEC:

$ ldns-walk paypal.com
paypal.com.     paypal.com. A NS SOA MX TXT RRSIG NSEC DNSKEY TYPE65534 
3pimages.paypal.com. A RRSIG NSEC 
_dmarc.paypal.com. TXT RRSIG NSEC 
ym2._domainkey.paypal.com. TXT RRSIG NSEC 
3rdparty._spf.paypal.com. TXT RRSIG NSEC 
3rdparty1._spf.paypal.com. TXT RRSIG NSEC 
3rdparty2._spf.paypal.com. TXT RRSIG NSEC 
pp._spf.paypal.com. TXT RRSIG NSEC 
_autodiscover._tcp.paypal.com. SRV RRSIG NSEC 
accounts.paypal.com. CNAME RRSIG NSEC 
active-history.paypal.com. A RRSIG NSEC 
active-www.paypal.com. A RRSIG NSEC 
adnormserv.paypal.com. A RRSIG NSEC 
adnormserv-dft.paypal.com. A RRSIG NSEC 
adnormserv-phx.paypal.com. A RRSIG NSEC 
adnormserv-slc-a.paypal.com. A RRSIG NSEC 
adnormserv-slc-b.paypal.com. A RRSIG NSEC 
....

For some DNS zones, this is an issue. The NSEC3 record option in DNSSEC solves this by creating the linked list using hashed domain-names, instead of clear-text domain names.

It is important to know that NSEC3 also enables a new function in DNSSEC, called 'opt-out'. With 'opt-out', it is possible to 'jump-over' (delegation) domain names in a zone where the child zone itself is not DNSSEC signed (it does not increase the security to provide a secure delegation in case the child itself is insecure). Zone administrators can decide to deploy NSEC3 to prevent zone walking, or to use 'opt-out', or both. Top-Level zone administrators choose NSEC3 because of this 'opt-out' function. This needs to be taken into account when looking at the NSEC3 parameters of DNSSEC signed zones.

In this blog post I will look into the NSEC3 parameters that prevent 'zone-walking', and I will not discuss 'opt-out'.

NSEC3 cannot prevent 'zone-walking' entirely, but it can make 'zone-walking' more expensive for the attacker. There are two parameters in NSEC3 that can be set by the administrator of a zone to fine tune the amount of work required on the attacker side to 'walk' a DNSSEC signed zone with NSEC3 records: the salt and the number of iterations.

the salt

NSEC3 is using a hashing algorithm to disguise the real DNS domain names used. It is impossible to recreate the original domain names from the hash name. Here is our zone, but now using NSEC3 (again, RRSIG and DNSKEY records have been removed):

myzone.example.com.     3600    IN SOA  dns1.myinfrastructure.org. hostmaster.myinfrastructure.org. (
                                        2011123001 ; serial
                                        7200       ; refresh (2 hours)
                                        3600       ; retry (1 hour)
                                        3600000    ; expire (5 weeks 6 days 16 hours)
                                        3600       ; minimum (1 hour)
                                        )
                        3600    NS      dns1.myinfrastructure.org.
                        3600    NS      dns2.myinfrastructure.org.
                        3600    MX      10 mail.myinfrastructure.org.
                        0       NSEC3PARAM 1 0 10 1A2B3C4D5E6F
6HAUGENGIFFS98J25KBEASD720PGAN36.myzone.example.com. 3600 IN NSEC3 1 0 10 1A2B3C4D5E6F (
                          BE61EEUDCS4VQO71L3LFJMRKEL16S534 A AAAA )
www.myzone.example.com. 3600    IN A    192.0.2.100
                        3600    AAAA    2001:db6:100::80
BE61EEUDCS4VQO71L3LFJMRKEL16S534.myzone.example.com. 3600 IN NSEC3 1 0 10 1A2B3C4D5E6F (
                          6HAUGENGIFFS98J25KBEASD720PGAN36 NS SOA MX NSEC3PARAM )

The first NSEC3 record is for the name "www.myzone.example.com.", while the last one is for the zones apex ("myzone.example.com."). The NSEC3 records in a DNSSEC signed zone are not in the proximity of the domain names they are securing (but the list of record types can give a hint).

An attacker needs to create a rainbow table to be able to 'walk' a NSEC3 zone. A rainbow table lists precomputed hashes for common domain names in that zone. The attacker will take the hashed domain names returned in an NSEC3 resource record and will compare the hash with the values in the rainbow table. If the hash matches one entry in the table, the clear text of the domain name is found. The alternative approach would be to brute force try all possible domain names and send queries to the zone. However this approach might be detected if the DNS queries towards the authoritative DNS servers are monitored (and you monitor the queries towards your DNS, do you?).

Using a rainbow table the attacker can first collect all hashed domain names by following the NSEC3 linked-list, and then try to reverse the hashes using the rainbow table in the privacy of his own environment.

The input to the hash is always the full qualified domain name (like 'www.myzone.example.com.'), so the address records pointing to a web-service "www" in two different zones will hash into different hash values. An attacker will need to create a dedicated rainbow table for each DNS zone. But once the table is calculated and working, the attacker can re-use the table for every subsequent scan.

To prevent the re-use (or even the first use of a rainbow table), there is the salt. The salt is a random, hexadecimal string that is appended to the domain name before applying the hash function to the name. The salt in the example above is '1A2B3C4D5E6F' (the last parameter in the NSEC3PARAM record, and the 4th parameter of every NSEC3 record). This salt is appended to the domain name 'www.myzone.example.com.1A2B3C4D5E6F' (but the domain name would be in wire format, and the hash in binary, not hexadecimal!) and then the hash function (today SHA1) is applied. The tool 'ldns-nsec3-hash' can be used to hash a domain name on the command line:

$ ldns-nsec3-hash -t 10 -s 1A2B3C4D5E6F  www.myzone.example.com 
6haugengiffs98j25kbeasd720pgan36.

The salt value is public (it is in the NSEC3PARAM record in the zone, and in every NSEC3 record). It must be public, because a validating DNS server must know the salt value to be able to validate the NSEC3 records coming in a negative DNS answer. Because it is public, attackers can fetch the value from the zone to generate a rainbow-table. Therefore, the salt needs to be changed from time to time.

Whenever the salt is changed in a zone, the attacker needs to throw away any pre-computed rainbow-table for the zone and start re-creating the table from scratch. If the salt is changed in intervals shorter than the time it takes to compute a reasonable large rainbow-table, it makes 'zone walking' impossible.

RFC 5155 that defines the NSEC3 record recommends to change the salt whenever a zone is signed. Because a new salt will change all NSEC3 records, and all RRSIG records for the NSEC3 records, this is quite some overhead for a large zone. The RFC draft 'draft-ietf-dnsop-rfc4641bis-08' recommends to change the salt whenever the zone signing key is rolled (because that triggers re-generation of all signatures anyway).

The salt can be up to 510 hexadecimal characters, but in practice, using 8-16 hexadecimal characters is a good value (32-64 bit). It is recommended to automate the salt generation: whenever a new zone signing key (ZSK) is generated, there should be a new salt generated.

One possible way to generate the salt is to use 16 characters out of the SHA1 hash of the current date and time:

$ date | sha1sum | cut -b 1-16
784d739287d3336

If the salt is generated from a cron script, using the date as the input to the hashing function might be predictable by an attacker. In that case, using 512 byte of randomness can be used as an alternative:

$ head -c 512 /dev/random | sha1sum | cut -b 1-16
7ac59a6dd87fa477

It is possible to use NSEC3 without a salt. In the signing command, and in the NSEC3PARAM resource record, an empty salt value is written with a single dash '-' (NSEC3PARAM 1 0 0 -). Not using a salt still protects again basic zone walking, but it allows an attacker to create and re-use a rainbow table. The 'com' gTLD is using an empty salt:

$ dig com nsec3param
; <<>> DiG 9.7.3 <<>> com nsec3param
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 1835
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 13, ADDITIONAL: 0

;; QUESTION SECTION:
;com.                           IN      NSEC3PARAM

;; ANSWER SECTION:
com.                    86400   IN      NSEC3PARAM 1 0 0 -

;; Query time: 154 msec
;; SERVER: 127.0.0.1#53(127.0.0.1)
;; WHEN: Fri Dec 30 14:03:48 2011
;; MSG SIZE  rcvd: 262

The iterations

The second parameter important for the NSEC3 hash function is the number of iterations (3rd field in the NSEC3 and NSEC3PARAM records). As computer become more powerful over time, it might be possible to calculate rainbow tables in a short amount of time. The number of iterations in NSEC3 controls how often the result of the first hash operation is hashed again (so even with iterations=0, the domain names are hashed once). By increasing the number if iterations, calculating a rainbow table can be made more expensive. But it also makes sending negative answers more expensive for authoritative DNS servers hosting the zone, as well as validating these answers on the receiver side. The number of iterations must be carfully balanced, a too high number can invite denial-of-service attacks agains the zones authoritative servers.

The current default value for NSEC3 iterations in BIND 9.8 is 10 iterations. the number of iterations is always a compromise between security and CPU usage. The default in the BIND signing tool is a good value for most zones, but every administrator should evaluate if the default is also good for her/his zones.

The number of iterations have a dependency on the size of the smallest zone-signing key in the zone (see RFC 5155, Section 10.3). These are the upper limit values (do not use higher values for the iteration field!):
 smallest ZSK Key Size in zone  max possible NSEC3 iterations  recommended by RFC 4641bis 
1024150100
2048500330
409625001600

NSEC3 records that use too high iteration values will be seen as 'insecure' by a validating DNSSEC resolver! (see RFC 5155, 12.1.4). RFC 4641bis recommends 2/3 of the maximum value. For a 1024 bit ZSK this would be 100 iterations.

Conclusion

  • If you wish to prevent 'zone walking', then sign your zone with NSEC3. If you don't mind (DNS data is public data), use plain NSEC.
  • if your domain is a 'important enough target' (whatever that might be), and there is risk that someone creates a rainbow-table for your zone, schedule a change of the NSEC3 salt parameter every time you roll your zone signing key.
  • from time to time re-evaluate the number of hash iterations used in your NSEC3 signed zone, based on the advances in computing power that might be available to a potential attacker.

References:

Thanks to Peter Koch, Alan Clegg and Miek Gieben for valuable input and answering my questions.

Comments:

Excellent article expaining NSEC3.

What a coincidence - i just done a study of actual NSEC3 parameters used by TLDs. Here it is:

http://dk379.posterous.com/nsec3param-salt-hunt

It seems that essentially nobody used high iteration count, just one domain goes over 100.

Posted by Dmitry Kohmanyuk on January 02, 2012 at 04:41 PM CET #

Nice and clear article, with sane recommendations in the conclusions.

One remark though: You state that the NSEC3PARAM RR must be public for validating DNS servers. However, validators will never use this record, they get the NSEC3 parameters from the NSEC3 RRs in the response. The NSEC3PARAM RR is intended for secondary servers, so that they know which parameters to use to hash the QNAME.

Posted by Matthijs Mekking on January 04, 2012 at 11:05 AM CET #

@Matthijs Mekking: What I was trying to say is that the salt is public: it is both in the NSEC3PARAM and in each NSEC3 record. Of course only the NSEC3 is used for validation, the NSEC3PARAM is only used for secondaries (as you write). The attacker can fetch the salt from either record type.

Posted by Carsten Strotmann on January 04, 2012 at 01:47 PM CET #

Yuri Schaeffer of NLnet Labs ( http://nlnetlabs.nl/ ) did some interesting research on NSEC3 Hash Performance in 2010
( http://nlnetlabs.nl/downloads/publications/nsec3_hash_performance.pdf ).


"When signing a zone with DNSSEC and NSEC3, a choice has to be made for the
key size and the number of hash iterations. We have measured the effect of the number of hash iterations in NSEC3 in terms of maximum query load using NSD and Unbound. This document presents the results of these measurements and compares the cost for validating and authoritative name servers and allows for an educated choice for these parameters."

Posted by Carsten Strotmann on January 04, 2012 at 02:09 PM CET #

Post a Comment:
  • HTML Syntax: Allowed

Calendar

Feeds

Search

Links

Navigation