resolved: chase DNSKEY/DS RRs when doing look-ups with DNSSEC enabled

This adds initial support for validating RRSIG/DNSKEY/DS chains when
doing lookups. Proof-of-non-existance, or proof-of-unsigned-zones is not
implemented yet.

With this change DnsTransaction objects will generate additional
DnsTransaction objects when looking for DNSKEY or DS RRs to validate an
RRSIG on a response. DnsTransaction objects are thus created for three
reasons now:

1) Because a user asked for something to be resolved, i.e. requested by
   a DnsQuery/DnsQueryCandidate object.
2) As result of LLMNR RR probing, requested by a DnsZoneItem.
3) Because another DnsTransaction requires the requested RRs for
   validation of its own response.

DnsTransactions are shared between all these users, and are GC
automatically as soon as all of these users don't need a specific
transaction anymore.

To unify the handling of these three reasons for existance for a
DnsTransaction, a new common naming is introduced: each DnsTransaction
now tracks its "owners" via a Set* object named "notify_xyz", containing
all owners to notify on completion.

A new DnsTransaction state is introduced called "VALIDATING" that is
entered after a response has been receieved which needs to be validated,
as long as we are still waiting for the DNSKEY/DS RRs from other
DnsTransactions.

This patch will request the DNSKEY/DS RRs bottom-up, and then validate
them top-down.

Caching of RRs is now only done after verification, so that the cache is
not poisoned with known invalid data.

The "DnsAnswer" object gained a substantial number of new calls, since
we need to add/remove RRs to it dynamically now.

15 files changed, 929 insertions, 146 deletions

diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index 0ceca56371..1427638233 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -60,6 +60,9 @@ static int reply_query_state(DnsQuery *q) {
         case DNS_TRANSACTION_ABORTED:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_ABORTED, "Query aborted");
 
+        case DNS_TRANSACTION_DNSSEC_FAILED:
+                return sd_bus_reply_method_errorf(q->request, BUS_ERROR_ABORTED, "DNSSEC validation failed");
+
         case DNS_TRANSACTION_FAILURE: {
                 _cleanup_(sd_bus_error_free) sd_bus_error error = SD_BUS_ERROR_NULL;
 
diff --git a/src/resolve/resolved-dns-answer.c b/src/resolve/resolved-dns-answer.c
index 92b9871dbb..de8c4d9dd3 100644
--- a/src/resolve/resolved-dns-answer.c
+++ b/src/resolve/resolved-dns-answer.c
@@ -73,6 +73,35 @@ DnsAnswer *dns_answer_unref(DnsAnswer *a) {
         return NULL;
 }
 
+static int dns_answer_add_raw(DnsAnswer *a, DnsResourceRecord *rr, int ifindex) {
+        assert(rr);
+
+        if (!a)
+                return -ENOSPC;
+
+        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++;
+
+        return 1;
+}
+
+static int dns_answer_add_raw_all(DnsAnswer *a, DnsAnswer *source) {
+        DnsResourceRecord *rr;
+        int ifindex, r;
+
+        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, source) {
+                r = dns_answer_add_raw(a, rr, ifindex);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
+}
+
 int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex) {
         unsigned i;
         int r;
@@ -105,14 +134,33 @@ int dns_answer_add(DnsAnswer *a, DnsResourceRecord *rr, int ifindex) {
                 }
         }
 
-        if (a->n_rrs >= a->n_allocated)
-                return -ENOSPC;
+        return dns_answer_add_raw(a, rr, ifindex);
+}
 
