The peculiar case of NSEC processing using expanded wildcard records

By Ralph Dolmans

Last week we released a new version of Unbound with a fix for CVE-2017–15105. Unbound, Google public DNS, PowerDNS and Dnsmasq contained a flaw that made it possible to downgrade secure connections.

Every year NLnet Labs assist the DNS and DNSSEC practical lab as part of the University of Amsterdam’s Security and Network Engineering master programme. It was during that visit that Karst Koymans persuaded me to look into wildcard NSEC records. This was the beginning of the security vulnerability identified as CVE-2017-15105.

Before going into the details of this vulnerability, I will give a very brief explanation of NSEC records and the case of DNSSEC signatures for wildcard records.

NSEC and DNSSEC signatures on wildcard records

DNSSEC is not only used to prove the authenticity of records in a DNS answer by verifying the DNSSEC signatures of the records, it is also used to prove the absence of records. DNSSEC uses NSEC (and NSEC3) records for these proof of non-existence answers. An NSEC record indicates that there are no records that are sorted between the two domain names it contains. The canonical DNS name order is used for the sorting. An NSEC record also has a type bitmap which specifies the record types that exist for the owner name of the NSEC record. Like any other DNS record, the authenticity of NSEC records can be validated using its DNSSEC signature which is located in the RRSIG record.

Let’s have a look at an example NSEC record:

giraffe.nlnetlabs.nl NSEC koala.nlnetlabs.nl TXT RRSIG NSEC

This record indicates that the owner name (giraffe.nlnetlabs.nl) exists and that the owner name has records for the TXT, RRSIG and NSEC types. It therefore proves that there is no A record for giraffe.nlnetlabs.nl. This NSEC record also proves that there are no records alphabetically sorted between its owner and its next domain name (koala.nlnetlabs.nl). This record therefore proves that there is no record for jaguar.nlnetlabs.nl.

In order to answer a DNS query using a wildcard record, an authoritative nameserver replaces the owner name of the wildcard record with the name in the query. DNSSEC is designed in such way that it can sign a complete zone before it starts serving. Because the query name that will be used for the wildcard record is not known when the zone is being signed, it is not possible to make a DNSSEC signature for it. Therefore the original owner name with the wildcard label is used for the signature. The labels field that is part of the RRSIG record indicates the number of labels of the owner name without the wildcard label. This labels field can be used by a DNSSEC validator to detect that this is a signature for a wildcard record. A DNSSEC validator then knows it needs to validate the signature using the original wildcard owner, and not the expanded owner that matches the query name. A validator gets the original owner name by taking the number of rightmost labels defined in the labels field from the expanded owner and then prepend it with the wildcard label *.

This is an example of a wildcard expanded RRSIG record, with the signature omitted to keep the text compact:

zebra.nlnetlabs.nl.  2710 IN RRSIG NSEC 8 2 10200 20180226143900 20180129143900 42393 nlnetlabs.nl. [..]

This RRSIG record has a label count of two, while the number of labels in the owner name (excluding the root label) is three. Using that information a validator will take the two last labels of the owner name (nlnetlabs.nl) and prepend the wildcard label to it. It therefore checks the signature using the original wildcard name, which is *.nlnetlabs.nl.

Combining NSEC processing and wildcard expansion

Combining wildcard expansion and the processing of NSEC records is where things start to become interesting. The owner name of the NSEC record is used to prove that there are records for that name for the record types in the bitmap. The NSEC record is also used to prove that there are no records between its owner name and its next domain name. However, due to wildcard expansion, that same NSEC owner name can be changed and still be validated using DNSSEC. An NSEC record with a wildcard expanded name does not prove anything for the expanded name, the proof is for the original owner name with the wildcard label. Wildcard expansion on NSEC record is specifically allowed by RFC4592.

When Karst shared his opinion with me that wildcard expanded NSEC records are by definition wrong, I initially defended the RFC. I argued that a DNSSEC validator can use the labels field from the NSEC signature to determine the original owner, which needs to be done to validate the record anyway. That original owner can then be used for the NSEC processing. However, I was interested in double checking Unbound’s implementation.

The non-existence validation in Unbound happens in two stages. First the signature over the NSEC record is validated, as with any DNS record. Then the NSEC record is used for the NSEC processing. For the signature verification, the original owner name of the wildcard record is used. If everything is correct the record is marked as secure and the NSEC record is passed on to the NSEC processing. Mind you, this is the expanded NSEC record received from the authoritative nameserver that is passed to the NSEC processing. This record is passed without information about this signature, that makes it impossible for the NSEC processing code to know this is a wildcard expanded name. That can’t be good! Unbound is using the expanded owner name for the NSEC processing, not the original owner name.

