resolved: add support NSEC3 proofs, as well as proofs for domains that are OK to be unsigned

This large patch adds a couple of mechanisms to ensure we get NSEC3 and
proof-of-unsigned support into place. Specifically:

- Each item in an DnsAnswer gets two bit flags now:
  DNS_ANSWER_AUTHENTICATED and DNS_ANSWER_CACHEABLE. The former is
  necessary since DNS responses might contain signed as well as unsigned
  RRsets in one, and we need to remember which ones are signed and which
  ones aren't. The latter is necessary, since not we need to keep track
  which RRsets may be cached and which ones may not be, even while
  manipulating DnsAnswer objects.

- The .n_answer_cachable of DnsTransaction is dropped now (it used to
  store how many of the first DnsAnswer entries are cachable), and
  replaced by the DNS_ANSWER_CACHABLE flag instead.

- NSEC3 proofs are implemented now (lacking support for the wildcard
  part, to be added in a later commit).

- Support for the "AD" bit has been dropped. It's unsafe, and now that
  we have end-to-end authentication we don't need it anymore.

- An auxiliary DnsTransaction of a DnsTransactions is now kept around as
  least as long as the latter stays around. We no longer remove the
  auxiliary DnsTransaction as soon as it completed. THis is necessary,
  as we now are interested not only in the RRsets it acquired but also
  in its authentication status.

16 files changed, 1038 insertions, 234 deletions

diff --git a/src/resolve/resolved-dns-answer.c b/src/resolve/resolved-dns-answer.c
index 727fa75067..cb0be7d18c 100644
--- a/src/resolve/resolved-dns-answer.c
+++ b/src/resolve/resolved-dns-answer.c
@@ -74,7 +74,7 @@ DnsAnswer *dns_answer_unref(DnsAnswer *a) {
         return NULL;
 }
 
-static int dns_answer_add_raw(DnsAnswer *a, DnsResourceRecord *rr, int ifindex) {
+static int dns_answer_add_raw(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags) {
         assert(rr);
 
         if (!a)
@@ -83,19 +83,22 @@ static int dns_answer_add_raw(DnsAnswer *a, DnsResourceRecord *rr, int ifindex)
         if (a->n_rrs >= a->n_allocated)
                 return -ENOSPC;
 
-        a->items[a->n_rrs].rr = dns_resource_record_ref(rr);
-        a->items[a->n_rrs].ifindex = ifindex;
-        a->n_rrs++;
+        a->items[a->n_rrs++] = (DnsAnswerItem) {
+                .rr = dns_resource_record_ref(rr),
+                .ifindex = ifindex,
+                .flags = flags,
+        };
 
         return 1;
 }
 
 static int dns_answer_add_raw_all(DnsAnswer *a, DnsAnswer *source) {
         DnsResourceRecord *rr;
+        DnsAnswerFlags flags;
         int ifindex, r;
 
-        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, source) {
-                r = dns_answer_add_raw(a, rr, ifindex);
+        DNS_ANSWER_FOREACH_FULL(rr, ifindex, flags, source) {
+                r = dns_answer_add_raw(a, rr, ifindex, flags);
                 if (r < 0)
                         return r;
         }
@@ -103,7 +106,7 @@ static int dns_answer_add_raw_all(DnsAnswer *a, DnsAnswer *source) {
         return 0;
 }
 
-int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex) {
+int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags) {
         unsigned i;
         int r;
 
@@ -131,19 +134,21 @@ int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex) {
                                 a->items[i].rr = rr;
                         }
 
+                        a->items[i].flags |= flags;
                         return 0;
                 }
         }
 
-        return dns_answer_add_raw(a, rr, ifindex);
+        return dns_answer_add_raw(a, rr, ifindex, flags);
 }
 
 static int dns_answer_add_all(DnsAnswer *a, DnsAnswer *b) {
         DnsResourceRecord *rr;
+        DnsAnswerFlags flags;
         int ifindex, r;
 
-        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, b) {
-                r = dns_answer_add(a, rr, ifindex);
+        DNS_ANSWER_FOREACH_FULL(rr, ifindex, flags, b) {
+                r = dns_answer_add(a, rr, ifindex, flags);
                 if (r < 0)
                         return r;
         }
@@ -151,7 +156,7 @@ static int dns_answer_add_all(DnsAnswer *a, DnsAnswer *b) {
         return 0;
 }
 
-int dns_answer_add_extend(DnsAnswer **a, DnsResourceRecord *rr, int ifindex) {
+int dns_answer_add_extend(DnsAnswer **a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags) {
         int r;
 
         assert(a);
@@ -161,7 +166,7 @@ int dns_answer_add_extend(DnsAnswer **a, DnsResourceRecord *rr, int ifindex) {
         if (r < 0)
                 return r;
 
-        return dns_answer_add(*a, rr, ifindex);
+        return dns_answer_add(*a, rr, ifindex, flags);
 }
 
 int dns_answer_add_soa(DnsAnswer *a, const char *name, uint32_t ttl) {
@@ -187,44 +192,114 @@ int dns_answer_add_soa(DnsAnswer *a, const char *name, uint32_t ttl) {
         soa->soa.expire = 1;
         soa->soa.minimum = ttl;
 
-        return dns_answer_add(a, soa, 0);
+        return dns_answer_add(a, soa, 0, DNS_ANSWER_AUTHENTICATED);
 }
 
-int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key) {
+int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key, DnsAnswerFlags *ret_flags) {
+        DnsAnswerFlags flags = 0, i_flags;
         DnsResourceRecord *i;
+        bool found = false;
         int r;
 
         assert(key);
 
-        if (!a)
-                return 0;
-
-        DNS_ANSWER_FOREACH(i, a) {
+        DNS_ANSWER_FOREACH_FLAGS(i, i_flags, a) {
                 r = dns_resource_key_match_rr(key, i, NULL);
                 if (r < 0)
                         return r;
-                if (r > 0)
+                if (r == 0)
+                        continue;
+
+                if (!ret_flags)
                         return 1;
+
+                if (found)
+                        flags &= i_flags;
+                else {
+                        flags = i_flags;
+                        found = true;
+                }
         }
 
-        return 0;
+        if (ret_flags)
+                *ret_flags = flags;
+
+        return found;
 }
 
-int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr) {
+int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr, DnsAnswerFlags *ret_flags) {
+        DnsAnswerFlags flags = 0, i_flags;
         DnsResourceRecord *i;
+        bool found = false;
         int r;
 
         assert(rr);
 
-        DNS_ANSWER_FOREACH(i, a) {
+        DNS_ANSWER_FOREACH_FLAGS(i, i_flags, a) {
                 r = dns_resource_record_equal(i, rr);
                 if (r < 0)
                         return r;
-                if (r > 0)
+                if (r == 0)
+                        continue;
+
+                if (!ret_flags)
                         return 1;
+
+                if (found)
+                        flags &= i_flags;
+                else {
+                        flags = i_flags;
+                        found = true;
+                }
         }
 
-        return 0;
+        if (ret_flags)
+                *ret_flags = flags;
+
+        return found;
+}
+
+int dns_answer_contains_key(DnsAnswer *a, const DnsResourceKey *key, DnsAnswerFlags *ret_flags) {
+        DnsAnswerFlags flags = 0, i_flags;
+        DnsResourceRecord *i;
+        bool found = false;
+        int r;
+
+        assert(key);
+
+        DNS_ANSWER_FOREACH_FLAGS(i, i_flags, a) {
+                r = dns_resource_key_equal(i->key, key);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                if (!ret_flags)
+                        return true;
+
+                if (found)
+                        flags &= i_flags;
+                else {
+                        flags = i_flags;
+                        found = true;
+                }
+        }
+
+        if (ret_flags)
+                *ret_flags = flags;
+
+        return found;
+}
+
+int dns_answer_contains_nsec_or_nsec3(DnsAnswer *a) {
+        DnsResourceRecord *i;
+
+        DNS_ANSWER_FOREACH(i, a) {
+                if (IN_SET(i->key->type, DNS_TYPE_NSEC, DNS_TYPE_NSEC3))
+                        return true;
+        }
+
+        return false;
 }
 
 int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret) {
@@ -251,8 +326,9 @@ int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceReco
         return 0;
 }
 
-int dns_answer_find_cname_or_dname(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret) {
+int dns_answer_find_cname_or_dname(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret, DnsAnswerFlags *flags) {
         DnsResourceRecord *rr;
+        DnsAnswerFlags rr_flags;
         int r;
 
         assert(key);
@@ -261,13 +337,15 @@ int dns_answer_find_cname_or_dname(DnsAnswer *a, const DnsResourceKey *key, DnsR
         if (key->type == DNS_TYPE_CNAME || key->type == DNS_TYPE_DNAME)
                 return 0;
 
-        DNS_ANSWER_FOREACH(rr, a) {
+        DNS_ANSWER_FOREACH_FLAGS(rr, rr_flags, a) {
                 r = dns_resource_key_match_cname_or_dname(key, rr->key, NULL);
                 if (r < 0)
                         return r;
                 if (r > 0) {
                         if (ret)
                                 *ret = rr;
+                        if (flags)
+                                *flags = rr_flags;
                         return 1;
                 }
         }
@@ -359,20 +437,21 @@ int dns_answer_remove_by_key(DnsAnswer **a, const DnsResourceKey *key) {
 
         if ((*a)->n_ref > 1) {
                 _cleanup_(dns_answer_unrefp) DnsAnswer *copy = NULL;
+                DnsAnswerFlags flags;
                 int ifindex;
 
                 copy = dns_answer_new((*a)->n_rrs);
                 if (!copy)
                         return -ENOMEM;
 
-                DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, *a) {
+                DNS_ANSWER_FOREACH_FULL(rr, ifindex, flags, *a) {
                         r = dns_resource_key_equal(rr->key, key);
                         if (r < 0)
                                 return r;
                         if (r > 0)
                                 continue;
 
-                        r = dns_answer_add_raw(copy, rr, ifindex);
+                        r = dns_answer_add_raw(copy, rr, ifindex, flags);
                         if (r < 0)
                                 return r;
                 }
@@ -410,16 +489,17 @@ int dns_answer_remove_by_key(DnsAnswer **a, const DnsResourceKey *key) {
         return 1;
 }
 
-int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKey *key) {
+int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKey *key, DnsAnswerFlags or_flags) {
         DnsResourceRecord *rr_source;
         int ifindex_source, r;
+        DnsAnswerFlags flags_source;
 
         assert(a);
         assert(key);
 
         /* Copy all RRs matching the specified key from source into *a */
 
-        DNS_ANSWER_FOREACH_IFINDEX(rr_source, ifindex_source, source) {
+        DNS_ANSWER_FOREACH_FULL(rr_source, ifindex_source, flags_source, source) {
 
                 r = dns_resource_key_equal(rr_source->key, key);
                 if (r < 0)
@@ -432,7 +512,7 @@ int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKe
                 if (r < 0)
                         return r;
 
-                r = dns_answer_add(*a, rr_source, ifindex_source);
+                r = dns_answer_add(*a, rr_source, ifindex_source, flags_source|or_flags);
                 if (r < 0)
                         return r;
         }
@@ -440,6 +520,20 @@ int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKe
         return 0;
 }
 
+int dns_answer_move_by_key(DnsAnswer **to, DnsAnswer **from, const DnsResourceKey *key, DnsAnswerFlags or_flags) {
+        int r;
+
+        assert(to);
+        assert(from);
+        assert(key);
+
+        r = dns_answer_copy_by_key(to, *from, key, or_flags);
+        if (r < 0)
+                return r;
+
+        return dns_answer_remove_by_key(from, key);
+}
+
 void dns_answer_order_by_scope(DnsAnswer *a, bool prefer_link_local) {
         DnsAnswerItem *items;
         unsigned i, start, end;
diff --git a/src/resolve/resolved-dns-answer.h b/src/resolve/resolved-dns-answer.h
index 56b462ed7e..569f283d03 100644
--- a/src/resolve/resolved-dns-answer.h
+++ b/src/resolve/resolved-dns-answer.h
@@ -32,11 +32,17 @@ typedef struct DnsAnswerItem DnsAnswerItem;
  * can qualify A and AAAA RRs referring to a local link with the
  * right ifindex.
  *
- * Note that we usually encode the empty answer as a simple NULL. */
+ * Note that we usually encode the the empty DnsAnswer object as a simple NULL. */
+
+typedef enum DnsAnswerFlags {
+        DNS_ANSWER_AUTHENTICATED = 1,
+        DNS_ANSWER_CACHEABLE     = 2,
+} DnsAnswerFlags;
 
 struct DnsAnswerItem {
         DnsResourceRecord *rr;
         int ifindex;
+        DnsAnswerFlags flags;
 };
 
 struct DnsAnswer {
@@ -49,15 +55,17 @@ DnsAnswer *dns_answer_new(unsigned n);
 DnsAnswer *dns_answer_ref(DnsAnswer *a);
 DnsAnswer *dns_answer_unref(DnsAnswer *a);
 
-int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex);
-int dns_answer_add_extend(DnsAnswer **a, DnsResourceRecord *rr, int ifindex);
+int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags);
+int dns_answer_add_extend(DnsAnswer **a, DnsResourceRecord *rr, int ifindex, DnsAnswerFlags flags);
 int dns_answer_add_soa(DnsAnswer *a, const char *name, uint32_t ttl);
 
-int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key);
-int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr);
+int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key, DnsAnswerFlags *combined_flags);
+int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr, DnsAnswerFlags *combined_flags);
+int dns_answer_contains_key(DnsAnswer *a, const DnsResourceKey *key, DnsAnswerFlags *combined_flags);
+int dns_answer_contains_nsec_or_nsec3(DnsAnswer *a);
 
 int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret);
-int dns_answer_find_cname_or_dname(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret);
+int dns_answer_find_cname_or_dname(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret, DnsAnswerFlags *flags);
 
 int dns_answer_merge(DnsAnswer *a, DnsAnswer *b, DnsAnswer **ret);
 int dns_answer_extend(DnsAnswer **a, DnsAnswer *b);
@@ -68,7 +76,8 @@ int dns_answer_reserve(DnsAnswer **a, unsigned n_free);
 int dns_answer_reserve_or_clone(DnsAnswer **a, unsigned n_free);
 
 int dns_answer_remove_by_key(DnsAnswer **a, const DnsResourceKey *key);
-int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKey *key);
+int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKey *key, DnsAnswerFlags or_flags);
+int dns_answer_move_by_key(DnsAnswer **to, DnsAnswer **from, const DnsResourceKey *key, DnsAnswerFlags or_flags);
 
 static inline unsigned dns_answer_size(DnsAnswer *a) {
         return a ? a->n_rrs : 0;
@@ -93,6 +102,36 @@ DEFINE_TRIVIAL_CLEANUP_FUNC(DnsAnswer*, dns_answer_unref);
                                 0;                                      \
                         });                                             \
              (a) && (UNIQ_T(i, q) < (a)->n_rrs);                        \
-             UNIQ_T(i, q)++, (kk) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].rr : NULL), (ifi) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].ifindex : 0))
+             UNIQ_T(i, q)++,                                            \
+                     (kk) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].rr : NULL), \
+                     (ifi) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].ifindex : 0))
 
 #define DNS_ANSWER_FOREACH_IFINDEX(kk, ifindex, a) _DNS_ANSWER_FOREACH_IFINDEX(UNIQ, kk, ifindex, a)
