DNSCurve: Usable security for DNS

Installing current DNSSEC (NSEC3) exposes private DNS data to low-cost DNS database espionage. The nsec3walker tool allows administrators and users to see how much private information is being given away by DNSSEC.

This page explains how to use nsec3walker. Prerequisites: typical Linux/UNIX; e.g., Ubuntu.

Download and compile the nsec3walker tool:

     wget https://dnscurve.org/nsec3walker-20101223.tar.gz
     tar -xzf nsec3walker-20101223.tar.gz
     cd nsec3walker-20101223
     make

Collect DNSSEC information from the domain being evaluated:

     time ./collect org.br > org.br.collect

This example collects DNSSEC information for *.org.br from the .org.br servers. You can, as an option, specify DNS server addresses:

     time ./collect de 87.233.175.25 > de.collect

This example collects DNSSEC information for .de from the DNS server at 87.233.175.25 (a DNSSEC testbed set up by the .de administrators), rather than from the regular .de servers (which at the time of this writing don't support DNSSEC).

DNSSEC information is hashed so that it looks like incomprehensible hex gibberish. Undo this hashing, exposing the data that the DNSSEC administrator is giving away:

     time ./unhash < org.br.collect > org.br.unhash &

You can watch the output file as it is being built:

     queries to DNS servers: 511
     local hash computations during queries: 484199
     names: 513
     og2oju8stk9q0eberafbft8pi6n17a4h adenauer.org.br.
     found 1 private NSEC3 names (0%) using 62 hash computations
     ...
     3fbshhk80cjrmqtsh2qlu1o05scs3hac kooltura.org.br.
     found 199 private NSEC3 names (38%) using 992669360 hash computations
     ...

At the time of this writing, the name adenauer.org.br has many Google results, but the name kooltura.org.br has none.

For larger zones the same amount of computation will find a smaller percentage of names but a larger number of names:

     ...
     e9ejdu75af4elca6agre9et4pf7dinsf mitrefix.de.
     found 28459 private NSEC3 names (6%) using 1121289463 hash computations
     ...

Of course, one could have discovered the same 28459 names by sending the same 1121289463 guesses as DNS queries to the .de servers, but that would have been vastly slower and thousands of times louder, generating hundreds of gigabytes of network traffic.

Network traffic

The collect tool usually needs just one query (sending one DNS query packet and receiving one DNS response packet) for each name that the administrator has "protected" with DNSSEC. For example, the collect tool needs 457655 queries for .de, which has 457657 DNSSEC (NSEC3) names; but only 511 packets for org.br, which has only 513 DNSSEC names. The unhash tool does not generate network traffic.

The collect queries use random 8-letter prefixes: e.g., hsniurus.org.br. Occasionally a queried name exists by accident; then the collect tool needs another query. Of course, extra packets will also be required if the network is overloaded, if a server is down, etc.

Local computation

NSEC3 requires clients and servers to compute various hashes, so it shouldn't be a surprise that nsec3walker also needs to compute many hashes.

The collect tool hashes random names to find hashes within the NSEC3 intervals on the DNSSEC server. Sometimes an NSEC3 interval happens to be particularly short and takes a while to find. You can watch the collect output file for statistics as the file is being built:

     stats 841 126439195 327395 327396 maybe 328239

This line (from .dk) says that 327395 network packets have been sent after 126439195 local hash computations, finding 327396 NSEC3 intervals but leaving 841 gaps. The total number of NSEC3 names is estimated to be 328239.

It is quite rare for short gaps to contain more than one NSEC3 interval, so most of the final hash computations don't actually produce new information, except for building confidence that all of the data exposed by DNSSEC has been collected. You can run unhash on a partial collect output file.

The unhash tool hashes a series of guesses for names that could exist. The order of names uses a simple cost model based on trigraph statistics from /usr/share/dict/words. You can specify another dictionary on the unhash command line.

Future work

The hashing in nsec3walker is embarrassingly slow: it isn't parallelized and isn't even marginally vectorized. Good hashing code for a modern graphics card will be hundreds of times faster. Furthermore, unhash should use a better model of domain names.

New software from Ruben Niederhagen, not released yet, checks 12000 billion hashes in a single week on a standard PC with two NVIDIA GTX 295 graphics cards. Each hash is 32 salted iterations of SHA-1 (as in the .de database), checked against a database of half a million targets (such as the .de database). DNSSEC advocate Rickard Bellgrim claims that this is something "you can already do in regular DNS"; however, sending 12000 billion DNS queries through a 20Mbps network to the DNS servers would require flooding the network for more than 25 years.

Version

This is version 2017.01.22 of the nsec3walker.html web page.