-        a->items[a->n_rrs].rr = dns_resource_record_ref(rr);
-        a->items[a->n_rrs].ifindex = ifindex;
-        a->n_rrs++;
+static int dns_answer_add_all(DnsAnswer *a, DnsAnswer *b) {
+        DnsResourceRecord *rr;
+        int ifindex, r;
 
-        return 1;
+        DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, b) {
+                r = dns_answer_add(a, rr, ifindex);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
+}
+
+int dns_answer_add_extend(DnsAnswer **a, DnsResourceRecord *rr, int ifindex) {
+        int r;
+
+        assert(a);
+        assert(rr);
+
+        r = dns_answer_reserve_or_clone(a, 1);
+        if (r < 0)
+                return r;
+
+        return dns_answer_add(*a, rr, ifindex);
 }
 
 int dns_answer_add_soa(DnsAnswer *a, const char *name, uint32_t ttl) {
@@ -141,8 +189,8 @@ int dns_answer_add_soa(DnsAnswer *a, const char *name, uint32_t ttl) {
         return dns_answer_add(a, soa, 0);
 }
 
-int dns_answer_contains(DnsAnswer *a, DnsResourceKey *key) {
-        unsigned i;
+int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key) {
+        DnsResourceRecord *i;
         int r;
 
         assert(key);
@@ -150,8 +198,8 @@ int dns_answer_contains(DnsAnswer *a, DnsResourceKey *key) {
         if (!a)
                 return 0;
 
-        for (i = 0; i < a->n_rrs; i++) {
-                r = dns_resource_key_match_rr(key, a->items[i].rr, NULL);
+        DNS_ANSWER_FOREACH(i, a) {
+                r = dns_resource_key_match_rr(key, i, NULL);
                 if (r < 0)
                         return r;
                 if (r > 0)
@@ -161,21 +209,25 @@ int dns_answer_contains(DnsAnswer *a, DnsResourceKey *key) {
         return 0;
 }
 
-int dns_answer_match_soa(DnsResourceKey *key, DnsResourceKey *soa) {
-        if (soa->class != DNS_CLASS_IN)
-                return 0;
+int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr) {
+        DnsResourceRecord *i;
+        int r;
 
-        if (soa->type != DNS_TYPE_SOA)
-                return 0;
+        assert(rr);
 
-        if (!dns_name_endswith(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(soa)))
-                return 0;
+        DNS_ANSWER_FOREACH(i, a) {
+                r = dns_resource_record_equal(i, rr);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        return 1;
+        }
 
-        return 1;
+        return 0;
 }
 
-int dns_answer_find_soa(DnsAnswer *a, DnsResourceKey *key, DnsResourceRecord **ret) {
-        unsigned i;
+int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret) {
+        DnsResourceRecord *rr;
 
         assert(key);
         assert(ret);
@@ -187,10 +239,9 @@ int dns_answer_find_soa(DnsAnswer *a, DnsResourceKey *key, DnsResourceRecord **r
         if (key->type == DNS_TYPE_SOA)
                 return 0;
 
-        for (i = 0; i < a->n_rrs; i++) {
-
-                if (dns_answer_match_soa(key, a->items[i].rr->key)) {
-                        *ret = a->items[i].rr;
+        DNS_ANSWER_FOREACH(rr, a) {
+                if (dns_resource_key_match_soa(key, rr->key)) {
+                        *ret = rr;
                         return 1;
                 }
         }
@@ -198,41 +249,169 @@ int dns_answer_find_soa(DnsAnswer *a, DnsResourceKey *key, DnsResourceRecord **r
         return 0;
 }
 
-DnsAnswer *dns_answer_merge(DnsAnswer *a, DnsAnswer *b) {
-        _cleanup_(dns_answer_unrefp) DnsAnswer *ret = NULL;
-        DnsAnswer *k;
+int dns_answer_merge(DnsAnswer *a, DnsAnswer *b, DnsAnswer **ret) {
+        _cleanup_(dns_answer_unrefp) DnsAnswer *k = NULL;
+        int r;
+
+        assert(ret);
+
+        if (dns_answer_size(a) <= 0) {
+                *ret = dns_answer_ref(b);
+                return 0;
+        }
+
+        if (dns_answer_size(b) <= 0) {
+                *ret = dns_answer_ref(a);
+                return 0;
+        }
+
+        k = dns_answer_new(a->n_rrs + b->n_rrs);
+        if (!k)
+                return -ENOMEM;
+
+        r = dns_answer_add_raw_all(k, a);
+        if (r < 0)
+                return r;
+
+        r = dns_answer_add_all(k, b);
+        if (r < 0)
+                return r;
+
+        *ret = k;
+        k = NULL;
+
+        return 0;
+}
+
+int dns_answer_extend(DnsAnswer **a, DnsAnswer *b) {
+        DnsAnswer *merged;
+        int r;
+
+        assert(a);
+
+        r = dns_answer_merge(*a, b, &merged);
+        if (r < 0)
+                return r;
+
+        dns_answer_unref(*a);
+        *a = merged;
+
+        return 0;
+}
+
+int dns_answer_remove_by_key(DnsAnswer **a, const DnsResourceKey *key) {
+        bool found = false, other = false;
+        DnsResourceRecord *rr;
         unsigned i;
         int r;
 
-        if (a && (!b || b->n_rrs <= 0))
-                return dns_answer_ref(a);
-        if ((!a || a->n_rrs <= 0) && b)
-                return dns_answer_ref(b);
+        assert(a);
+        assert(key);
 
-        ret = dns_answer_new((a ? a->n_rrs : 0) + (b ? b->n_rrs : 0));
-        if (!ret)
-                return NULL;
+        /* Remove all entries matching the specified key from *a */
 
-        if (a) {
-                for (i = 0; i < a->n_rrs; i++) {
-                        r = dns_answer_add(ret, a->items[i].rr, a->items[i].ifindex);
-                        if (r < 0)
-                                return NULL;
-                }
+        DNS_ANSWER_FOREACH(rr, *a) {
+                r = dns_resource_key_equal(rr->key, key);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        found = true;
+                else
+                        other = true;
+
+                if (found && other)
+                        break;
+        }
+
+        if (!found)
+                return 0;
+
+        if (!other) {
+                *a = dns_answer_unref(*a); /* Return NULL for the empty answer */
+                return 1;
         }
 
-        if (b) {
-                for (i = 0; i < b->n_rrs; i++) {
-                        r = dns_answer_add(ret, b->items[i].rr, b->items[i].ifindex);
+        if ((*a)->n_ref > 1) {
+                _cleanup_(dns_answer_unrefp) DnsAnswer *copy = NULL;
+                int ifindex;
+
+                copy = dns_answer_new((*a)->n_rrs);
+                if (!copy)
+                        return -ENOMEM;
+
+                DNS_ANSWER_FOREACH_IFINDEX(rr, ifindex, *a) {
+                        r = dns_resource_key_equal(rr->key, key);
                         if (r < 0)
-                                return NULL;
+                                return r;
+                        if (r > 0)
+                                continue;
+
+                        r = dns_answer_add_raw(copy, rr, ifindex);
+                        if (r < 0)
+                                return r;
                 }
+
+                dns_answer_unref(*a);
+                *a = copy;
+                copy = NULL;
+
+                return 1;
+        }
+
+        /* Only a single reference, edit in-place */
+
+        i = 0;
+        for (;;) {
+                if (i >= (*a)->n_rrs)
+                        break;
+
+                r = dns_resource_key_equal((*a)->items[i].rr->key, key);
+                if (r < 0)
+                        return r;
+                if (r > 0) {
+                        /* Kill this entry */
+
+                        dns_resource_record_unref((*a)->items[i].rr);
+                        memmove((*a)->items + i, (*a)->items + i + 1, sizeof(DnsAnswerItem) * ((*a)->n_rrs - i - 1));
+                        (*a)->n_rrs --;
+                        continue;
+
+                } else
+                        /* Keep this entry */
+                        i++;
         }
 
-        k = ret;
-        ret = NULL;
+        return 1;
+}
+
+int dns_answer_copy_by_key(DnsAnswer **a, DnsAnswer *source, const DnsResourceKey *key) {
+        DnsResourceRecord *rr_source;
+        int ifindex_source, r;
+
+        assert(a);
+        assert(key);
+
+        /* Copy all RRs matching the specified key from source into *a */
+
+        DNS_ANSWER_FOREACH_IFINDEX(rr_source, ifindex_source, source) {
+
+                r = dns_resource_key_equal(rr_source->key, key);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                /* Make space for at least one entry */
+                r = dns_answer_reserve_or_clone(a, 1);
+                if (r < 0)
+                        return r;
 
-        return k;
+                r = dns_answer_add(*a, rr_source, ifindex_source);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
 }
 
 void dns_answer_order_by_scope(DnsAnswer *a, bool prefer_link_local) {
@@ -304,3 +483,36 @@ int dns_answer_reserve(DnsAnswer **a, unsigned n_free) {
         *a = n;
         return 0;
 }
+
+int dns_answer_reserve_or_clone(DnsAnswer **a, unsigned n_free) {
+        _cleanup_(dns_answer_unrefp) DnsAnswer *n = NULL;
+        int r;
+
+        assert(a);
+
+        /* Tries to extend the DnsAnswer object. And if that's not
+         * possibly, since we are not the sole owner, then allocate a
+         * new, appropriately sized one. Either way, after this call
+         * the object will only have a single reference, and has room
+         * for at least the specified number of RRs. */
+
+        r = dns_answer_reserve(a, n_free);
+        if (r != -EBUSY)
+                return r;
+
+        assert(*a);
+
+        n = dns_answer_new(((*a)->n_rrs + n_free) * 2);
+        if (!n)
+                return -ENOMEM;
+
+        r = dns_answer_add_raw_all(n, *a);
+        if (r < 0)
+                return r;
+
+        dns_answer_unref(*a);
+        *a = n;
+        n = NULL;
+
+        return 0;
+}
diff --git a/src/resolve/resolved-dns-answer.h b/src/resolve/resolved-dns-answer.h
index 08c84c1cda..8d95131dbe 100644
--- a/src/resolve/resolved-dns-answer.h
+++ b/src/resolve/resolved-dns-answer.h
@@ -30,7 +30,9 @@ typedef struct DnsAnswerItem DnsAnswerItem;
 /* A simple array of resource records. We keep track of the
  * originating ifindex for each RR where that makes sense, so that we
  * can qualify A and AAAA RRs referring to a local link with the
- * right ifindex. */
+ * right ifindex.
+ *
+ * Note that we usually encode the empty answer as a simple NULL. */
 
 struct DnsAnswerItem {
         DnsResourceRecord *rr;
@@ -48,15 +50,28 @@ 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_soa(DnsAnswer *a, const char *name, uint32_t ttl);
-int dns_answer_contains(DnsAnswer *a, DnsResourceKey *key);
-int dns_answer_match_soa(DnsResourceKey *key, DnsResourceKey *soa);
-int dns_answer_find_soa(DnsAnswer *a, DnsResourceKey *key, DnsResourceRecord **ret);
 
-DnsAnswer *dns_answer_merge(DnsAnswer *a, DnsAnswer *b);
+int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key);
+int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr);
+
+int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret);
+
+int dns_answer_merge(DnsAnswer *a, DnsAnswer *b, DnsAnswer **ret);
+int dns_answer_extend(DnsAnswer **a, DnsAnswer *b);
+
 void dns_answer_order_by_scope(DnsAnswer *a, bool prefer_link_local);
 
 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);
+
+static inline unsigned dns_answer_size(DnsAnswer *a) {
+        return a ? a->n_rrs : 0;
+}
 
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsAnswer*, dns_answer_unref);
 
diff --git a/src/resolve/resolved-dns-cache.c b/src/resolve/resolved-dns-cache.c
index f9769f5cda..4aacc268e2 100644
--- a/src/resolve/resolved-dns-cache.c
+++ b/src/resolve/resolved-dns-cache.c
@@ -473,15 +473,15 @@ int dns_cache_put(
                 return 0;
 
         /* Third, add in negative entries if the key has no RR */
-        r = dns_answer_contains(answer, key);
+        r = dns_answer_match_key(answer, key);
         if (r < 0)
                 goto fail;
         if (r > 0)
                 return 0;
 
-        /* See https://tools.ietf.org/html/rfc2308, which
-         * say that a matching SOA record in the packet
-         * is used to to enable negative caching. */
+        /* See https://tools.ietf.org/html/rfc2308, which say that a
+         * matching SOA record in the packet is used to to enable
+         * negative caching. */
 
         r = dns_answer_find_soa(answer, key, &soa);
         if (r < 0)
diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index 8cfed27a34..df12e86167 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -273,7 +273,8 @@ int dnssec_verify_rrset(
                 DnsResourceKey *key,
                 DnsResourceRecord *rrsig,
                 DnsResourceRecord *dnskey,
-                usec_t realtime) {
+                usec_t realtime,
+                DnssecResult *result) {
 
         uint8_t wire_format_name[DNS_WIRE_FOMAT_HOSTNAME_MAX];
         size_t exponent_size, modulus_size, hash_size;
@@ -286,6 +287,7 @@ int dnssec_verify_rrset(
         assert(key);
         assert(rrsig);
         assert(dnskey);
+        assert(result);
         assert(rrsig->key->type == DNS_TYPE_RRSIG);
         assert(dnskey->key->type == DNS_TYPE_DNSKEY);
 
@@ -302,8 +304,10 @@ int dnssec_verify_rrset(
         r = dnssec_rrsig_expired(rrsig, realtime);
         if (r < 0)
                 return r;
-        if (r > 0)
-                return DNSSEC_SIGNATURE_EXPIRED;
+        if (r > 0) {
+                *result = DNSSEC_SIGNATURE_EXPIRED;
+                return 0;
+        }
 
         /* Collect all relevant RRs in a single array, so that we can look at the RRset */
         list = newa(DnsResourceRecord *, a->n_rrs);
@@ -445,7 +449,8 @@ int dnssec_verify_rrset(
         if (r < 0)
                 goto finish;
 
-        r = r ? DNSSEC_VERIFIED : DNSSEC_INVALID;
+        *result = r ? DNSSEC_VALIDATED : DNSSEC_INVALID;
+        r = 0;
 
 finish:
         gcry_md_close(md);
@@ -500,13 +505,15 @@ int dnssec_verify_rrset_search(
                 DnsAnswer *a,
                 DnsResourceKey *key,
                 DnsAnswer *validated_dnskeys,
-                usec_t realtime) {
+                usec_t realtime,
+                DnssecResult *result) {
 
         bool found_rrsig = false, found_dnskey = false;
         DnsResourceRecord *rrsig;
         int r;
 
         assert(key);
+        assert(result);
 
         /* Verifies all RRs from "a" that match the key "key", against DNSKEY and DS RRs in "validated_dnskeys" */
 
@@ -525,7 +532,9 @@ int dnssec_verify_rrset_search(
 
                 found_rrsig = true;
 
+                /* Look for a matching key */
                 DNS_ANSWER_FOREACH(dnskey, validated_dnskeys) {
+                        DnssecResult one_result;
 
                         r = dnssec_rrsig_match_dnskey(rrsig, dnskey);
                         if (r < 0)
@@ -546,11 +555,13 @@ int dnssec_verify_rrset_search(
                          * the RRSet against the RRSIG and DNSKEY
                          * combination. */
 
-                        r = dnssec_verify_rrset(a, key, rrsig, dnskey, realtime);
+                        r = dnssec_verify_rrset(a, key, rrsig, dnskey, realtime, &one_result);
                         if (r < 0 && r != EOPNOTSUPP)
                                 return r;
-                        if (r == DNSSEC_VERIFIED)
-                                return DNSSEC_VERIFIED;
+                        if (one_result == DNSSEC_VALIDATED) {
+                                *result = DNSSEC_VALIDATED;
+                                return 0;
+                        }
 
                         /* If the signature is invalid, or done using
                            an unsupported algorithm, let's try another
@@ -561,12 +572,13 @@ int dnssec_verify_rrset_search(
         }
 
         if (found_dnskey)
-                return DNSSEC_INVALID;
-
-        if (found_rrsig)
-                return DNSSEC_MISSING_KEY;
+                *result = DNSSEC_INVALID;
+        else if (found_rrsig)
+                *result = DNSSEC_MISSING_KEY;
+        else
+                *result = DNSSEC_NO_SIGNATURE;
 
-        return DNSSEC_NO_SIGNATURE;
+        return 0;
 }
 
 int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
@@ -710,9 +722,44 @@ finish:
         return r;
 }
 
+int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_ds) {
+        DnsResourceRecord *ds;
+        int r;
+
+        assert(dnskey);
+
+        if (dnskey->key->type != DNS_TYPE_DNSKEY)
+                return 0;
+
+        DNS_ANSWER_FOREACH(ds, validated_ds) {
+
+                if (ds->key->type != DNS_TYPE_DS)
+                        continue;
+
+                r = dnssec_verify_dnskey(dnskey, ds);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        return 1;
+        }
+
+        return 0;
+}
+
 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);
+
+static const char* const dnssec_result_table[_DNSSEC_RESULT_MAX] = {
+        [DNSSEC_VALIDATED] = "validated",
+        [DNSSEC_INVALID] = "invalid",
+        [DNSSEC_UNSIGNED] = "unsigned",
+        [DNSSEC_NO_SIGNATURE] = "no-signature",
+        [DNSSEC_MISSING_KEY] = "missing-key",
+        [DNSSEC_SIGNATURE_EXPIRED] = "signature-expired",
+        [DNSSEC_FAILED_AUXILIARY] = "failed-auxiliary",
+};
+DEFINE_STRING_TABLE_LOOKUP(dnssec_result, DnssecResult);
diff --git a/src/resolve/resolved-dns-dnssec.h b/src/resolve/resolved-dns-dnssec.h
index f4cb58988a..f0825ba23f 100644
--- a/src/resolve/resolved-dns-dnssec.h
+++ b/src/resolve/resolved-dns-dnssec.h
@@ -22,6 +22,7 @@
 ***/
 
 typedef enum DnssecMode DnssecMode;
+typedef enum DnssecResult DnssecResult;
 
 #include "dns-domain.h"
 #include "resolved-dns-answer.h"
@@ -41,12 +42,16 @@ enum DnssecMode {
         _DNSSEC_MODE_INVALID = -1
 };
 
-enum {
-        DNSSEC_VERIFIED,
+enum DnssecResult {
+        DNSSEC_VALIDATED,
         DNSSEC_INVALID,
+        DNSSEC_UNSIGNED,
         DNSSEC_NO_SIGNATURE,
         DNSSEC_MISSING_KEY,
         DNSSEC_SIGNATURE_EXPIRED,
+        DNSSEC_FAILED_AUXILIARY,
+        _DNSSEC_RESULT_MAX,
+        _DNSSEC_RESULT_INVALID = -1
 };
 
 #define DNSSEC_CANONICAL_HOSTNAME_MAX (DNS_HOSTNAME_MAX + 2)
@@ -54,10 +59,11 @@ enum {
 int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnskey);
 int dnssec_key_match_rrsig(DnsResourceKey *key, DnsResourceRecord *rrsig);
 
-int dnssec_verify_rrset(DnsAnswer *answer, DnsResourceKey *key, DnsResourceRecord *rrsig, DnsResourceRecord *dnskey, usec_t realtime);
-int dnssec_verify_rrset_search(DnsAnswer *a, DnsResourceKey *key, DnsAnswer *validated_dnskeys, usec_t realtime);
+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);
 
 int dnssec_verify_dnskey(DnsResourceRecord *dnskey, DnsResourceRecord *ds);
+int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_ds);
 
 uint16_t dnssec_keytag(DnsResourceRecord *dnskey);
 
@@ -65,3 +71,6 @@ int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max);
 
 const char* dnssec_mode_to_string(DnssecMode m) _const_;
 DnssecMode dnssec_mode_from_string(const char *s) _pure_;
+
+const char* dnssec_result_to_string(DnssecResult m) _const_;
+DnssecResult dnssec_result_from_string(const char *s) _pure_;
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index 5dc42fb96d..a6565f2ba2 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -59,7 +59,7 @@ static void dns_query_candidate_stop(DnsQueryCandidate *c) {
         assert(c);
 
         while ((t = set_steal_first(c->transactions))) {
-                set_remove(t->query_candidates, c);
+                set_remove(t->notify_query_candidates, c);
                 dns_transaction_gc(t);
         }
 }
@@ -116,32 +116,35 @@ static int dns_query_candidate_add_transaction(DnsQueryCandidate *c, DnsResource
         assert(c);
         assert(key);
 
-        r = set_ensure_allocated(&c->transactions, NULL);
-        if (r < 0)
-                return r;
-
         t = dns_scope_find_transaction(c->scope, key, true);
         if (!t) {
                 r = dns_transaction_new(&t, c->scope, key);
                 if (r < 0)
                         return r;
+        } else {
+                if (set_contains(c->transactions, t))
+                        return 0;
         }
 
-        r = set_ensure_allocated(&t->query_candidates, NULL);
+        r = set_ensure_allocated(&c->transactions, NULL);
+        if (r < 0)
+                goto gc;
+
+        r = set_ensure_allocated(&t->notify_query_candidates, NULL);
         if (r < 0)
                 goto gc;
 
-        r = set_put(t->query_candidates, c);
+        r = set_put(t->notify_query_candidates, c);
         if (r < 0)
                 goto gc;
 
         r = set_put(c->transactions, t);
         if (r < 0) {
-                set_remove(t->query_candidates, c);
+                (void) set_remove(t->notify_query_candidates, c);
                 goto gc;
         }
 
-        return 0;
+        return 1;
 
 gc:
         dns_transaction_gc(t);
@@ -183,13 +186,20 @@ static DnsTransactionState dns_query_candidate_state(DnsQueryCandidate *c) {
                 switch (t->state) {
 
                 case DNS_TRANSACTION_PENDING:
-                case DNS_TRANSACTION_NULL:
-                        return t->state;
+                case DNS_TRANSACTION_VALIDATING:
+                        /* If there's one transaction currently in
+                         * VALIDATING state, then this means there's
+                         * also one in PENDING state, hence we can
+                         * return PENDING immediately. */
+                        return DNS_TRANSACTION_PENDING;
 
                 case DNS_TRANSACTION_SUCCESS:
                         state = t->state;
                         break;
 
+                case DNS_TRANSACTION_NULL:
+                        assert_not_reached("Transaction not started?");
+
                 default:
                         if (state != DNS_TRANSACTION_SUCCESS)
                                 state = t->state;
@@ -233,7 +243,7 @@ fail:
         return r;
 }
 
-void dns_query_candidate_ready(DnsQueryCandidate *c) {
+void dns_query_candidate_notify(DnsQueryCandidate *c) {
         DnsTransactionState state;
         int r;
 
@@ -241,7 +251,7 @@ void dns_query_candidate_ready(DnsQueryCandidate *c) {
 
         state = dns_query_candidate_state(c);
 
-        if (IN_SET(state, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_NULL))
+        if (DNS_TRANSACTION_IS_LIVE(state))
                 return;
 
         if (state != DNS_TRANSACTION_SUCCESS && c->search_domain) {
@@ -394,8 +404,8 @@ int dns_query_make_auxiliary(DnsQuery *q, DnsQuery *auxiliary_for) {
 
 static void dns_query_complete(DnsQuery *q, DnsTransactionState state) {
         assert(q);
-        assert(!IN_SET(state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
-        assert(IN_SET(q->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
+        assert(!DNS_TRANSACTION_IS_LIVE(state));
+        assert(DNS_TRANSACTION_IS_LIVE(q->state));
 
         /* Note that this call might invalidate the query. Callers
          * should hence not attempt to access the query or transaction
@@ -970,9 +980,10 @@ fail:
 
 static void dns_query_accept(DnsQuery *q, DnsQueryCandidate *c) {
         DnsTransactionState state = DNS_TRANSACTION_NO_SERVERS;
+        bool has_authenticated = false, has_non_authenticated = false;
         DnsTransaction *t;
         Iterator i;
-        bool has_authenticated = false, has_non_authenticated = false;
+        int r;
 
         assert(q);
 
@@ -988,16 +999,11 @@ static void dns_query_accept(DnsQuery *q, DnsQueryCandidate *c) {
 
                 case DNS_TRANSACTION_SUCCESS: {
                         /* We found a successfuly reply, merge it into the answer */
-                        DnsAnswer *merged;
-
-                        merged = dns_answer_merge(q->answer, t->answer);
-                        if (!merged) {
+                        r = dns_answer_extend(&q->answer, t->answer);
+                        if (r < 0) {
                                 dns_query_complete(q, DNS_TRANSACTION_RESOURCES);
                                 return;
                         }
-
-                        dns_answer_unref(q->answer);
-                        q->answer = merged;
                         q->answer_rcode = t->answer_rcode;
 
                         if (t->answer_authenticated)
@@ -1009,8 +1015,9 @@ static void dns_query_accept(DnsQuery *q, DnsQueryCandidate *c) {
                         break;
                 }
 
-                case DNS_TRANSACTION_PENDING:
                 case DNS_TRANSACTION_NULL:
+                case DNS_TRANSACTION_PENDING:
+                case DNS_TRANSACTION_VALIDATING:
                 case DNS_TRANSACTION_ABORTED:
                         /* Ignore transactions that didn't complete */
                         continue;
@@ -1049,7 +1056,7 @@ void dns_query_ready(DnsQuery *q) {
         bool pending = false;
 
         assert(q);
-        assert(IN_SET(q->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
+        assert(DNS_TRANSACTION_IS_LIVE(q->state));
 
         /* Note that this call might invalidate the query. Callers
          * should hence not attempt to access the query or transaction
@@ -1066,14 +1073,16 @@ void dns_query_ready(DnsQuery *q) {
                 switch (state) {
 
                 case DNS_TRANSACTION_SUCCESS:
-                        /* One of the transactions is successful,
+                        /* One of the candidates is successful,
                          * let's use it, and copy its data out */
                         dns_query_accept(q, c);
                         return;
 
-                case DNS_TRANSACTION_PENDING:
                 case DNS_TRANSACTION_NULL:
-                        /* One of the transactions is still going on, let's maybe wait for it */
+                case DNS_TRANSACTION_PENDING:
+                case DNS_TRANSACTION_VALIDATING:
+                        /* One of the candidates is still going on,
+                         * let's maybe wait for it */
                         pending = true;
                         break;
 
diff --git a/src/resolve/resolved-dns-query.h b/src/resolve/resolved-dns-query.h
index b71bb2352b..d7f96c3ca4 100644
--- a/src/resolve/resolved-dns-query.h
+++ b/src/resolve/resolved-dns-query.h
@@ -95,7 +95,7 @@ struct DnsQuery {
 };
 
 DnsQueryCandidate* dns_query_candidate_free(DnsQueryCandidate *c);
-void dns_query_candidate_ready(DnsQueryCandidate *c);
+void dns_query_candidate_notify(DnsQueryCandidate *c);
 
 int dns_query_new(Manager *m, DnsQuery **q, DnsQuestion *question, int family, uint64_t flags);
 DnsQuery *dns_query_free(DnsQuery *q);
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index c7667990b6..55e85eec2b 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -253,7 +253,24 @@ int dns_resource_key_match_cname(const DnsResourceKey *key, const DnsResourceRec
         }
 
         return 0;
+}
+
+int dns_resource_key_match_soa(const DnsResourceKey *key, const DnsResourceKey *soa) {
+        assert(soa);
+        assert(key);
+
+        /* Checks whether 'soa' is a SOA record for the specified key. */
+
+        if (soa->class != DNS_CLASS_IN)
+                return 0;
 
+        if (soa->type != DNS_TYPE_SOA)
+                return 0;
+
+        if (!dns_name_endswith(DNS_RESOURCE_KEY_NAME(key), DNS_RESOURCE_KEY_NAME(soa)))
+                return 0;
+
+        return 1;
 }
 
 static void dns_resource_key_hash_func(const void *i, struct siphash *state) {
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index 941f3cfe67..4c0f72eea3 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -247,6 +247,7 @@ 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_cname(const DnsResourceKey *key, const DnsResourceRecord *rr, 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);
 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsResourceKey*, dns_resource_key_unref);
 
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index a0b8e1e223..00ecd3d11e 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -32,6 +32,7 @@
 DnsTransaction* dns_transaction_free(DnsTransaction *t) {
         DnsQueryCandidate *c;
         DnsZoneItem *i;
+        DnsTransaction *z;
 
         if (!t)
                 return NULL;
@@ -59,14 +60,25 @@ DnsTransaction* dns_transaction_free(DnsTransaction *t) {
 
         dns_resource_key_unref(t->key);
 
-        while ((c = set_steal_first(t->query_candidates)))
+        while ((c = set_steal_first(t->notify_query_candidates)))
                 set_remove(c->transactions, t);
+        set_free(t->notify_query_candidates);
 
-        set_free(t->query_candidates);
-
-        while ((i = set_steal_first(t->zone_items)))
+        while ((i = set_steal_first(t->notify_zone_items)))
                 i->probe_transaction = NULL;
-        set_free(t->zone_items);
+        set_free(t->notify_zone_items);
+
+        while ((z = set_steal_first(t->notify_transactions)))
+                set_remove(z->dnssec_transactions, t);
+        set_free(t->notify_transactions);
+
+        while ((z = set_steal_first(t->dnssec_transactions))) {
+                set_remove(z->notify_transactions, t);
+                dns_transaction_gc(z);
+        }
+        set_free(t->dnssec_transactions);
+
+        dns_answer_unref(t->validated_keys);
 
         free(t);
         return NULL;
@@ -80,7 +92,9 @@ void dns_transaction_gc(DnsTransaction *t) {
         if (t->block_gc > 0)
                 return;
 
-        if (set_isempty(t->query_candidates) && set_isempty(t->zone_items))
+        if (set_isempty(t->notify_query_candidates) &&
+            set_isempty(t->notify_zone_items) &&
+            set_isempty(t->notify_transactions))
                 dns_transaction_free(t);
 }
 
@@ -106,6 +120,7 @@ int dns_transaction_new(DnsTransaction **ret, DnsScope *s, DnsResourceKey *key)
 
         t->dns_udp_fd = -1;
         t->answer_source = _DNS_TRANSACTION_SOURCE_INVALID;
+        t->dnssec_result = _DNSSEC_RESULT_INVALID;
         t->key = dns_resource_key_ref(key);
 
         /* Find a fresh, unused transaction id */
@@ -175,7 +190,7 @@ static void dns_transaction_tentative(DnsTransaction *t, DnsPacket *p) {
         log_debug("We have the lexicographically larger IP address and thus lost in the conflict.");
 
         t->block_gc++;
-        while ((z = set_first(t->zone_items))) {
+        while ((z = set_first(t->notify_zone_items))) {
                 /* First, make sure the zone item drops the reference
                  * to us */
                 dns_zone_item_probe_stop(z);
@@ -192,10 +207,11 @@ static void dns_transaction_tentative(DnsTransaction *t, DnsPacket *p) {
 void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state) {
         DnsQueryCandidate *c;
         DnsZoneItem *z;
+        DnsTransaction *d;
         Iterator i;
 
         assert(t);
-        assert(!IN_SET(state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING));
+        assert(!DNS_TRANSACTION_IS_LIVE(state));
 
         /* Note that this call might invalidate the query. Callers
          * should hence not attempt to access the query or transaction
@@ -215,10 +231,12 @@ void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state) {
         /* Notify all queries that are interested, but make sure the
          * transaction isn't freed while we are still looking at it */
         t->block_gc++;
-        SET_FOREACH(c, t->query_candidates, i)
-                dns_query_candidate_ready(c);
-        SET_FOREACH(z, t->zone_items, i)
-                dns_zone_item_ready(z);
+        SET_FOREACH(c, t->notify_query_candidates, i)
+                dns_query_candidate_notify(c);
+        SET_FOREACH(z, t->notify_zone_items, i)
+                dns_zone_item_notify(z);
+        SET_FOREACH(d, t->notify_transactions, i)
+                dns_transaction_notify(d, t);
         t->block_gc--;
 
         dns_transaction_gc(t);
@@ -348,6 +366,73 @@ static void dns_transaction_next_dns_server(DnsTransaction *t) {
         dns_scope_next_dns_server(t->scope);
 }
 
+static void dns_transaction_cache_answer(DnsTransaction *t) {
+        unsigned n_cache;
+
+        assert(t);
+
+        /* For mDNS we cache whenever we get the packet, rather than
+         * in each transaction. */
+        if (!IN_SET(t->scope->protocol, DNS_PROTOCOL_DNS, DNS_PROTOCOL_LLMNR))
+                return;
+
+        /* We never cache if this packet is from the local host, under
+         * the assumption that a locally running DNS server would
+         * cache this anyway, and probably knows better when to flush
+         * the cache then we could. */
+        if (!DNS_PACKET_SHALL_CACHE(t->received))
+                return;
+
+        /* 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)
+                n_cache = dns_answer_size(t->answer);
+        else
+                n_cache = DNS_PACKET_ANCOUNT(t->received);
+
+        dns_cache_put(&t->scope->cache,
+                      t->key,
+                      t->answer_rcode,
+                      t->answer,
+                      n_cache,
+                      t->answer_authenticated,
+                      0,
+                      t->received->family,
+                      &t->received->sender);
+}
+
+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))
+                return;
+
+        /* All our auxiliary DNSSEC transactions are complete now. Try
+         * to validate our RRset now. */
+        r = dns_transaction_validate_dnssec(t);
+        if (r < 0) {
+                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+                return;
+        }
+
+        if (!IN_SET(t->dnssec_result, _DNSSEC_RESULT_INVALID, DNSSEC_VALIDATED, DNSSEC_NO_SIGNATURE /* FOR NOW! */)) {
+                dns_transaction_complete(t, DNS_TRANSACTION_DNSSEC_FAILED);
+                return;
+        }
+
+        dns_transaction_cache_answer(t);
+
+        if (t->answer_rcode == DNS_RCODE_SUCCESS)
+                dns_transaction_complete(t, DNS_TRANSACTION_SUCCESS);
+        else
+                dns_transaction_complete(t, DNS_TRANSACTION_FAILURE);
+}
+
 void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
         usec_t ts;
         int r;
@@ -525,23 +610,19 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
                 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 */
-                if (DNS_PACKET_SHALL_CACHE(p))
-                        dns_cache_put(&t->scope->cache,
-                                      t->key,
-                                      DNS_PACKET_RCODE(p),
-                                      p->answer,
-                                      DNS_PACKET_ANCOUNT(p),
-                                      t->answer_authenticated,
-                                      0,
-                                      p->family,
-                                      &p->sender);
+                r = dns_transaction_request_dnssec_keys(t);
+                if (r < 0) {
+                        dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+                        return;
+                }
+                if (r > 0) {
+                        /* There are DNSSEC transactions pending now. Update the state accordingly. */
+                        t->state = DNS_TRANSACTION_VALIDATING;
+                        return;
+                }
         }
 
-        if (DNS_PACKET_RCODE(p) == DNS_RCODE_SUCCESS)
-                dns_transaction_complete(t, DNS_TRANSACTION_SUCCESS);
-        else
-                dns_transaction_complete(t, DNS_TRANSACTION_FAILURE);
+        dns_transaction_process_dnssec(t);
 }
 
 static int on_dns_packet(sd_event_source *s, int fd, uint32_t revents, void *userdata) {
@@ -700,7 +781,7 @@ static int dns_transaction_prepare_next_attempt(DnsTransaction *t, usec_t ts) {
 
         /* Check the zone, but only if this transaction is not used
          * for probing or verifying a zone item. */
-        if (set_isempty(t->zone_items)) {
+        if (set_isempty(t->notify_zone_items)) {
 
                 r = dns_zone_lookup(&t->scope->zone, t->key, &t->answer, NULL, NULL);
                 if (r < 0)
@@ -716,7 +797,7 @@ static int dns_transaction_prepare_next_attempt(DnsTransaction *t, usec_t ts) {
 
         /* Check the cache, but only if this transaction is not used
          * for probing or verifying a zone item. */
-        if (set_isempty(t->zone_items)) {
+        if (set_isempty(t->notify_zone_items)) {
 
                 /* Before trying the cache, let's make sure we figured out a
                  * server to use. Should this cause a change of server this
@@ -887,14 +968,22 @@ int dns_transaction_go(DnsTransaction *t) {
         assert(t);
 
         assert_se(sd_event_now(t->scope->manager->event, clock_boottime_or_monotonic(), &ts) >= 0);
+
         r = dns_transaction_prepare_next_attempt(t, ts);
         if (r <= 0)
                 return r;
 
-        log_debug("Excercising transaction on scope %s on %s/%s",
-                  dns_protocol_to_string(t->scope->protocol),
-                  t->scope->link ? t->scope->link->name : "*",
-                  t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
+        if (log_get_max_level() >= LOG_DEBUG) {
+                _cleanup_free_ char *ks = NULL;
+
+                (void) dns_resource_key_to_string(t->key, &ks);
+
+                log_debug("Excercising transaction for <%s> on scope %s on %s/%s",
+                          ks ? strstrip(ks) : "???",
+                          dns_protocol_to_string(t->scope->protocol),
+                          t->scope->link ? t->scope->link->name : "*",
+                          t->scope->family == AF_UNSPEC ? "*" : af_to_name(t->scope->family));
+        }
 
         if (!t->initial_jitter_scheduled &&
             (t->scope->protocol == DNS_PROTOCOL_LLMNR ||
@@ -999,9 +1088,364 @@ int dns_transaction_go(DnsTransaction *t) {
         return 1;
 }
 
+static int dns_transaction_add_dnssec_transaction(DnsTransaction *t, DnsResourceKey *key, DnsTransaction **ret) {
+        DnsTransaction *aux;
+        int r;
+
+        assert(t);
+        assert(ret);
+        assert(key);
+
+        aux = dns_scope_find_transaction(t->scope, key, true);
+        if (!aux) {
+                r = dns_transaction_new(&aux, t->scope, key);
+                if (r < 0)
+                        return r;
+        } else {
+                if (set_contains(t->dnssec_transactions, aux)) {
+                        *ret = aux;
+                        return 0;
+                }
+        }
+
+        r = set_ensure_allocated(&t->dnssec_transactions, NULL);
+        if (r < 0)
+                goto gc;
+
+        r = set_ensure_allocated(&aux->notify_transactions, NULL);
+        if (r < 0)
+                goto gc;
+
+        r = set_put(t->dnssec_transactions, aux);
+        if (r < 0)
+                goto gc;
+
+        r = set_put(aux->notify_transactions, t);
+        if (r < 0) {
+                (void) set_remove(t->dnssec_transactions, aux);
+                goto gc;
+        }
+
+        *ret = aux;
+        return 1;
+
+gc:
+        dns_transaction_gc(aux);
+        return r;
+}
+
+static int dns_transaction_request_dnssec_rr(DnsTransaction *t, DnsResourceKey *key) {
+        _cleanup_(dns_answer_unrefp) DnsAnswer *a = NULL;
+        DnsTransaction *aux;
+        int r;
+
+        assert(t);
+        assert(key);
+
+        /* Try to get the data from the trust anchor */
+        r = dns_trust_anchor_lookup(&t->scope->manager->trust_anchor, key, &a);
+        if (r < 0)
+                return r;
+        if (r > 0) {
+                r = dns_answer_extend(&t->validated_keys, a);
+                if (r < 0)
+                        return r;
+
+                return 0;
+        }
+
+        /* This didn't work, ask for it via the network/cache then. */
+        r = dns_transaction_add_dnssec_transaction(t, key, &aux);
+        if (r < 0)
+                return r;
+
+        if (aux->state == DNS_TRANSACTION_NULL) {
+                r = dns_transaction_go(aux);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
+}
+
+int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
+        DnsResourceRecord *rr;
+        int r;
+
+        assert(t);
+
+        if (t->scope->dnssec_mode != DNSSEC_YES)
+                return 0;
+
+        DNS_ANSWER_FOREACH(rr, t->answer) {
+
+                switch (rr->key->type) {
+
+                case DNS_TYPE_RRSIG: {
+                        /* For each RRSIG we request the matching DNSKEY */
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *dnskey = NULL;
+
+                        /* If this RRSIG is about a DNSKEY RR and the
+                         * signer is the same as the owner, then we
+                         * already have the DNSKEY, and we don't have
+                         * to look for more. */
+                        if (rr->rrsig.type_covered == DNS_TYPE_DNSKEY) {
+                                r = dns_name_equal(rr->rrsig.signer, DNS_RESOURCE_KEY_NAME(rr->key));
+                                if (r < 0)
+                                        return r;
+                                if (r > 0)
+                                        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 (r < 0)
+                                return r;
+                        if (r == 0)
+                                continue;
+
+                        dnskey = dns_resource_key_new(rr->key->class, DNS_TYPE_DNSKEY, rr->rrsig.signer);
+                        if (!dnskey)
+                                return -ENOMEM;
+
+                        log_debug("Requesting DNSKEY to validate transaction %" PRIu16" (key tag: %" PRIu16 ").", t->id, rr->rrsig.key_tag);
+
+                        r = dns_transaction_request_dnssec_rr(t, dnskey);
+                        if (r < 0)
+                                return r;
+                        break;
+                }
+
+                case DNS_TYPE_DNSKEY: {
+                        /* For each DNSKEY we request the matching DS */
+                        _cleanup_(dns_resource_key_unrefp) DnsResourceKey *ds = NULL;
+
+                        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));
+
+                        r = dns_transaction_request_dnssec_rr(t, ds);
+                        if (r < 0)
+                                return r;
+
+                        break;
+                }}
+        }
+
+        return !set_isempty(t->dnssec_transactions);
+}
+
+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);
+
+        /* Invoked whenever any of our auxiliary DNSSEC transactions
+           completed its work. We simply copy the answer from that
+           transaction over. */
+
+        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;
+                }
+        }
+
+        /* 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);
+}
+
+int dns_transaction_validate_dnssec(DnsTransaction *t) {
+        _cleanup_(dns_answer_unrefp) DnsAnswer *validated = NULL;
+        DnsResourceRecord *rr;
+        int ifindex, r;
+
+        assert(t);
+
+        /* We have now collected all DS and DNSKEY RRs in
+         * t->validated_keys, let's see which RRs we can now
+         * authenticate with that. */
+
+        if (t->scope->dnssec_mode != DNSSEC_YES)
+                return 0;
+
+        /* Already validated */
+        if (t->dnssec_result != _DNSSEC_RESULT_INVALID)
+                return 0;
+
+        if (IN_SET(t->answer_source, DNS_TRANSACTION_ZONE, DNS_TRANSACTION_TRUST_ANCHOR)) {
+                t->dnssec_result = DNSSEC_VALIDATED;
+                t->answer_authenticated = true;
+                return 0;
+        }
+
+        if (log_get_max_level() >= LOG_DEBUG) {
+                _cleanup_free_ char *ks = NULL;
+
+                (void) dns_resource_key_to_string(t->key, &ks);
+                log_debug("Validating response from transaction %" PRIu16 " (%s).", t->id, ks ? strstrip(ks) : "???");
+        }
+
+        /* First see if there are DNSKEYs we already known a validated DS for. */
+        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);
+                if (r < 0)
+                        return r;
+        }
+
+        for (;;) {
+                bool changed = false, missing_key_for_transaction = false;
+
+                DNS_ANSWER_FOREACH(rr, t->answer) {
+                        DnssecResult result;
+
+                        if (rr->key->type == DNS_TYPE_RRSIG)
+                                continue;
+
+                        r = dnssec_verify_rrset_search(t->answer, rr->key, t->validated_keys, USEC_INFINITY, &result);
+                        if (r < 0)
+                                return r;
+
+                        if (log_get_max_level() >= LOG_DEBUG) {
+                                _cleanup_free_ char *rrs = NULL;
+
+                                (void) dns_resource_record_to_string(rr, &rrs);
+                                log_debug("Looking at %s: %s", rrs ? strstrip(rrs) : "???", dnssec_result_to_string(result));
+                        }
+
+                        switch (result) {
+
+                        case 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
+                                         * add these keys to the set
+                                         * of validated keys for this
+                                         * transaction. */
+
+                                        r = dns_answer_copy_by_key(&t->validated_keys, t->answer, rr->key);
+                                        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);
+                                if (r < 0)
+                                        return r;
+
+                                changed = true;
+                                break;
+
+                        case DNSSEC_INVALID:
+                        case DNSSEC_NO_SIGNATURE:
+                        case DNSSEC_SIGNATURE_EXPIRED:
+
+                                /* Is this the RRset that we were looking for? If so, this is fatal for the whole transaction */
+                                r = dns_resource_key_match_rr(t->key, rr, NULL);
+                                if (r < 0)
+                                        return r;
+                                if (r > 0) {
+                                        t->dnssec_result = result;
+                                        return 0;
+                                }
+
+                                /* Is this a CNAME for a record we were looking for? If so, it's also fatal for the whole transaction */
+                                r = dns_resource_key_match_cname(t->key, rr, NULL);
+                                if (r < 0)
+                                        return r;
+                                if (r > 0) {
+                                        t->dnssec_result = result;
+                                        return 0;
+                                }
+
+                                /* This is just something auxiliary. Just remove the RRset and continue. */
+                                r = dns_answer_remove_by_key(&t->answer, rr->key);
+                                if (r < 0)
+                                        return r;
+
+                                changed = true;
+                                break;
+
+                        case DNSSEC_MISSING_KEY:
+                                /* They key is missing? Let's continue
+                                 * with the next iteration, maybe
+                                 * we'll find it in an DNSKEY RRset
+                                 * later on. */
+
+                                r = dns_resource_key_equal(rr->key, t->key);
+                                if (r < 0)
+                                        return r;
+                                if (r > 0)
+                                        missing_key_for_transaction = true;
+
+                                break;
+
+                        default:
+                                assert_not_reached("Unexpected DNSSEC result");
+                        }
+
+                        if (changed)
+                                break;
+                }
+
+                if (changed)
+                        continue;
+
+                /* This didn't work either, there's no point in
+                 * continuing. */
+                if (missing_key_for_transaction) {
+                        t->dnssec_result = DNSSEC_MISSING_KEY;
+                        return 0;
+                }
+
+                break;
+        }
+
+        dns_answer_unref(t->answer);
+        t->answer = validated;
+        validated = NULL;
+
+        t->answer_authenticated = true;
+        t->dnssec_result = DNSSEC_VALIDATED;
+        return 1;
+}
+
 static const char* const dns_transaction_state_table[_DNS_TRANSACTION_STATE_MAX] = {
         [DNS_TRANSACTION_NULL] = "null",
         [DNS_TRANSACTION_PENDING] = "pending",
+        [DNS_TRANSACTION_VALIDATING] = "validating",
         [DNS_TRANSACTION_FAILURE] = "failure",
         [DNS_TRANSACTION_SUCCESS] = "success",
         [DNS_TRANSACTION_NO_SERVERS] = "no-servers",
@@ -1010,6 +1454,7 @@ static const char* const dns_transaction_state_table[_DNS_TRANSACTION_STATE_MAX]
         [DNS_TRANSACTION_INVALID_REPLY] = "invalid-reply",
         [DNS_TRANSACTION_RESOURCES] = "resources",
         [DNS_TRANSACTION_ABORTED] = "aborted",
+        [DNS_TRANSACTION_DNSSEC_FAILED] = "dnssec-failed",
 };
 DEFINE_STRING_TABLE_LOOKUP(dns_transaction_state, DnsTransactionState);
 
diff --git a/src/resolve/resolved-dns-transaction.h b/src/resolve/resolved-dns-transaction.h
index af08b20e44..2328e7937c 100644
--- a/src/resolve/resolved-dns-transaction.h
+++ b/src/resolve/resolved-dns-transaction.h
@@ -28,6 +28,7 @@ typedef enum DnsTransactionSource DnsTransactionSource;
 enum DnsTransactionState {
         DNS_TRANSACTION_NULL,
         DNS_TRANSACTION_PENDING,
+        DNS_TRANSACTION_VALIDATING,
         DNS_TRANSACTION_FAILURE,
         DNS_TRANSACTION_SUCCESS,
         DNS_TRANSACTION_NO_SERVERS,
@@ -36,10 +37,13 @@ enum DnsTransactionState {
         DNS_TRANSACTION_INVALID_REPLY,
         DNS_TRANSACTION_RESOURCES,
         DNS_TRANSACTION_ABORTED,
+        DNS_TRANSACTION_DNSSEC_FAILED,
         _DNS_TRANSACTION_STATE_MAX,
         _DNS_TRANSACTION_STATE_INVALID = -1
 };
 
+#define DNS_TRANSACTION_IS_LIVE(state) IN_SET((state), DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_VALIDATING)
+
 enum DnsTransactionSource {
         DNS_TRANSACTION_NETWORK,
         DNS_TRANSACTION_CACHE,
@@ -60,6 +64,8 @@ struct DnsTransaction {
         DnsResourceKey *key;
 
         DnsTransactionState state;
+        DnssecResult dnssec_result;
+
         uint16_t id;
 
         bool initial_jitter_scheduled;
@@ -72,6 +78,9 @@ struct DnsTransaction {
         DnsTransactionSource answer_source;
         bool answer_authenticated;
 
+        /* Contains DS and DNSKEY RRs we already verified and need to authenticate this reply */
+        DnsAnswer *validated_keys;
+
         usec_t start_usec;
         usec_t next_attempt_after;
         sd_event_source *timeout_event_source;
@@ -83,7 +92,7 @@ struct DnsTransaction {
         /* The active server */
         DnsServer *server;
 
-        /* the features of the DNS server at time of transaction start */
+        /* The features of the DNS server at time of transaction start */
         DnsServerFeatureLevel current_features;
 
         /* TCP connection logic, if we need it */
@@ -92,11 +101,21 @@ struct DnsTransaction {
         /* Query candidates this transaction is referenced by and that
          * shall be notified about this specific transaction
          * completing. */
-        Set *query_candidates;
+        Set *notify_query_candidates;
 
         /* Zone items this transaction is referenced by and that shall
          * be notified about completion. */
-        Set *zone_items;
+        Set *notify_zone_items;
+
+        /* Other transactions that this transactions is referenced by
+         * and that shall be notified about completion. This is used
+         * when transactions want to validate their RRsets, but need
+         * another DNSKEY or DS RR to do so. */
+        Set *notify_transactions;
+
+        /* The opposite direction: the transactions this transaction
+         * created in order to request DNSKEY or DS RRs. */
+        Set *dnssec_transactions;
 
         unsigned block_gc;
 
@@ -112,6 +131,10 @@ int dns_transaction_go(DnsTransaction *t);
 void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p);
 void dns_transaction_complete(DnsTransaction *t, DnsTransactionState state);
 
+void dns_transaction_notify(DnsTransaction *t, DnsTransaction *source);
+int dns_transaction_validate_dnssec(DnsTransaction *t);
+int dns_transaction_request_dnssec_keys(DnsTransaction *t);
+
 const char* dns_transaction_state_to_string(DnsTransactionState p) _const_;
 DnsTransactionState dns_transaction_state_from_string(const char *s) _pure_;
 
diff --git a/src/resolve/resolved-dns-zone.c b/src/resolve/resolved-dns-zone.c
index 78f44d51a2..8046e2ed34 100644
--- a/src/resolve/resolved-dns-zone.c
+++ b/src/resolve/resolved-dns-zone.c
@@ -39,7 +39,7 @@ void dns_zone_item_probe_stop(DnsZoneItem *i) {
         t = i->probe_transaction;
         i->probe_transaction = NULL;
 
-        set_remove(t->zone_items, i);
+        set_remove(t->notify_zone_items, i);
         dns_transaction_gc(t);
 }
 
@@ -184,11 +184,11 @@ static int dns_zone_item_probe_start(DnsZoneItem *i)  {
                         return r;
         }
 
-        r = set_ensure_allocated(&t->zone_items, NULL);
+        r = set_ensure_allocated(&t->notify_zone_items, NULL);
         if (r < 0)
                 goto gc;
 
-        r = set_put(t->zone_items, i);
+        r = set_put(t->notify_zone_items, i);
         if (r < 0)
                 goto gc;
 
@@ -206,7 +206,7 @@ static int dns_zone_item_probe_start(DnsZoneItem *i)  {
                 }
         }
 
-        dns_zone_item_ready(i);
+        dns_zone_item_notify(i);
         return 0;
 
 gc:
@@ -491,7 +491,7 @@ void dns_zone_item_conflict(DnsZoneItem *i) {
                 manager_next_hostname(i->scope->manager);
 }
 
-void dns_zone_item_ready(DnsZoneItem *i) {
+void dns_zone_item_notify(DnsZoneItem *i) {
         _cleanup_free_ char *pretty = NULL;
 
         assert(i);
@@ -500,7 +500,7 @@ void dns_zone_item_ready(DnsZoneItem *i) {
         if (i->block_ready > 0)
                 return;
 
-        if (IN_SET(i->probe_transaction->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING))
+        if (IN_SET(i->probe_transaction->state, DNS_TRANSACTION_NULL, DNS_TRANSACTION_PENDING, DNS_TRANSACTION_VALIDATING))
                 return;
 
         if (i->probe_transaction->state == DNS_TRANSACTION_SUCCESS) {
diff --git a/src/resolve/resolved-dns-zone.h b/src/resolve/resolved-dns-zone.h
index 44a8624c30..dbd6a2a368 100644
--- a/src/resolve/resolved-dns-zone.h
+++ b/src/resolve/resolved-dns-zone.h
@@ -70,7 +70,7 @@ void dns_zone_remove_rr(DnsZone *z, DnsResourceRecord *rr);
 int dns_zone_lookup(DnsZone *z, DnsResourceKey *key, DnsAnswer **answer, DnsAnswer **soa, bool *tentative);
 
 void dns_zone_item_conflict(DnsZoneItem *i);
-void dns_zone_item_ready(DnsZoneItem *i);
+void dns_zone_item_notify(DnsZoneItem *i);
 
 int dns_zone_check_conflicts(DnsZone *zone, DnsResourceRecord *rr);
 int dns_zone_verify_conflicts(DnsZone *zone, DnsResourceKey *key);
diff --git a/src/resolve/test-dnssec.c b/src/resolve/test-dnssec.c
index 0b2ffeeddd..a2118513f1 100644
--- a/src/resolve/test-dnssec.c
+++ b/src/resolve/test-dnssec.c
@@ -56,6 +56,7 @@ static void test_dnssec_verify_rrset(void) {
         _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *a = NULL, *rrsig = NULL, *dnskey = NULL;
         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
         _cleanup_free_ char *x = NULL, *y = NULL, *z = NULL;
+        DnssecResult result;
 
         a = dns_resource_record_new_full(DNS_CLASS_IN, DNS_TYPE_A, "nAsA.gov");
         assert_se(a);
@@ -106,7 +107,8 @@ static void test_dnssec_verify_rrset(void) {
         assert_se(dns_answer_add(answer, a, 0) >= 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) == DNSSEC_VERIFIED);
+        assert_se(dnssec_verify_rrset(answer, a->key, rrsig, dnskey, 1449092754*USEC_PER_SEC, &result) >= 0);
+        assert_se(result == DNSSEC_VALIDATED);
 }
 
 static void test_dnssec_verify_dns_key(void) {