Cryptographic sanity: NSEC3 parameters

Written by Rick van Rein in category: Crypto, Security

Wikimedia Commons

One of the factors that delayed the adoption of DNSSEC has been the privacy of the information stored in it. This is a topic of debate, as DNS has always been designed as a public database, but the Internet of today cannot be reigned from purely technical motivations.

The problem is with securely denying a DNS record if it does not exist. If such denials were not secured (meaning, signed) it would still be quite possible to mount a DoS attack against a domain. Although signing does solve that problem, it introduces another. All other signing in DNSSEC can be done offline, but signing a denial that includes the name being denied would have to be done online, and that could introduce an opportunity for leaks of key material. How to solve that conflict of interests?

The solution is to sign the denial for holes, that is, to create offline signatures on NXDOMAIN answers stating that no names exist between X and Z. The offline signer simply sorts all names, determines what holes exist between them and signs for any such hole. This original solution was dubbed NSEC, but it was considered an invasion of privacy because it enabled “walking” a zone, that is hopping from hole to hole to determine all the names in a zone. To solve this problem, NSEC3 was created. NSEC3 does not sign holes between names, but holes between secure hashes of names. While it is still possible to “walk” a zone for the hashes of its names, it is not possible to derive the names from which these hashes were derived.

We emphasize that anything that is truly private does not belong in public DNS. You should setup an internal view on your zone, or define records in /etc/hosts, or perhaps define an internal-only zone, but you should not rely on this mechanism to guard your secrets. That being said, it would be good to discourage massive attacks on zones, such as may be done by spammers looking for entries that look like, or contain, email addresses. And to discourage harvesting of SSH server key publications and addresses. Or X.509 and PGP certificates.

The way NSEC3 works is by repeated hashing with a plain hashing algorithm, each time incorporating a “salt” into the hash. A salt is a bit of extra data that helps to scramble the outcome of the hashing operation. A first step to take is to use a different salt on each of the zones. Also, this salt should be as random as possible — it should not be easy to influence the process of generating the salt. Furthermore, entropy (which may be read as “randomness” in this case) can be as weak as its weakest link, so it is a good idea to use a long salt. Longer than the hash outcome would be silly though; so if the hash algorithm used is SHA1, take 160 bits worth of salt, and if SHA256 is used take 256 bits. If multiple algorithms are used, just follow the longest algorithm.

The question that remains is how often the hashes should be run over a bit of data. The trick with repetitions is that even weak hash algorithms become very strong when their number of iterations is taken high enough. Common hash algorithms run about 5 rounds over the data that is to be hashed, and doubling that already means a severe complication for any attacker. This is because the algorithms are designed to scatter the data that they are given as randomly as possible. If it takes N attempts to crack one pass of an algorithm then it takes N*N attempts to crack two passes. In general, the cracks become more difficult in an exponential relation to the number of passes made. This means that 5 passes really compares to raising the cracking effort to the fifth power! From the perspective of computational load on a secure resolver, 5 hashing passes are acceptable as well; their influence on the validation process then remains minimal in comparison to RSA validation.

Note that NSEC3 hashing does not only impact validating caches, but the authoritative name servers for a domain just as well. This is because an NXDOMAIN response can only be provided after establishing the hash of the name being rejected, which selects the NSEC3 “hole” that is to be sent from the authoritative name server to the secure resolver.

In short, given the relative public nature of DNS, a single pass should suffice; if you feel that this blog article leans over more to public DNS data than you can afford, you may alternatively choose to make two or all the way up to five passes and thus attain a quadratic up to a fifth-power cracking effort.

1 Comment to “Cryptographic sanity: NSEC3 parameters”

  1. Fred Woodbridge says:

    Thanks for this explanation; succinct without losing clarity.