Merge pull request #2289 from poettering/dnssec13

Thirteenth DNSSEC patch set

31 files changed, 1232 insertions, 456 deletions

diff --git a/src/basic/fd-util.h b/src/basic/fd-util.h
index 5ce1592eeb..973413ff42 100644
--- a/src/basic/fd-util.h
+++ b/src/basic/fd-util.h
@@ -73,3 +73,6 @@ int same_fd(int a, int b);
 void cmsg_close_all(struct msghdr *mh);
 
 bool fdname_is_valid(const char *s);
+
+#define ERRNO_IS_DISCONNECT(r) \
+        IN_SET(r, ENOTCONN, ECONNRESET, ECONNREFUSED, ECONNABORTED, EPIPE)
diff --git a/src/basic/hash-funcs.c b/src/basic/hash-funcs.c
new file mode 100644
index 0000000000..d4affaffee
--- /dev/null
+++ b/src/basic/hash-funcs.c
@@ -0,0 +1,83 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2010 Lennart Poettering
+  Copyright 2014 Michal Schmidt
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "hash-funcs.h"
+
+void string_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(p, strlen(p) + 1, state);
+}
+
+int string_compare_func(const void *a, const void *b) {
+        return strcmp(a, b);
+}
+
+const struct hash_ops string_hash_ops = {
+        .hash = string_hash_func,
+        .compare = string_compare_func
+};
+
+void trivial_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(&p, sizeof(p), state);
+}
+
+int trivial_compare_func(const void *a, const void *b) {
+        return a < b ? -1 : (a > b ? 1 : 0);
+}
+
+const struct hash_ops trivial_hash_ops = {
+        .hash = trivial_hash_func,
+        .compare = trivial_compare_func
+};
+
+void uint64_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(p, sizeof(uint64_t), state);
+}
+
+int uint64_compare_func(const void *_a, const void *_b) {
+        uint64_t a, b;
+        a = *(const uint64_t*) _a;
+        b = *(const uint64_t*) _b;
+        return a < b ? -1 : (a > b ? 1 : 0);
+}
+
+const struct hash_ops uint64_hash_ops = {
+        .hash = uint64_hash_func,
+        .compare = uint64_compare_func
+};
+
+#if SIZEOF_DEV_T != 8
+void devt_hash_func(const void *p, struct siphash *state) {
+        siphash24_compress(p, sizeof(dev_t), state);
+}
+
+int devt_compare_func(const void *_a, const void *_b) {
+        dev_t a, b;
+        a = *(const dev_t*) _a;
+        b = *(const dev_t*) _b;
+        return a < b ? -1 : (a > b ? 1 : 0);
+}
+
+const struct hash_ops devt_hash_ops = {
+        .hash = devt_hash_func,
+        .compare = devt_compare_func
+};
+#endif
diff --git a/src/basic/hash-funcs.h b/src/basic/hash-funcs.h
new file mode 100644
index 0000000000..c640eaf4d1
--- /dev/null
+++ b/src/basic/hash-funcs.h
@@ -0,0 +1,67 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+  This file is part of systemd.
+
+  Copyright 2010 Lennart Poettering
+  Copyright 2014 Michal Schmidt
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd is distributed in the hope that it will be useful, but
+  WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "macro.h"
+#include "siphash24.h"
+
+typedef void (*hash_func_t)(const void *p, struct siphash *state);
+typedef int (*compare_func_t)(const void *a, const void *b);
+
+struct hash_ops {
+        hash_func_t hash;
+        compare_func_t compare;
+};
+
+void string_hash_func(const void *p, struct siphash *state);
+int string_compare_func(const void *a, const void *b) _pure_;
+extern const struct hash_ops string_hash_ops;
+
+/* This will compare the passed pointers directly, and will not
+ * dereference them. This is hence not useful for strings or
+ * suchlike. */
+void trivial_hash_func(const void *p, struct siphash *state);
+int trivial_compare_func(const void *a, const void *b) _const_;
+extern const struct hash_ops trivial_hash_ops;
+
+/* 32bit values we can always just embed in the pointer itself, but
+ * in order to support 32bit archs we need store 64bit values
+ * indirectly, since they don't fit in a pointer. */
+void uint64_hash_func(const void *p, struct siphash *state);
+int uint64_compare_func(const void *a, const void *b) _pure_;
+extern const struct hash_ops uint64_hash_ops;
+
+/* On some archs dev_t is 32bit, and on others 64bit. And sometimes
+ * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
+#if SIZEOF_DEV_T != 8
+void devt_hash_func(const void *p, struct siphash *state) _pure_;
+int devt_compare_func(const void *a, const void *b) _pure_;
+extern const struct hash_ops devt_hash_ops = {
+        .hash = devt_hash_func,
+        .compare = devt_compare_func
+};
+#else
+#define devt_hash_func uint64_hash_func
+#define devt_compare_func uint64_compare_func
+#define devt_hash_ops uint64_hash_ops
+#endif
diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c
index 286ddfef5b..dcd8ae412d 100644
--- a/src/basic/hashmap.c
+++ b/src/basic/hashmap.c
@@ -280,66 +280,6 @@ static const struct hashmap_type_info hashmap_type_info[_HASHMAP_TYPE_MAX] = {
         },
 };
 
-void string_hash_func(const void *p, struct siphash *state) {
-        siphash24_compress(p, strlen(p) + 1, state);
-}
-
-int string_compare_func(const void *a, const void *b) {
-        return strcmp(a, b);
-}
-
-const struct hash_ops string_hash_ops = {
-        .hash = string_hash_func,
-        .compare = string_compare_func
-};
-
-void trivial_hash_func(const void *p, struct siphash *state) {
-        siphash24_compress(&p, sizeof(p), state);
-}
-
-int trivial_compare_func(const void *a, const void *b) {
-        return a < b ? -1 : (a > b ? 1 : 0);
-}
-
-const struct hash_ops trivial_hash_ops = {
-        .hash = trivial_hash_func,
-        .compare = trivial_compare_func
-};
-
-void uint64_hash_func(const void *p, struct siphash *state) {
-        siphash24_compress(p, sizeof(uint64_t), state);
-}
-
-int uint64_compare_func(const void *_a, const void *_b) {
-        uint64_t a, b;
-        a = *(const uint64_t*) _a;
-        b = *(const uint64_t*) _b;
-        return a < b ? -1 : (a > b ? 1 : 0);
-}
-
-const struct hash_ops uint64_hash_ops = {
-        .hash = uint64_hash_func,
-        .compare = uint64_compare_func
-};
-
-#if SIZEOF_DEV_T != 8
-void devt_hash_func(const void *p, struct siphash *state) {
-        siphash24_compress(p, sizeof(dev_t), state);
-}
-
-int devt_compare_func(const void *_a, const void *_b) {
-        dev_t a, b;
-        a = *(const dev_t*) _a;
-        b = *(const dev_t*) _b;
-        return a < b ? -1 : (a > b ? 1 : 0);
-}
-
-const struct hash_ops devt_hash_ops = {
-        .hash = devt_hash_func,
-        .compare = devt_compare_func
-};
-#endif
-
 static unsigned n_buckets(HashmapBase *h) {
         return h->has_indirect ? h->indirect.n_buckets
                                : hashmap_type_info[h->type].n_direct_buckets;
diff --git a/src/basic/hashmap.h b/src/basic/hashmap.h
index 708811124b..fdba9c61ff 100644
--- a/src/basic/hashmap.h
+++ b/src/basic/hashmap.h
@@ -26,8 +26,8 @@
 #include <stdbool.h>
 #include <stddef.h>
 
+#include "hash-funcs.h"
 #include "macro.h"
-#include "siphash24.h"
 #include "util.h"
 
 /*
@@ -70,47 +70,6 @@ typedef struct {
 #define _IDX_ITERATOR_FIRST (UINT_MAX - 1)
 #define ITERATOR_FIRST ((Iterator) { .idx = _IDX_ITERATOR_FIRST, .next_key = NULL })
 
-typedef void (*hash_func_t)(const void *p, struct siphash *state);
-typedef int (*compare_func_t)(const void *a, const void *b);
-
-struct hash_ops {
-        hash_func_t hash;
-        compare_func_t compare;
-};
-
-void string_hash_func(const void *p, struct siphash *state);
-int string_compare_func(const void *a, const void *b) _pure_;
-extern const struct hash_ops string_hash_ops;
-
-/* This will compare the passed pointers directly, and will not
- * dereference them. This is hence not useful for strings or
- * suchlike. */
-void trivial_hash_func(const void *p, struct siphash *state);
-int trivial_compare_func(const void *a, const void *b) _const_;
-extern const struct hash_ops trivial_hash_ops;
-
-/* 32bit values we can always just embedd in the pointer itself, but
- * in order to support 32bit archs we need store 64bit values
- * indirectly, since they don't fit in a pointer. */
-void uint64_hash_func(const void *p, struct siphash *state);
-int uint64_compare_func(const void *a, const void *b) _pure_;
-extern const struct hash_ops uint64_hash_ops;
-
-/* On some archs dev_t is 32bit, and on others 64bit. And sometimes
- * it's 64bit on 32bit archs, and sometimes 32bit on 64bit archs. Yuck! */
-#if SIZEOF_DEV_T != 8
-void devt_hash_func(const void *p, struct siphash *state) _pure_;
-int devt_compare_func(const void *a, const void *b) _pure_;
-extern const struct hash_ops devt_hash_ops = {
-        .hash = devt_hash_func,
-        .compare = devt_compare_func
-};
-#else
-#define devt_hash_func uint64_hash_func
-#define devt_compare_func uint64_compare_func
-#define devt_hash_ops uint64_hash_ops
-#endif
-
 /* Macros for type checking */
 #define PTR_COMPATIBLE_WITH_HASHMAP_BASE(h) \
         (__builtin_types_compatible_p(typeof(h), HashmapBase*) || \
diff --git a/src/basic/siphash24.h b/src/basic/siphash24.h
index 3f7e20362b..54e2420cc6 100644
--- a/src/basic/siphash24.h
+++ b/src/basic/siphash24.h
@@ -16,6 +16,8 @@ struct siphash {
 
 void siphash24_init(struct siphash *state, const uint8_t k[16]);
 void siphash24_compress(const void *in, size_t inlen, struct siphash *state);
+#define siphash24_compress_byte(byte, state) siphash24_compress((const uint8_t[]) { (byte) }, 1, (state))
+
 uint64_t siphash24_finalize(struct siphash *state);
 
 uint64_t siphash24(const void *in, size_t inlen, const uint8_t k[16]);
diff --git a/src/basic/string-util.c b/src/basic/string-util.c
index 8178c7093f..849e457439 100644
--- a/src/basic/string-util.c
+++ b/src/basic/string-util.c
@@ -317,14 +317,33 @@ char *truncate_nl(char *s) {
         return s;
 }
 
+char ascii_tolower(char x) {
+
+        if (x >= 'A' && x <= 'Z')
+                return x - 'A' + 'a';
+
+        return x;
+}
+
 char *ascii_strlower(char *t) {
         char *p;
 
         assert(t);
 
         for (p = t; *p; p++)
-                if (*p >= 'A' && *p <= 'Z')
-                        *p = *p - 'A' + 'a';
+                *p = ascii_tolower(*p);
+
+        return t;
+}
+
+char *ascii_strlower_n(char *t, size_t n) {
+        size_t i;
+
+        if (n <= 0)
+                return t;
+
+        for (i = 0; i < n; i++)
+                t[i] = ascii_tolower(t[i]);
 
         return t;
 }
diff --git a/src/basic/string-util.h b/src/basic/string-util.h
index b59b9b5a71..1ac6bcd6f8 100644
--- a/src/basic/string-util.h
+++ b/src/basic/string-util.h
@@ -130,7 +130,9 @@ char *strstrip(char *s);
 char *delete_chars(char *s, const char *bad);
 char *truncate_nl(char *s);
 
-char *ascii_strlower(char *path);
+char ascii_tolower(char x);
+char *ascii_strlower(char *s);
+char *ascii_strlower_n(char *s, size_t n);
 
 bool chars_intersect(const char *a, const char *b) _pure_;
 
diff --git a/src/libsystemd/sd-bus/bus-common-errors.h b/src/libsystemd/sd-bus/bus-common-errors.h
index 9e49725843..7a5f6cda87 100644
--- a/src/libsystemd/sd-bus/bus-common-errors.h
+++ b/src/libsystemd/sd-bus/bus-common-errors.h
@@ -76,6 +76,7 @@
 #define BUS_ERROR_NO_SUCH_SERVICE "org.freedesktop.resolve1.NoSuchService"
 #define BUS_ERROR_DNSSEC_FAILED "org.freedesktop.resolve1.DnssecFailed"
 #define BUS_ERROR_NO_TRUST_ANCHOR "org.freedesktop.resolve1.NoTrustAnchor"
+#define BUS_ERROR_RR_TYPE_UNSUPPORTED "org.freedesktop.resolve1.ResourceRecordTypeUnsupported"
 #define _BUS_ERROR_DNS "org.freedesktop.resolve1.DnsError."
 
 #define BUS_ERROR_NO_SUCH_TRANSFER "org.freedesktop.import1.NoSuchTransfer"
diff --git a/src/resolve/dns-type.c b/src/resolve/dns-type.c
index 0571d65f0b..fb8228048d 100644
--- a/src/resolve/dns-type.c
+++ b/src/resolve/dns-type.c
@@ -77,7 +77,13 @@ bool dns_type_is_valid_query(uint16_t type) {
                        0,
                        DNS_TYPE_OPT,
                        DNS_TYPE_TSIG,
-                       DNS_TYPE_TKEY);
+                       DNS_TYPE_TKEY,
+
+                       /* RRSIG are technically valid as questions, but we refuse doing explicit queries for them, as
+                        * they aren't really payload, but signatures for payload, and cannot be validated on their
+                        * own. After all they are the signatures, and have no signatures of their own validating
+                        * them. */
+                       DNS_TYPE_RRSIG);
 }
 
 bool dns_type_is_valid_rr(uint16_t type) {
@@ -114,6 +120,43 @@ bool dns_type_may_redirect(uint16_t type) {
                        DNS_TYPE_KEY);
 }
 