By being able to change the owner name of an NSEC record it becomes possible to trick a DNSSEC validator into accepting a proof of non-existence answer for data that in fact does exist.

Impact

NXDOMAIN answers

There are some limitations in the possible expanded owner names we can use in the attack. The owner name needs to be sorted before the next domain name. Changing the owner in a name that will be sorted after the original owner but before the next domain name is useless since that part is already proven to be non-existent. Therefore the only interesting thing we can do here is changing the owner into something that will be sorted before the original owner name. Because the wildcard label is sorted almost at the beginning the impact is somewhat limited. The biggest impact is that we can create a proof of non-existence for the wildcard record itself.

Let say that we have a zone with these records:

nlnetlabs.nl NSEC *.nlnetlabs.nl
*.nlnetlabs.nl NSEC buffalo.nlnetlabs.nl
buffalo.nlnetlabs.nl NSEC nlnetlabs.nl

We can now change the wildcard label into something that will be sorted before buffalo.nlnetlabs.nl, for example in !.nlnetlabs.nl. Although a query for albatross.nlnetlabs.nl is supposed to be answered with the wildcard record, a vulnerable validator will accept an answer with an NXDOMAIN status and the !.nlnetlabs.nl NSEC record. The assumption here is that the attacker is able to trick a resolver into accepting spoofed answers, which is the reason why DNSSEC exists.

Remember that I mentioned that we can only change the NSEC owner name into something that will be sorted before the next domain name? Well, that turns out to not always be the case. The NSEC for the last record in the zone points back to the first record, which is always the zone apex. An NSEC record with a next domain name before the NSEC owner is only accepted by Unbound when the next domain name is the zone apex (nlnetlabs.nl in our example). During the impact analysis of this vulnerability I discovered that there are DNSSEC validation implementations that do not have this check. In that case it is possible to change the owner into something that is sorted just after the next domain name, for example we can make the record:

a.buffalo.nlnetlabs.nl NSEC buffalo.nlnetlabs.nl

This record then proves that there is nothing between the two domain names, which is almost the entire zone. Imagine what can happen when an NSEC record like that ends up in an aggressive use of NSEC cache!

NODATA answers

Being able to trick a validator into accepting NXDOMAIN answers that in fact do exist is not good, but as said, the impact is somewhat limited. An end user does not often care whether the attempt to visit a website is not working because a validator marks the answer as DNSSEC bogus, or if the return code is an NXDOMAIN. This does change when the proof of non-existence is used to make security related decisions, as is the case with DANE.

One of the things where DANE is very valuable is in the SMTP transport. DANE can turn the opportunistic STARTTLS security into downgrade-proof security. The requirement here is that the mailserver’s zone has a TLSA record; no TLSA record means no downgrade-proof security. It is therefore very important to be able to verify the absence of a DANE record.

Using the method described above we can use this vulnerability to give an NXDOMAIN answer for a TLSA query. However, this will only work when the TLSA record we are trying to hide is placed at the location of the wildcard record. Besides proving that a name does not exist (NXDOMAIN) there is also the NODATA proof. This is an answer with the NOERROR status but without any record in the answer section. This answer indicates that records exist for the query name, but that name does not have records for the query type. This answer is accompanied by an NSEC record that equals the query name, and has a bitmap field where the bit for the query type is not set. The interesting aspect of this is that a validator does not have to look at the NSEC’s next domain name because it is not using the span between the two domains for the NODATA proof. It turns out that NSEC records with owner names sorted after the next domain name are accepted in the NODATA proof.

So, when we have an wildcard NSEC record for which the TLSA bit is not set in the type bit map, all we have to do is change the owner name into the name of the TLSA record that has been queried:

_25._tcp.mail.nlnetlabs.nl NSEC buffalo.nlnetlabs.nl

Although _25._tcp.mail is sorted after the next domain name, this record will be accepted because the validator has no need to look at the next domain name. This results in the possibility to prove the non-existence for all records, including all TLSA records.

Insecure delegation proof

Another record type for which security related decisions are made based on its presence is the DS type. The absence of a DS record for the owner of a delegation in a DNSSEC signed zone is proof that the zone below the delegation is DNSSEC insecure. This means that a DNSSEC validator does not have to validate anything below the delegation. If we would be able to use this vulnerability to prove the non-existence of a DS record, we would effectively remove DNSSEC protection for everything below a delegation in a zone with a wildcard record. Luckily this is not possible in Unbound.

