resolved: add negative trust anchro support, and add trust anchor configuration files

This adds negative trust anchor support and allows reading trust anchor
data from disk, from files
/etc/systemd/dnssec-trust-anchors.d/*.positive and
/etc/systemd/dnssec-trust-anchros.d/*.negative, as well as the matching
counterparts in /usr/lib and /run.

The positive trust anchor files are more or less compatible to normal
DNS zone files containing DNSKEY and DS RRs. The negative trust anchor
files contain only new-line separated hostnames for which to require no
signing.

By default no trust anchor files are installed, in which case the
compiled-in root domain DS RR is used, as before. As soon as at least
one positive root anchor for the root is defined via trust anchor files
this buil-in DS RR is not added though.

6 files changed, 372 insertions, 28 deletions

diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index 7736a67d96..b7c0b5b824 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -35,7 +35,6 @@
  *
  * TODO:
  *
- *   - Make trust anchor store read additional DS+DNSKEY data from disk
  *   - wildcard zones compatibility (NSEC/NSEC3 wildcard check is missing)
  *   - multi-label zone compatibility
  *   - cname/dname compatibility
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index 4d47f48e9b..76723ec4d0 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -916,20 +916,21 @@ const char *dns_resource_record_to_string(DnsResourceRecord *rr) {
                 break;
 
         case DNS_TYPE_DNSKEY: {
-                const char *alg;
+                _cleanup_free_ char *alg = NULL;
 
-                alg = dnssec_algorithm_to_string(rr->dnskey.algorithm);
+                r = dnssec_algorithm_to_string_alloc(rr->dnskey.algorithm, &alg);
+                if (r < 0)
+                        return NULL;
 
                 t = base64mem(rr->dnskey.key, rr->dnskey.key_size);
                 if (!t)
                         return NULL;
 
-                r = asprintf(&s, "%s %u %u %.*s%.*u %s",
+                r = asprintf(&s, "%s %u %u %s %s",
                              k,
                              rr->dnskey.flags,
                              rr->dnskey.protocol,
-                             alg ? -1 : 0, alg,
-                             alg ? 0 : 1, alg ? 0u : (unsigned) rr->dnskey.algorithm,
+                             alg,
                              t);
                 if (r < 0)
                         return NULL;
@@ -937,11 +938,15 @@ const char *dns_resource_record_to_string(DnsResourceRecord *rr) {
         }
 
         case DNS_TYPE_RRSIG: {
-                const char *type, *alg;
+                _cleanup_free_ char *alg = NULL;
                 char expiration[strlen("YYYYMMDDHHmmSS") + 1], inception[strlen("YYYYMMDDHHmmSS") + 1];
+                const char *type;
 
                 type = dns_type_to_string(rr->rrsig.type_covered);
-                alg = dnssec_algorithm_to_string(rr->rrsig.algorithm);
+
+                r = dnssec_algorithm_to_string_alloc(rr->rrsig.algorithm, &alg);
+                if (r < 0)
+                        return NULL;
 
                 t = base64mem(rr->rrsig.signature, rr->rrsig.signature_size);
                 if (!t)
@@ -958,12 +963,11 @@ const char *dns_resource_record_to_string(DnsResourceRecord *rr) {
                 /* TYPE?? follows
                  * http://tools.ietf.org/html/rfc3597#section-5 */
 