+
+#define _DNS_ANSWER_FOREACH_FLAGS(q, kk, fl, a)                         \
+        for (unsigned UNIQ_T(i, q) = ({                                 \
+                                (kk) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].rr : NULL; \
+                                (fl) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].flags : 0; \
+                                0;                                      \
+                        });                                             \
+             (a) && (UNIQ_T(i, q) < (a)->n_rrs);                        \
+             UNIQ_T(i, q)++,                                            \
+                     (kk) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].rr : NULL), \
+                     (fl) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].flags : 0))
+
+#define DNS_ANSWER_FOREACH_FLAGS(kk, flags, a) _DNS_ANSWER_FOREACH_FLAGS(UNIQ, kk, flags, a)
+
+#define _DNS_ANSWER_FOREACH_FULL(q, kk, ifi, fl, a)                     \
+        for (unsigned UNIQ_T(i, q) = ({                                 \
+                                (kk) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].rr : NULL; \
+                                (ifi) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].ifindex : 0; \
+                                (fl) = ((a) && (a)->n_rrs > 0) ? (a)->items[0].flags : 0; \
+                                0;                                      \
+                        });                                             \
+             (a) && (UNIQ_T(i, q) < (a)->n_rrs);                        \
+             UNIQ_T(i, q)++,                                            \
+                     (kk) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].rr : NULL), \
+                     (ifi) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].ifindex : 0), \
+                     (fl) = ((UNIQ_T(i, q) < (a)->n_rrs) ? (a)->items[UNIQ_T(i, q)].flags : 0))
+
+#define DNS_ANSWER_FOREACH_FULL(kk, ifindex, flags, a) _DNS_ANSWER_FOREACH_FULL(UNIQ, kk, ifindex, flags, a)
diff --git a/src/resolve/resolved-dns-cache.c b/src/resolve/resolved-dns-cache.c
index 62713b5a6a..a8d612794c 100644
--- a/src/resolve/resolved-dns-cache.c
+++ b/src/resolve/resolved-dns-cache.c
@@ -436,14 +436,14 @@ int dns_cache_put(
                 DnsResourceKey *key,
                 int rcode,
                 DnsAnswer *answer,
-                unsigned max_rrs,
                 bool authenticated,
                 usec_t timestamp,
                 int owner_family,
                 const union in_addr_union *owner_address) {
 
         DnsResourceRecord *soa = NULL, *rr;
-        unsigned cache_keys, i;
+        DnsAnswerFlags flags;
+        unsigned cache_keys;
         int r;
 
         assert(c);
@@ -468,9 +468,13 @@ int dns_cache_put(
                 return 0;
         }
 
-        DNS_ANSWER_FOREACH(rr, answer)
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                if ((flags & DNS_ANSWER_CACHEABLE) == 0)
+                        continue;
+
                 if (rr->key->cache_flush)
                         dns_cache_remove(c, rr->key);
+        }
 
         /* We only care for positive replies and NXDOMAINs, on all
          * other replies we will simply flush the respective entries,
@@ -480,7 +484,6 @@ int dns_cache_put(
                 return 0;
 
         cache_keys = answer->n_rrs;
-
         if (key)
                 cache_keys ++;
 
@@ -491,10 +494,12 @@ int dns_cache_put(
                 timestamp = now(clock_boottime_or_monotonic());
 
         /* Second, add in positive entries for all contained RRs */
-        for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
-                rr = answer->items[i].rr;
 
-                r = dns_cache_put_positive(c, rr, authenticated, timestamp, owner_family, owner_address);
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                if ((flags & DNS_ANSWER_CACHEABLE) == 0)
+                        continue;
+
+                r = dns_cache_put_positive(c, rr, flags & DNS_ANSWER_AUTHENTICATED, timestamp, owner_family, owner_address);
                 if (r < 0)
                         goto fail;
         }
@@ -503,7 +508,7 @@ int dns_cache_put(
                 return 0;
 
         /* Third, add in negative entries if the key has no RR */
-        r = dns_answer_match_key(answer, key);
+        r = dns_answer_match_key(answer, key, NULL);
         if (r < 0)
                 goto fail;
         if (r > 0)
@@ -512,7 +517,7 @@ int dns_cache_put(
         /* But not if it has a matching CNAME/DNAME (the negative
          * caching will be done on the canonical name, not on the
          * alias) */
-        r = dns_answer_find_cname_or_dname(answer, key, NULL);
+        r = dns_answer_find_cname_or_dname(answer, key, NULL, NULL);
         if (r < 0)
                 goto fail;
         if (r > 0)
@@ -541,8 +546,12 @@ fail:
         if (key)
                 dns_cache_remove(c, key);
 
-        for (i = 0; i < answer->n_rrs; i++)
-                dns_cache_remove(c, answer->items[i].rr->key);
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                if ((flags & DNS_ANSWER_CACHEABLE) == 0)
+                        continue;
+
+                dns_cache_remove(c, rr->key);
+        }
 
         return r;
 }