+bool dns_type_is_dnssec(uint16_t type) {
+        return IN_SET(type,
+                      DNS_TYPE_DS,
+                      DNS_TYPE_DNSKEY,
+                      DNS_TYPE_RRSIG,
+                      DNS_TYPE_NSEC,
+                      DNS_TYPE_NSEC3,
+                      DNS_TYPE_NSEC3PARAM);
+}
+
+bool dns_type_is_obsolete(uint16_t type) {
+        return IN_SET(type,
+                      /* Obsoleted by RFC 973 */
+                      DNS_TYPE_MD,
+                      DNS_TYPE_MF,
+                      DNS_TYPE_MAILA,
+
+                      /* Kinda obsoleted by RFC 2505 */
+                      DNS_TYPE_MB,
+                      DNS_TYPE_MG,
+                      DNS_TYPE_MR,
+                      DNS_TYPE_MINFO,
+                      DNS_TYPE_MAILB,
+
+                      /* RFC1127 kinda obsoleted this by recommending against its use */
+                      DNS_TYPE_WKS,
+
+                      /* Declared historical by RFC 6563 */
+                      DNS_TYPE_A6,
+
+                      /* Obsoleted by DNSSEC-bis */
+                      DNS_TYPE_NXT,
+
+                      /* RFC 1035 removed support for concepts that needed this from RFC 883 */
+                      DNS_TYPE_NULL);
+}
+
 const char *dns_class_to_string(uint16_t class) {
 
         switch (class) {
diff --git a/src/resolve/dns-type.h b/src/resolve/dns-type.h
index c3bb26a5ee..45080fd243 100644
--- a/src/resolve/dns-type.h
+++ b/src/resolve/dns-type.h
@@ -129,6 +129,8 @@ bool dns_type_is_pseudo(uint16_t type);
 bool dns_type_is_valid_query(uint16_t type);
 bool dns_type_is_valid_rr(uint16_t type);
 bool dns_type_may_redirect(uint16_t type);
+bool dns_type_is_dnssec(uint16_t type);
+bool dns_type_is_obsolete(uint16_t type);
 
 bool dns_class_is_pseudo(uint16_t class);
 bool dns_class_is_valid_rr(uint16_t class);
diff --git a/src/resolve/resolved-bus.c b/src/resolve/resolved-bus.c
index 7193f639d4..41f90dedfd 100644
--- a/src/resolve/resolved-bus.c
+++ b/src/resolve/resolved-bus.c
@@ -57,9 +57,6 @@ static int reply_query_state(DnsQuery *q) {
         case DNS_TRANSACTION_RESOURCES:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_RESOURCES, "Not enough resources");
 
-        case DNS_TRANSACTION_CONNECTION_FAILURE:
-                return sd_bus_reply_method_errorf(q->request, BUS_ERROR_CONNECTION_FAILURE, "DNS server connection failure");
-
         case DNS_TRANSACTION_ABORTED:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_ABORTED, "Query aborted");
 
@@ -70,6 +67,9 @@ static int reply_query_state(DnsQuery *q) {
         case DNS_TRANSACTION_NO_TRUST_ANCHOR:
                 return sd_bus_reply_method_errorf(q->request, BUS_ERROR_NO_TRUST_ANCHOR, "No suitable trust anchor known");
 
+        case DNS_TRANSACTION_RR_TYPE_UNSUPPORTED:
+                return sd_bus_reply_method_errorf(q->request, BUS_ERROR_RR_TYPE_UNSUPPORTED, "Server does not support requested resource record type");
+
         case DNS_TRANSACTION_RCODE_FAILURE: {
                 _cleanup_(sd_bus_error_free) sd_bus_error error = SD_BUS_ERROR_NULL;
 
@@ -94,6 +94,7 @@ static int reply_query_state(DnsQuery *q) {
 
         case DNS_TRANSACTION_NULL:
         case DNS_TRANSACTION_PENDING:
+        case DNS_TRANSACTION_VALIDATING:
         case DNS_TRANSACTION_SUCCESS:
         default:
                 assert_not_reached("Impossible state");
@@ -561,7 +562,9 @@ static int bus_method_resolve_record(sd_bus_message *message, void *userdata, sd
                 return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid name '%s'", name);
 
         if (!dns_type_is_valid_query(type))
-                return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Invalid RR type for query %" PRIu16, type);
+                return sd_bus_error_setf(error, SD_BUS_ERROR_INVALID_ARGS, "Specified resource record type %" PRIu16 " may not be used in a query.", type);
+        if (dns_type_is_obsolete(type))
+                return sd_bus_error_setf(error, SD_BUS_ERROR_NOT_SUPPORTED, "Specified DNS resource record type %" PRIu16 " is obsolete.", type);
 
         r = check_ifindex_flags(ifindex, &flags, 0, error);
         if (r < 0)
@@ -1390,6 +1393,7 @@ int manager_connect_bus(Manager *m) {
                 if (r < 0)
                         return log_error_errno(r, "Failed to install bus reconnect time event: %m");
 
+                (void) sd_event_source_set_description(m->bus_retry_event_source, "bus-retry");
                 return 0;
         }
 
diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index 51fe710795..43fcbe1460 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -39,11 +39,13 @@
  *   - multi-label zone compatibility
  *   - cname/dname compatibility
  *   - nxdomain on qname
- *   - workable hack for the .corp, .home, .box case
  *   - bus calls to override DNSEC setting per interface
  *   - log all DNSSEC downgrades
  *   - enable by default
  *
+ *   - RFC 4035, Section 5.3.4 (When receiving a positive wildcard reply, use NSEC to ensure it actually really applies)
+ *   - RFC 6840, Section 4.1 (ensure we don't get fed a glue NSEC from the parent zone)
+ *   - RFC 6840, Section 4.3 (check for CNAME on NSEC too)
  * */
 
 #define VERIFY_RRS_MAX 256
@@ -52,8 +54,8 @@
 /* Permit a maximum clock skew of 1h 10min. This should be enough to deal with DST confusion */
 #define SKEW_MAX (1*USEC_PER_HOUR + 10*USEC_PER_MINUTE)
 
-/* Maximum number of NSEC3 iterations we'll do. */
-#define NSEC3_ITERATIONS_MAX 2048
+/* Maximum number of NSEC3 iterations we'll do. RFC5155 says 2500 shall be the maximum useful value */
+#define NSEC3_ITERATIONS_MAX 2500
 
 /*
  * The DNSSEC Chain of trust:
@@ -510,6 +512,7 @@ int dnssec_verify_rrset(
         DnsResourceRecord **list, *rr;
         gcry_md_hd_t md = NULL;
         int r, md_algorithm;
+        bool wildcard = false;
         size_t k, n = 0;
 
         assert(key);
@@ -540,7 +543,7 @@ int dnssec_verify_rrset(
         }
 
         /* Collect all relevant RRs in a single array, so that we can look at the RRset */
-        list = newa(DnsResourceRecord *, a->n_rrs);
+        list = newa(DnsResourceRecord *, dns_answer_size(a));
 
         DNS_ANSWER_FOREACH(rr, a) {
                 r = dns_resource_key_equal(key, rr->key);
@@ -597,8 +600,10 @@ int dnssec_verify_rrset(
                 r = dns_name_suffix(DNS_RESOURCE_KEY_NAME(rr->key), rrsig->rrsig.labels, &suffix);
                 if (r < 0)
                         goto finish;
-                if (r > 0) /* This is a wildcard! */
+                if (r > 0) /* This is a wildcard! */ {
                         gcry_md_write(md, (uint8_t[]) { 1, '*'}, 2);
+                        wildcard = true;
+                }
 
                 r = dns_name_to_wire_format(suffix, wire_format_name, sizeof(wire_format_name), true);
                 if (r < 0)
@@ -649,7 +654,12 @@ int dnssec_verify_rrset(
         if (r < 0)
                 goto finish;
 
-        *result = r ? DNSSEC_VALIDATED : DNSSEC_INVALID;
+        if (!r)
+                *result = DNSSEC_INVALID;
+        else if (wildcard)
+                *result = DNSSEC_VALIDATED_WILDCARD;
+        else
+                *result = DNSSEC_VALIDATED;
         r = 0;
 
 finish:
@@ -746,7 +756,8 @@ int dnssec_verify_rrset_search(
                 const DnsResourceKey *key,
                 DnsAnswer *validated_dnskeys,
                 usec_t realtime,
-                DnssecResult *result) {
+                DnssecResult *result,
+                DnsResourceRecord **ret_rrsig) {
 
         bool found_rrsig = false, found_invalid = false, found_expired_rrsig = false, found_unsupported_algorithm = false;
         DnsResourceRecord *rrsig;
@@ -806,13 +817,17 @@ int dnssec_verify_rrset_search(
                         switch (one_result) {
 
                         case DNSSEC_VALIDATED:
+                        case DNSSEC_VALIDATED_WILDCARD:
                                 /* Yay, the RR has been validated,
                                  * return immediately, but fix up the expiry */
                                 r = dnssec_fix_rrset_ttl(a, key, rrsig, realtime);
                                 if (r < 0)
                                         return r;
 
-                                *result = DNSSEC_VALIDATED;
+                                if (ret_rrsig)
+                                        *ret_rrsig = rrsig;
+
+                                *result = one_result;
                                 return 0;
 
                         case DNSSEC_INVALID:
@@ -857,6 +872,9 @@ int dnssec_verify_rrset_search(
         else
                 *result = DNSSEC_NO_SIGNATURE;
 
+        if (ret_rrsig)
+                *ret_rrsig = NULL;
+
         return 0;
 }
 
@@ -888,8 +906,6 @@ int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
                 return -ENOBUFS;
 
         for (;;) {
-                size_t i;
-
                 r = dns_label_unescape(&n, buffer, buffer_max);
                 if (r < 0)
                         return r;
@@ -916,11 +932,7 @@ int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
                 if (memchr(buffer, '.', r))
                         return -EINVAL;
 
-                for (i = 0; i < (size_t) r; i ++) {
-                        if (buffer[i] >= 'A' && buffer[i] <= 'Z')
-                                buffer[i] = buffer[i] - 'A' + 'a';
-                }
-
+                ascii_strlower_n(buffer, (size_t) r);
                 buffer[r] = '.';
 
                 buffer += r + 1;
@@ -1158,7 +1170,7 @@ finish:
         return r;
 }
 
-static int nsec3_is_good(DnsResourceRecord *rr, DnsAnswerFlags flags, DnsResourceRecord *nsec3) {
+static int nsec3_is_good(DnsResourceRecord *rr, DnsResourceRecord *nsec3) {
         const char *a, *b;
         int r;
 
@@ -1214,8 +1226,28 @@ static int nsec3_is_good(DnsResourceRecord *rr, DnsAnswerFlags flags, DnsResourc
         return dns_name_equal(a, b);
 }
 
-static int nsec3_hashed_domain(DnsResourceRecord *nsec3, const char *domain, const char *zone, char **ret) {
-        _cleanup_free_ char *l = NULL, *hashed_domain = NULL;
+static int nsec3_hashed_domain_format(const uint8_t *hashed, size_t hashed_size, const char *zone, char **ret) {
+        _cleanup_free_ char *l = NULL;
+        char *j;
+
+        assert(hashed);
+        assert(hashed_size > 0);
+        assert(zone);
+        assert(ret);
+
+        l = base32hexmem(hashed, hashed_size, false);
+        if (!l)
+                return -ENOMEM;
+
+        j = strjoin(l, ".", zone, NULL);
+        if (!j)
+                return -ENOMEM;
+
+        *ret = j;
+        return (int) hashed_size;
+}
+
+static int nsec3_hashed_domain_make(DnsResourceRecord *nsec3, const char *domain, const char *zone, char **ret) {
         uint8_t hashed[DNSSEC_HASH_SIZE_MAX];
         int hashed_size;
 
@@ -1228,18 +1260,7 @@ static int nsec3_hashed_domain(DnsResourceRecord *nsec3, const char *domain, con
         if (hashed_size < 0)
                 return hashed_size;
 
-        l = base32hexmem(hashed, hashed_size, false);
-        if (!l)
-                return -ENOMEM;
-
-        hashed_domain = strjoin(l, ".", zone, NULL);
-        if (!hashed_domain)
-                return -ENOMEM;
-
-        *ret = hashed_domain;
-        hashed_domain = NULL;
-
-        return hashed_size;
+        return nsec3_hashed_domain_format(hashed, (size_t) hashed_size, zone, ret);
 }
 
 /* See RFC 5155, Section 8
@@ -1255,7 +1276,7 @@ static int nsec3_hashed_domain(DnsResourceRecord *nsec3, const char *domain, con
 static int dnssec_test_nsec3(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result, bool *authenticated, uint32_t *ttl) {
         _cleanup_free_ char *next_closer_domain = NULL, *wildcard = NULL, *wildcard_domain = NULL;
         const char *zone, *p, *pp = NULL;
-        DnsResourceRecord *rr, *enclosure_rr, *suffix_rr, *wildcard_rr = NULL;
+        DnsResourceRecord *rr, *enclosure_rr, *zone_rr, *wildcard_rr = NULL;
         DnsAnswerFlags flags;
         int hashed_size, r;
         bool a, no_closer = false, no_wildcard = false, optout = false;
@@ -1270,14 +1291,14 @@ static int dnssec_test_nsec3(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecR
          * parameters. */
         zone = DNS_RESOURCE_KEY_NAME(key);
         for (;;) {
-                DNS_ANSWER_FOREACH_FLAGS(suffix_rr, flags, answer) {
-                        r = nsec3_is_good(suffix_rr, flags, NULL);
+                DNS_ANSWER_FOREACH_FLAGS(zone_rr, flags, answer) {
+                        r = nsec3_is_good(zone_rr, NULL);
                         if (r < 0)
                                 return r;
                         if (r == 0)
                                 continue;
 
-                        r = dns_name_equal_skip(DNS_RESOURCE_KEY_NAME(suffix_rr->key), 1, zone);
+                        r = dns_name_equal_skip(DNS_RESOURCE_KEY_NAME(zone_rr->key), 1, zone);
                         if (r < 0)
                                 return r;
                         if (r > 0)
@@ -1301,7 +1322,7 @@ found_zone:
         for (;;) {
                 _cleanup_free_ char *hashed_domain = NULL;
 
-                hashed_size = nsec3_hashed_domain(suffix_rr, p, zone, &hashed_domain);
+                hashed_size = nsec3_hashed_domain_make(zone_rr, p, zone, &hashed_domain);
                 if (hashed_size == -EOPNOTSUPP) {
                         *result = DNSSEC_NSEC_UNSUPPORTED_ALGORITHM;
                         return 0;
@@ -1311,7 +1332,7 @@ found_zone:
 
                 DNS_ANSWER_FOREACH_FLAGS(enclosure_rr, flags, answer) {
 
-                        r = nsec3_is_good(enclosure_rr, flags, suffix_rr);
+                        r = nsec3_is_good(enclosure_rr, zone_rr);
                         if (r < 0)
                                 return r;
                         if (r == 0)
@@ -1384,34 +1405,30 @@ found_closest_encloser:
         if (!wildcard)
                 return -ENOMEM;
 
-        r = nsec3_hashed_domain(enclosure_rr, wildcard, zone, &wildcard_domain);
+        r = nsec3_hashed_domain_make(enclosure_rr, wildcard, zone, &wildcard_domain);
         if (r < 0)
                 return r;
         if (r != hashed_size)
                 return -EBADMSG;
 
-        r = nsec3_hashed_domain(enclosure_rr, pp, zone, &next_closer_domain);
+        r = nsec3_hashed_domain_make(enclosure_rr, pp, zone, &next_closer_domain);
         if (r < 0)
                 return r;
         if (r != hashed_size)
                 return -EBADMSG;
 
         DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
-                _cleanup_free_ char *label = NULL, *next_hashed_domain = NULL;
+                _cleanup_free_ char *next_hashed_domain = NULL;
 
-                r = nsec3_is_good(rr, flags, suffix_rr);
+                r = nsec3_is_good(rr, zone_rr);
                 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, ".", zone, NULL);
-                if (!next_hashed_domain)
-                        return -ENOMEM;
+                r = nsec3_hashed_domain_format(rr->nsec3.next_hashed_name, rr->nsec3.next_hashed_name_size, zone, &next_hashed_domain);
+                if (r < 0)
+                        return r;
 
                 r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), next_closer_domain, next_hashed_domain);
                 if (r < 0)
@@ -1500,7 +1517,7 @@ found_closest_encloser:
         return 0;
 }
 
-int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result, bool *authenticated, uint32_t *ttl) {
+int dnssec_nsec_test(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result, bool *authenticated, uint32_t *ttl) {
         DnsResourceRecord *rr;
         bool have_nsec3 = false;
         DnsAnswerFlags flags;
@@ -1569,8 +1586,90 @@ int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *r
         return 0;
 }
 
+int dnssec_nsec_test_between(DnsAnswer *answer, const char *name, const char *zone, bool *authenticated) {
+        DnsResourceRecord *rr;
+        DnsAnswerFlags flags;
+        int r;
+
+        assert(name);
+        assert(zone);
+
+        /* Checks whether there's an NSEC/NSEC3 that proves that the specified 'name' is non-existing in the specified
+         * 'zone'. The 'zone' must be a suffix of the 'name'. */
+
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                bool found = false;
+
+                r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(rr->key), zone);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                switch (rr->key->type) {
+
+                case DNS_TYPE_NSEC:
+                        r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), name, rr->nsec.next_domain_name);
+                        if (r < 0)
+                                return r;
+
+                        found = r > 0;
+                        break;
+
+                case DNS_TYPE_NSEC3: {
+                        _cleanup_free_ char *hashed_domain = NULL, *next_hashed_domain = NULL;
+
+                        r = nsec3_is_good(rr, NULL);
+                        if (r < 0)
+                                return r;
+                        if (r == 0)
+                                break;
+
+                        /* Format the domain we are testing with the NSEC3 RR's hash function */
+                        r = nsec3_hashed_domain_make(
+                                        rr,
+                                        name,
+                                        zone,
+                                        &hashed_domain);
+                        if (r < 0)
+                                return r;
+                        if ((size_t) r != rr->nsec3.next_hashed_name_size)
+                                break;
+
+                        /* Format the NSEC3's next hashed name as proper domain name */
+                        r = nsec3_hashed_domain_format(
+                                        rr->nsec3.next_hashed_name,
+                                        rr->nsec3.next_hashed_name_size,
+                                        zone,
+                                        &next_hashed_domain);
+                        if (r < 0)
+                                return r;
+
+                        r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), hashed_domain, next_hashed_domain);
+                        if (r < 0)
+                                return r;
+
+                        found = r > 0;
+                        break;
+                }
+
+                default:
+                        continue;
+                }
+
+                if (found) {
+                        if (authenticated)
+                                *authenticated = flags & DNS_ANSWER_AUTHENTICATED;
+                        return 1;
+                }
+        }
+
+        return 0;
+}
+
 static const char* const dnssec_result_table[_DNSSEC_RESULT_MAX] = {
         [DNSSEC_VALIDATED] = "validated",
+        [DNSSEC_VALIDATED_WILDCARD] = "validated-wildcard",
         [DNSSEC_INVALID] = "invalid",
         [DNSSEC_SIGNATURE_EXPIRED] = "signature-expired",
         [DNSSEC_UNSUPPORTED_ALGORITHM] = "unsupported-algorithm",
diff --git a/src/resolve/resolved-dns-dnssec.h b/src/resolve/resolved-dns-dnssec.h
index 6977faca75..8a9bcf5b91 100644
--- a/src/resolve/resolved-dns-dnssec.h
+++ b/src/resolve/resolved-dns-dnssec.h
@@ -29,8 +29,9 @@ typedef enum DnssecResult DnssecResult;
 #include "resolved-dns-rr.h"
 
 enum DnssecResult {
-        /* These four are returned by dnssec_verify_rrset() */
+        /* These five are returned by dnssec_verify_rrset() */
         DNSSEC_VALIDATED,
+        DNSSEC_VALIDATED_WILDCARD, /* Validated via a wildcard RRSIG, further NSEC/NSEC3 checks necessary */
         DNSSEC_INVALID,
         DNSSEC_SIGNATURE_EXPIRED,
         DNSSEC_UNSUPPORTED_ALGORITHM,
@@ -58,7 +59,7 @@ int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnske
 int dnssec_key_match_rrsig(const DnsResourceKey *key, DnsResourceRecord *rrsig);
 
 int dnssec_verify_rrset(DnsAnswer *answer, const DnsResourceKey *key, DnsResourceRecord *rrsig, DnsResourceRecord *dnskey, usec_t realtime, DnssecResult *result);
-int dnssec_verify_rrset_search(DnsAnswer *answer, const DnsResourceKey *key, DnsAnswer *validated_dnskeys, usec_t realtime, DnssecResult *result);
+int dnssec_verify_rrset_search(DnsAnswer *answer, const DnsResourceKey *key, DnsAnswer *validated_dnskeys, usec_t realtime, DnssecResult *result, DnsResourceRecord **rrsig);
 
 int dnssec_verify_dnskey(DnsResourceRecord *dnskey, DnsResourceRecord *ds, bool mask_revoke);
 int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_ds);
@@ -73,7 +74,7 @@ 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_CNAME,     /* Would be NODATA, but for the existence of a CNAME RR */
+        DNSSEC_NSEC_CNAME,     /* Didn't find what was asked for, but did find CNAME */
         DNSSEC_NSEC_UNSUPPORTED_ALGORITHM,
         DNSSEC_NSEC_NXDOMAIN,
         DNSSEC_NSEC_NODATA,
@@ -81,7 +82,8 @@ typedef enum DnssecNsecResult {
         DNSSEC_NSEC_OPTOUT,
 } DnssecNsecResult;
 
-int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result, bool *authenticated, uint32_t *ttl);
+int dnssec_nsec_test(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result, bool *authenticated, uint32_t *ttl);
+int dnssec_nsec_test_between(DnsAnswer *answer, const char *name, const char *zone, bool *authenticated);
 
 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-packet.c b/src/resolve/resolved-dns-packet.c
index 4750bf1f5d..a8a8632491 100644
--- a/src/resolve/resolved-dns-packet.c
+++ b/src/resolve/resolved-dns-packet.c
@@ -466,12 +466,8 @@ int dns_packet_append_label(DnsPacket *p, const char *d, size_t l, bool canonica
                 /* Generate in canonical form, as defined by DNSSEC
                  * RFC 4034, Section 6.2, i.e. all lower-case. */
 
-                for (i = 0; i < l; i++) {
-                        if (d[i] >= 'A' && d[i] <= 'Z')
-                                w[i] = (uint8_t) (d[i] - 'A' + 'a');
-                        else
-                                w[i] = (uint8_t) d[i];
-                }
+                for (i = 0; i < l; i++)
+                        w[i] = (uint8_t) ascii_tolower(d[i]);
         } else
                 /* Otherwise, just copy the string unaltered. This is
                  * essential for DNS-SD, where the casing of labels
@@ -2089,11 +2085,12 @@ int dns_packet_extract(DnsPacket *p) {
                                         goto finish;
                                 }
 
-                                /* The OPT RR is only valid in the Additional section */
-                                if (i < DNS_PACKET_ANCOUNT(p) + DNS_PACKET_NSCOUNT(p)) {
-                                        r = -EBADMSG;
-                                        goto finish;
-                                }
+                                /* Note that we accept the OPT RR in
+                                 * any section, not just in the
+                                 * additional section, as some routers
+                                 * (Belkin!)  blindly copy the OPT RR
+                                 * from the query to the reply packet,
+                                 * and don't get the section right. */
 
                                 /* Two OPT RRs? */
                                 if (p->opt) {
diff --git a/src/resolve/resolved-dns-query.c b/src/resolve/resolved-dns-query.c
index 0f2f2599ab..1948d59fc4 100644
--- a/src/resolve/resolved-dns-query.c
+++ b/src/resolve/resolved-dns-query.c
@@ -961,6 +961,8 @@ int dns_query_go(DnsQuery *q) {
         if (r < 0)
                 goto fail;
 
+        (void) sd_event_source_set_description(q->timeout_event_source, "query-timeout");
+
         q->state = DNS_TRANSACTION_PENDING;
         q->block_ready++;
 
diff --git a/src/resolve/resolved-dns-rr.c b/src/resolve/resolved-dns-rr.c
index 76723ec4d0..dbf840157f 100644
--- a/src/resolve/resolved-dns-rr.c
+++ b/src/resolve/resolved-dns-rr.c
@@ -1085,6 +1085,157 @@ int dns_resource_record_to_wire_format(DnsResourceRecord *rr, bool canonical) {
         return 0;
 }
 
+static void dns_resource_record_hash_func(const void *i, struct siphash *state) {
+        const DnsResourceRecord *rr = i;
+
+        assert(rr);
+
+        dns_resource_key_hash_func(rr->key, state);
+
+        switch (rr->unparseable ? _DNS_TYPE_INVALID : rr->key->type) {
+
+        case DNS_TYPE_SRV:
+                siphash24_compress(&rr->srv.priority, sizeof(rr->srv.priority), state);
+                siphash24_compress(&rr->srv.weight, sizeof(rr->srv.weight), state);
+                siphash24_compress(&rr->srv.port, sizeof(rr->srv.port), state);
+                dns_name_hash_func(rr->srv.name, state);
+                break;
+
+        case DNS_TYPE_PTR:
+        case DNS_TYPE_NS:
+        case DNS_TYPE_CNAME:
+        case DNS_TYPE_DNAME:
+                dns_name_hash_func(rr->ptr.name, state);
+                break;
+
+        case DNS_TYPE_HINFO:
+                string_hash_func(rr->hinfo.cpu, state);
+                string_hash_func(rr->hinfo.os, state);
+                break;
+
+        case DNS_TYPE_TXT:
+        case DNS_TYPE_SPF: {
+                DnsTxtItem *j;
+
+                LIST_FOREACH(items, j, rr->txt.items) {
+                        siphash24_compress(j->data, j->length, state);
+
+                        /* Add an extra NUL byte, so that "a" followed by "b" doesn't result in the same hash as "ab"
+                         * followed by "". */
+                        siphash24_compress_byte(0, state);
+                }
+                break;
+        }
+
+        case DNS_TYPE_A:
+                siphash24_compress(&rr->a.in_addr, sizeof(rr->a.in_addr), state);
+                break;
+
+        case DNS_TYPE_AAAA:
+                siphash24_compress(&rr->aaaa.in6_addr, sizeof(rr->aaaa.in6_addr), state);
+                break;
+
+        case DNS_TYPE_SOA:
+                dns_name_hash_func(rr->soa.mname, state);
+                dns_name_hash_func(rr->soa.rname, state);
+                siphash24_compress(&rr->soa.serial, sizeof(rr->soa.serial), state);
+                siphash24_compress(&rr->soa.refresh, sizeof(rr->soa.refresh), state);
+                siphash24_compress(&rr->soa.retry, sizeof(rr->soa.retry), state);
+                siphash24_compress(&rr->soa.expire, sizeof(rr->soa.expire), state);
+                siphash24_compress(&rr->soa.minimum, sizeof(rr->soa.minimum), state);
+                break;
+
+        case DNS_TYPE_MX:
+                siphash24_compress(&rr->mx.priority, sizeof(rr->mx.priority), state);
+                dns_name_hash_func(rr->mx.exchange, state);
+                break;
+
+        case DNS_TYPE_LOC:
+                siphash24_compress(&rr->loc.version, sizeof(rr->loc.version), state);
+                siphash24_compress(&rr->loc.size, sizeof(rr->loc.size), state);
+                siphash24_compress(&rr->loc.horiz_pre, sizeof(rr->loc.horiz_pre), state);
+                siphash24_compress(&rr->loc.vert_pre, sizeof(rr->loc.vert_pre), state);
+                siphash24_compress(&rr->loc.latitude, sizeof(rr->loc.latitude), state);
+                siphash24_compress(&rr->loc.longitude, sizeof(rr->loc.longitude), state);
+                siphash24_compress(&rr->loc.altitude, sizeof(rr->loc.altitude), state);
+                break;
+
+        case DNS_TYPE_SSHFP:
+                siphash24_compress(&rr->sshfp.algorithm, sizeof(rr->sshfp.algorithm), state);
+                siphash24_compress(&rr->sshfp.fptype, sizeof(rr->sshfp.fptype), state);
+                siphash24_compress(rr->sshfp.fingerprint, rr->sshfp.fingerprint_size, state);
+                break;
+
+        case DNS_TYPE_DNSKEY:
+                siphash24_compress(&rr->dnskey.flags, sizeof(rr->dnskey.flags), state);
+                siphash24_compress(&rr->dnskey.protocol, sizeof(rr->dnskey.protocol), state);
+                siphash24_compress(&rr->dnskey.algorithm, sizeof(rr->dnskey.algorithm), state);
+                siphash24_compress(rr->dnskey.key, rr->dnskey.key_size, state);
+                break;
+
+        case DNS_TYPE_RRSIG:
+                siphash24_compress(&rr->rrsig.type_covered, sizeof(rr->rrsig.type_covered), state);
+                siphash24_compress(&rr->rrsig.algorithm, sizeof(rr->rrsig.algorithm), state);
+                siphash24_compress(&rr->rrsig.labels, sizeof(rr->rrsig.labels), state);
+                siphash24_compress(&rr->rrsig.original_ttl, sizeof(rr->rrsig.original_ttl), state);
+                siphash24_compress(&rr->rrsig.expiration, sizeof(rr->rrsig.expiration), state);
+                siphash24_compress(&rr->rrsig.inception, sizeof(rr->rrsig.inception), state);
+                siphash24_compress(&rr->rrsig.key_tag, sizeof(rr->rrsig.key_tag), state);
+                dns_name_hash_func(rr->rrsig.signer, state);
+                siphash24_compress(rr->rrsig.signature, rr->rrsig.signature_size, state);
+                break;
+
+        case DNS_TYPE_NSEC:
+                dns_name_hash_func(rr->nsec.next_domain_name, state);
+                /* FIXME: we leave out the type bitmap here. Hash
+                 * would be better if we'd take it into account
+                 * too. */
+                break;
+
+        case DNS_TYPE_DS:
+                siphash24_compress(&rr->ds.key_tag, sizeof(rr->ds.key_tag), state);
+                siphash24_compress(&rr->ds.algorithm, sizeof(rr->ds.algorithm), state);
+                siphash24_compress(&rr->ds.digest_type, sizeof(rr->ds.digest_type), state);
+                siphash24_compress(rr->ds.digest, rr->ds.digest_size, state);
+                break;
+
+        case DNS_TYPE_NSEC3:
+                siphash24_compress(&rr->nsec3.algorithm, sizeof(rr->nsec3.algorithm), state);
+                siphash24_compress(&rr->nsec3.flags, sizeof(rr->nsec3.flags), state);
+                siphash24_compress(&rr->nsec3.iterations, sizeof(rr->nsec3.iterations), state);
+                siphash24_compress(rr->nsec3.salt, rr->nsec3.salt_size, state);
+                siphash24_compress(rr->nsec3.next_hashed_name, rr->nsec3.next_hashed_name_size, state);
+                /* FIXME: We leave the bitmaps out */
+                break;
+
+        default:
+                siphash24_compress(rr->generic.data, rr->generic.size, state);
+                break;
+        }
+}
+
+static int dns_resource_record_compare_func(const void *a, const void *b) {
+        const DnsResourceRecord *x = a, *y = b;
+        int ret;
+
+        ret = dns_resource_key_compare_func(x->key, y->key);
+        if (ret != 0)
+                return ret;
+
+        if (dns_resource_record_equal(x, y))
+                return 0;
+
+        /* This is a bit dirty, we don't implement proper odering, but
+         * the hashtable doesn't need ordering anyway, hence we don't
+         * care. */
+        return x < y ? -1 : 1;
+}
+
+const struct hash_ops dns_resource_record_hash_ops = {
+        .hash = dns_resource_record_hash_func,
+        .compare = dns_resource_record_compare_func,
+};
+
 DnsTxtItem *dns_txt_item_free_all(DnsTxtItem *i) {
         DnsTxtItem *n;
 
diff --git a/src/resolve/resolved-dns-rr.h b/src/resolve/resolved-dns-rr.h
index 26ab36401c..fe29a41566 100644
--- a/src/resolve/resolved-dns-rr.h
+++ b/src/resolve/resolved-dns-rr.h
@@ -300,6 +300,7 @@ DnsTxtItem *dns_txt_item_free_all(DnsTxtItem *i);
 bool dns_txt_item_equal(DnsTxtItem *a, DnsTxtItem *b);
 
 extern const struct hash_ops dns_resource_key_hash_ops;
+extern const struct hash_ops dns_resource_record_hash_ops;
 
 int dnssec_algorithm_to_string_alloc(int i, char **ret);
 int dnssec_algorithm_from_string(const char *s) _pure_;
diff --git a/src/resolve/resolved-dns-scope.c b/src/resolve/resolved-dns-scope.c
index c96bed04b0..dd3609bd12 100644
--- a/src/resolve/resolved-dns-scope.c
+++ b/src/resolve/resolved-dns-scope.c
@@ -912,6 +912,8 @@ int dns_scope_notify_conflict(DnsScope *scope, DnsResourceRecord *rr) {
         if (r < 0)
                 return log_debug_errno(r, "Failed to add conflict dispatch event: %m");
 
+        (void) sd_event_source_set_description(scope->conflict_event_source, "scope-conflict");
+
         return 0;
 }
 
diff --git a/src/resolve/resolved-dns-server.c b/src/resolve/resolved-dns-server.c
index fbd1c27c14..0969e31e8a 100644
--- a/src/resolve/resolved-dns-server.c
+++ b/src/resolve/resolved-dns-server.c
@@ -135,6 +135,7 @@ DnsServer* dns_server_unref(DnsServer *s)  {
         if (s->n_ref > 0)
                 return NULL;
 
+        free(s->server_string);
         free(s);
         return NULL;
 }
@@ -224,31 +225,48 @@ void dns_server_move_back_and_unmark(DnsServer *s) {
         }
 }
 
-void dns_server_packet_received(DnsServer *s, DnsServerFeatureLevel level, usec_t rtt, size_t size) {
+static void dns_server_verified(DnsServer *s, DnsServerFeatureLevel level) {
         assert(s);
 
-        if (level == DNS_SERVER_FEATURE_LEVEL_LARGE) {
-                /* Even if we successfully receive a reply to a
-                   request announcing support for large packets, that
-                   does not mean we can necessarily receive large
-                   packets. */
+        if (s->verified_feature_level > level)
+                return;
 
-                if (s->verified_feature_level < DNS_SERVER_FEATURE_LEVEL_LARGE - 1) {
-                        s->verified_feature_level = DNS_SERVER_FEATURE_LEVEL_LARGE - 1;
-                        assert_se(sd_event_now(s->manager->event, clock_boottime_or_monotonic(), &s->verified_usec) >= 0);
-                }
-        } else if (s->verified_feature_level < level) {
+        if (s->verified_feature_level != level) {
+                log_debug("Verified feature level %s.", dns_server_feature_level_to_string(level));
                 s->verified_feature_level = level;
-                assert_se(sd_event_now(s->manager->event, clock_boottime_or_monotonic(), &s->verified_usec) >= 0);
         }
 
-        if (s->possible_feature_level == level)
-                s->n_failed_attempts = 0;
+        assert_se(sd_event_now(s->manager->event, clock_boottime_or_monotonic(), &s->verified_usec) >= 0);
+}
+
+void dns_server_packet_received(DnsServer *s, int protocol, DnsServerFeatureLevel level, usec_t rtt, size_t size) {
+        assert(s);
+
+        if (protocol == IPPROTO_UDP) {
+                if (s->possible_feature_level == level)
+                        s->n_failed_udp = 0;
+
+                if (level == DNS_SERVER_FEATURE_LEVEL_LARGE)
+                        /* Even if we successfully receive a reply to a request announcing support for large packets,
+                           that does not mean we can necessarily receive large packets. */
+                        dns_server_verified(s, DNS_SERVER_FEATURE_LEVEL_LARGE - 1);
+                else
+                        /* A successful UDP reply, verifies UDP, ENDS0 and DO levels */
+                        dns_server_verified(s, level);
+
+        } else if (protocol == IPPROTO_TCP) {
+
+                if (s->possible_feature_level == level)
+                        s->n_failed_tcp = 0;
+
+                /* Successful TCP connections are only useful to verify the TCP feature level. */
+                dns_server_verified(s, DNS_SERVER_FEATURE_LEVEL_TCP);
+        }
 
         /* Remember the size of the largest UDP packet we received from a server,
            we know that we can always announce support for packets with at least
            this size. */
-        if (s->received_udp_packet_max < size)
+        if (protocol == IPPROTO_UDP && s->received_udp_packet_max < size)
                 s->received_udp_packet_max = size;
 
         if (s->max_rtt < rtt) {
@@ -257,12 +275,16 @@ void dns_server_packet_received(DnsServer *s, DnsServerFeatureLevel level, usec_
         }
 }
 
-void dns_server_packet_lost(DnsServer *s, DnsServerFeatureLevel level, usec_t usec) {
+void dns_server_packet_lost(DnsServer *s, int protocol, DnsServerFeatureLevel level, usec_t usec) {
         assert(s);
         assert(s->manager);
 
-        if (s->possible_feature_level == level)
-                s->n_failed_attempts ++;
+        if (s->possible_feature_level == level) {
+                if (protocol == IPPROTO_UDP)
+                        s->n_failed_udp ++;
+                else if (protocol == IPPROTO_TCP)
+                        s->n_failed_tcp ++;
+        }
 
         if (s->resend_timeout > usec)
                 return;
@@ -274,19 +296,31 @@ void dns_server_packet_failed(DnsServer *s, DnsServerFeatureLevel level) {
         assert(s);
         assert(s->manager);
 
+        /* Invoked whenever we get a FORMERR, SERVFAIL or NOTIMP rcode from a server. */
+
         if (s->possible_feature_level != level)
                 return;
 
-        s->n_failed_attempts  = (unsigned) -1;
+        s->packet_failed = true;
+}
+
+void dns_server_packet_truncated(DnsServer *s, DnsServerFeatureLevel level) {
+        assert(s);
+        assert(s->manager);
+
+        /* Invoked whenever we get a packet with TC bit set. */
+
+        if (s->possible_feature_level != level)
+                return;
+
+        s->packet_truncated = true;
 }
 
 void dns_server_packet_rrsig_missing(DnsServer *s) {
-        _cleanup_free_ char *ip = NULL;
         assert(s);
         assert(s->manager);
 
-        in_addr_to_string(s->family, &s->address, &ip);
-        log_warning("DNS server %s does not augment replies with RRSIG records, DNSSEC not available.", strna(ip));
+        log_warning("DNS server %s does not augment replies with RRSIG records, DNSSEC not available.", dns_server_string(s));
 
         s->rrsig_missing = true;
 }
@@ -310,33 +344,80 @@ static bool dns_server_grace_period_expired(DnsServer *s) {
         return true;
 }
 
+static void dns_server_reset_counters(DnsServer *s) {
+        assert(s);
+
+        s->n_failed_udp = 0;
+        s->n_failed_tcp = 0;
+        s->packet_failed = false;
+        s->packet_truncated = false;
+        s->verified_usec = 0;
+}
+
 DnsServerFeatureLevel dns_server_possible_feature_level(DnsServer *s) {
         assert(s);
 
         if (s->possible_feature_level != DNS_SERVER_FEATURE_LEVEL_BEST &&
             dns_server_grace_period_expired(s)) {
-                _cleanup_free_ char *ip = NULL;
 
                 s->possible_feature_level = DNS_SERVER_FEATURE_LEVEL_BEST;
-                s->n_failed_attempts = 0;
-                s->verified_usec = 0;
                 s->rrsig_missing = false;
 
-                in_addr_to_string(s->family, &s->address, &ip);
-                log_info("Grace period over, resuming full feature set for DNS server %s", strna(ip));
-        } else if (s->possible_feature_level <= s->verified_feature_level)
-                s->possible_feature_level = s->verified_feature_level;
-        else if (s->n_failed_attempts >= DNS_SERVER_FEATURE_RETRY_ATTEMPTS &&
-                 s->possible_feature_level > DNS_SERVER_FEATURE_LEVEL_WORST) {
-                _cleanup_free_ char *ip = NULL;
+                dns_server_reset_counters(s);
 
-                s->possible_feature_level --;
-                s->n_failed_attempts = 0;
-                s->verified_usec = 0;
+                log_info("Grace period over, resuming full feature set (%s) for DNS server %s",
+                         dns_server_feature_level_to_string(s->possible_feature_level),
+                         dns_server_string(s));
 
-                in_addr_to_string(s->family, &s->address, &ip);
-                log_warning("Using degraded feature set (%s) for DNS server %s",
-                            dns_server_feature_level_to_string(s->possible_feature_level), strna(ip));
+        } else if (s->possible_feature_level <= s->verified_feature_level)
+                s->possible_feature_level = s->verified_feature_level;
+        else {
+                DnsServerFeatureLevel p = s->possible_feature_level;
+
+                if (s->n_failed_tcp >= DNS_SERVER_FEATURE_RETRY_ATTEMPTS &&
+                    s->possible_feature_level == DNS_SERVER_FEATURE_LEVEL_TCP)
+
+                        /* We are at the TCP (lowest) level, and we tried a couple of TCP connections, and it didn't
+                         * work. Upgrade back to UDP again. */
+                        s->possible_feature_level = DNS_SERVER_FEATURE_LEVEL_UDP;
+
+                else if ((s->n_failed_udp >= DNS_SERVER_FEATURE_RETRY_ATTEMPTS &&
+                          s->possible_feature_level >= DNS_SERVER_FEATURE_LEVEL_UDP) ||
+                         (s->packet_failed &&
+                          s->possible_feature_level > DNS_SERVER_FEATURE_LEVEL_UDP) ||
+                         (s->n_failed_tcp >= DNS_SERVER_FEATURE_RETRY_ATTEMPTS &&
+                          s->packet_truncated &&
+                          s->possible_feature_level > DNS_SERVER_FEATURE_LEVEL_UDP))
+
+                        /* Downgrade the feature one level, maybe things will work better then. We do this under any of
+                         * three conditions:
+                         *
+                         * 1. We lost too many UDP packets in a row, and are on a feature level of UDP or higher. If
+                         *    the packets are lost, maybe the server cannot parse them, hence downgrading sounds like a
+                         *    good idea. We might downgrade all the way down to TCP this way.
+                         *
+                         * 2. We got a failure packet, and are at a feature level above UDP. Note that in this case we
+                         *    downgrade no further than UDP, under the assumption that a failure packet indicates an
+                         *    incompatible packet contents, but not a problem with the transport.
+                         *
+                         * 3. We got too many TCP connection failures in a row, we had at least one truncated packet,
+                         *    and are on a feature level above UDP. By downgrading things and getting rid of DNSSEC or
+                         *    EDNS0 data we hope to make the packet smaller, so that it still works via UDP given that
+                         *    TCP appears not to be a fallback. Note that if we are already at the lowest UDP level, we
+                         *    don't go further down, since that's TCP, and TCP failed too often after all.
+                         */
+
+                        s->possible_feature_level--;
+
+                if (p != s->possible_feature_level) {
+
+                        /* We changed the feature level, reset the counting */
+                        dns_server_reset_counters(s);
+
+                        log_warning("Using degraded feature set (%s) for DNS server %s",
+                                    dns_server_feature_level_to_string(s->possible_feature_level),
+                                    dns_server_string(s));
+                }
         }
 
         return s->possible_feature_level;
@@ -370,6 +451,33 @@ int dns_server_adjust_opt(DnsServer *server, DnsPacket *packet, DnsServerFeature
         return dns_packet_append_opt(packet, packet_size, edns_do, NULL);
 }
 
+const char *dns_server_string(DnsServer *server) {
+        assert(server);
+
+        if (!server->server_string)
+                (void) in_addr_to_string(server->family, &server->address, &server->server_string);
+
+        return strna(server->server_string);
+}
+
+bool dns_server_dnssec_supported(DnsServer *server) {
+        assert(server);
+
+        /* Returns whether the server supports DNSSEC according to what we know about it */
+
+        if (server->possible_feature_level < DNS_SERVER_FEATURE_LEVEL_DO)
+                return false;
+
+        if (server->rrsig_missing)
+                return false;
+
+        /* DNSSEC servers need to support TCP properly (see RFC5966), if they don't, we assume DNSSEC is borked too */
+        if (server->n_failed_tcp >= DNS_SERVER_FEATURE_RETRY_ATTEMPTS)
+                return false;
+
+        return true;
+}
+
 static void dns_server_hash_func(const void *p, struct siphash *state) {
         const DnsServer *s = p;
 
@@ -461,12 +569,8 @@ DnsServer *manager_set_dns_server(Manager *m, DnsServer *s) {
         if (m->current_dns_server == s)
                 return s;
 
-        if (s) {
-                _cleanup_free_ char *ip = NULL;
-
-                in_addr_to_string(s->family, &s->address, &ip);
-                log_info("Switching to system DNS server %s.", strna(ip));
-        }
+        if (s)
+                log_info("Switching to system DNS server %s.", dns_server_string(s));
 
         dns_server_unref(m->current_dns_server);
         m->current_dns_server = dns_server_ref(s);
diff --git a/src/resolve/resolved-dns-server.h b/src/resolve/resolved-dns-server.h
index da21e6571a..323f702903 100644
--- a/src/resolve/resolved-dns-server.h
+++ b/src/resolve/resolved-dns-server.h
@@ -61,13 +61,18 @@ struct DnsServer {
         int family;
         union in_addr_union address;
 
+        char *server_string;
+
         usec_t resend_timeout;
         usec_t max_rtt;
 
         DnsServerFeatureLevel verified_feature_level;
         DnsServerFeatureLevel possible_feature_level;
         size_t received_udp_packet_max;
-        unsigned n_failed_attempts;
+        unsigned n_failed_udp;
+        unsigned n_failed_tcp;
+        bool packet_failed:1;
+        bool packet_truncated:1;
         usec_t verified_usec;
         usec_t features_grace_period_usec;
 
@@ -99,15 +104,20 @@ DnsServer* dns_server_unref(DnsServer *s);
 void dns_server_unlink(DnsServer *s);
 void dns_server_move_back_and_unmark(DnsServer *s);
 
-void dns_server_packet_received(DnsServer *s, DnsServerFeatureLevel level, usec_t rtt, size_t size);
-void dns_server_packet_lost(DnsServer *s, DnsServerFeatureLevel level, usec_t usec);
+void dns_server_packet_received(DnsServer *s, int protocol, DnsServerFeatureLevel level, usec_t rtt, size_t size);
+void dns_server_packet_lost(DnsServer *s, int protocol, DnsServerFeatureLevel level, usec_t usec);
 void dns_server_packet_failed(DnsServer *s, DnsServerFeatureLevel level);
+void dns_server_packet_truncated(DnsServer *s, DnsServerFeatureLevel level);
 void dns_server_packet_rrsig_missing(DnsServer *s);
 
 DnsServerFeatureLevel dns_server_possible_feature_level(DnsServer *s);
 
 int dns_server_adjust_opt(DnsServer *server, DnsPacket *packet, DnsServerFeatureLevel level);
 
+const char *dns_server_string(DnsServer *server);
+
+bool dns_server_dnssec_supported(DnsServer *server);
+
 DnsServer *dns_server_find(DnsServer *first, int family, const union in_addr_union *in_addr);
 
 void dns_server_unlink_all(DnsServer *first);
diff --git a/src/resolve/resolved-dns-stream.c b/src/resolve/resolved-dns-stream.c
index 180f8e0877..b72e6cc06f 100644
--- a/src/resolve/resolved-dns-stream.c
+++ b/src/resolve/resolved-dns-stream.c
@@ -367,6 +367,8 @@ int dns_stream_new(Manager *m, DnsStream **ret, DnsProtocol protocol, int fd) {
         if (r < 0)
                 return r;
 
+        (void) sd_event_source_set_description(s->io_event_source, "dns-stream-io");
+
         r = sd_event_add_time(
                         m->event,
                         &s->timeout_event_source,
@@ -376,6 +378,8 @@ int dns_stream_new(Manager *m, DnsStream **ret, DnsProtocol protocol, int fd) {
         if (r < 0)
                 return r;
 
+        (void) sd_event_source_set_description(s->timeout_event_source, "dns-stream-timeout");
+
         LIST_PREPEND(streams, m->dns_streams, s);
         s->manager = m;
         s->fd = fd;
diff --git a/src/resolve/resolved-dns-transaction.c b/src/resolve/resolved-dns-transaction.c
index f5171a940f..9ee10f21c8 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -138,6 +138,8 @@ int dns_transaction_new(DnsTransaction **ret, DnsScope *s, DnsResourceKey *key)
         /* Don't allow looking up invalid or pseudo RRs */
         if (!dns_type_is_valid_query(key->type))
                 return -EINVAL;
+        if (dns_type_is_obsolete(key->type))
+                return -EOPNOTSUPP;
 
         /* We only support the IN class */
         if (key->class != DNS_CLASS_IN && key->class != DNS_CLASS_ANY)
@@ -160,6 +162,7 @@ int dns_transaction_new(DnsTransaction **ret, DnsScope *s, DnsResourceKey *key)
         t->answer_dnssec_result = _DNSSEC_RESULT_INVALID;
         t->answer_nsec_ttl = (uint32_t) -1;
         t->key = dns_resource_key_ref(key);
+        t->current_feature_level = _DNS_SERVER_FEATURE_LEVEL_INVALID;
 
         /* Find a fresh, unused transaction id */
         do
@@ -325,7 +328,7 @@ static int dns_transaction_pick_server(DnsTransaction *t) {
         if (!server)
                 return -ESRCH;
 
-        t->current_features = dns_server_possible_feature_level(server);
+        t->current_feature_level = dns_server_possible_feature_level(server);
 
         if (server == t->server)
                 return 0;
@@ -336,6 +339,21 @@ static int dns_transaction_pick_server(DnsTransaction *t) {
         return 1;
 }
 
+static void dns_transaction_retry(DnsTransaction *t) {
+        int r;
+
+        assert(t);
+
+        log_debug("Retrying transaction %" PRIu16 ".", t->id);
+
+        /* Before we try again, switch to a new server. */
+        dns_scope_next_dns_server(t->scope);
+
+        r = dns_transaction_go(t);
+        if (r < 0)
+                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+}
+
 static int on_stream_complete(DnsStream *s, int error) {
         _cleanup_(dns_packet_unrefp) DnsPacket *p = NULL;
         DnsTransaction *t;
@@ -350,11 +368,16 @@ static int on_stream_complete(DnsStream *s, int error) {
 
         t->stream = dns_stream_free(t->stream);
 
-        if (IN_SET(error, ENOTCONN, ECONNRESET, ECONNREFUSED, ECONNABORTED, EPIPE)) {
-                dns_transaction_complete(t, DNS_TRANSACTION_CONNECTION_FAILURE);
+        if (ERRNO_IS_DISCONNECT(error)) {
+                usec_t usec;
+
+                log_debug_errno(error, "Connection failure for DNS TCP stream: %m");
+                assert_se(sd_event_now(t->scope->manager->event, clock_boottime_or_monotonic(), &usec) >= 0);
+                dns_server_packet_lost(t->server, IPPROTO_TCP, t->current_feature_level, usec - t->start_usec);
+
+                dns_transaction_retry(t);
                 return 0;
         }
-
         if (error != 0) {
                 dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
                 return 0;
@@ -398,7 +421,10 @@ static int dns_transaction_open_tcp(DnsTransaction *t) {
                 if (r < 0)
                         return r;
 
-                r = dns_server_adjust_opt(t->server, t->sent, t->current_features);
+                if (!dns_server_dnssec_supported(t->server) && dns_type_is_dnssec(t->key->type))
+                        return -EOPNOTSUPP;
+
+                r = dns_server_adjust_opt(t->server, t->sent, t->current_feature_level);
                 if (r < 0)
                         return r;
 
@@ -644,17 +670,13 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
                         /* Request failed, immediately try again with reduced features */
                         log_debug("Server returned error: %s", dns_rcode_to_string(DNS_PACKET_RCODE(p)));
 
-                        dns_server_packet_failed(t->server, t->current_features);
-
-                        r = dns_transaction_go(t);
-                        if (r < 0) {
-                                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
-                                return;
-                        }
-
+                        dns_server_packet_failed(t->server, t->current_feature_level);
+                        dns_transaction_retry(t);
                         return;
-                } else
-                        dns_server_packet_received(t->server, t->current_features, ts - t->start_usec, p->size);
+                } else if (DNS_PACKET_TC(p))
+                        dns_server_packet_truncated(t->server, t->current_feature_level);
+                else
+                        dns_server_packet_received(t->server, p->ipproto, t->current_feature_level, ts - t->start_usec, p->size);
 
                 break;
 
@@ -675,6 +697,8 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
                         return;
                 }
 
+                log_debug("Reply truncated, retrying via TCP.");
+
                 /* Response was truncated, let's try again with good old TCP */
                 r = dns_transaction_open_tcp(t);
                 if (r == -ESRCH) {
@@ -682,22 +706,21 @@ void dns_transaction_process_reply(DnsTransaction *t, DnsPacket *p) {
                         dns_transaction_complete(t, DNS_TRANSACTION_NO_SERVERS);
                         return;
                 }
+                if (r == -EOPNOTSUPP) {
+                        /* Tried to ask for DNSSEC RRs, on a server that doesn't do DNSSEC  */
+                        dns_transaction_complete(t, DNS_TRANSACTION_RR_TYPE_UNSUPPORTED);
+                        return;
+                }
                 if (r < 0) {
                         /* On LLMNR, if we cannot connect to the host,
                          * we immediately give up */
-                        if (t->scope->protocol == DNS_PROTOCOL_LLMNR) {
+                        if (t->scope->protocol != DNS_PROTOCOL_DNS) {
                                 dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
                                 return;
                         }
 
                         /* On DNS, couldn't send? Try immediately again, with a new server */
-                        dns_scope_next_dns_server(t->scope);
-
-                        r = dns_transaction_go(t);
-                        if (r < 0) {
-                                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
-                                return;
-                        }
+                        dns_transaction_retry(t);
                 }
 
                 return;
@@ -771,15 +794,40 @@ static int on_dns_packet(sd_event_source *s, int fd, uint32_t revents, void *use
         assert(t->scope);
 
         r = manager_recv(t->scope->manager, fd, DNS_PROTOCOL_DNS, &p);
-        if (r <= 0)
-                return r;
+        if (ERRNO_IS_DISCONNECT(-r)) {
+                usec_t usec;
 
-        if (dns_packet_validate_reply(p) > 0 &&
-            DNS_PACKET_ID(p) == t->id)
-                dns_transaction_process_reply(t, p);
-        else
-                log_debug("Invalid DNS UDP packet, ignoring.");
+                /* UDP connection failure get reported via ICMP and then are possible delivered to us on the next
+                 * recvmsg(). Treat this like a lost packet. */
 
+                log_debug_errno(r, "Connection failure for DNS UDP packet: %m");
+                assert_se(sd_event_now(t->scope->manager->event, clock_boottime_or_monotonic(), &usec) >= 0);
+                dns_server_packet_lost(t->server, IPPROTO_UDP, t->current_feature_level, usec - t->start_usec);
+
+                dns_transaction_retry(t);
+                return 0;
+        }
+        if (r < 0) {
+                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
+                return 0;
+        }
+
+        r = dns_packet_validate_reply(p);
+        if (r < 0) {
+                log_debug_errno(r, "Received invalid DNS packet as response, ignoring: %m");
+                return 0;
+        }
+        if (r == 0) {
+                log_debug("Received inappropriate DNS packet as response, ignoring: %m");
+                return 0;
+        }
+
+        if (DNS_PACKET_ID(p) != t->id) {
+                log_debug("Received packet with incorrect transaction ID, ignoring: %m");
+                return 0;
+        }
+
+        dns_transaction_process_reply(t, p);
         return 0;
 }
 
@@ -794,9 +842,12 @@ static int dns_transaction_emit_udp(DnsTransaction *t) {
                 if (r < 0)
                         return r;
 
-                if (t->current_features < DNS_SERVER_FEATURE_LEVEL_UDP)
+                if (t->current_feature_level < DNS_SERVER_FEATURE_LEVEL_UDP)
                         return -EAGAIN;
 
+                if (!dns_server_dnssec_supported(t->server) && dns_type_is_dnssec(t->key->type))
+                        return -EOPNOTSUPP;
+
                 if (r > 0 || t->dns_udp_fd < 0) { /* Server changed, or no connection yet. */
                         int fd;
 
@@ -812,10 +863,11 @@ static int dns_transaction_emit_udp(DnsTransaction *t) {
                                 return r;
                         }
 
+                        (void) sd_event_source_set_description(t->dns_udp_event_source, "dns-transaction-udp");
                         t->dns_udp_fd = fd;
                 }
 
-                r = dns_server_adjust_opt(t->server, t->sent, t->current_features);
+                r = dns_server_adjust_opt(t->server, t->sent, t->current_feature_level);
                 if (r < 0)
                         return r;
         } else
@@ -832,7 +884,6 @@ static int dns_transaction_emit_udp(DnsTransaction *t) {
 
 static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdata) {
         DnsTransaction *t = userdata;
-        int r;
 
         assert(s);
         assert(t);
@@ -843,7 +894,7 @@ static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdat
 
                 case DNS_PROTOCOL_DNS:
                         assert(t->server);
-                        dns_server_packet_lost(t->server, t->current_features, usec - t->start_usec);
+                        dns_server_packet_lost(t->server, t->stream ? IPPROTO_TCP : IPPROTO_UDP, t->current_feature_level, usec - t->start_usec);
                         break;
 
                 case DNS_PROTOCOL_LLMNR:
@@ -861,13 +912,7 @@ static int on_transaction_timeout(sd_event_source *s, usec_t usec, void *userdat
 
         log_debug("Timeout reached on transaction %" PRIu16 ".", t->id);
 
-        /* ...and try again with a new server */
-        dns_scope_next_dns_server(t->scope);
-
-        r = dns_transaction_go(t);
-        if (r < 0)
-                dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
-
+        dns_transaction_retry(t);
         return 0;
 }
 
@@ -1088,6 +1133,8 @@ static int dns_transaction_make_packet_mdns(DnsTransaction *t) {
                 if (r < 0)
                         return r;
 
+                (void) sd_event_source_set_description(t->timeout_event_source, "dns-transaction-timeout");
+
                 other->state = DNS_TRANSACTION_PENDING;
                 other->next_attempt_after = ts;
 
@@ -1203,6 +1250,8 @@ int dns_transaction_go(DnsTransaction *t) {
                 if (r < 0)
                         return r;
 
+                (void) sd_event_source_set_description(t->timeout_event_source, "dns-transaction-timeout");
+
                 t->n_attempts = 0;
                 t->next_attempt_after = ts;
                 t->state = DNS_TRANSACTION_PENDING;
@@ -1234,6 +1283,10 @@ int dns_transaction_go(DnsTransaction *t) {
                 /* Try via UDP, and if that fails due to large size or lack of
                  * support try via TCP */
                 r = dns_transaction_emit_udp(t);
+                if (r == -EMSGSIZE)
+                        log_debug("Sending query via TCP since it is too large.");
+                if (r == -EAGAIN)
+                        log_debug("Sending query via TCP since server doesn't support UDP.");
                 if (r == -EMSGSIZE || r == -EAGAIN)
                         r = dns_transaction_open_tcp(t);
         }
@@ -1242,7 +1295,13 @@ int dns_transaction_go(DnsTransaction *t) {
                 /* No servers to send this to? */
                 dns_transaction_complete(t, DNS_TRANSACTION_NO_SERVERS);
                 return 0;
-        } else if (r < 0) {
+        }
+        if (r == -EOPNOTSUPP) {
+                /* Tried to ask for DNSSEC RRs, on a server that doesn't do DNSSEC  */
+                dns_transaction_complete(t, DNS_TRANSACTION_RR_TYPE_UNSUPPORTED);
+                return 0;
+        }
+        if (r < 0) {
                 if (t->scope->protocol != DNS_PROTOCOL_DNS) {
                         dns_transaction_complete(t, DNS_TRANSACTION_RESOURCES);
                         return 0;
@@ -1265,6 +1324,8 @@ int dns_transaction_go(DnsTransaction *t) {
         if (r < 0)
                 return r;
 
+        (void) sd_event_source_set_description(t->timeout_event_source, "dns-transaction-timeout");
+
         t->state = DNS_TRANSACTION_PENDING;
         t->next_attempt_after = ts;
 
@@ -1497,6 +1558,44 @@ static int dns_transaction_is_primary_response(DnsTransaction *t, DnsResourceRec
         return rr->key->type == DNS_TYPE_NSEC;
 }
 
+static bool dns_transaction_dnssec_supported(DnsTransaction *t) {
+        assert(t);
+
+        /* Checks whether our transaction's DNS server is assumed to be compatible with DNSSEC. Returns false as soon
+         * as we changed our mind about a server, and now believe it is incompatible with DNSSEC. */
+
+        if (t->scope->protocol != DNS_PROTOCOL_DNS)
+                return false;
+
+        /* If we have picked no server, then we are working from the cache or some other source, and DNSSEC might well
+         * be supported, hence return true. */
+        if (!t->server)
+                return true;
+
+        if (t->current_feature_level < DNS_SERVER_FEATURE_LEVEL_DO)
+                return false;
+
+        return dns_server_dnssec_supported(t->server);
+}
+
+static bool dns_transaction_dnssec_supported_full(DnsTransaction *t) {
+        DnsTransaction *dt;
+        Iterator i;
+
+        assert(t);
+
+        /* Checks whether our transaction our any of the auxiliary transactions couldn't do DNSSEC. */
+
+        if (!dns_transaction_dnssec_supported(t))
+                return false;
+
+        SET_FOREACH(dt, t->dnssec_transactions, i)
+                if (!dns_transaction_dnssec_supported(dt))
+                        return false;
+
+        return true;
+}
+
 int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
         DnsResourceRecord *rr;
 
@@ -1520,11 +1619,10 @@ int dns_transaction_request_dnssec_keys(DnsTransaction *t) {
 
         if (t->scope->dnssec_mode == DNSSEC_NO)
                 return 0;
-
-        if (t->current_features < DNS_SERVER_FEATURE_LEVEL_DO)
-                return 0; /* Server doesn't do DNSSEC, there's no point in requesting any RRs then. */
-        if (t->server && t->server->rrsig_missing)
-                return 0; /* Server handles DNSSEC requests, but isn't augmenting responses with RRSIGs. No point in trying DNSSEC then. */
+        if (t->answer_source != DNS_TRANSACTION_NETWORK)
+                return 0; /* We only need to validate stuff from the network */
+        if (!dns_transaction_dnssec_supported(t))
+                return 0; /* If we can't do DNSSEC anyway there's no point in geting the auxiliary RRs */
 
         DNS_ANSWER_FOREACH(rr, t->answer) {
 
@@ -2227,9 +2325,66 @@ static int dns_transaction_known_signed(DnsTransaction *t, DnsResourceRecord *rr
                 dns_name_is_root(DNS_RESOURCE_KEY_NAME(rr->key));
 }
 
+static int dns_transaction_check_revoked_trust_anchors(DnsTransaction *t) {
+        DnsResourceRecord *rr;
+        int r;
+
+        assert(t);
+
+        /* Maybe warn the user that we encountered a revoked DNSKEY
+         * for a key from our trust anchor. Note that we don't care
+         * whether the DNSKEY can be authenticated or not. It's
+         * sufficient if it is self-signed. */
+
+        DNS_ANSWER_FOREACH(rr, t->answer) {
+                r = dns_trust_anchor_check_revoked(&t->scope->manager->trust_anchor, rr, t->answer);
+                if (r < 0)
+                        return r;
+        }
+
+        return 0;
+}
+
+static int dns_transaction_invalidate_revoked_keys(DnsTransaction *t) {
+        bool changed;
+        int r;
+
+        assert(t);
+
+        /* Removes all DNSKEY/DS objects from t->validated_keys that
+         * our trust anchors database considers revoked. */
+
+        do {
+                DnsResourceRecord *rr;
+
+                changed = false;
+
+                DNS_ANSWER_FOREACH(rr, t->validated_keys) {
+                        r = dns_trust_anchor_is_revoked(&t->scope->manager->trust_anchor, rr);
+                        if (r < 0)
+                                return r;
+                        if (r > 0) {
+                                r = dns_answer_remove_by_rr(&t->validated_keys, rr);
+                                if (r < 0)
+                                        return r;
+
+                                assert(r > 0);
+                                changed = true;
+                                break;
+                        }
+                }
+        } while (changed);
+
+        return 0;
+}
+
 int dns_transaction_validate_dnssec(DnsTransaction *t) {
         _cleanup_(dns_answer_unrefp) DnsAnswer *validated = NULL;
-        bool dnskeys_finalized = false;
+        enum {
+                PHASE_DNSKEY,   /* Phase #1, only validate DNSKEYs */
+                PHASE_NSEC,     /* Phase #2, only validate NSEC+NSEC3 */
+                PHASE_ALL,      /* Phase #3, validate everything else */
+        } phase;
         DnsResourceRecord *rr;
         DnsAnswerFlags flags;
         int r;
@@ -2258,30 +2413,73 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
         if (t->answer_source != DNS_TRANSACTION_NETWORK)
                 return 0;
 
-        if (t->current_features < DNS_SERVER_FEATURE_LEVEL_DO ||
-            (t->server && t->server->rrsig_missing)) {
+        if (!dns_transaction_dnssec_supported_full(t)) {
                 /* The server does not support DNSSEC, or doesn't augment responses with RRSIGs. */
                 t->answer_dnssec_result = DNSSEC_INCOMPATIBLE_SERVER;
+                log_debug("Cannot validate response, server lacks DNSSEC support.");
                 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. */
+        /* First, see if this response contains any revoked trust
+         * anchors we care about */
+        r = dns_transaction_check_revoked_trust_anchors(t);
+        if (r < 0)
+                return r;
+
+        /* Second, see if there are DNSKEYs we already know a
+         * validated DS for. */
         r = dns_transaction_validate_dnskey_by_ds(t);
         if (r < 0)
                 return r;
 
+        /* Third, remove all DNSKEY and DS RRs again that our trust
+         * anchor says are revoked. After all we might have marked
+         * some keys revoked above, but they might still be lingering
+         * in our validated_keys list. */
+        r = dns_transaction_invalidate_revoked_keys(t);
+        if (r < 0)
+                return r;
+
+        phase = PHASE_DNSKEY;
         for (;;) {
-                bool changed = false;
+                bool changed = false, have_nsec = false;
 
                 DNS_ANSWER_FOREACH(rr, t->answer) {
+                        DnsResourceRecord *rrsig = NULL;
                         DnssecResult result;
 
-                        if (rr->key->type == DNS_TYPE_RRSIG)
+                        switch (rr->key->type) {
+
+                        case DNS_TYPE_RRSIG:
                                 continue;
 
-                        r = dnssec_verify_rrset_search(t->answer, rr->key, t->validated_keys, USEC_INFINITY, &result);
+                        case DNS_TYPE_DNSKEY:
+                                /* We validate DNSKEYs only in the DNSKEY and ALL phases */
+                                if (phase == PHASE_NSEC)
+                                        continue;
+                                break;
+
+                        case DNS_TYPE_NSEC:
+                        case DNS_TYPE_NSEC3:
+                                have_nsec = true;
+
+                                /* We validate NSEC/NSEC3 only in the NSEC and ALL phases */
+                                if (phase == PHASE_DNSKEY)
+                                        continue;
+
+                                break;
+
+                        default:
+                                /* We validate all other RRs only in the ALL phases */
+                                if (phase != PHASE_ALL)
+                                        continue;
+
+                                break;
+                        }
+
+                        r = dnssec_verify_rrset_search(t->answer, rr->key, t->validated_keys, USEC_INFINITY, &result, &rrsig);
                         if (r < 0)
                                 return r;
 
@@ -2300,11 +2498,11 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                                         if (r < 0)
                                                 return r;
 
-                                        /* Maybe warn the user that we
-                                         * encountered a revoked
-                                         * DNSKEY for a key from our
-                                         * trust anchor */
-                                        r = dns_trust_anchor_check_revoked(&t->scope->manager->trust_anchor, t->answer, rr->key);
+                                        /* some of the DNSKEYs we just
+                                         * added might already have
+                                         * been revoked, remove them
+                                         * again in that case. */
+                                        r = dns_transaction_invalidate_revoked_keys(t);
                                         if (r < 0)
                                                 return r;
                                 }
@@ -2323,69 +2521,86 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                                 /* Exit the loop, we dropped something from the answer, start from the beginning */
                                 changed = true;
                                 break;
+                        }
 
-                        } else if (dnskeys_finalized) {
+                        /* If we haven't read all DNSKEYs yet a negative result of the validation is irrelevant, as
+                         * there might be more DNSKEYs coming. Similar, if we haven't read all NSEC/NSEC3 RRs yet, we
+                         * cannot do positive wildcard proofs yet, as those require the NSEC/NSEC3 RRs. */
+                        if (phase != PHASE_ALL)
+                                continue;
 
-                                /* If we haven't read all DNSKEYs yet
-                                 * a negative result of the validation
-                                 * is irrelevant, as there might be
-                                 * more DNSKEYs coming. */
+                        if (result == DNSSEC_VALIDATED_WILDCARD) {
+                                bool authenticated = false;
+                                const char *suffix;
 
-                                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;
+                                /* This RRset validated, but as a wildcard. This means we need to proof via NSEC/NSEC3
+                                 * that no matching non-wildcard RR exists.
+                                 *
+                                 * See RFC 5155, Section 8.8 and RFC 4035, Section 5.3.4*/
 
-                                                t->scope->manager->n_dnssec_insecure++;
+                                r = dns_name_suffix(DNS_RESOURCE_KEY_NAME(rr->key), rrsig->rrsig.labels, &suffix);
+                                if (r < 0)
+                                        return r;
+                                if (r == 0)
+                                        return -EBADMSG;
 
-                                                changed = true;
-                                                break;
-                                        }
+                                r = dns_name_parent(&suffix);
+                                if (r < 0)
+                                        return r;
+                                if (r == 0)
+                                        return -EBADMSG;
 
-                                        r = dns_transaction_known_signed(t, rr);
+                                r = dnssec_nsec_test_between(validated, DNS_RESOURCE_KEY_NAME(rr->key), suffix, &authenticated);
+                                if (r < 0)
+                                        return r;
+
+                                /* Unless the NSEC proof showed that the key really doesn't exist something is off. */
+                                if (r == 0)
+                                        result = DNSSEC_INVALID;
+                                else {
+                                        r = dns_answer_move_by_key(&validated, &t->answer, rr->key, authenticated ? (DNS_ANSWER_AUTHENTICATED|DNS_ANSWER_CACHEABLE) : 0);
                                         if (r < 0)
                                                 return r;
-                                        if (r > 0) {
-                                                /* This is an RR we know has to be signed. If it isn't this means
-                                                 * the server is not attaching RRSIGs, hence complain. */
 
-                                                dns_server_packet_rrsig_missing(t->server);
+                                        if (authenticated)
+                                                t->scope->manager->n_dnssec_secure++;
+                                        else
+                                                t->scope->manager->n_dnssec_insecure++;
 
-                                                if (t->scope->dnssec_mode == DNSSEC_ALLOW_DOWNGRADE) {
+                                        /* Exit the loop, we dropped something from the answer, start from the beginning */
+                                        changed = true;
+                                        break;
+                                }
+                        }
 
-                                                        /* Downgrading is OK? If so, just consider the information unsigned */
+                        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;
 
-                                                        r = dns_answer_move_by_key(&validated, &t->answer, rr->key, 0);
-                                                        if (r < 0)
-                                                                return r;
+                                        t->scope->manager->n_dnssec_insecure++;
+                                        changed = true;
+                                        break;
+                                }
 
-                                                        t->scope->manager->n_dnssec_insecure++;
-                                                        changed = true;
-                                                        break;
-                                                }
+                                r = dns_transaction_known_signed(t, rr);
+                                if (r < 0)
+                                        return r;
+                                if (r > 0) {
+                                        /* This is an RR we know has to be signed. If it isn't this means
+                                         * the server is not attaching RRSIGs, hence complain. */
 
-                                                /* Otherwise, fail */
-                                                t->answer_dnssec_result = DNSSEC_INCOMPATIBLE_SERVER;
-                                                return 0;
-                                        }
+                                        dns_server_packet_rrsig_missing(t->server);
 
-                                        r = dns_transaction_in_private_tld(t, rr->key);
-                                        if (r < 0)
-                                                return r;
-                                        if (r > 0) {
-                                                _cleanup_free_ char *s = NULL;
+                                        if (t->scope->dnssec_mode == DNSSEC_ALLOW_DOWNGRADE) {
 
-                                                /* The data is from a TLD that is proven not to exist, and we are in downgrade
-                                                 * mode, hence ignore the fact that this was not signed. */
-
-                                                (void) dns_resource_key_to_string(rr->key, &s);
-                                                log_info("Detected RRset %s is in a private DNS zone, permitting unsigned RRs.", strna(s ? strstrip(s) : NULL));
+                                                /* Downgrading is OK? If so, just consider the information unsigned */
 
                                                 r = dns_answer_move_by_key(&validated, &t->answer, rr->key, 0);
                                                 if (r < 0)
@@ -2395,75 +2610,102 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                                                 changed = true;
                                                 break;
                                         }
+
+                                        /* Otherwise, fail */
+                                        t->answer_dnssec_result = DNSSEC_INCOMPATIBLE_SERVER;
+                                        return 0;
                                 }
 
-                                if (IN_SET(result,
-                                           DNSSEC_MISSING_KEY,
-                                           DNSSEC_SIGNATURE_EXPIRED,
-                                           DNSSEC_UNSUPPORTED_ALGORITHM)) {
+                                r = dns_transaction_in_private_tld(t, rr->key);
+                                if (r < 0)
+                                        return r;
+                                if (r > 0) {
+                                        _cleanup_free_ char *s = NULL;
 
-                                        r = dns_transaction_dnskey_authenticated(t, rr);
-                                        if (r < 0 && r != -ENXIO)
-                                                return r;
-                                        if (r == 0) {
-                                                /* The DNSKEY transaction was not authenticated, this means there's
-                                                 * no DS for this, which means it's OK if no keys are found for this signature. */
+                                        /* The data is from a TLD that is proven not to exist, and we are in downgrade
+                                         * mode, hence ignore the fact that this was not signed. */
 
-                                                r = dns_answer_move_by_key(&validated, &t->answer, rr->key, 0);
-                                                if (r < 0)
-                                                        return r;
+                                        (void) dns_resource_key_to_string(rr->key, &s);
+                                        log_info("Detected RRset %s is in a private DNS zone, permitting unsigned RRs.", strna(s ? strstrip(s) : NULL));
 
-                                                t->scope->manager->n_dnssec_insecure++;
+                                        r = dns_answer_move_by_key(&validated, &t->answer, rr->key, 0);
+                                        if (r < 0)
+                                                return r;
 
-                                                changed = true;
-                                                break;
-                                        }
+                                        t->scope->manager->n_dnssec_insecure++;
+                                        changed = true;
+                                        break;
                                 }
+                        }
 
-                                if (IN_SET(result,
-                                           DNSSEC_INVALID,
-                                           DNSSEC_SIGNATURE_EXPIRED,
-                                           DNSSEC_NO_SIGNATURE))
-                                        t->scope->manager->n_dnssec_bogus++;
-                                else /* DNSSEC_MISSING_KEY or DNSSEC_UNSUPPORTED_ALGORITHM */
-                                        t->scope->manager->n_dnssec_indeterminate++;
+                        if (IN_SET(result,
+                                   DNSSEC_MISSING_KEY,
+                                   DNSSEC_SIGNATURE_EXPIRED,
+                                   DNSSEC_UNSUPPORTED_ALGORITHM)) {
 
-                                r = dns_transaction_is_primary_response(t, rr);
-                                if (r < 0)
+                                r = dns_transaction_dnskey_authenticated(t, rr);
+                                if (r < 0 && r != -ENXIO)
                                         return r;
-                                if (r > 0) {
-                                        /* This is a primary response
-                                         * to our question, and it
-                                         * failed validation. That's
-                                         * fatal. */
-                                        t->answer_dnssec_result = result;
-                                        return 0;
+                                if (r == 0) {
+                                        /* The DNSKEY transaction was not authenticated, this means there's
+                                         * no DS for this, which means it's OK if no keys are found for this signature. */
+
+                                        r = dns_answer_move_by_key(&validated, &t->answer, rr->key, 0);
+                                        if (r < 0)
+                                                return r;
+
+                                        t->scope->manager->n_dnssec_insecure++;
+                                        changed = true;
+                                        break;
                                 }
+                        }
 
-                                /* This is just some auxiliary
-                                 * data. Just remove the RRset and
-                                 * continue. */
-                                r = dns_answer_remove_by_key(&t->answer, rr->key);
-                                if (r < 0)
-                                        return r;
+                        if (IN_SET(result,
+                                   DNSSEC_INVALID,
+                                   DNSSEC_SIGNATURE_EXPIRED,
+                                   DNSSEC_NO_SIGNATURE))
+                                t->scope->manager->n_dnssec_bogus++;
+                        else /* DNSSEC_MISSING_KEY or DNSSEC_UNSUPPORTED_ALGORITHM */
+                                t->scope->manager->n_dnssec_indeterminate++;
 
-                                /* Exit the loop, we dropped something from the answer, start from the beginning */
-                                changed = true;
-                                break;
+                        r = dns_transaction_is_primary_response(t, rr);
+                        if (r < 0)
+                                return r;
+                        if (r > 0) {
+                                /* This is a primary response
+                                 * to our question, and it
+                                 * failed validation. That's
+                                 * fatal. */
+                                t->answer_dnssec_result = result;
+                                return 0;
                         }
+
+                        /* This is just some auxiliary
+                         * data. Just remove the RRset and
+                         * continue. */
+                        r = dns_answer_remove_by_key(&t->answer, rr->key);
+                        if (r < 0)
+                                return r;
+
+                        /* Exit the loop, we dropped something from the answer, start from the beginning */
+                        changed = true;
+                        break;
                 }
 
+                /* Restart the inner loop as long as we managed to achieve something */
                 if (changed)
                         continue;
 
-                if (!dnskeys_finalized) {
-                        /* OK, now we know we have added all DNSKEYs
-                         * we possibly could to our validated
-                         * list. Now run the whole thing once more,
-                         * and strip everything we still cannot
-                         * validate.
-                         */
-                        dnskeys_finalized = true;
+                if (phase == PHASE_DNSKEY && have_nsec) {
+                        /* OK, we processed all DNSKEYs, and there are NSEC/NSEC3 RRs, look at those now. */
+                        phase = PHASE_NSEC;
+                        continue;
+                }
+
+                if (phase != PHASE_ALL) {
+                        /* OK, we processed all DNSKEYs and NSEC/NSEC3 RRs, look at all the rest now. Note that in this
+                         * third phase we start to remove RRs we couldn't validate. */
+                        phase = PHASE_ALL;
                         continue;
                 }
 
@@ -2499,7 +2741,7 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                 bool authenticated = false;
 
                 /* Bummer! Let's check NSEC/NSEC3 */
-                r = dnssec_test_nsec(t->answer, t->key, &nr, &authenticated, &t->answer_nsec_ttl);
+                r = dnssec_nsec_test(t->answer, t->key, &nr, &authenticated, &t->answer_nsec_ttl);
                 if (r < 0)
                         return r;
 
@@ -2584,10 +2826,10 @@ static const char* const dns_transaction_state_table[_DNS_TRANSACTION_STATE_MAX]
         [DNS_TRANSACTION_ATTEMPTS_MAX_REACHED] = "attempts-max-reached",
         [DNS_TRANSACTION_INVALID_REPLY] = "invalid-reply",
         [DNS_TRANSACTION_RESOURCES] = "resources",
-        [DNS_TRANSACTION_CONNECTION_FAILURE] = "connection-failure",
         [DNS_TRANSACTION_ABORTED] = "aborted",
         [DNS_TRANSACTION_DNSSEC_FAILED] = "dnssec-failed",
         [DNS_TRANSACTION_NO_TRUST_ANCHOR] = "no-trust-anchor",
+        [DNS_TRANSACTION_RR_TYPE_UNSUPPORTED] = "rr-type-unsupported",
 };
 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 ede33f9547..76cf6e71db 100644
--- a/src/resolve/resolved-dns-transaction.h
+++ b/src/resolve/resolved-dns-transaction.h
@@ -36,10 +36,10 @@ enum DnsTransactionState {
         DNS_TRANSACTION_ATTEMPTS_MAX_REACHED,
         DNS_TRANSACTION_INVALID_REPLY,
         DNS_TRANSACTION_RESOURCES,
-        DNS_TRANSACTION_CONNECTION_FAILURE,
         DNS_TRANSACTION_ABORTED,
         DNS_TRANSACTION_DNSSEC_FAILED,
         DNS_TRANSACTION_NO_TRUST_ANCHOR,
+        DNS_TRANSACTION_RR_TYPE_UNSUPPORTED,
         _DNS_TRANSACTION_STATE_MAX,
         _DNS_TRANSACTION_STATE_INVALID = -1
 };
@@ -113,7 +113,7 @@ struct DnsTransaction {
         DnsServer *server;
 
         /* The features of the DNS server at time of transaction start */
-        DnsServerFeatureLevel current_features;
+        DnsServerFeatureLevel current_feature_level;
 
         /* Query candidates this transaction is referenced by and that
          * shall be notified about this specific transaction
diff --git a/src/resolve/resolved-dns-trust-anchor.c b/src/resolve/resolved-dns-trust-anchor.c
index 9f8b76ebe2..9bee44b5c7 100644
--- a/src/resolve/resolved-dns-trust-anchor.c
+++ b/src/resolve/resolved-dns-trust-anchor.c
@@ -511,13 +511,18 @@ int dns_trust_anchor_load(DnsTrustAnchor *d) {
 
 void dns_trust_anchor_flush(DnsTrustAnchor *d) {
         DnsAnswer *a;
+        DnsResourceRecord *rr;
 
         assert(d);
 
         while ((a = hashmap_steal_first(d->positive_by_key)))
                 dns_answer_unref(a);
-
         d->positive_by_key = hashmap_free(d->positive_by_key);
+
+        while ((rr = set_steal_first(d->revoked_by_rr)))
+                dns_resource_record_unref(rr);
+        d->revoked_by_rr = set_free(d->revoked_by_rr);
+
         d->negative_by_name = set_free_free(d->negative_by_name);
 }
 
@@ -547,11 +552,35 @@ int dns_trust_anchor_lookup_negative(DnsTrustAnchor *d, const char *name) {
         return set_contains(d->negative_by_name, name);
 }
 
+static int dns_trust_anchor_revoked_put(DnsTrustAnchor *d, DnsResourceRecord *rr) {
+        int r;
+
+        assert(d);
+
+        r = set_ensure_allocated(&d->revoked_by_rr, &dns_resource_record_hash_ops);
+        if (r < 0)
+                return r;
+
+        r = set_put(d->revoked_by_rr, rr);
+        if (r < 0)
+                return r;
+        if (r > 0)
+                dns_resource_record_ref(rr);
+
+        return r;
+}
+
 static int dns_trust_anchor_remove_revoked(DnsTrustAnchor *d, DnsResourceRecord *rr) {
         _cleanup_(dns_answer_unrefp) DnsAnswer *new_answer = NULL;
         DnsAnswer *old_answer;
         int r;
 
+        /* Remember that this is a revoked trust anchor RR */
+        r = dns_trust_anchor_revoked_put(d, rr);
+        if (r < 0)
+                return r;
+
+        /* Remove this from the positive trust anchor */
         old_answer = hashmap_get(d->positive_by_key, rr->key);
         if (!old_answer)
                 return 0;
@@ -610,6 +639,9 @@ static int dns_trust_anchor_check_revoked_one(DnsTrustAnchor *d, DnsResourceReco
                         if (anchor->dnskey.key_size != revoked_dnskey->dnskey.key_size)
                                 continue;
 
+                        /* Note that we allow the REVOKE bit to be
+                         * different! It will be set in the revoked
+                         * key, but unset in our version of it */
                         if (((anchor->dnskey.flags ^ revoked_dnskey->dnskey.flags) | DNSKEY_FLAG_REVOKE) != DNSKEY_FLAG_REVOKE)
                                 continue;
 
@@ -629,6 +661,10 @@ static int dns_trust_anchor_check_revoked_one(DnsTrustAnchor *d, DnsResourceReco
 
                 DNS_ANSWER_FOREACH(anchor, a) {
 
+                        /* We set mask_revoke to true here, since our
+                         * DS fingerprint will be the one of the
+                         * unrevoked DNSKEY, but the one we got passed
+                         * here has the bit set. */
                         r = dnssec_verify_dnskey(revoked_dnskey, anchor, true);
                         if (r < 0)
                                 return r;
@@ -643,62 +679,67 @@ static int dns_trust_anchor_check_revoked_one(DnsTrustAnchor *d, DnsResourceReco
         return 0;
 }
 
-int dns_trust_anchor_check_revoked(DnsTrustAnchor *d, DnsAnswer *rrs, const DnsResourceKey *key) {
-        DnsResourceRecord *dnskey;
+int dns_trust_anchor_check_revoked(DnsTrustAnchor *d, DnsResourceRecord *dnskey, DnsAnswer *rrs) {
+        DnsResourceRecord *rrsig;
         int r;
 
         assert(d);
-        assert(key);
+        assert(dnskey);
 
-        /* Looks for self-signed DNSKEY RRs in "rrs" that have been revoked. */
+        /* Looks if "dnskey" is a self-signed RR that has been revoked
+         * and matches one of our trust anchor entries. If so, removes
+         * it from the trust anchor and returns > 0. */
 
-        if (key->type != DNS_TYPE_DNSKEY)
+        if (dnskey->key->type != DNS_TYPE_DNSKEY)
                 return 0;
 
-        DNS_ANSWER_FOREACH(dnskey, rrs) {
-                DnsResourceRecord *rrsig;
+        /* Is this DNSKEY revoked? */
+        if ((dnskey->dnskey.flags & DNSKEY_FLAG_REVOKE) == 0)
+                return 0;
+
+        /* Could this be interesting to us at all? If not,
+         * there's no point in looking for and verifying a
+         * self-signed RRSIG. */
+        if (!dns_trust_anchor_knows_domain_positive(d, DNS_RESOURCE_KEY_NAME(dnskey->key)))
+                return 0;
+
+        /* Look for a self-signed RRSIG in the other rrs belonging to this DNSKEY */
+        DNS_ANSWER_FOREACH(rrsig, rrs) {
                 DnssecResult result;
 
-                r = dns_resource_key_equal(key, dnskey->key);
+                if (rrsig->key->type != DNS_TYPE_RRSIG)
+                        continue;
+
+                r = dnssec_rrsig_match_dnskey(rrsig, dnskey, true);
                 if (r < 0)
                         return r;
                 if (r == 0)
                         continue;
 
-                /* Is this DNSKEY revoked? */
-                if ((dnskey->dnskey.flags & DNSKEY_FLAG_REVOKE) == 0)
-                        continue;
-
-                /* Could this be interesting to us at all? If not,
-                 * there's no point in looking for and verifying a
-                 * self-signed RRSIG. */
-                if (!dns_trust_anchor_knows_domain_positive(d, DNS_RESOURCE_KEY_NAME(dnskey->key)))
+                r = dnssec_verify_rrset(rrs, dnskey->key, rrsig, dnskey, USEC_INFINITY, &result);
+                if (r < 0)
+                        return r;
+                if (result != DNSSEC_VALIDATED)
                         continue;
 
-                /* Look for a self-signed RRSIG */
-                DNS_ANSWER_FOREACH(rrsig, rrs) {
+                /* Bingo! This is a revoked self-signed DNSKEY. Let's
+                 * see if this precise one exists in our trust anchor
+                 * database, too. */
+                r = dns_trust_anchor_check_revoked_one(d, dnskey);
+                if (r < 0)
+                        return r;
 
-                        if (rrsig->key->type != DNS_TYPE_RRSIG)
-                                continue;
+                return 1;
+        }
 
-                        r = dnssec_rrsig_match_dnskey(rrsig, dnskey, true);
-                        if (r < 0)
-                                return r;
-                        if (r == 0)
-                                continue;
+        return 0;
+}
 
-                        r = dnssec_verify_rrset(rrs, key, rrsig, dnskey, USEC_INFINITY, &result);
-                        if (r < 0)
-                                return r;
-                        if (result != DNSSEC_VALIDATED)
-                                continue;
+int dns_trust_anchor_is_revoked(DnsTrustAnchor *d, DnsResourceRecord *rr) {
+        assert(d);
 
-                        /* Bingo! Now, act! */
-                        r = dns_trust_anchor_check_revoked_one(d, dnskey);
-                        if (r < 0)
-                                return r;
-                }
-        }
+        if (!IN_SET(rr->key->type, DNS_TYPE_DS, DNS_TYPE_DNSKEY))
+                return 0;
 
-        return 0;
+        return set_contains(d->revoked_by_rr, rr);
 }
diff --git a/src/resolve/resolved-dns-trust-anchor.h b/src/resolve/resolved-dns-trust-anchor.h
index 303c4088d1..5d137faae1 100644
--- a/src/resolve/resolved-dns-trust-anchor.h
+++ b/src/resolve/resolved-dns-trust-anchor.h
@@ -32,6 +32,7 @@ typedef struct DnsTrustAnchor DnsTrustAnchor;
 struct DnsTrustAnchor {
         Hashmap *positive_by_key;
         Set *negative_by_name;
+        Set *revoked_by_rr;
 };
 
 int dns_trust_anchor_load(DnsTrustAnchor *d);
@@ -40,4 +41,5 @@ void dns_trust_anchor_flush(DnsTrustAnchor *d);
 int dns_trust_anchor_lookup_positive(DnsTrustAnchor *d, const DnsResourceKey* key, DnsAnswer **answer);
 int dns_trust_anchor_lookup_negative(DnsTrustAnchor *d, const char *name);
 
-int dns_trust_anchor_check_revoked(DnsTrustAnchor *d, DnsAnswer *rrs, const DnsResourceKey *key);
+int dns_trust_anchor_check_revoked(DnsTrustAnchor *d, DnsResourceRecord *dnskey, DnsAnswer *rrs);
+int dns_trust_anchor_is_revoked(DnsTrustAnchor *d, DnsResourceRecord *rr);
diff --git a/src/resolve/resolved-link.c b/src/resolve/resolved-link.c
index 30838ef8cc..928307e004 100644
--- a/src/resolve/resolved-link.c
+++ b/src/resolve/resolved-link.c
@@ -463,12 +463,8 @@ DnsServer* link_set_dns_server(Link *l, DnsServer *s) {
         if (l->current_dns_server == s)
                 return s;
 
-        if (s) {
-                _cleanup_free_ char *ip = NULL;
-
-                in_addr_to_string(s->family, &s->address, &ip);
-                log_info("Switching to DNS server %s for interface %s.", strna(ip), l->name);
-        }
+        if (s)
+                log_info("Switching to DNS server %s for interface %s.", dns_server_string(s), l->name);
 
         dns_server_unref(l->current_dns_server);
         l->current_dns_server = dns_server_ref(s);
diff --git a/src/resolve/resolved-llmnr.c b/src/resolve/resolved-llmnr.c
index dd4d9508ba..f52ab8f384 100644
--- a/src/resolve/resolved-llmnr.c
+++ b/src/resolve/resolved-llmnr.c
@@ -193,6 +193,8 @@ int manager_llmnr_ipv4_udp_fd(Manager *m) {
         if (r < 0)
                 goto fail;
 
+        (void) sd_event_source_set_description(m->llmnr_ipv4_udp_event_source, "llmnr-ipv4-udp");
+
         return m->llmnr_ipv4_udp_fd;
 
 fail:
@@ -267,10 +269,10 @@ int manager_llmnr_ipv6_udp_fd(Manager *m) {
         }
 
         r = sd_event_add_io(m->event, &m->llmnr_ipv6_udp_event_source, m->llmnr_ipv6_udp_fd, EPOLLIN, on_llmnr_packet, m);
-        if (r < 0)  {
-                r = -errno;
+        if (r < 0)
                 goto fail;
-        }
+
+        (void) sd_event_source_set_description(m->llmnr_ipv6_udp_event_source, "llmnr-ipv6-udp");
 
         return m->llmnr_ipv6_udp_fd;
 
@@ -393,6 +395,8 @@ int manager_llmnr_ipv4_tcp_fd(Manager *m) {
         if (r < 0)
                 goto fail;
 
+        (void) sd_event_source_set_description(m->llmnr_ipv4_tcp_event_source, "llmnr-ipv4-tcp");
+
         return m->llmnr_ipv4_tcp_fd;
 
 fail:
@@ -464,6 +468,8 @@ int manager_llmnr_ipv6_tcp_fd(Manager *m) {
         if (r < 0)
                 goto fail;
 
+        (void) sd_event_source_set_description(m->llmnr_ipv6_tcp_event_source, "llmnr-ipv6-tcp");
+
         return m->llmnr_ipv6_tcp_fd;
 
 fail:
diff --git a/src/resolve/resolved-manager.c b/src/resolve/resolved-manager.c
index b32bad456b..b17a19d331 100644
--- a/src/resolve/resolved-manager.c
+++ b/src/resolve/resolved-manager.c
@@ -313,6 +313,8 @@ static int manager_network_monitor_listen(Manager *m) {
         if (r < 0)
                 return r;
 
+        (void) sd_event_source_set_description(m->network_event_source, "network-monitor");
+
         return 0;
 }
 
@@ -420,6 +422,8 @@ static int manager_watch_hostname(Manager *m) {
                         return log_error_errno(r, "Failed to add hostname event source: %m");
         }
 
+        (void) sd_event_source_set_description(m->hostname_event_source, "hostname");
+
         r = determine_hostname(&m->llmnr_hostname, &m->mdns_hostname);
         if (r < 0) {
                 log_info("Defaulting to hostname 'linux'.");
diff --git a/src/resolve/resolved-resolv-conf.c b/src/resolve/resolved-resolv-conf.c
index 956f380f3c..7567f4c369 100644
--- a/src/resolve/resolved-resolv-conf.c
+++ b/src/resolve/resolved-resolv-conf.c
@@ -147,16 +147,14 @@ clear:
 }
 
 static void write_resolv_conf_server(DnsServer *s, FILE *f, unsigned *count) {
-        _cleanup_free_ char *t  = NULL;
-        int r;
-
         assert(s);
         assert(f);
         assert(count);
 
-        r = in_addr_to_string(s->family, &s->address, &t);
-        if (r < 0) {
-                log_warning_errno(r, "Invalid DNS address. Ignoring: %m");
+        (void) dns_server_string(s);
+
+        if (!s->server_string) {
+                log_warning("Our of memory, or invalid DNS address. Ignoring server.");
                 return;
         }
 
@@ -164,7 +162,7 @@ static void write_resolv_conf_server(DnsServer *s, FILE *f, unsigned *count) {
                 fputs("# Too many DNS servers configured, the following entries may be ignored.\n", f);
         (*count) ++;
 
-        fprintf(f, "nameserver %s\n", t);
+        fprintf(f, "nameserver %s\n", s->server_string);
 }
 
 static void write_resolv_conf_search(
diff --git a/src/shared/dns-domain.c b/src/shared/dns-domain.c
index 68404ca9e5..59475115ba 100644
--- a/src/shared/dns-domain.c
+++ b/src/shared/dns-domain.c
@@ -486,13 +486,15 @@ void dns_name_hash_func(const void *s, struct siphash *state) {
 
         assert(p);
 
-        while (*p) {
+        for (;;) {
                 char label[DNS_LABEL_MAX+1];
                 int k;
 
                 r = dns_label_unescape(&p, label, sizeof(label));
                 if (r < 0)
                         break;
+                if (r == 0)
+                        break;
 
                 k = dns_label_undo_idna(label, r, label, sizeof(label));
                 if (k < 0)
@@ -500,13 +502,9 @@ void dns_name_hash_func(const void *s, struct siphash *state) {
                 if (k > 0)
                         r = k;
 
-                if (r == 0)
-                        break;
-
-                label[r] = 0;
-                ascii_strlower(label);
-
-                string_hash_func(label, state);
+                ascii_strlower_n(label, r);
+                siphash24_compress(label, r, state);
+                siphash24_compress_byte(0, state); /* make sure foobar and foo.bar result in different hashes */
         }
 
         /* enforce that all names are terminated by the empty label */
@@ -913,19 +911,11 @@ int dns_name_to_wire_format(const char *domain, uint8_t *buffer, size_t len, boo
                 if (r < 0)
                         return r;
 
-                if (canonical) {
-                        size_t i;
-
-                        /* Optionally, output the name in DNSSEC
-                         * canonical format, as described in RFC 4034,
-                         * section 6.2. Or in other words: in
-                         * lower-case. */
-
-                        for (i = 0; i < (size_t) r; i++) {
-                                if (out[i] >= 'A' && out[i] <= 'Z')
-                                        out[i] = out[i] - 'A' + 'a';
-                        }
-                }
+                /* Optionally, output the name in DNSSEC canonical
+                 * format, as described in RFC 4034, section 6.2. Or
+                 * in other words: in lower-case. */
+                if (canonical)
+                        ascii_strlower_n((char*) out, (size_t) r);
 
                 /* Fill label length, move forward */
                 *label_length = r;