Subdomain enumeration with DNSSEC

In my previous blog post,I described how subdomain enumeration and subdomain brute force in particular could be enhanced by taking the DNS status code into account, rather than relying on the existence of A or AAAA records only.

This follow-up post describes what techniques exist to enumerate subdomains in a DNSSEC-enabled zone and what countermeasures exist to prevent it. DNSSEC itself is not explained further, however, some relevant record types are briefly described.

Within this post, almost all shown examples are based on the following DNS zone of :

The zone is relatively simple and contains some A records, a CNAME and a TXT record. The zone above does not use DNSSEC yet, however for the following sections it will be enabled and relevant aspects for reconnaissance will be described.

NSEC

In order to show the differences between a DNS zone without DNSSEC and a DNS zone with DNSSEC, the zone layout is shown below, after DNSSEC was enabled:

Compared to the previous zone, this one is significantly larger and contains some additional resource records (RRs) like DNSKEY, RRSIG and NSEC.

DNSSEC allows proving the non-existence of nodes or the non-existence of record types belonging to existing nodes. If, for example, the nameserver is asked for the subdomain , the nameserver would respond with an answer similar to:

'The name does not exist. The previous entry in the zone is and the next entry is . No entry exists in between.'

This is exactly where NSEC records (RFC 4034) come into play, and for this procedure to work, the DNS zone needs to be lexicographically ordered. The informal statement above corresponds to the following response after sending a request to the DNSSEC-enabled nameserver:

The relevant line in the response above is:

This NSEC record states, that no node exists between and , and since would fall into that range, the statement implies that does not exist. The RRSIG records are cryptographic signatures of RRs. Clients that verify these signatures could make sure that the DNS communication has not been tampered with.

As NSEC records point to the next lexicographic entry within the DNS zone, it is possible to enumerate the whole DNS zone in linear time. This approach, which is called 'zone walking', is described in the section 'NSEC zone walking' below.

NSEC3

To overcome the problems regarding zone enumeration, NSEC3 was introduced and described in RFC 5155. NSEC3 is using the linked list approach as well, however, the owner names and the next owner names are cryptographic hashes of the original name. Similar to NSEC, the linked list is lexicographically ordered, taking the hashed name as a basis.

In order to provide an overview, the same zone as before is printed below, with DNSSEC and NSEC3 enabled:

In Figure 1, the zone output above looks quite messy, but the inner working is straightforward. The zone is relatively similar to the one with NSEC enabled, however, the labels are no longer present in clear text but in their hashed form.

To improve readability, the and records were extracted and shown below:

The list in Figure 2 shows an record and eight records.

The record provides information about the configured mode for . Generally, it comprises the following elements:

The hash algorithm is always SHA1, denoted by the value .

'Flags' refer to the opt-out feature, which influences whether delegations within the zone are signed as well. This feature is relevant for large operators, who include thousands of names within their zone files. With the opt-out flag being set, unsigned delegations do not require additional records and can be covered by a single record.

The hash function is applied at least once, but could go through additional iterations, determined by the value of 'iterations'.

Finally, an optional salt could be defined, or just left empty by adding a ''.

The NSEC3 records above start with the hashed label, followed by the domain name, for example, . Furthermore, the record contains the value as well, which in this case is . It indicates that the hash function is set to , the opt-out flag is cleared and no additional iterations or salt are used. The last important component of an NSEC3 record is the next hashed owner name, for example, .

For the calculation of the hashes, the values for the algorithm , iterations and salt are taken into account. The final hash is calculated by hashing the domain name, denoted as (needs to be in wire format; see the section below) concatenated with the raw salt bytes (RFC 5155):

The resulting hash is encoded using Base32hex and is then ready to be used in NSEC3 records.

DNS wire format

When using domain names in DNS messages, they need to be converted into a byte sequence, defined in RFC 1035, Section 3.1.

In order to convert a domain name into a sequence that could be used in DNS messages, the following steps should be performed:

1. Split the fully qualified domain name into labels (at each '.' delimiter)
2. Count the length of each label and prepend it to the label

An example of domain is shown below (note how the empty root label results in a byte):

1. Data lab test

Zone walking techniques