The NSEC record that is used to prove the absence of a DS record always needs to have the NS bit set in its type bitmap. If this wouldn’t be required it would be possible to use any NSEC record in a zone for the insecure delegation proof. Because parent side NS records are not DNSSEC signed, this would mean that for every record in a zone an insecure delegation can be created which completely removes DNSSEC protection. During the analysis of this vulnerability I found an implementation that did not check for the NS bit. This has been reported and fixed by now.

Although wildcard NS records are not strictly forbidden but only discouraged by the RFC, they do not seem to occur in the wild in DNSSEC signed zones. Because there are no NS records with a wildcard as owner name, the NS bit will not be set on in the type bitmap of the wildcard NSEC record. The wildcard expanded NSEC records can therefore not be used to prove to absence of a DS record.

Attack requirements

The attacks described in this article require the presence of a wildcard record in the zone. Another requirement is that the zone uses NSEC to prove the non-existence of records. Zones that use NSEC3 cannot be attacked using this vulnerability.

We noticed the existence of nameserver implementations that generate matching NSEC records, signed online, for non-existing names. This is a method called white lies. When using white lies the wildcard record always exists. These dynamically generated wildcard records can be used for this attack when its signature is a wildcard signature; meaning that the label count in the signature is smaller than the number of labels at the owner name.

Proof of concept

To get an better understanding of the impact of the attack, and to be able to check if other implementations were also vulnerable, I created a DNS zone containing proof of concept records for the described attacks. These test records are still online so feel free to test your own DNSSEC validator.

The proof of concept domain for the NXDOMAIN attack is located at !.nsecwc.nlnetlabs.nl. I omitted the signature from the RRSIG record to keep the text compact:

!.nsecwc.nlnetlabs.nl. 3600 IN NSEC delegation.nsecwc.nlnetlabs.nl. TXT RRSIG NSEC
!.nsecwc.nlnetlabs.nl. 3600 IN RRSIG NSEC 8 3 3600 20200101000000 20171108114635 565 nsecwc.nlnetlabs.nl. [..]

Note that the label count field in the signature that matches the NSEC record is 3, this indicated that this is an expanded wildcard record. The label count in the signature would have been 4 if this would not be a wildcard record. The original NSEC record without wildcard expansion is:

*.nsecwc.nlnetlabs.nl. 3600 IN NSEC delegation.nsecwc.nlnetlabs.nl. TXT RRSIG NSEC

A query for albatross.nsecwc.nlnetlabs.nl should be answered by the wildcard record but the vulnerable implementation does accept an NXDOMAIN by using this proof.

The record for the NODATA proof of concept can be found at _25._tcp.mail.nsecwc.nlnetlabs.nl:

_25._tcp.mail.nsecwc.nlnetlabs.nl. 3599 IN NSEC delegation.nsecwc.nlnetlabs.nl. TXT RRSIG NSEC
_25._tcp.mail.nsecwc.nlnetlabs.nl. 3599 IN RRSIG NSEC 8 3 3600 20200101000000 20171108114635 565 nsecwc.nlnetlabs.nl. [..]

This record does not prove anything for the expanded owner namer. This NODATA answer will be accepted by the vulnerable implementations anyway.

Using these, and other records I was able to identify vulnerabilities in Unbound, the Google public resolver, PowerDNS and Dnsmasq. These findings were reported and are now fixed.

Vulnerability fix

After discovering this vulnerability in Unbound we started working on a fix. We implemented this by overwriting the expanded owner names of NSEC records found in the authority section on a DNS answer, back to the original owner name.

This fix is present in Unbound 1.6.8. There is also a patch available that can be applied on Unbound 1.6.7: https://unbound.net/downloads/patch_cve_2017_15105.diff.

Looking ahead

We identified multiple independently developed DNSSEC validation implementations to be vulnerable for the attacks described in this article. This makes it debatable whether the RFC is clear enough on this topic and whether a secure DNSSEC validation implementation can be developed by following the specification. It might not be clear from the specification that a DNSSEC validated NSEC record can not be used on its own for the NSEC processing but that the signature’s label count is needed as well. Karst already submitted an errata for RFC4592 before knowing that multiple vendors used the wildcard expanded NSEC owner name in the NSEC processing. This errata states that wildcard synthesis of NSEC records should not be allowed. These recent findings might shed some new light on the decision whether the errata should be accepted.