@@ -722,7 +731,7 @@ int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **r
                 if (!j->rr)
                         continue;
 
-                r = dns_answer_add(answer, j->rr, 0);
+                r = dns_answer_add(answer, j->rr, 0, have_authenticated && !have_non_authenticated ? DNS_ANSWER_AUTHENTICATED : 0);
                 if (r < 0)
                         return r;
         }
diff --git a/src/resolve/resolved-dns-cache.h b/src/resolve/resolved-dns-cache.h
index 0f28bbe543..856c975299 100644
--- a/src/resolve/resolved-dns-cache.h
+++ b/src/resolve/resolved-dns-cache.h
@@ -39,7 +39,7 @@ typedef struct DnsCache {
 void dns_cache_flush(DnsCache *c);
 void dns_cache_prune(DnsCache *c);
 
-int dns_cache_put(DnsCache *c, DnsResourceKey *key, int rcode, DnsAnswer *answer, unsigned max_rrs, bool authenticated, usec_t timestamp, int owner_family, const union in_addr_union *owner_address);
+int dns_cache_put(DnsCache *c, DnsResourceKey *key, int rcode, DnsAnswer *answer, bool authenticated, usec_t timestamp, int owner_family, const union in_addr_union *owner_address);
 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **answer, bool *authenticated);
 
 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address);
diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index ed126505ad..d1d2faca06 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -499,7 +499,7 @@ int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnske
         return dns_name_equal(DNS_RESOURCE_KEY_NAME(dnskey->key), rrsig->rrsig.signer);
 }
 