NSEC zone walking

NSEC walking is a technique that leverages the design of NSEC records to obtain the full DNS zone of a chosen domain. As all subdomains within a DNSSEC-enabled zone that uses NSEC are connected via pointers, it's possible to query all subdomains in a row, since every subdomain reveals its successor.

For demonstration purposes, let's look at all NSEC records of the zone file above:

Within this list, it can easily be seen that every subdomain within the zone has a successor. The successor is determined by the lexicographic order:

To start NSEC walking, the root domain/apex is queried first, which reveals its successor . Next is queried, with its successor being .

This sequence is repeated until the root domain itself will be printed again. This operation could be performed within O(n) and results in the following list:

To avoid full DNS zone disclosure, countermeasures like NSEC3, White Lies, and Black Lies have been developed.

NSEC3 zone enumeration

Zone walking with NSEC records is quite easy and could be done in linear time since it's only following a linked list. With NSEC3 it's still possible to enumerate the zone contents, but a slightly different approach has to be chosen. In order to demonstrate this, let's start with the classic NSEC approach first, and see what happens.

Like in the NSEC examples, we start by querying the NSEC3 record of the root domain :

The NSEC3 record indicates, that the successor of (hash of ) is .

The naive approach would be to just take that label as a basis for the next NSEC3 query:

This request failed with the error code because the hashed label cannot be queried directly in order to get the next NSEC3 record. When looking back to the first request to , the queried NSEC3 record is also not present, although the nameserver returned . The non-existence is indicated by the returned NSEC3 record (proof of non-existence) and the returned SOA record.

Another interesting behaviour can be observed: Two NSEC3 records were returned. Due to the hashing, structural information about the zone is lost and the resolver wouldn't know if a wildcard is to be expanded. To mitigate this, the resolver needs to be told about the 'closest encloser' and 'next closer name' to determine the source of wildcard synthesis in order to deny the existence of a wildcard. A third record might be necessary to cover the wildcard itself (RFC 7129 Section 5.5, Authenticated Denial of Existence in the DNS).

Since it is no longer possible to follow a chain of records like with NSEC, a different approach to enumeration is necessary.

Collecting NSEC3 hashes

By sending large amounts of requests for arbitrary domain names the nameserver will respond with many different next-owner names. To start with an example, a request for (Hashed: ) is sent, for which the nameserver returns the following NSEC3 record:

The non-existence proof above indicates that no nodes exist between and . The first hash corresponds to , and the second hash to . In this case, we know what plain text the hash corresponds to because we have full insights into the DNS zone.

An attacker without any knowledge about the zone contents requires a rainbow table to retrieve the plain text values. The steps above showed that a query for a random name revealed two new hashes, which could be stored in a list for further processing. This step is repeated with another random name :

As this random name also does not exist, the lexicographically close predecessor and successor are returned, which are () and (). Again, two new hashes are returned that could be appended to the list of hashes.

This procedure is repeated until no or very few new hashes are returned. Jonathan Demke and Casey Deccio researched this topic, developed a methodology to approximate zone sizes and found that "[…] in approximately 75% of cases, the methodology would yield an estimate that is within 20% of the actual zone size, with only 18 queries."

The phase described above could be described as the 'online phase' since requests are sent to nameservers. If the list of hashes is complete, the 'offline phase' could be started during which rainbow tables are leveraged to crack as many hashes as possible. Because the zone name is always part of the hash input, custom rainbow tables need to be computed for each zone.

The result of the offline phase is a list of retrieved subdomains.

Zone walking countermeasures

In order to prevent zone enumeration, hashing the owner names as per NSEC3 is not sufficient since it is still possible to conduct offline brute-force attacks using rainbow tables.

Therefore, a couple of mechanisms were suggested that render zone walking impossible. While RFC 4470 and Black Lies describe a general approach to modifying NSEC records, 'White Lies' is a concept that is predominantly used with NSEC3 and is also described in the following subsections.

RFC 4470

In order to not disclose actual next names within a DNS zone, RFC 4470 suggests to "[…] list any name that falls lexically after the NSEC's owner name and before the next instantiated name in the zone. […]".