-                r = asprintf(&s, "%s %s%.*u %.*s%.*u %u %u %s %s %u %s %s",
+                r = asprintf(&s, "%s %s%.*u %s %u %u %s %s %u %s %s",
                              k,
                              type ?: "TYPE",
                              type ? 0 : 1, type ? 0u : (unsigned) rr->rrsig.type_covered,
-                             alg ? -1 : 0, alg,
-                             alg ? 0 : 1, alg ? 0u : (unsigned) rr->rrsig.algorithm,
+                             alg,
                              rr->rrsig.labels,
                              rr->rrsig.original_ttl,
                              expiration,
@@ -1131,7 +1135,7 @@ static const char* const dnssec_algorithm_table[_DNSSEC_ALGORITHM_MAX_DEFINED] =
         [DNSSEC_ALGORITHM_PRIVATEDNS]         = "PRIVATEDNS",
         [DNSSEC_ALGORITHM_PRIVATEOID]         = "PRIVATEOID",
 };
-DEFINE_STRING_TABLE_LOOKUP(dnssec_algorithm, int);
+DEFINE_STRING_TABLE_LOOKUP_WITH_FALLBACK(dnssec_algorithm, int, 255);
 
 static const char* const dnssec_digest_table[_DNSSEC_DIGEST_MAX_DEFINED] = {
         /* Names as listed on https://www.iana.org/assignments/ds-rr-types/ds-rr-types.xhtml */
@@ -1140,4 +1144,4 @@ static const char* const dnssec_digest_table[_DNSSEC_DIGEST_MAX_DEFINED] = {
         [DNSSEC_DIGEST_GOST_R_34_11_94] = "GOST_R_34.11-94",
         [DNSSEC_DIGEST_SHA384] = "SHA-384",
 };
-DEFINE_STRING_TABLE_LOOKUP(dnssec_digest, int);
+DEFINE_STRING_TABLE_LOOKUP_WITH_FALLBACK(dnssec_digest, int, 255);
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index 27c5f5384e..90c3629166 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -279,8 +279,8 @@ bool dns_txt_item_equal(DnsTxtItem *a, DnsTxtItem *b);
 
 extern const struct hash_ops dns_resource_key_hash_ops;
 
-const char* dnssec_algorithm_to_string(int i) _const_;
+int dnssec_algorithm_to_string_alloc(int i, char **ret);
 int dnssec_algorithm_from_string(const char *s) _pure_;
 
-const char *dnssec_digest_to_string(int i) _const_;
+int dnssec_digest_to_string_alloc(int i, char **ret);
 int dnssec_digest_from_string(const char *s) _pure_;
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index c8248761b2..9a03baa9ec 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -892,7 +892,7 @@ static int dns_transaction_prepare(DnsTransaction *t, usec_t ts) {
 
         /* Check the trust anchor. Do so only on classic DNS, since DNSSEC does not apply otherwise. */
         if (t->scope->protocol == DNS_PROTOCOL_DNS) {
-                r = dns_trust_anchor_lookup(&t->scope->manager->trust_anchor, t->key, &t->answer);
+                r = dns_trust_anchor_lookup_positive(&t->scope->manager->trust_anchor, t->key, &t->answer);
                 if (r < 0)
                         return r;
                 if (r > 0) {
@@ -1270,7 +1270,7 @@ static int dns_transaction_request_dnssec_rr(DnsTransaction *t, DnsResourceKey *
                 return 0;
 
         /* Try to get the data from the trust anchor */
-        r = dns_trust_anchor_lookup(&t->scope->manager->trust_anchor, key, &a);
+        r = dns_trust_anchor_lookup_positive(&t->scope->manager->trust_anchor, key, &a);
         if (r < 0)
                 return r;
         if (r > 0) {
@@ -1328,6 +1328,14 @@ static int dns_transaction_has_unsigned_negative_answer(DnsTransaction *t) {
         if (r > 0)
                 return false;
 
+        /* Is this key explicitly listed as a negative trust anchor?
+         * If so, it's nothing we need to care about */
+        r = dns_trust_anchor_lookup_negative(&t->scope->manager->trust_anchor, DNS_RESOURCE_KEY_NAME(t->key));
+        if (r < 0)
+                return r;
+        if (r > 0)
+                return false;
+
         /* The answer does not contain any RRs that match to the
          * question. If so, let's see if there are any NSEC/NSEC3 RRs
          * included. If not, the answer is unsigned. */
@@ -1412,6 +1420,13 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                 if (dns_type_is_pseudo(rr->key->type))
                         continue;
 
+                /* If this RR is in the negative trust anchor, we don't need to validate it. */
+                r = dns_trust_anchor_lookup_negative(&t->scope->manager->trust_anchor, DNS_RESOURCE_KEY_NAME(rr->key));
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        continue;
+
                 switch (rr->key->type) {
 
                 case DNS_TYPE_RRSIG: {
@@ -1756,6 +1771,12 @@ static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *
         if (dns_type_is_pseudo(rr->key->type))
                 return -EINVAL;
 
+        r = dns_trust_anchor_lookup_negative(&t->scope->manager->trust_anchor, DNS_RESOURCE_KEY_NAME(rr->key));
+        if (r < 0)
+                return r;
+        if (r > 0)
+                return false;
+
         switch (rr->key->type) {
 
         case DNS_TYPE_RRSIG:
@@ -1893,6 +1914,12 @@ static int dns_transaction_requires_nsec(DnsTransaction *t) {
         if (dns_type_is_pseudo(t->key->type))
                 return -EINVAL;
 
+        r = dns_trust_anchor_lookup_negative(&t->scope->manager->trust_anchor, DNS_RESOURCE_KEY_NAME(t->key));
+        if (r < 0)
+                return r;
+        if (r > 0)
+                return false;
+
         name = DNS_RESOURCE_KEY_NAME(t->key);
 
         if (IN_SET(t->key->type, DNS_TYPE_SOA, DNS_TYPE_NS, DNS_TYPE_DS)) {
@@ -1944,6 +1971,12 @@ static int dns_transaction_dnskey_authenticated(DnsTransaction *t, DnsResourceRe
          * the specified RRset is authenticated (i.e. has a matching
          * DS RR). */
 
+        r = dns_trust_anchor_lookup_negative(&t->scope->manager->trust_anchor, DNS_RESOURCE_KEY_NAME(rr->key));
+        if (r < 0)
+                return r;
+        if (r > 0)
+                return false;
+
         DNS_ANSWER_FOREACH(rrsig, t->answer) {
                 DnsTransaction *dt;
                 Iterator i;
diff --git a/src/resolve/resolved-dns-trust-anchor.c b/src/resolve/resolved-dns-trust-anchor.c
index 208b7fefc4..03c5b9406e 100644
--- a/src/resolve/resolved-dns-trust-anchor.c
+++ b/src/resolve/resolved-dns-trust-anchor.c
@@ -20,25 +20,37 @@
 ***/
 
 #include "alloc-util.h"
+#include "conf-files.h"
+#include "def.h"
+#include "dns-domain.h"
+#include "fd-util.h"
+#include "fileio.h"
+#include "hexdecoct.h"
+#include "parse-util.h"
 #include "resolved-dns-trust-anchor.h"
+#include "set.h"
+#include "string-util.h"
+#include "strv.h"
 
-/* The DS RR from https://data.iana.org/root-anchors/root-anchors.xml */
+static const char trust_anchor_dirs[] = CONF_PATHS_NULSTR("systemd/dnssec-trust-anchors.d");
+
+/* The DS RR from https://data.iana.org/root-anchors/root-anchors.xml, retrieved December 2015 */
 static const uint8_t root_digest[] =
         { 0x49, 0xAA, 0xC1, 0x1D, 0x7B, 0x6F, 0x64, 0x46, 0x70, 0x2E, 0x54, 0xA1, 0x60, 0x73, 0x71, 0x60,
           0x7A, 0x1A, 0x41, 0x85, 0x52, 0x00, 0xFD, 0x2C, 0xE1, 0xCD, 0xDE, 0x32, 0xF2, 0x4E, 0x8F, 0xB5 };
 
-int dns_trust_anchor_load(DnsTrustAnchor *d) {
+static int dns_trust_anchor_add_builtin(DnsTrustAnchor *d) {
         _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
         int r;
 
         assert(d);
 
-        r = hashmap_ensure_allocated(&d->by_key, &dns_resource_key_hash_ops);
+        r = hashmap_ensure_allocated(&d->positive_by_key, &dns_resource_key_hash_ops);
         if (r < 0)
                 return r;
 
-        if (hashmap_get(d->by_key, &DNS_RESOURCE_KEY_CONST(DNS_CLASS_IN, DNS_TYPE_DS, ".")))
+        if (hashmap_get(d->positive_by_key, &DNS_RESOURCE_KEY_CONST(DNS_CLASS_IN, DNS_TYPE_DS, ".")))
                 return 0;
 
         /* Add the RR from https://data.iana.org/root-anchors/root-anchors.xml */
@@ -62,11 +74,297 @@ int dns_trust_anchor_load(DnsTrustAnchor *d) {
         if (r < 0)
                 return r;
 
-        r = hashmap_put(d->by_key, rr->key, answer);
+        r = hashmap_put(d->positive_by_key, rr->key, answer);
+        if (r < 0)
+                return r;
+
+        answer = NULL;
+        return 0;
+}
+
+static int dns_trust_anchor_load_positive(DnsTrustAnchor *d, const char *path, unsigned line, const char *s) {
+        _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
+        _cleanup_free_ char *domain = NULL, *class = NULL, *type = NULL;
+        _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
+        DnsAnswer *old_answer = NULL;
+        const char *p = s;
+        int r;
+
+        assert(d);
+        assert(line);
+
+        r = extract_first_word(&p, &domain, NULL, EXTRACT_QUOTES);
+        if (r < 0)
+                return log_warning_errno(r, "Unable to parse domain in line %s:%u: %m", path, line);
+
+        if (!dns_name_is_valid(domain)) {
+                log_warning("Domain name %s is invalid, at line %s:%u, ignoring line.", domain, path, line);
+                return -EINVAL;
+        }
+
+        r = extract_many_words(&p, NULL, 0, &class, &type, NULL);
+        if (r < 0)
+                return log_warning_errno(r, "Unable to parse class and type in line %s:%u: %m", path, line);
+        if (r != 2) {
+                log_warning("Missing class or type in line %s:%u", path, line);
+                return -EINVAL;
+        }
+
+        if (!strcaseeq(class, "IN")) {
+                log_warning("RR class %s is not supported, ignoring line %s:%u.", class, path, line);
+                return -EINVAL;
+        }
+
+        if (strcaseeq(type, "DS")) {
+                _cleanup_free_ char *key_tag = NULL, *algorithm = NULL, *digest_type = NULL, *digest = NULL;
+                _cleanup_free_ void *dd = NULL;
+                uint16_t kt;
+                int a, dt;
+                size_t l;
+
+                r = extract_many_words(&p, NULL, 0, &key_tag, &algorithm, &digest_type, &digest, NULL);
+                if (r < 0) {
+                        log_warning_errno(r, "Failed to parse DS parameters on line %s:%u: %m", path, line);
+                        return -EINVAL;
+                }
+                if (r != 4) {
+                        log_warning("Missing DS parameters on line %s:%u", path, line);
+                        return -EINVAL;
+                }
+
+                r = safe_atou16(key_tag, &kt);
+                if (r < 0)
+                        return log_warning_errno(r, "Failed to parse DS key tag %s on line %s:%u: %m", key_tag, path, line);
+
+                a = dnssec_algorithm_from_string(algorithm);
+                if (a < 0) {
+                        log_warning("Failed to parse DS algorithm %s on line %s:%u", algorithm, path, line);
+                        return -EINVAL;
+                }
+
+                dt = dnssec_digest_from_string(digest_type);
+                if (dt < 0) {
+                        log_warning("Failed to parse DS digest type %s on line %s:%u", digest_type, path, line);
+                        return -EINVAL;
+                }
+
+                r = unhexmem(digest, strlen(digest), &dd, &l);
+                if (r < 0) {
+                        log_warning("Failed to parse DS digest %s on line %s:%u", digest, path, line);
+                        return -EINVAL;
+                }
+
+                rr = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_DS, domain);
+                if (!rr)
+                        return log_oom();
+
+                rr->ds.key_tag = kt;
+                rr->ds.algorithm = a;
+                rr->ds.digest_type = dt;
+                rr->ds.digest_size = l;
+                rr->ds.digest = dd;
+                dd = NULL;
+
+        } else if (strcaseeq(type, "DNSKEY")) {
+                _cleanup_free_ char *flags = NULL, *protocol = NULL, *algorithm = NULL, *key = NULL;
+                _cleanup_free_ void *k = NULL;
+                uint16_t f;
+                size_t l;
+                int a;
+
+                r = extract_many_words(&p, NULL, 0, &flags, &protocol, &algorithm, &key, NULL);
+                if (r < 0)
+                        return log_warning_errno(r, "Failed to parse DNSKEY parameters on line %s:%u: %m", path, line);
+                if (r != 4) {
+                        log_warning("Missing DNSKEY parameters on line %s:%u", path, line);
+                        return -EINVAL;
+                }
+
+                if (!streq(protocol, "3")) {
+                        log_warning("DNSKEY Protocol is not 3 on line %s:%u", path, line);
+                        return -EINVAL;
+                }
+
+                r = safe_atou16(flags, &f);
+                if (r < 0)
+                        return log_warning_errno(r, "Failed to parse DNSKEY flags field %s on line %s:%u", flags, path, line);
+
+                a = dnssec_algorithm_from_string(algorithm);
+                if (a < 0) {
+                        log_warning("Failed to parse DNSKEY algorithm %s on line %s:%u", algorithm, path, line);
+                        return -EINVAL;
+                }
+
+                r = unbase64mem(key, strlen(key), &k, &l);
+                if (r < 0)
+                        return log_warning_errno(r, "Failed to parse DNSKEY key data %s on line %s:%u", key, path, line);
+
+                rr = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_DNSKEY, domain);
+                if (!rr)
+                        return log_oom();
+
+                rr->dnskey.flags = f;
+                rr->dnskey.protocol = 3;
+                rr->dnskey.algorithm = a;
+                rr->dnskey.key_size = l;
+                rr->dnskey.key = k;
+                k = NULL;
+
+        } else {
+                log_warning("RR type %s is not supported, ignoring line %s:%u.", type, path, line);
+                return -EINVAL;
+        }
+
+        if (!isempty(p)) {
+                log_warning("Trailing garbage on line %s:%u, ignoring line.", path, line);
+                return -EINVAL;
+        }
+
+        r = hashmap_ensure_allocated(&d->positive_by_key, &dns_resource_key_hash_ops);
         if (r < 0)
                 return r;
 
+        old_answer = hashmap_get(d->positive_by_key, rr->key);
+        answer = dns_answer_ref(old_answer);
+
+        r = dns_answer_add_extend(&answer, rr, 0, DNS_ANSWER_AUTHENTICATED);
+        if (r < 0)
+                return log_error_errno(r, "Failed to add trust anchor RR: %m");
+
+        r = hashmap_replace(d->positive_by_key, rr->key, answer);
+        if (r < 0)
+                return log_error_errno(r, "Failed to add answer to trust anchor: %m");
+
+        old_answer = dns_answer_unref(old_answer);
         answer = NULL;
+
+        return 0;
+}
+
+static int dns_trust_anchor_load_negative(DnsTrustAnchor *d, const char *path, unsigned line, const char *s) {
+        _cleanup_free_ char *domain = NULL;
+        const char *p = s;
+        int r;
+
+        assert(d);
+        assert(line);
+
+        r = extract_first_word(&p, &domain, NULL, EXTRACT_QUOTES);
+        if (r < 0)
+                return log_warning_errno(r, "Unable to parse line %s:%u: %m", path, line);
+
+        if (!dns_name_is_valid(domain)) {
+                log_warning("Domain name %s is invalid, at line %s:%u, ignoring line.", domain, path, line);
+                return -EINVAL;
+        }
+
+        if (!isempty(p)) {
+                log_warning("Trailing garbage at line %s:%u, ignoring line.", path, line);
+                return -EINVAL;
+        }
+
+        r = set_ensure_allocated(&d->negative_by_name, &dns_name_hash_ops);
+        if (r < 0)
+                return r;
+
+        r = set_put(d->negative_by_name, domain);
+        if (r < 0)
+                return log_oom();
+        if (r > 0)
+                domain = NULL;
+
+        return 0;
+}
+
+static int dns_trust_anchor_load_files(
+                DnsTrustAnchor *d,
+                const char *suffix,
+                int (*loader)(DnsTrustAnchor *d, const char *path, unsigned n, const char *line)) {
+
+        _cleanup_strv_free_ char **files = NULL;
+        char **f;
+        int r;
+
+        assert(d);
+        assert(suffix);
+        assert(loader);
+
+        r = conf_files_list_nulstr(&files, suffix, NULL, trust_anchor_dirs);
+        if (r < 0)
+                return log_error_errno(r, "Failed to enumerate %s trust anchor files: %m", suffix);
+
+        STRV_FOREACH(f, files) {
+                _cleanup_fclose_ FILE *g = NULL;
+                char line[LINE_MAX];
+                unsigned n = 0;
+
+                g = fopen(*f, "r");
+                if (!g) {
+                        if (errno == ENOENT)
+                                continue;
+
+                        log_warning_errno(errno, "Failed to open %s: %m", *f);
+                        continue;
+                }
+
+                FOREACH_LINE(line, g, log_warning_errno(errno, "Failed to read %s, ignoring: %m", *f)) {
+                        char *l;
+
+                        n++;
+
+                        l = strstrip(line);
+                        if (isempty(l))
+                                continue;
+
+                        if (*l == ';')
+                                continue;
+
+                        (void) loader(d, *f, n, l);
+                }
+        }
+
+        return 0;
+}
+
+static void dns_trust_anchor_dump(DnsTrustAnchor *d) {
+        DnsAnswer *a;
+        Iterator i;
+
+        assert(d);
+
+        log_info("Positive Trust Anchors:");
+        HASHMAP_FOREACH(a, d->positive_by_key, i) {
+                DnsResourceRecord *rr;
+
+                DNS_ANSWER_FOREACH(rr, a)
+                        log_info("%s", dns_resource_record_to_string(rr));
+        }
+
+        if (!set_isempty(d->negative_by_name)) {
+                char *n;
+                log_info("Negative trust anchors:");
+
+                SET_FOREACH(n, d->negative_by_name, i)
+                        log_info("%s%s", n, endswith(n, ".") ? "" : ".");
+        }
+}
+
+int dns_trust_anchor_load(DnsTrustAnchor *d) {
+        int r;
+
+        assert(d);
+
+        /* If loading things from disk fails, we don't consider this fatal */
+        (void) dns_trust_anchor_load_files(d, ".positive", dns_trust_anchor_load_positive);
+        (void) dns_trust_anchor_load_files(d, ".negative", dns_trust_anchor_load_negative);
+
+        /* However, if the built-in DS fails, then we have a problem. */
+        r = dns_trust_anchor_add_builtin(d);
+        if (r < 0)
+                return log_error_errno(r, "Failed to add trust anchor built-in: %m");
+
+        dns_trust_anchor_dump(d);
+
         return 0;
 }
 
@@ -75,13 +373,14 @@ void dns_trust_anchor_flush(DnsTrustAnchor *d) {
 
         assert(d);
 
-        while ((a = hashmap_steal_first(d->by_key)))
+        while ((a = hashmap_steal_first(d->positive_by_key)))
                 dns_answer_unref(a);
 
-        d->by_key = hashmap_free(d->by_key);
+        d->positive_by_key = hashmap_free(d->positive_by_key);
+        d->negative_by_name = set_free_free(d->negative_by_name);
 }
 
-int dns_trust_anchor_lookup(DnsTrustAnchor *d, DnsResourceKey *key, DnsAnswer **ret) {
+int dns_trust_anchor_lookup_positive(DnsTrustAnchor *d, const DnsResourceKey *key, DnsAnswer **ret) {
         DnsAnswer *a;
 
         assert(d);
@@ -92,10 +391,17 @@ int dns_trust_anchor_lookup(DnsTrustAnchor *d, DnsResourceKey *key, DnsAnswer **
         if (!IN_SET(key->type, DNS_TYPE_DS, DNS_TYPE_DNSKEY))
                 return 0;
 
-        a = hashmap_get(d->by_key, key);
+        a = hashmap_get(d->positive_by_key, key);
         if (!a)
                 return 0;
 
         *ret = dns_answer_ref(a);
         return 1;
 }
+
+int dns_trust_anchor_lookup_negative(DnsTrustAnchor *d, const char *name) {
+        assert(d);
+        assert(name);
+
+        return set_contains(d->negative_by_name, name);
+}
diff --git a/src/resolve/resolved-dns-trust-anchor.h b/src/resolve/resolved-dns-trust-anchor.h
index 06f3723914..1140cde041 100644
--- a/src/resolve/resolved-dns-trust-anchor.h
+++ b/src/resolve/resolved-dns-trust-anchor.h
@@ -30,10 +30,12 @@ typedef struct DnsTrustAnchor DnsTrustAnchor;
 /* This contains a fixed database mapping domain names to DS or DNSKEY records. */
 
 struct DnsTrustAnchor {
-        Hashmap *by_key;
+        Hashmap *positive_by_key;
+        Set *negative_by_name;
 };
 
 int dns_trust_anchor_load(DnsTrustAnchor *d);
 void dns_trust_anchor_flush(DnsTrustAnchor *d);
 
-int dns_trust_anchor_lookup(DnsTrustAnchor *d, DnsResourceKey* key, DnsAnswer **answer);
+int dns_trust_anchor_lookup_positive(DnsTrustAnchor *d, const DnsResourceKey* key, DnsAnswer **answer);
+int dns_trust_anchor_lookup_negative(DnsTrustAnchor *d, const char *name);