-int dnssec_key_match_rrsig(DnsResourceKey *key, DnsResourceRecord *rrsig) {
+int dnssec_key_match_rrsig(const DnsResourceKey *key, DnsResourceRecord *rrsig) {
         assert(key);
         assert(rrsig);
 
@@ -529,7 +529,7 @@ int dnssec_verify_rrset_search(
         assert(key);
         assert(result);
 
-        /* Verifies all RRs from "a" that match the key "key", against DNSKEY and DS RRs in "validated_dnskeys" */
+        /* Verifies all RRs from "a" that match the key "key" against DNSKEYs in "validated_dnskeys" */
 
         if (!a || a->n_rrs <= 0)
                 return -ENODATA;
@@ -537,6 +537,7 @@ int dnssec_verify_rrset_search(
         /* Iterate through each RRSIG RR. */
         DNS_ANSWER_FOREACH(rrsig, a) {
                 DnsResourceRecord *dnskey;
+                DnsAnswerFlags flags;
 
                 /* Is this an RRSIG RR that applies to RRs matching our key? */
                 r = dnssec_key_match_rrsig(key, rrsig);
@@ -548,9 +549,12 @@ int dnssec_verify_rrset_search(
                 found_rrsig = true;
 
                 /* Look for a matching key */
-                DNS_ANSWER_FOREACH(dnskey, validated_dnskeys) {
+                DNS_ANSWER_FOREACH_FLAGS(dnskey, flags, validated_dnskeys) {
                         DnssecResult one_result;
 
+                        if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                                continue;
+
                         /* Is this a DNSKEY RR that matches they key of our RRSIG? */
                         r = dnssec_rrsig_match_dnskey(rrsig, dnskey);
                         if (r < 0)
@@ -626,6 +630,23 @@ int dnssec_verify_rrset_search(
         return 0;
 }
 
+int dnssec_has_rrsig(DnsAnswer *a, const DnsResourceKey *key) {
+        DnsResourceRecord *rr;
+        int r;
+
+        /* Checks whether there's at least one RRSIG in 'a' that proctects RRs of the specified key */
+
+        DNS_ANSWER_FOREACH(rr, a) {
+                r = dnssec_key_match_rrsig(key, rr);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        return 1;
+        }
+
+        return 0;
+}
+
 int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
         size_t c = 0;
         int r;
@@ -776,6 +797,7 @@ finish:
 
 int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_ds) {
         DnsResourceRecord *ds;
+        DnsAnswerFlags flags;
         int r;
 
         assert(dnskey);
@@ -783,7 +805,10 @@ int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_
         if (dnskey->key->type != DNS_TYPE_DNSKEY)
                 return 0;
 
-        DNS_ANSWER_FOREACH(ds, validated_ds) {
+        DNS_ANSWER_FOREACH_FLAGS(ds, flags, validated_ds) {
+
+                if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                        continue;
 
                 if (ds->key->type != DNS_TYPE_DS)
                         continue;
@@ -866,114 +891,218 @@ finish:
         return r;
 }
 
-int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result) {
+static int dnssec_test_nsec3(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result) {
+        _cleanup_free_ char *next_closer_domain = NULL, *l = NULL;
+        uint8_t hashed[DNSSEC_HASH_SIZE_MAX];
+        const char *p, *pp = NULL;
         DnsResourceRecord *rr;
-        int r;
+        DnsAnswerFlags flags;
+        int hashed_size, r;
 
         assert(key);
         assert(result);
 
-        /* Look for any NSEC/NSEC3 RRs that say something about the specified key. */
-
-        DNS_ANSWER_FOREACH(rr, answer) {
+        /* First step, look for the closest encloser NSEC3 RR in 'answer' that matches 'key' */
+        p = DNS_RESOURCE_KEY_NAME(key);
+        for (;;) {
+                DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                        _cleanup_free_ char *hashed_domain = NULL, *label = NULL;
 
-                if (rr->key->class != key->class)
-                        continue;
+                        if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                                continue;
 
-                switch (rr->key->type) {
+                        if (rr->key->type != DNS_TYPE_NSEC3)
+                                continue;
 
-                case DNS_TYPE_NSEC:
+                        /* RFC  5155, Section 8.2 says we MUST ignore NSEC3 RRs with flags != 0 or 1 */
+                        if (!IN_SET(rr->nsec3.flags, 0, 1))
+                                continue;
 
-                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
+                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(rr->key), p);
                         if (r < 0)
                                 return r;
-                        if (r > 0) {
-                                *result = bitmap_isset(rr->nsec.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
+                        if (r == 0)
+                                continue;
+
+                        hashed_size = dnssec_nsec3_hash(rr, p, hashed);
+                        if (hashed_size == -EOPNOTSUPP) {
+                                *result = DNSSEC_NSEC_UNSUPPORTED_ALGORITHM;
                                 return 0;
                         }
+                        if (hashed_size < 0)
+                                return hashed_size;
+                        if (rr->nsec3.next_hashed_name_size != (size_t) hashed_size)
+                                return -EBADMSG;
 
-                        r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key), rr->nsec.next_domain_name);
+                        label = base32hexmem(hashed, hashed_size, false);
+                        if (!label)
+                                return -ENOMEM;
+
+                        hashed_domain = strjoin(label, ".", p, NULL);
+                        if (!hashed_domain)
+                                return -ENOMEM;
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), hashed_domain);
                         if (r < 0)
                                 return r;
-                        if (r > 0) {
-                                *result = DNSSEC_NSEC_NXDOMAIN;
-                                return 0;
-                        }
+                        if (r > 0)
+                                goto found;
+                }
+
+                /* We didn't find the closest encloser with this name,
+                 * but let's remember this domain name, it might be
+                 * the next closer name */
+
+                pp = p;
+
+                /* Strip one label from the front */
+                r = dns_name_parent(&p);
+                if (r < 0)
+                        return r;
+                if (r == 0)
                         break;
+        }
 
-                case DNS_TYPE_NSEC3: {
-                        _cleanup_free_ void *decoded = NULL;
-                        size_t decoded_size;
-                        char label[DNS_LABEL_MAX];
-                        uint8_t hashed[DNSSEC_HASH_SIZE_MAX];
-                        int label_length, c, q;
-                        const char *p;
-                        bool covered;
+        *result = DNSSEC_NSEC_NO_RR;
+        return 0;
 
-                        /* RFC  5155, Section 8.2 says we MUST ignore NSEC3 RRs with flags != 0 or 1 */
-                        if (!IN_SET(rr->nsec3.flags, 0, 1))
-                                continue;
+found:
+        /* We found a closest encloser in 'p'; next closer is 'pp' */
 
-                        p = DNS_RESOURCE_KEY_NAME(rr->key);
-                        label_length = dns_label_unescape(&p, label, sizeof(label));
-                        if (label_length < 0)
-                                return label_length;
-                        if (label_length == 0)
-                                continue;
+        /* Ensure this is not a DNAME domain, see RFC5155, section 8.3. */
+        if (bitmap_isset(rr->nsec3.types, DNS_TYPE_DNAME))
+                return -EBADMSG;
 
-                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(key), p);
-                        if (r < 0)
-                                return r;
-                        if (r == 0)
-                                continue;
+        /* Ensure that this data is from the delegated domain
+         * (i.e. originates from the "lower" DNS server), and isn't
+         * just glue records (i.e. doesn't originate from the "upper"
+         * DNS server). */
+        if (bitmap_isset(rr->nsec3.types, DNS_TYPE_NS) &&
+            !bitmap_isset(rr->nsec3.types, DNS_TYPE_SOA))
+                return -EBADMSG;
 
-                        r = unbase32hexmem(label, label_length, false, &decoded, &decoded_size);
-                        if (r == -EINVAL)
-                                continue;
-                        if (r < 0)
-                                return r;
+        if (!pp) {
+                /* No next closer NSEC3 RR. That means there's a direct NSEC3 RR for our key. */
+                *result = bitmap_isset(rr->nsec3.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
+                return 0;
+        }
 
-                        if (decoded_size != rr->nsec3.next_hashed_name_size)
-                                continue;
+        r = dnssec_nsec3_hash(rr, pp, hashed);
+        if (r < 0)
+                return r;
+        if (r != hashed_size)
+                return -EBADMSG;
 
-                        c = memcmp(decoded, rr->nsec3.next_hashed_name, decoded_size);
-                        if (c == 0)
-                                continue;
+        l = base32hexmem(hashed, hashed_size, false);
+        if (!l)
+                return -ENOMEM;
 
-                        r = dnssec_nsec3_hash(rr, DNS_RESOURCE_KEY_NAME(key), hashed);
-                        /* RFC 5155, Section 8.1 says we MUST ignore NSEC3 RRs with unknown algorithms */
-                        if (r == -EOPNOTSUPP)
-                                continue;
-                        if (r < 0)
-                                return r;
-                        if ((size_t) r != decoded_size)
-                                continue;
+        next_closer_domain = strjoin(l, ".", p, NULL);
+        if (!next_closer_domain)
+                return -ENOMEM;
 
-                        r = memcmp(decoded, hashed, decoded_size);
-                        if (r == 0) {
-                                *result = bitmap_isset(rr->nsec3.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
-                                return 0;
-                        }
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                _cleanup_free_ char *label = NULL, *next_hashed_domain = NULL;
+                const char *nsec3_parent;
+
+                if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                        continue;
 
-                        q = memcmp(hashed, rr->nsec3.next_hashed_name, decoded_size);
+                if (rr->key->type != DNS_TYPE_NSEC3)
+                        continue;
 
-                        covered = c < 0 ?
-                                r < 0 && q < 0 :
-                                q < 0 || r < 0;
+                /* RFC  5155, Section 8.2 says we MUST ignore NSEC3 RRs with flags != 0 or 1 */
+                if (!IN_SET(rr->nsec3.flags, 0, 1))
+                        continue;
 
-                        if (covered) {
+                nsec3_parent = DNS_RESOURCE_KEY_NAME(rr->key);
+                r = dns_name_parent(&nsec3_parent);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                r = dns_name_equal(p, nsec3_parent);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                label = base32hexmem(rr->nsec3.next_hashed_name, rr->nsec3.next_hashed_name_size, false);
+                if (!label)
+                        return -ENOMEM;
+
+                next_hashed_domain = strjoin(label, ".", p, NULL);
+                if (!next_hashed_domain)
+                        return -ENOMEM;
+
+                r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), next_closer_domain, next_hashed_domain);
+                if (r < 0)
+                        return r;
+                if (r > 0) {
+                        if (rr->nsec3.flags & 1)
+                                *result = DNSSEC_NSEC_OPTOUT;
+                        else
                                 *result = DNSSEC_NSEC_NXDOMAIN;
+
+                        return 1;
+                }
+        }
+
+        *result = DNSSEC_NSEC_NO_RR;
+        return 0;
+}
+
+int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result) {
+        DnsResourceRecord *rr;
+        bool have_nsec3 = false;
+        DnsAnswerFlags flags;
+        int r;
+
+        assert(key);
+        assert(result);
+
+        /* Look for any NSEC/NSEC3 RRs that say something about the specified key. */
+
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+
+                if (rr->key->class != key->class)
+                        continue;
+
+                if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                        continue;
+
+                switch (rr->key->type) {
+
+                case DNS_TYPE_NSEC:
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
+                        if (r < 0)
+                                return r;
+                        if (r > 0) {
+                                *result = bitmap_isset(rr->nsec.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
                                 return 0;
                         }
 
+                        r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key), rr->nsec.next_domain_name);
+                        if (r < 0)
+                                return r;
+                        if (r > 0) {
+                                *result = DNSSEC_NSEC_NXDOMAIN;
+                                return 0;
+                        }
                         break;
-                }
 
-                default:
+                case DNS_TYPE_NSEC3:
+                        have_nsec3 = true;
                         break;
                 }
         }
 
+        /* OK, this was not sufficient. Let's see if NSEC3 can help. */
+        if (have_nsec3)
+                return dnssec_test_nsec3(answer, key, result);
+
         /* No approproate NSEC RR found, report this. */
         *result = DNSSEC_NSEC_NO_RR;
         return 0;
@@ -981,7 +1110,6 @@ int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *r
 
 static const char* const dnssec_mode_table[_DNSSEC_MODE_MAX] = {
         [DNSSEC_NO] = "no",
-        [DNSSEC_TRUST] = "trust",
         [DNSSEC_YES] = "yes",
 };
 DEFINE_STRING_TABLE_LOOKUP(dnssec_mode, DnssecMode);
diff --git a/src/resolve/resolved-dns-dnssec.h b/src/resolve/resolved-dns-dnssec.h
index 442e301302..d17d5142f5 100644
--- a/src/resolve/resolved-dns-dnssec.h
+++ b/src/resolve/resolved-dns-dnssec.h
@@ -32,9 +32,6 @@ enum DnssecMode {
         /* No DNSSEC validation is done */
         DNSSEC_NO,
 
-        /* Trust the AD bit sent by the server. UNSAFE! */
-        DNSSEC_TRUST,
-
         /* Validate locally, if the server knows DO, but if not, don't. Don't trust the AD bit */
         DNSSEC_YES,
 
@@ -67,7 +64,7 @@ enum DnssecResult {
 #define DNSSEC_HASH_SIZE_MAX (MAX(20, 32))
 
 int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnskey);
-int dnssec_key_match_rrsig(DnsResourceKey *key, DnsResourceRecord *rrsig);
+int dnssec_key_match_rrsig(const DnsResourceKey *key, DnsResourceRecord *rrsig);
 
 int dnssec_verify_rrset(DnsAnswer *answer, DnsResourceKey *key, DnsResourceRecord *rrsig, DnsResourceRecord *dnskey, usec_t realtime, DnssecResult *result);
 int dnssec_verify_rrset_search(DnsAnswer *answer, DnsResourceKey *key, DnsAnswer *validated_dnskeys, usec_t realtime, DnssecResult *result);
@@ -75,6 +72,8 @@ int dnssec_verify_rrset_search(DnsAnswer *answer, DnsResourceKey *key, DnsAnswer
 int dnssec_verify_dnskey(DnsResourceRecord *dnskey, DnsResourceRecord *ds);
 int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_ds);
 
+int dnssec_has_rrsig(DnsAnswer *a, const DnsResourceKey *key);
+
 uint16_t dnssec_keytag(DnsResourceRecord *dnskey);
 
 int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max);
@@ -83,9 +82,11 @@ int dnssec_nsec3_hash(DnsResourceRecord *nsec3, const char *name, void *ret);
 
 typedef enum DnssecNsecResult {
         DNSSEC_NSEC_NO_RR,     /* No suitable NSEC/NSEC3 RR found */
+        DNSSEC_NSEC_UNSUPPORTED_ALGORITHM,
         DNSSEC_NSEC_NXDOMAIN,
         DNSSEC_NSEC_NODATA,
         DNSSEC_NSEC_FOUND,
+        DNSSEC_NSEC_OPTOUT,
 } DnssecNsecResult;
 
 int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result);
diff --git a/src/resolve/resolved-dns-packet.c b/src/resolve/resolved-dns-packet.c
index c34ecc44f8..c8dd5fdeee 100644
--- a/src/resolve/resolved-dns-packet.c
+++ b/src/resolve/resolved-dns-packet.c
@@ -2018,7 +2018,17 @@ int dns_packet_extract(DnsPacket *p) {
 
                                 p->opt = dns_resource_record_ref(rr);
                         } else {
-                                r = dns_answer_add(answer, rr, p->ifindex);
+
+                                /* According to RFC 4795, section
+                                 * 2.9. only the RRs from the Answer
+                                 * section shall be cached. Hence mark
+                                 * only those RRs as cacheable by
+                                 * default, but not the ones from the
+                                 * Additional or Authority
+                                 * sections. */
+
+                                r = dns_answer_add(answer, rr, p->ifindex,
+                                                   i < DNS_PACKET_ANCOUNT(p) ? DNS_ANSWER_CACHEABLE : 0);
                                 if (r < 0)
                                         goto finish;
                         }
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index 405882a6ea..9e8131386c 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -554,7 +554,7 @@ static int synthesize_localhost_rr(DnsQuery *q, DnsResourceKey *key, DnsAnswer *
 
                 rr->a.in_addr.s_addr = htobe32(INADDR_LOOPBACK);
 
-                r = dns_answer_add(*answer, rr, SYNTHESIZE_IFINDEX(q->ifindex));
+                r = dns_answer_add(*answer, rr, SYNTHESIZE_IFINDEX(q->ifindex), DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
         }
@@ -568,7 +568,7 @@ static int synthesize_localhost_rr(DnsQuery *q, DnsResourceKey *key, DnsAnswer *
 
                 rr->aaaa.in6_addr = in6addr_loopback;
 
-                r = dns_answer_add(*answer, rr, SYNTHESIZE_IFINDEX(q->ifindex));
+                r = dns_answer_add(*answer, rr, SYNTHESIZE_IFINDEX(q->ifindex), DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
         }
@@ -576,7 +576,7 @@ static int synthesize_localhost_rr(DnsQuery *q, DnsResourceKey *key, DnsAnswer *
         return 0;
 }
 
-static int answer_add_ptr(DnsAnswer **answer, const char *from, const char *to, int ifindex) {
+static int answer_add_ptr(DnsAnswer **answer, const char *from, const char *to, int ifindex, DnsAnswerFlags flags) {
         _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
 
         rr = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_PTR, from);
@@ -587,7 +587,7 @@ static int answer_add_ptr(DnsAnswer **answer, const char *from, const char *to,
         if (!rr->ptr.name)
                 return -ENOMEM;
 
-        return dns_answer_add(*answer, rr, ifindex);
+        return dns_answer_add(*answer, rr, ifindex, flags);
 }
 
 static int synthesize_localhost_ptr(DnsQuery *q, DnsResourceKey *key, DnsAnswer **answer) {
@@ -597,12 +597,12 @@ static int synthesize_localhost_ptr(DnsQuery *q, DnsResourceKey *key, DnsAnswer
         assert(key);
         assert(answer);
 
-        r = dns_answer_reserve(answer, 1);
-        if (r < 0)
-                return r;
-
         if (IN_SET(key->type, DNS_TYPE_PTR, DNS_TYPE_ANY)) {
-                r = answer_add_ptr(answer, DNS_RESOURCE_KEY_NAME(key), "localhost", SYNTHESIZE_IFINDEX(q->ifindex));
+                r = dns_answer_reserve(answer, 1);
+                if (r < 0)
+                        return r;
+
+                r = answer_add_ptr(answer, DNS_RESOURCE_KEY_NAME(key), "localhost", SYNTHESIZE_IFINDEX(q->ifindex), DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
         }
@@ -633,7 +633,7 @@ static int answer_add_addresses_rr(
                 if (r < 0)
                         return r;
 
-                r = dns_answer_add(*answer, rr, addresses[j].ifindex);
+                r = dns_answer_add(*answer, rr, addresses[j].ifindex, DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
         }
@@ -674,7 +674,7 @@ static int answer_add_addresses_ptr(
                 if (r < 0)
                         return r;
 
-                r = dns_answer_add(*answer, rr, addresses[j].ifindex);
+                r = dns_answer_add(*answer, rr, addresses[j].ifindex, DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
         }
@@ -740,15 +740,15 @@ static int synthesize_system_hostname_ptr(DnsQuery *q, int af, const union in_ad
                 if (r < 0)
                         return r;
 
-                r = answer_add_ptr(answer, "2.0.0.127.in-addr.arpa", q->manager->llmnr_hostname, SYNTHESIZE_IFINDEX(q->ifindex));
+                r = answer_add_ptr(answer, "2.0.0.127.in-addr.arpa", q->manager->llmnr_hostname, SYNTHESIZE_IFINDEX(q->ifindex), DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
 
-                r = answer_add_ptr(answer, "2.0.0.127.in-addr.arpa", q->manager->mdns_hostname, SYNTHESIZE_IFINDEX(q->ifindex));
+                r = answer_add_ptr(answer, "2.0.0.127.in-addr.arpa", q->manager->mdns_hostname, SYNTHESIZE_IFINDEX(q->ifindex), DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
 
-                r = answer_add_ptr(answer, "2.0.0.127.in-addr.arpa", "localhost", SYNTHESIZE_IFINDEX(q->ifindex));
+                r = answer_add_ptr(answer, "2.0.0.127.in-addr.arpa", "localhost", SYNTHESIZE_IFINDEX(q->ifindex), DNS_ANSWER_AUTHENTICATED);
                 if (r < 0)
                         return r;
 
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index 74c9d87319..60a614fb6d 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -184,7 +184,7 @@ int dns_resource_key_equal(const DnsResourceKey *a, const DnsResourceKey *b) {
         return 1;
 }
 
-int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr, const char *search_domain) {
+int dns_resource_key_match_rr(const DnsResourceKey *key, DnsResourceRecord *rr, const char *search_domain) {
         int r;
 
         assert(key);
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index 632ee59994..8d2bc2dc21 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -245,7 +245,7 @@ DnsResourceKey* dns_resource_key_ref(DnsResourceKey *key);
 DnsResourceKey* dns_resource_key_unref(DnsResourceKey *key);
 bool dns_resource_key_is_address(const DnsResourceKey *key);
 int dns_resource_key_equal(const DnsResourceKey *a, const DnsResourceKey *b);
-int dns_resource_key_match_rr(const DnsResourceKey *key, const DnsResourceRecord *rr, const char *search_domain);
+int dns_resource_key_match_rr(const DnsResourceKey *key, DnsResourceRecord *rr, const char *search_domain);
 int dns_resource_key_match_cname_or_dname(const DnsResourceKey *key, const DnsResourceKey *cname, const char *search_domain);
 int dns_resource_key_match_soa(const DnsResourceKey *key, const DnsResourceKey *soa);
 int dns_resource_key_to_string(const DnsResourceKey *key, char **ret);
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index 5b6846f008..5e66a7af33 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -385,7 +385,6 @@ static int dns_transaction_open_tcp(DnsTransaction *t) {
         t->server = dns_server_ref(server);
         t->received = dns_packet_unref(t->received);
         t->answer = dns_answer_unref(t->answer);
-        t->n_answer_cacheable = 0;
         t->answer_rcode = 0;
         t->stream->complete = on_stream_complete;
         t->stream->transaction = t;
@@ -428,20 +427,32 @@ static void dns_transaction_cache_answer(DnsTransaction *t) {
                       t->key,
                       t->answer_rcode,
                       t->answer,
-                      t->n_answer_cacheable,
                       t->answer_authenticated,
                       0,
                       t->received->family,
                       &t->received->sender);
 }
 
+static bool dns_transaction_dnssec_is_live(DnsTransaction *t) {
+        DnsTransaction *dt;
+        Iterator i;
+
+        assert(t);
+
+        SET_FOREACH(dt, t->dnssec_transactions, i)
+                if (DNS_TRANSACTION_IS_LIVE(dt->state))
+                        return true;
+
+        return false;
+}
+
 static void dns_transaction_process_dnssec(DnsTransaction *t) {
         int r;
 
         assert(t);
 
         /* Are there ongoing DNSSEC transactions? If so, let's wait for them. */
-        if (!set_isempty(t->dnssec_transactions))
+        if (dns_transaction_dnssec_is_live(t))
                 return;
 
         /* All our auxiliary DNSSEC transactions are complete now. Try
@@ -452,7 +463,10 @@ static void dns_transaction_process_dnssec(DnsTransaction *t) {
                 return;
         }
 
-        if (!IN_SET(t->dnssec_result, _DNSSEC_RESULT_INVALID, DNSSEC_VALIDATED, DNSSEC_NO_SIGNATURE /* FOR NOW! */)) {
+        if (!IN_SET(t->dnssec_result,
+                    _DNSSEC_RESULT_INVALID, /* No DNSSEC validation enabled */
+                    DNSSEC_VALIDATED,       /* Answer is signed and validated successfully */
+                    DNSSEC_UNSIGNED)) {     /* Answer is right-fully unsigned */
                 dns_transaction_complete(t, DNS_TRANSACTION_DNSSEC_FAILED);
                 return;
         }
@@ -640,16 +654,7 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
                 dns_answer_unref(t->answer);
                 t->answer = dns_answer_ref(p->answer);
                 t->answer_rcode = DNS_PACKET_RCODE(p);
-                t->answer_authenticated = t->scope->dnssec_mode == DNSSEC_TRUST && DNS_PACKET_AD(p);
-
-                /* According to RFC 4795, section 2.9. only the RRs
-                 * from the answer section shall be cached. However,
-                 * if we know the message is authenticated, we might
-                 * as well cache everything. */
-                if (t->answer_authenticated)
-                        t->n_answer_cacheable = (unsigned) -1; /* everything! */
-                else
-                        t->n_answer_cacheable = DNS_PACKET_ANCOUNT(t->received); /* only the answer section */
+                t->answer_authenticated = false;
 
                 r = dns_transaction_request_dnssec_keys(t);
                 if (r < 0) {
@@ -806,7 +811,6 @@ static int dns_transaction_prepare(DnsTransaction *t, usec_t ts) {
         t->start_usec = ts;
         t->received = dns_packet_unref(t->received);
         t->answer = dns_answer_unref(t->answer);
-        t->n_answer_cacheable = 0;
         t->answer_rcode = 0;
         t->answer_source = _DNS_TRANSACTION_SOURCE_INVALID;
 
@@ -1213,17 +1217,118 @@ static int dns_transaction_request_dnssec_rr(DnsTransaction *t, DnsResourceKey *
         return 0;
 }
 
+static int dns_transaction_has_positive_answer(DnsTransaction *t, DnsAnswerFlags *flags) {
+        int r;
+
+        assert(t);
+
+        /* Checks whether the answer is positive, i.e. either a direct
+         * answer to the question, or a CNAME/DNAME for it */
+
+        r = dns_answer_match_key(t->answer, t->key, flags);
+        if (r != 0)
+                return r;
+
+        r = dns_answer_find_cname_or_dname(t->answer, t->key, NULL, flags);
+        if (r != 0)
+                return r;
+
+        return false;
+}
+
+static int dns_transaction_has_unsigned_negative_answer(DnsTransaction *t) {
+        int r;
+
+        assert(t);
+
+        /* Checks whether the answer is negative, and lacks NSEC/NSEC3
+         * RRs to prove it */
+
+        r = dns_transaction_has_positive_answer(t, NULL);
+        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. */
+
+        r = dns_answer_contains_nsec_or_nsec3(t->answer);
+        if (r < 0)
+                return r;
+        if (r > 0)
+                return false;
+
+        return true;
+}
+
+static int dns_transaction_is_primary_response(DnsTransaction *t, DnsResourceRecord *rr) {
+        int r;
+
+        assert(t);
+        assert(rr);
+
+        /* Check if the specified RR is the "primary" response,
+         * i.e. either matches the question precisely or is a
+         * CNAME/DNAME for it, or is any kind of NSEC/NSEC3 RR */
+
+        r = dns_resource_key_match_rr(t->key, rr, NULL);
+        if (r != 0)
+                return r;
+
+        r = dns_resource_key_match_cname_or_dname(t->key, rr->key, NULL);
+        if (r != 0)
+                return r;
+
+        if (rr->key->type == DNS_TYPE_NSEC3) {
+                const char *p;
+
+                p = DNS_RESOURCE_KEY_NAME(rr->key);
+                r = dns_name_parent(&p);
+                if (r < 0)
+                        return r;
+                if (r > 0) {
+                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(t->key), p);
+                        if (r < 0)
+                                return r;
+                        if (r > 0)
+                                return true;
+                }
+        }
+
+        return rr->key->type == DNS_TYPE_NSEC;
+}
+
 int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
         DnsResourceRecord *rr;
+
         int r;
 
         assert(t);
 
+        /*
+         * Retrieve all auxiliary RRs for the answer we got, so that
+         * we can verify signatures or prove that RRs are rightfully
+         * unsigned. Specifically:
+         *
+         * - For RRSIG we get the matching DNSKEY
+         * - For DNSKEY we get the matching DS
+         * - For unsigned SOA/NS we get the matching DS
+         * - For unsigned CNAME/DNAME we get the parent SOA RR
+         * - For other unsigned RRs we get the matching SOA RR
+         * - For SOA/NS/DS queries with no matching response RRs, and no NSEC/NSEC3, the parent's SOA RR
+         * - For other queries with no matching response RRs, and no NSEC/NSEC3, the SOA RR
+         */
+
         if (t->scope->dnssec_mode != DNSSEC_YES)
                 return 0;
 
         DNS_ANSWER_FOREACH(rr, t->answer) {
 
+                if (dns_type_is_pseudo(rr->key->type))
+                        continue;
+
                 switch (rr->key->type) {
 
                 case DNS_TYPE_RRSIG: {
@@ -1242,10 +1347,18 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                                         continue;
                         }
 
-                        /* If the signer is not a parent of the owner,
-                         * then the signature is bogus, let's ignore
-                         * it. */
-                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(rr->key), rr->rrsig.signer);
+                        /* If the signer is not a parent of our
+                         * original query, then this is about an
+                         * auxiliary RRset, but not anything we asked
+                         * for. In this case we aren't interested,
+                         * because we don't want to request additional
+                         * RRs for stuff we didn't really ask for, and
+                         * also to avoid request loops, where
+                         * additional RRs from one transaction result
+                         * in another transaction whose additonal RRs
+                         * point back to the original transaction, and
+                         * we deadlock. */
+                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(t->key), rr->rrsig.signer);
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -1255,8 +1368,7 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                         if (!dnskey)
                                 return -ENOMEM;
 
-                        log_debug("Requesting DNSKEY to validate transaction %" PRIu16" (key tag: %" PRIu16 ").", t->id, rr->rrsig.key_tag);
-
+                        log_debug("Requesting DNSKEY to validate transaction %" PRIu16" (%s, RRSIG with key tag: %" PRIu16 ").", t->id, DNS_RESOURCE_KEY_NAME(rr->key), rr->rrsig.key_tag);
                         r = dns_transaction_request_dnssec_rr(t, dnskey);
                         if (r < 0)
                                 return r;
@@ -1267,112 +1379,467 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
                         /* For each DNSKEY we request the matching DS */
                         _cleanup_(dns_resource_key_unrefp) DnsResourceKey *ds = NULL;
 
+                        /* If the DNSKEY we are looking at is not for
+                         * zone we are interested in, nor any of its
+                         * parents, we aren't interested, and don't
+                         * request it. After all, we don't want to end
+                         * up in request loops, and want to keep
+                         * additional traffic down. */
+
+                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(t->key), DNS_RESOURCE_KEY_NAME(rr->key));
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
                         ds = dns_resource_key_new(rr->key->class, DNS_TYPE_DS, DNS_RESOURCE_KEY_NAME(rr->key));
                         if (!ds)
                                 return -ENOMEM;
 
-                        log_debug("Requesting DS to validate transaction %" PRIu16" (key tag: %" PRIu16 ").", t->id, dnssec_keytag(rr));
+                        log_debug("Requesting DS to validate transaction %" PRIu16" (%s, DNSKEY with key tag: %" PRIu16 ").", t->id, DNS_RESOURCE_KEY_NAME(rr->key), dnssec_keytag(rr));
+                        r = dns_transaction_request_dnssec_rr(t, ds);
+                        if (r < 0)
+                                return r;
 
+                        break;
+                }
+
+                case DNS_TYPE_DS:
+                case DNS_TYPE_NSEC:
+                case DNS_TYPE_NSEC3:
+                        /* Don't acquire anything for
+                         * DS/NSEC/NSEC3. We require they come with an
+                         * RRSIG without us asking for anything, and
+                         * that's sufficient. */
+                        break;
+
+                case DNS_TYPE_SOA:
+                case DNS_TYPE_NS: {
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *ds = NULL;
+
+                        /* For an unsigned SOA or NS, try to acquire
+                         * the matching DS RR, as we are at a zone cut
+                         * then, and whether a DS exists tells us
+                         * whether the zone is signed. Do so only if
+                         * this RR matches our original question,
+                         * however. */
+
+                        r = dns_resource_key_match_rr(t->key, rr, NULL);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        r = dnssec_has_rrsig(t->answer, rr->key);
+                        if (r < 0)
+                                return r;
+                        if (r > 0)
+                                continue;
+
+                        ds = dns_resource_key_new(rr->key->class, DNS_TYPE_DS, DNS_RESOURCE_KEY_NAME(rr->key));
+                        if (!ds)
+                                return -ENOMEM;
+
+                        log_debug("Requesting DS to validate transaction %" PRIu16 " (%s, unsigned SOA/NS RRset).", t->id, DNS_RESOURCE_KEY_NAME(rr->key));
                         r = dns_transaction_request_dnssec_rr(t, ds);
                         if (r < 0)
                                 return r;
 
                         break;
+                }
+
+                case DNS_TYPE_CNAME:
+                case DNS_TYPE_DNAME: {
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *soa = NULL;
+                        const char *name;
+
+                        /* CNAMEs and DNAMEs cannot be located at a
+                         * zone apex, hence ask for the parent SOA for
+                         * unsigned CNAME/DNAME RRs, maybe that's the
+                         * apex. But do all that only if this is
+                         * actually a response to our original
+                         * question. */
+
+                        r = dns_transaction_is_primary_response(t, rr);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        r = dnssec_has_rrsig(t->answer, rr->key);
+                        if (r < 0)
+                                return r;
+                        if (r > 0)
+                                continue;
+
+                        name = DNS_RESOURCE_KEY_NAME(rr->key);
+                        r = dns_name_parent(&name);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        soa = dns_resource_key_new(rr->key->class, DNS_TYPE_SOA, name);
+                        if (!soa)
+                                return -ENOMEM;
+
+                        log_debug("Requesting parent SOA to validate transaction %" PRIu16 " (%s, unsigned CNAME/DNAME RRset).", t->id, DNS_RESOURCE_KEY_NAME(rr->key));
+                        r = dns_transaction_request_dnssec_rr(t, soa);
+                        if (r < 0)
+                                return r;
+
+                        break;
+                }
+
+                default: {
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *soa = NULL;
+
+                        /* For other unsigned RRsets, look for proof
+                         * the zone is unsigned, by requesting the SOA
+                         * RR of the zone. However, do so only if they
+                         * are directly relevant to our original
+                         * question. */
+
+                        r = dns_transaction_is_primary_response(t, rr);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        r = dnssec_has_rrsig(t->answer, rr->key);
+                        if (r < 0)
+                                return r;
+                        if (r > 0)
+                                continue;
+
+                        soa = dns_resource_key_new(rr->key->class, DNS_TYPE_SOA, DNS_RESOURCE_KEY_NAME(rr->key));
+                        if (!soa)
+                                return -ENOMEM;
+
+                        log_debug("Requesting SOA to validate transaction %" PRIu16 " (%s, unsigned non-SOA/NS RRset).", t->id, DNS_RESOURCE_KEY_NAME(rr->key));
+                        r = dns_transaction_request_dnssec_rr(t, soa);
+                        if (r < 0)
+                                return r;
+                        break;
                 }}
         }
 
-        return !set_isempty(t->dnssec_transactions);
+        /* Above, we requested everything necessary to validate what
+         * we got. Now, let's request what we need to validate what we
+         * didn't get... */
+
+        r = dns_transaction_has_unsigned_negative_answer(t);
+        if (r < 0)
+                return r;
+        if (r > 0) {
+                const char *name;
+
+                name = DNS_RESOURCE_KEY_NAME(t->key);
+
+                /* If this was a SOA or NS request, then this
+                 * indicates that we are not at a zone apex, hence ask
+                 * the parent name instead. If this was a DS request,
+                 * then it's signed when the parent zone is signed,
+                 * hence ask the parent in that case, too. */
+
+                if (IN_SET(t->key->type, DNS_TYPE_SOA, DNS_TYPE_NS, DNS_TYPE_DS)) {
+                        r = dns_name_parent(&name);
+                        if (r < 0)
+                                return r;
+                        if (r > 0)
+                                log_debug("Requesting parent SOA to validate transaction %" PRIu16 " (%s, unsigned empty SOA/NS/DS response).", t->id, DNS_RESOURCE_KEY_NAME(t->key));
+                        else
+                                name = NULL;
+                } else
+                        log_debug("Requesting SOA to validate transaction %" PRIu16 " (%s, unsigned empty non-SOA/NS/DS response).", t->id, DNS_RESOURCE_KEY_NAME(t->key));
+
+                if (name) {
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *soa = NULL;
+
+                        soa = dns_resource_key_new(t->key->class, DNS_TYPE_SOA, name);
+                        if (!soa)
+                                return -ENOMEM;
+
+                        r = dns_transaction_request_dnssec_rr(t, soa);
+                        if (r < 0)
+                                return r;
+                }
+        }
+
+        return dns_transaction_dnssec_is_live(t);
 }
 
 void dns_transaction_notify(DnsTransaction *t, DnsTransaction *source) {
         int r;
 
         assert(t);
-        assert(IN_SET(t->state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_VALIDATING));
         assert(source);
 
+        if (!IN_SET(t->state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_VALIDATING))
+                return;
+
         /* Invoked whenever any of our auxiliary DNSSEC transactions
-           completed its work. We simply copy the answer from that
-           transaction over. */
+           completed its work. We copy any RRs from that transaction
+           over into our list of validated keys -- but only if the
+           answer is authenticated.
+
+           Note that we fail our transaction if the auxiliary
+           transaction failed, except on NXDOMAIN. This is because
+           some broken DNS servers (Akamai...) will return NXDOMAIN
+           for empty non-terminals. */
+
+        if (source->state != DNS_TRANSACTION_SUCCESS &&
+            !(source->state == DNS_TRANSACTION_FAILURE && source->answer_rcode == DNS_RCODE_NXDOMAIN)) {
+                log_debug("Auxiliary DNSSEC RR query failed: rcode=%i.", source->answer_rcode);
+                goto fail;
+        } else if (source->answer_authenticated) {
 
-        if (source->state != DNS_TRANSACTION_SUCCESS) {
-                log_debug("Auxiliary DNSSEC RR query failed.");
-                t->dnssec_result = DNSSEC_FAILED_AUXILIARY;
-        } else {
                 r = dns_answer_extend(&t->validated_keys, source->answer);
                 if (r < 0) {
                         log_error_errno(r, "Failed to merge validated DNSSEC key data: %m");
-                        t->dnssec_result = DNSSEC_FAILED_AUXILIARY;
+                        goto fail;
                 }
         }
 
-        /* Detach us from the DNSSEC transaction. */
-        (void) set_remove(t->dnssec_transactions, source);
-        (void) set_remove(source->notify_transactions, t);
-
         /* If the state is still PENDING, we are still in the loop
          * that adds further DNSSEC transactions, hence don't check if
          * we are ready yet. If the state is VALIDATING however, we
          * should check if we are complete now. */
         if (t->state == DNS_TRANSACTION_VALIDATING)
                 dns_transaction_process_dnssec(t);
+
+        return;
+
+fail:
+        t->dnssec_result = DNSSEC_FAILED_AUXILIARY;
+        dns_transaction_complete(t, DNS_TRANSACTION_DNSSEC_FAILED);
 }
 
-static int dns_transaction_is_primary_response(DnsTransaction *t, DnsResourceRecord *rr) {
+static int dns_transaction_validate_dnskey_by_ds(DnsTransaction *t) {
+        DnsResourceRecord *rr;
+        int ifindex, r;
+
+        assert(t);
+
+        /* Add all DNSKEY RRs from the answer that are validated by DS
+         * RRs from the list of validated keys to the list of
+         * validated keys. */
+
+        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, t->answer) {
+
+                r = dnssec_verify_dnskey_search(rr, t->validated_keys);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                /* If so, the DNSKEY is validated too. */
+                r = dns_answer_add_extend(&t->validated_keys, rr, ifindex, DNS_ANSWER_AUTHENTICATED);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
+}
+
+static int dns_transaction_requires_rrsig(DnsTransaction *t, DnsResourceRecord *rr) {
         int r;
 
         assert(t);
         assert(rr);
 
-        /* Check if the specified RR is the "primary" response,
-         * i.e. either matches the question precisely or is a
-         * CNAME/DNAME for it, or is any kind of NSEC/NSEC3 RR */
+        /* Checks if the RR we are looking for must be signed with an
+         * RRSIG. This is used for positive responses. */
 
-        if (IN_SET(rr->key->type, DNS_TYPE_NSEC, DNS_TYPE_NSEC3))
-                return 1;
+        if (t->scope->dnssec_mode != DNSSEC_YES)
+                return false;
 
-        r = dns_resource_key_match_rr(t->key, rr, NULL);
-        if (r != 0)
-                return r;
+        if (dns_type_is_pseudo(rr->key->type))
+                return -EINVAL;
 
-        r = dns_resource_key_match_cname_or_dname(t->key, rr->key, NULL);
-        if (r != 0)
-                return r;
+        switch (rr->key->type) {
 
-        return 0;
+        case DNS_TYPE_DNSKEY:
+        case DNS_TYPE_DS:
+        case DNS_TYPE_NSEC:
+        case DNS_TYPE_NSEC3:
+                /* We never consider DNSKEY, DS, NSEC, NSEC3 RRs if they aren't signed. */
+                return true;
+
+        case DNS_TYPE_RRSIG:
+                /* RRSIGs are the signatures themselves, they need no signing. */
+                return false;
+
+        case DNS_TYPE_SOA:
+        case DNS_TYPE_NS: {
+                DnsTransaction *dt;
+                Iterator i;
+
+                /* For SOA or NS RRs we look for a matching DS transaction, or a SOA transaction of the parent */
+
+                SET_FOREACH(dt, t->dnssec_transactions, i) {
+
+                        if (dt->key->class != rr->key->class)
+                                continue;
+                        if (dt->key->type != DNS_TYPE_DS)
+                                continue;
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(dt->key), DNS_RESOURCE_KEY_NAME(rr->key));
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        /* We found a DS transactions for the SOA/NS
+                         * RRs we are looking at. If it discovered signed DS
+                         * RRs, then we need to be signed, too. */
+
+                         if (!dt->answer_authenticated)
+                                 return false;
+
+                         return dns_answer_match_key(dt->answer, dt->key, NULL);
+                }
+
+                /* We found nothing that proves this is safe to leave
+                 * this unauthenticated, hence ask inist on
+                 * authentication. */
+                return true;
+        }
+
+        case DNS_TYPE_CNAME:
+        case DNS_TYPE_DNAME: {
+                const char *parent = NULL;
+                DnsTransaction *dt;
+                Iterator i;
+
+                /* CNAME/DNAME RRs cannot be located at a zone apex, hence look directly for the parent SOA. */
+
+                SET_FOREACH(dt, t->dnssec_transactions, i) {
+
+                        if (dt->key->class != rr->key->class)
+                                continue;
+                        if (dt->key->type != DNS_TYPE_SOA)
+                                continue;
+
+                        if (!parent) {
+                                parent = DNS_RESOURCE_KEY_NAME(rr->key);
+                                r = dns_name_parent(&parent);
+                                if (r < 0)
+                                        return r;
+                                if (r == 0) {
+                                        /* A CNAME/DNAME without a parent? That's sooo weird. */
+                                        log_debug("Transaction %" PRIu16 " claims CNAME/DNAME at root. Refusing.", t->id);
+                                        return -EBADMSG;
+                                }
+                        }
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(dt->key), parent);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        return t->answer_authenticated;
+                }
+
+                return true;
+        }
+
+        default: {
+                DnsTransaction *dt;
+                Iterator i;
+
+                /* Any other kind of RR. Let's see if our SOA lookup was authenticated */
+
+                SET_FOREACH(dt, t->dnssec_transactions, i) {
+
+                        if (dt->key->class != rr->key->class)
+                                continue;
+                        if (dt->key->type != DNS_TYPE_SOA)
+                                continue;
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(dt->key), DNS_RESOURCE_KEY_NAME(rr->key));
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        /* We found the transaction that was supposed to find
+                         * the SOA RR for us. It was successful, but found no
+                         * RR for us. This means we are not at a zone cut. In
+                         * this case, we require authentication if the SOA
+                         * lookup was authenticated too. */
+                        return t->answer_authenticated;
+                }
+
+                return true;
+        }}
 }
 
-static int dns_transaction_validate_dnskey_by_ds(DnsTransaction *t) {
-        DnsResourceRecord *rr;
-        int ifindex, r;
+static int dns_transaction_requires_nsec(DnsTransaction *t) {
+        DnsTransaction *dt;
+        const char *name;
+        Iterator i;
+        int r;
 
         assert(t);
 
-        /* Add all DNSKEY RRs from the answer that are validated by DS
-         * RRs from the list of validated keys to the lis of validated
-         * keys. */
+        /* Checks if we need to insist on NSEC/NSEC3 RRs for proving
+         * this negative reply */
 
-        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, t->answer) {
+        if (t->scope->dnssec_mode != DNSSEC_YES)
+                return false;
 
-                r = dnssec_verify_dnskey_search(rr, t->validated_keys);
+        if (dns_type_is_pseudo(t->key->type))
+                return -EINVAL;
+
+        name = DNS_RESOURCE_KEY_NAME(t->key);
+
+        if (IN_SET(t->key->type, DNS_TYPE_SOA, DNS_TYPE_NS, DNS_TYPE_DS)) {
+
+                /* We got a negative reply for this SOA/NS lookup? If
+                 * so, then we are not at a zone apex, and thus should
+                 * look at the result of the parent SOA lookup.
+                 *
+                 * We got a negative reply for this DS lookup? DS RRs
+                 * are signed when their parent zone is signed, hence
+                 * also check the parent SOA in this case. */
+
+                r = dns_name_parent(&name);
                 if (r < 0)
                         return r;
                 if (r == 0)
+                        return true;
+        }
+
+        /* For all other RRs we check the SOA on the same level to see
+         * if it's signed. */
+
+        SET_FOREACH(dt, t->dnssec_transactions, i) {
+
+                if (dt->key->class != t->key->class)
+                        continue;
+                if (dt->key->type != DNS_TYPE_SOA)
                         continue;
 
-                /* If so, the DNSKEY is validated too. */
-                r = dns_answer_add_extend(&t->validated_keys, rr, ifindex);
+                r = dns_name_equal(DNS_RESOURCE_KEY_NAME(dt->key), name);
                 if (r < 0)
                         return r;
+                if (r == 0)
+                        continue;
+
+                return dt->answer_authenticated;
         }
 
-        return 0;
+        /* If in doubt, require NSEC/NSEC3 */
+        return true;
 }
 
 int dns_transaction_validate_dnssec(DnsTransaction *t) {
         _cleanup_(dns_answer_unrefp) DnsAnswer *validated = NULL;
         bool dnskeys_finalized = false;
         DnsResourceRecord *rr;
+        DnsAnswerFlags flags;
         int r;
 
         assert(t);
@@ -1388,12 +1855,17 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
         if (t->dnssec_result != _DNSSEC_RESULT_INVALID)
                 return 0;
 
+        /* Our own stuff needs no validation */
         if (IN_SET(t->answer_source, DNS_TRANSACTION_ZONE, DNS_TRANSACTION_TRUST_ANCHOR)) {
                 t->dnssec_result = DNSSEC_VALIDATED;
                 t->answer_authenticated = true;
                 return 0;
         }
 
+        /* Cached stuff is not affected by validation. */
+        if (t->answer_source != DNS_TRANSACTION_NETWORK)
+                return 0;
+
         log_debug("Validating response from transaction %" PRIu16 " (%s).", t->id, dns_transaction_key_string(t));
 
         /* First see if there are DNSKEYs we already known a validated DS for. */
@@ -1423,11 +1895,6 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
 
                         if (result == DNSSEC_VALIDATED) {
 
-                                /* Add the validated RRset to the new list of validated RRsets */
-                                r = dns_answer_copy_by_key(&validated, t->answer, rr->key);
-                                if (r < 0)
-                                        return r;
-
                                 if (rr->key->type == DNS_TYPE_DNSKEY) {
                                         /* If we just validated a
                                          * DNSKEY RRset, then let's
@@ -1435,13 +1902,17 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                                          * of validated keys for this
                                          * transaction. */
 
-                                        r = dns_answer_copy_by_key(&t->validated_keys, t->answer, rr->key);
+                                        r = dns_answer_copy_by_key(&t->validated_keys, t->answer, rr->key, DNS_ANSWER_AUTHENTICATED);
                                         if (r < 0)
                                                 return r;
                                 }
 
-                                /* Now, remove this RRset from the RRs still to process */
-                                r = dns_answer_remove_by_key(&t->answer, rr->key);
+                                /* Add the validated RRset to the new
+                                 * list of validated RRsets, and
+                                 * remove it from the unvalidated
+                                 * RRsets. We mark the RRset as
+                                 * authenticated and cacheable. */
+                                r = dns_answer_move_by_key(&validated, &t->answer, rr->key, DNS_ANSWER_AUTHENTICATED|DNS_ANSWER_CACHEABLE);
                                 if (r < 0)
                                         return r;
 
@@ -1455,6 +1926,22 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                                  * is irrelevant, as there might be
                                  * more DNSKEYs coming. */
 
+                                if (result == DNSSEC_NO_SIGNATURE) {
+                                        r = dns_transaction_requires_rrsig(t, rr);
+                                        if (r < 0)
+                                                return r;
+                                        if (r == 0) {
+                                                /* Data does not require signing. In that case, just copy it over,
+                                                 * but remember that this is by no means authenticated.*/
+                                                r = dns_answer_move_by_key(&validated, &t->answer, rr->key, 0);
+                                                if (r < 0)
+                                                        return r;
+
+                                                changed = true;
+                                                break;
+                                        }
+                                }
+
                                 r = dns_transaction_is_primary_response(t, rr);
                                 if (r < 0)
                                         return r;
@@ -1502,21 +1989,25 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
         t->answer = validated;
         validated = NULL;
 
-        /* Everything that's now in t->answer is known to be good, hence cacheable. */
-        t->n_answer_cacheable = (unsigned) -1; /* everything! */
-
         /* At this point the answer only contains validated
          * RRsets. Now, let's see if it actually answers the question
          * we asked. If so, great! If it doesn't, then see if
          * NSEC/NSEC3 can prove this. */
-        r = dns_answer_match_key(t->answer, t->key);
-        if (r < 0)
-                return r;
+        r = dns_transaction_has_positive_answer(t, &flags);
         if (r > 0) {
-                /* Yes, it answer the question, everything is authenticated. */
-                t->dnssec_result = DNSSEC_VALIDATED;
-                t->answer_rcode = DNS_RCODE_SUCCESS;
-                t->answer_authenticated = true;
+                /* Yes, it answers the question! */
+
+                if (flags & DNS_ANSWER_AUTHENTICATED) {
+                        /* The answer is fully authenticated, yay. */
+                        t->dnssec_result = DNSSEC_VALIDATED;
+                        t->answer_rcode = DNS_RCODE_SUCCESS;
+                        t->answer_authenticated = true;
+                } else {
+                        /* The answer is not fully authenticated. */
+                        t->dnssec_result = DNSSEC_UNSIGNED;
+                        t->answer_authenticated = false;
+                }
+
         } else if (r == 0) {
                 DnssecNsecResult nr;
 
@@ -1529,6 +2020,7 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
 
                 case DNSSEC_NSEC_NXDOMAIN:
                         /* NSEC proves the domain doesn't exist. Very good. */
+                        log_debug("Proved NXDOMAIN via NSEC/NSEC3 for transaction %u (%s)", t->id, dns_transaction_key_string(t));
                         t->dnssec_result = DNSSEC_VALIDATED;
                         t->answer_rcode = DNS_RCODE_NXDOMAIN;
                         t->answer_authenticated = true;
@@ -1536,14 +2028,37 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
 
                 case DNSSEC_NSEC_NODATA:
                         /* NSEC proves that there's no data here, very good. */
+                        log_debug("Proved NODATA via NSEC/NSEC3 for transaction %u (%s)", t->id, dns_transaction_key_string(t));
                         t->dnssec_result = DNSSEC_VALIDATED;
                         t->answer_rcode = DNS_RCODE_SUCCESS;
                         t->answer_authenticated = true;
                         break;
 
+                case DNSSEC_NSEC_OPTOUT:
+                        /* NSEC3 says the data might not be signed */
+                        log_debug("Data is NSEC3 opt-out via NSEC/NSEC3 for transaction %u (%s)", t->id, dns_transaction_key_string(t));
+                        t->dnssec_result = DNSSEC_UNSIGNED;
+                        t->answer_authenticated = false;
+                        break;
+
                 case DNSSEC_NSEC_NO_RR:
                         /* No NSEC data? Bummer! */
-                        t->dnssec_result = DNSSEC_UNSIGNED;
+
+                        r = dns_transaction_requires_nsec(t);
+                        if (r < 0)
+                                return r;
+                        if (r > 0)
+                                t->dnssec_result = DNSSEC_NO_SIGNATURE;
+                        else {
+                                t->dnssec_result = DNSSEC_UNSIGNED;
+                                t->answer_authenticated = false;
+                        }
+
+                        break;
+
+                case DNSSEC_NSEC_UNSUPPORTED_ALGORITHM:
+                        /* We don't know the NSEC3 algorithm used? */
+                        t->dnssec_result = DNSSEC_UNSUPPORTED_ALGORITHM;
                         break;
 
                 case DNSSEC_NSEC_FOUND:
diff --git a/src/resolve/resolved-dns-transaction.h b/src/resolve/resolved-dns-transaction.h
index 5f6a699454..f6ec8e5ead 100644
--- a/src/resolve/resolved-dns-transaction.h
+++ b/src/resolve/resolved-dns-transaction.h
@@ -75,12 +75,21 @@ struct DnsTransaction {
         DnsPacket *sent, *received;
 
         DnsAnswer *answer;
-        unsigned n_answer_cacheable; /* Specifies how many RRs of the answer shall be cached, from the beginning */
         int answer_rcode;
         DnsTransactionSource answer_source;
+
+        /* Indicates whether the primary answer is authenticated,
+         * i.e. whether the RRs from answer which directly match the
+         * question are authenticated, or, if there are none, whether
+         * the NODATA or NXDOMAIN case is. It says nothing about
+         * additional RRs listed in the answer, however they have
+         * their own DNS_ANSWER_AUTHORIZED FLAGS. Note that this bit
+         * is defined different than the AD bit in DNS packets, as
+         * that covers more than just the actual primary answer. */
         bool answer_authenticated;
 
-        /* Contains DS and DNSKEY RRs we already verified and need to authenticate this reply */
+        /* Contains DNSKEY, DS, SOA RRs we already verified and need
+         * to authenticate this reply */
         DnsAnswer *validated_keys;
 
         usec_t start_usec;
diff --git a/src/resolve/resolved-dns-trust-anchor.c b/src/resolve/resolved-dns-trust-anchor.c
index e55bdaa1ed..208b7fefc4 100644
--- a/src/resolve/resolved-dns-trust-anchor.c
+++ b/src/resolve/resolved-dns-trust-anchor.c
@@ -58,7 +58,7 @@ int dns_trust_anchor_load(DnsTrustAnchor *d) {
         if (!answer)
                 return -ENOMEM;
 
-        r = dns_answer_add(answer, rr, 0);
+        r = dns_answer_add(answer, rr, 0, DNS_ANSWER_AUTHENTICATED);
         if (r < 0)
                 return r;
 
diff --git a/src/resolve/resolved-dns-zone.c b/src/resolve/resolved-dns-zone.c
index 8046e2ed34..0ddf2be8b3 100644
--- a/src/resolve/resolved-dns-zone.c
+++ b/src/resolve/resolved-dns-zone.c
@@ -386,7 +386,7 @@ int dns_zone_lookup(DnsZone *z, DnsResourceKey *key, DnsAnswer **ret_answer, Dns
                         if (k < 0)
                                 return k;
                         if (k > 0) {
-                                r = dns_answer_add(answer, j->rr, 0);
+                                r = dns_answer_add(answer, j->rr, 0, DNS_ANSWER_AUTHENTICATED);
                                 if (r < 0)
                                         return r;
 
@@ -412,7 +412,7 @@ int dns_zone_lookup(DnsZone *z, DnsResourceKey *key, DnsAnswer **ret_answer, Dns
                         if (j->state != DNS_ZONE_ITEM_PROBING)
                                 tentative = false;
 
-                        r = dns_answer_add(answer, j->rr, 0);
+                        r = dns_answer_add(answer, j->rr, 0, DNS_ANSWER_AUTHENTICATED);
                         if (r < 0)
                                 return r;
                 }
diff --git a/src/resolve/resolved-mdns.c b/src/resolve/resolved-mdns.c
index d6973a6999..db23bc9d42 100644
--- a/src/resolve/resolved-mdns.c
+++ b/src/resolve/resolved-mdns.c
@@ -122,8 +122,7 @@ static int on_mdns_packet(sd_event_source *s, int fd, uint32_t revents, void *us
                                 dns_transaction_process_reply(t, p);
                 }
 
-                dns_cache_put(&scope->cache, NULL, DNS_PACKET_RCODE(p), p->answer,
-                              p->answer->n_rrs, false, 0, p->family, &p->sender);
+                dns_cache_put(&scope->cache, NULL, DNS_PACKET_RCODE(p), p->answer, false, 0, p->family, &p->sender);
 
         } else if (dns_packet_validate_query(p) > 0)  {
                 log_debug("Got mDNS query packet for id %u", DNS_PACKET_ID(p));
diff --git a/src/resolve/test-dnssec.c b/src/resolve/test-dnssec.c
index 3dab50ed6a..5b4ee220c4 100644
--- a/src/resolve/test-dnssec.c
+++ b/src/resolve/test-dnssec.c
@@ -118,7 +118,7 @@ static void test_dnssec_verify_rrset2(void) {
 
         answer = dns_answer_new(1);
         assert_se(answer);
-        assert_se(dns_answer_add(answer, nsec, 0) >= 0);
+        assert_se(dns_answer_add(answer, nsec, 0, DNS_ANSWER_AUTHENTICATED) >= 0);
 
         /* Validate the RR as it if was 2015-12-11 today */
         assert_se(dnssec_verify_rrset(answer, nsec->key, rrsig, dnskey, 1449849318*USEC_PER_SEC, &result) >= 0);
@@ -201,7 +201,7 @@ static void test_dnssec_verify_rrset(void) {
 
         answer = dns_answer_new(1);
         assert_se(answer);
-        assert_se(dns_answer_add(answer, a, 0) >= 0);
+        assert_se(dns_answer_add(answer, a, 0, DNS_ANSWER_AUTHENTICATED) >= 0);
 
         /* Validate the RR as it if was 2015-12-2 today */
         assert_se(dnssec_verify_rrset(answer, a->key, rrsig, dnskey, 1449092754*USEC_PER_SEC, &result) >= 0);