To achieve this, DNS names need to be canonically ordered as per RFC 4034 Section 6.1.

Generating a DNS record that is lexically close to the requested name requires the nameserver to sign the new record on-the-fly. Online signing could be problematic if many requests have to be processed in a short amount of time since each signing operation requires computational effort. Furthermore, in order to sign the records, the generating nameserver requires permanent access to the private key, which increases the impact in case of a successful nameserver breach.

If a next name needs to be generated, an 'epsilon function' calculates a name that is lexically close to the requested name, but not identical to any existing name. RFC 4470 does not suggest what epsilon function should be used, but provides an example of how such a function could look:

Incrementing a name: "To increment a name, add a leading label with a single null (zero-value) octet."

Decrementing a name: "Fill the leftmost label to its maximum length with zeros (numeric, not ASCII zeros) and subtract one."

Following the approach above, the nameserver might return the following responses for queries to the non-existing name :

The first result indicates that does not exist. The second result proves that no wildcard exists for .

The epsilon function that is described in RFC 4470 does not take length constraints into account and is not optimal for production use. In this exact form, it does not seem to be used in any major DNSSEC implementation, however, it serves as a basis for the concepts of White Lies and Black Lies.

NSEC3 White Lies

Even though NSEC3 was making the process of subdomain enumeration more difficult, the techniques mentioned above could still be used to approximate the size of the zone and discover subdomains by cracking NSEC3 hashes in offline brute-force attacks.

To stop zone enumeration by gathering NSEC3 hashes, Dan Kaminsky adopted the mechanisms as described in RFC 4470 and applied them to NSEC3, naming the approach White Lies. It is specific to NSEC3 and implemented within his software Phreebird. It could be used instead of the classic ways to prove non-existence.

When using NSEC3 White Lies, fake NSEC3 records are generated on-the-fly that surround the requested name, similar to the procedure described in RFC 4470. Existing records that surround the NSEC3 hash of the requested subdomain are no longer disclosed. Although fake NSEC3 records are being sent to the requesting party, the mechanism is still compliant with all RFCs, since the non-existence proof is still valid.

In order to demonstrate the inner workings of NSEC3 White Lies, a DNS query for is sent to an authoritative nameserver that runs PowerDNS in 'narrow mode', which is how NSEC3 White Lies is called in this specific implementation:

In section 'NSEC3 zone enumeration', two NSEC3 records were returned after requesting . The response above contains three NSEC3 records of which two are required to deny the existence of a wildcard. Compared to NSEC3 without White Lies, the hashes above look a bit different:

i2kfv8ko2gacgetvv4h5di8jfnfb92lp.lab.test. 3600 IN NSEC3 1 0 0 - I2KFV8KO2GACGETVV4H5DI8JFNFB92LQ NS SOA RRSIG DNSKEY NSEC3PARAM

dli7u1udp62ok2r60nbbupl27bn0qh55.lab.test. 3600 IN NSEC3 1 0 0 - DLI7U1UDP62OK2R60NBBUPL27BN0QH57

lhpuceck180r4ab4vnkhib4s7fc35t8j.lab.test. 3600 IN NSEC3 1 0 0 - LHPUCECK180R4AB4VNKHIB4S7FC35T8L

In this setup the hashing algorithm is set to , no additional iterations are performed, and no salt is used.

The first entry refers to the root domain , which after applying SHA1 hashing and Base32 encoding is . The next owner hash, as per the response, is . If you look closely, this hash is almost identical to the hash of and only differs in the last character, which is '' instead of ''. This exactly corresponds to the next possible ASCII value. does not correspond to the hash of an existing subdomain and was generated on-the-fly.

The next answer corresponds to the subdomain we requested, , which corresponds to . The surrounding NSEC3 records are returned as and , whose last bytes have a positive and negative distance of to the requested hash:

Although the surrounding NSEC3 records are forged, the mechanism is still producing valid non-existence proofs, as no record exists between and .

The last response corresponds to the wildcard domain . The previous and next owner names are returned as and , which minimally surround the hash of ().

This mechanism does not disclose any hashes of existing DNS records, except for the root domain and the wildcard.

Black Lies

