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 |
|---|---|---|
| 1024 | 150 | 100 |
| 2048 | 500 | 330 |
| 4096 | 2500 | 1600 |
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:
- SIDN NSEC3 Whitepaper (Version 2) (PDF)
- RFC 5155 'DNS Security (DNSSEC) Hashed Authenticated Denial of Existence'
- RFC 4641bis draft 'DNSSEC Operational Practices, Version 2'
- Minimizing Information Leakage in the DNS (PDF)
- NIST Secure Domain Name System (DNS) Deployment Guide (PDF)
- What values do the others use? Dmitry Kohmanyuk was on a "NSEC3PARAM salt hunt"
- How Rainbow Tables work by Kestas Kuliukas
Thanks to Peter Koch, Alan Clegg and Miek Gieben for valuable input and answering my questions.