The concept of Black Lies was implemented within Cloudflare's nameserver software RRDNS. The inner workings are described in their blog post. Amazon adopted Black Lies for zones hosted by Route 53 and uses a slightly different implementation. Besides Cloudflare and Amazon, the operator NS1 announced on 16 January 2018 it was using DNSSEC with Black Lies as well. Black Lies enables authenticated denial of existence for NSEC records, without revealing the actual zone contents.

The mechanism behind Black Lies is based on RFC 4470 and works by prepending a lexicographically close successor of the QNAME. As per an early draft, the successor should be set to the 'immediate lexicographic successor of the QNAME'. As opposed to NSEC3 White Lies, Cloudflare nameservers are omitting the previous node for performance reasons. Reducing the overall response size was one of the main drivers for their Black Lies implementation. In fact, there are a few differences between the implementations of Cloudflare, Amazon, and NS1. These differences will be highlighted shortly.

Cloudflare

First, we investigate the behaviour when the NSEC record of an existing subdomain is queried. For this example, cloudflare.com is used:

The request to returns a response that contains an NSEC record pointing to . This next name is a fake record that is the immediate lexicographic successor of the requested name. Besides the prefix, the RR bitmap of the NSEC record comprises a large number of record types:

Without Black Lies, the RR bitmap of an NSEC record would only contain the RRs that are present for the queried name. The decision to add the complete set of RRs to the RR bitmap was made by Cloudflare for performance reasons since it prevents unnecessary database lookups.

In their blog post about Black Lies they call this approach 'DNS Shotgun' and state that their DNS servers "[…] set all the types. We say, this name does exist, just not on the one type you asked for."

The RR bitmap above actually includes the NSEC type as well but that is because our queried NSEC record exists. The following example shows a query for an MX record. Please note that the MX record does not exist for this node:

The RR bitmap looks very similar to the previous example and contains most record types but is lacking the MX record type we asked for.

Next, a non-existing name is requested:

Like in the first example, an NSEC record is returned that was constructed by appending a null byte to the QNAME. Classic nameserver implementations would have returned an status code, however, in this case Cloudflare returns ( in particular). The main reason for this behaviour is that Cloudflare intends to prevent unnecessary database lookups. Since DNSSEC aims to prove non-existence, rather than the existence of nodes, this approach is compliant with DNSSEC standards.

The RR bitmap of the generated NSEC records for non-existing nodes is set to without setting any other bits. In their blog post, Cloudflare describes that they "[…] only have to return , , and , and we do not need to search the database or precompute dynamic answers."

This has an implication for active subdomain enumeration techniques like subdomain brute force, as it is no longer possible to use the code alone to find existing domains. However, due to the RR bitmap of , it is easy to distinguish between non-existing and existing nodes.

In my previous blog post, I described empty non-terminals and why they are important for reconnaissance. Let's check the Cloudflare behaviour when querying an ENT:

The status code is , as expected. The RR bitmap is set to all supported types, except the one that was specified in the query. This behaviour is the same when requesting a non-empty node. This means that it's not possible to distinguish between ENTs and non-empty nodes with a single request. However, it's still possible to request every single record type to check whether a node is an ENT or not.

Route 53

Next, the implementation of Amazon for their Route 53 nameservers is described. First, an existing leaf node is queried, which carries a single A record:

The response above looks quite familiar and indicates that Route 53 is handling this kind of request like Cloudflare does. The string is prepended to the next owner's name and the RR bitmap shows all supported record types except for the one that was requested.

The following example uses a query for a node that does not exist within the zone:

Again, this behaviour could also be seen in the Cloudflare examples. The bitmap of RRSIG and NSEC indicates that the node does not exist.

In the next example, an ENT is queried:

The response is a bit surprising since only the RRSIG and NSEC record types are part of the NSEC bitmap. This means that non-existing nodes cannot be distinguished from ENTs, as the nameserver would handle both in the same way. This could be problematic if client software relies on the correct detection of ENTs and this issue was highlighted in the IETF draft "Empty Non-Terminal Sentinel for Black Lies "

NS1

Now we will check how the NS1 implementation works and start with an existing, non-empty node:

Like Cloudflare, NS1 is returning a status code. The RR bitmap of the NSEC record, however, does not include all record types, but only the types that are set for this particular node. This is classic NSEC behaviour. A quick query is sent to the nameserver to verify if the RR bitmap is correct:

As returned by the previous response, the CNAME record is present. Now we request a non-existing node:

The structure of this response is identical to Cloudflare's response - the status code is and the bitmap is set to . As a last check, a node is queried that is known to be an ENT:

This behaviour is interesting. Besides the usual record types RRSIG and NSEC, a third record type is returned: TYPE65281, which represents the byte sequence . This record type is used by NS1 to represent an ENT and was proposed in the draft 'Empty Non-Terminal Sentinel for Black Lies'.

Skipping DNSSEC for enumeration

Although there are some ways to circumvent status code inspection, some tools still rely on different codes like and . If a tool is used that would produce a lot of false positives due to Black Lies behaviour, it might still be possible to fall back to non-DNSSEC mode by setting the (DNSSEC Okay) to zero:

A request with dig without setting the option shows the difference:

This time we got a response, with the DNS status code set to .

Black Lies implementation summary

After inspecting different implementations, this is a brief summary of the relevant aspects of Black Lies:

• (Cloudfare, NS1, Route 53) Black Lies prevent NSEC walking efficiently
• (Cloudfare, NS1, Route 53) DNS status codes cannot be used to show the existence of a domain
• (Cloudfare, NS1) The existence of domains could be induced by looking at the RR bitmap
• (Cloudfare) ENTs cannot be distinguished from non-empty nodes
• (Route 53) ENTs cannot be distinguished from non-existing nodes
• (NS1) Existing record types could be identified using a single request
• (NS1) ENTs could be identified using a single request
• If DNS status codes matter and Black Lies is used, try again with set to

Tool support

NSEC

NSEC Zone walking is supported by the following tools:

NSEC3

For NSEC3, classic zone walking is not possible, but some tools try to approximate the zone size as well as possible:

Conclusion

After describing the mechanisms of NSEC walking, NSEC3 zone enumeration and their countermeasures, what is the final conclusion? Should unprotected NSEC records be considered a vulnerability? This cannot be easily answered, as the answer to this question completely depends on how DNS zones are treated. This is especially so for Internet-based, public zones, hiding sensitive or internal content behind hard-to-guess subdomains, which is security by obscurity; it would be a better approach to not expose sensitive content at all.

That being said, if the owner of a zone is fully aware of the zone contents and assets that are located behind subdomains and if the owner made sure that these assets are properly secured, zone enumeration wouldn't be a big deal. On the other hand, if unprotected applications or applications affected by vulnerabilities are located behind subdomains of a public DNS zone, zone enumeration would help attackers to identify and potentially compromise these applications.

NSEC3 makes this process a little bit harder, as hashes need to be cracked and custom rainbow tables need to be constructed for each domain. In cryptography, even though salts are used as an additional layer of protection, this does not apply for NSEC3, since the zone name is hashed in the initial round of the hashing function, and attackers need to create a custom rainbow tables for each zone anyway (RFC 9276).

The best protection, however, could be achieved by using either NSEC3 White Lies or Black Lies. Both are efficient mechanisms to prevent zone enumeration. However, it should be noted that Black Lies do not appear to have been deployed outside of large providers like Cloudflare, Amazon and NS1.

Although NSEC3 White Lies is not proprietary, it is still not included in all implementations. PowerDNS supports NSEC3 White Lies (narrow mode) and uses an efficient epsilon function.

Is the classic way of subdomain brute force affected by DNSSEC? That is only the case if Black Lies is used, and only if the enumeration process relies on status codes like and . For Black Lies, a slightly different strategy needs to be adopted that takes RR bitmaps into account. Apart from Black Lies, subdomain brute force does not work any differently for zones without DNSSEC.

Bastian Kanbach (Twitter,Mastodon) works as a senior security consultant for Secure Systems Engineering (SSE), conducting penetration tests, red team exercises, and audits for international clients. Bastian's special areas of interest include network and infrastructure security and active directory environments.

This post is adapted from the original at SSE Blog.

The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.

Public link

Please use the above public link if you want to share this noodl on another website.