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

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

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

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

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

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

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

1 files changed, 202 insertions, 74 deletions

diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index ed126505ad..d1d2faca06 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -499,7 +499,7 @@ int dnssec_rrsig_match_dnskey(DnsResourceRecord *rrsig, DnsResourceRecord *dnske
         return dns_name_equal(DNS_RESOURCE_KEY_NAME(dnskey->key), rrsig->rrsig.signer);
 }
 
-int dnssec_key_match_rrsig(DnsResourceKey *key, DnsResourceRecord *rrsig) {
+int dnssec_key_match_rrsig(const DnsResourceKey *key, DnsResourceRecord *rrsig) {
         assert(key);
         assert(rrsig);
 
@@ -529,7 +529,7 @@ int dnssec_verify_rrset_search(
         assert(key);
         assert(result);
 
-        /* Verifies all RRs from "a" that match the key "key", against DNSKEY and DS RRs in "validated_dnskeys" */
+        /* Verifies all RRs from "a" that match the key "key" against DNSKEYs in "validated_dnskeys" */
 
         if (!a || a->n_rrs <= 0)
                 return -ENODATA;
@@ -537,6 +537,7 @@ int dnssec_verify_rrset_search(
         /* Iterate through each RRSIG RR. */
         DNS_ANSWER_FOREACH(rrsig, a) {
                 DnsResourceRecord *dnskey;
+                DnsAnswerFlags flags;
 
                 /* Is this an RRSIG RR that applies to RRs matching our key? */
                 r = dnssec_key_match_rrsig(key, rrsig);
@@ -548,9 +549,12 @@ int dnssec_verify_rrset_search(
                 found_rrsig = true;
 
                 /* Look for a matching key */
-                DNS_ANSWER_FOREACH(dnskey, validated_dnskeys) {
+                DNS_ANSWER_FOREACH_FLAGS(dnskey, flags, validated_dnskeys) {
                         DnssecResult one_result;
 
+                        if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                                continue;
+
                         /* Is this a DNSKEY RR that matches they key of our RRSIG? */
                         r = dnssec_rrsig_match_dnskey(rrsig, dnskey);
                         if (r < 0)
@@ -626,6 +630,23 @@ int dnssec_verify_rrset_search(
         return 0;
 }
 
+int dnssec_has_rrsig(DnsAnswer *a, const DnsResourceKey *key) {
+        DnsResourceRecord *rr;
+        int r;
+
+        /* Checks whether there's at least one RRSIG in 'a' that proctects RRs of the specified key */
+
+        DNS_ANSWER_FOREACH(rr, a) {
+                r = dnssec_key_match_rrsig(key, rr);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        return 1;
+        }
+
+        return 0;
+}
+
 int dnssec_canonicalize(const char *n, char *buffer, size_t buffer_max) {
         size_t c = 0;
         int r;
@@ -776,6 +797,7 @@ finish:
 
 int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_ds) {
         DnsResourceRecord *ds;
+        DnsAnswerFlags flags;
         int r;
 
         assert(dnskey);
@@ -783,7 +805,10 @@ int dnssec_verify_dnskey_search(DnsResourceRecord *dnskey, DnsAnswer *validated_
         if (dnskey->key->type != DNS_TYPE_DNSKEY)
                 return 0;
 
-        DNS_ANSWER_FOREACH(ds, validated_ds) {
+        DNS_ANSWER_FOREACH_FLAGS(ds, flags, validated_ds) {
+
+                if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                        continue;
 
                 if (ds->key->type != DNS_TYPE_DS)
                         continue;
@@ -866,114 +891,218 @@ finish:
         return r;
 }
 
-int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result) {
+static int dnssec_test_nsec3(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result) {
+        _cleanup_free_ char *next_closer_domain = NULL, *l = NULL;
+        uint8_t hashed[DNSSEC_HASH_SIZE_MAX];
+        const char *p, *pp = NULL;
         DnsResourceRecord *rr;
-        int r;
+        DnsAnswerFlags flags;
+        int hashed_size, r;
 
         assert(key);
         assert(result);
 
-        /* Look for any NSEC/NSEC3 RRs that say something about the specified key. */
-
-        DNS_ANSWER_FOREACH(rr, answer) {
+        /* First step, look for the closest encloser NSEC3 RR in 'answer' that matches 'key' */
+        p = DNS_RESOURCE_KEY_NAME(key);
+        for (;;) {
+                DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                        _cleanup_free_ char *hashed_domain = NULL, *label = NULL;
 
-                if (rr->key->class != key->class)
-                        continue;
+                        if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                                continue;
 
-                switch (rr->key->type) {
+                        if (rr->key->type != DNS_TYPE_NSEC3)
+                                continue;
 
-                case DNS_TYPE_NSEC:
+                        /* RFC  5155, Section 8.2 says we MUST ignore NSEC3 RRs with flags != 0 or 1 */
+                        if (!IN_SET(rr->nsec3.flags, 0, 1))
+                                continue;
 
-                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
+                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(rr->key), p);
                         if (r < 0)
                                 return r;
-                        if (r > 0) {
-                                *result = bitmap_isset(rr->nsec.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
+                        if (r == 0)
+                                continue;
+
+                        hashed_size = dnssec_nsec3_hash(rr, p, hashed);
+                        if (hashed_size == -EOPNOTSUPP) {
+                                *result = DNSSEC_NSEC_UNSUPPORTED_ALGORITHM;
                                 return 0;
                         }
+                        if (hashed_size < 0)
+                                return hashed_size;
+                        if (rr->nsec3.next_hashed_name_size != (size_t) hashed_size)
+                                return -EBADMSG;
 
-                        r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key), rr->nsec.next_domain_name);
+                        label = base32hexmem(hashed, hashed_size, false);
+                        if (!label)
+                                return -ENOMEM;
+
+                        hashed_domain = strjoin(label, ".", p, NULL);
+                        if (!hashed_domain)
+                                return -ENOMEM;
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), hashed_domain);
                         if (r < 0)
                                 return r;
-                        if (r > 0) {
-                                *result = DNSSEC_NSEC_NXDOMAIN;
-                                return 0;
-                        }
+                        if (r > 0)
+                                goto found;
+                }
+
+                /* We didn't find the closest encloser with this name,
+                 * but let's remember this domain name, it might be
+                 * the next closer name */
+
+                pp = p;
+
+                /* Strip one label from the front */
+                r = dns_name_parent(&p);
+                if (r < 0)
+                        return r;
+                if (r == 0)
                         break;
+        }
 
-                case DNS_TYPE_NSEC3: {
-                        _cleanup_free_ void *decoded = NULL;
-                        size_t decoded_size;
-                        char label[DNS_LABEL_MAX];
-                        uint8_t hashed[DNSSEC_HASH_SIZE_MAX];
-                        int label_length, c, q;
-                        const char *p;
-                        bool covered;
+        *result = DNSSEC_NSEC_NO_RR;
+        return 0;
 
-                        /* RFC  5155, Section 8.2 says we MUST ignore NSEC3 RRs with flags != 0 or 1 */
-                        if (!IN_SET(rr->nsec3.flags, 0, 1))
-                                continue;
+found:
+        /* We found a closest encloser in 'p'; next closer is 'pp' */
 
-                        p = DNS_RESOURCE_KEY_NAME(rr->key);
-                        label_length = dns_label_unescape(&p, label, sizeof(label));
-                        if (label_length < 0)
-                                return label_length;
-                        if (label_length == 0)
-                                continue;
+        /* Ensure this is not a DNAME domain, see RFC5155, section 8.3. */
+        if (bitmap_isset(rr->nsec3.types, DNS_TYPE_DNAME))
+                return -EBADMSG;
 
-                        r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(key), p);
-                        if (r < 0)
-                                return r;
-                        if (r == 0)
-                                continue;
+        /* Ensure that this data is from the delegated domain
+         * (i.e. originates from the "lower" DNS server), and isn't
+         * just glue records (i.e. doesn't originate from the "upper"
+         * DNS server). */
+        if (bitmap_isset(rr->nsec3.types, DNS_TYPE_NS) &&
+            !bitmap_isset(rr->nsec3.types, DNS_TYPE_SOA))
+                return -EBADMSG;
 
-                        r = unbase32hexmem(label, label_length, false, &decoded, &decoded_size);
-                        if (r == -EINVAL)
-                                continue;
-                        if (r < 0)
-                                return r;
+        if (!pp) {
+                /* No next closer NSEC3 RR. That means there's a direct NSEC3 RR for our key. */
+                *result = bitmap_isset(rr->nsec3.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
+                return 0;
+        }
 
-                        if (decoded_size != rr->nsec3.next_hashed_name_size)
-                                continue;
+        r = dnssec_nsec3_hash(rr, pp, hashed);
+        if (r < 0)
+                return r;
+        if (r != hashed_size)
+                return -EBADMSG;
 
-                        c = memcmp(decoded, rr->nsec3.next_hashed_name, decoded_size);
-                        if (c == 0)
-                                continue;
+        l = base32hexmem(hashed, hashed_size, false);
+        if (!l)
+                return -ENOMEM;
 
-                        r = dnssec_nsec3_hash(rr, DNS_RESOURCE_KEY_NAME(key), hashed);
-                        /* RFC 5155, Section 8.1 says we MUST ignore NSEC3 RRs with unknown algorithms */
-                        if (r == -EOPNOTSUPP)
-                                continue;
-                        if (r < 0)
-                                return r;
-                        if ((size_t) r != decoded_size)
-                                continue;
+        next_closer_domain = strjoin(l, ".", p, NULL);
+        if (!next_closer_domain)
+                return -ENOMEM;
 
-                        r = memcmp(decoded, hashed, decoded_size);
-                        if (r == 0) {
-                                *result = bitmap_isset(rr->nsec3.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
-                                return 0;
-                        }
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+                _cleanup_free_ char *label = NULL, *next_hashed_domain = NULL;
+                const char *nsec3_parent;
+
+                if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                        continue;
 
-                        q = memcmp(hashed, rr->nsec3.next_hashed_name, decoded_size);
+                if (rr->key->type != DNS_TYPE_NSEC3)
+                        continue;
 
-                        covered = c < 0 ?
-                                r < 0 && q < 0 :
-                                q < 0 || r < 0;
+                /* RFC  5155, Section 8.2 says we MUST ignore NSEC3 RRs with flags != 0 or 1 */
+                if (!IN_SET(rr->nsec3.flags, 0, 1))
+                        continue;
 
-                        if (covered) {
+                nsec3_parent = DNS_RESOURCE_KEY_NAME(rr->key);
+                r = dns_name_parent(&nsec3_parent);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                r = dns_name_equal(p, nsec3_parent);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                label = base32hexmem(rr->nsec3.next_hashed_name, rr->nsec3.next_hashed_name_size, false);
+                if (!label)
+                        return -ENOMEM;
+
+                next_hashed_domain = strjoin(label, ".", p, NULL);
+                if (!next_hashed_domain)
+                        return -ENOMEM;
+
+                r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), next_closer_domain, next_hashed_domain);
+                if (r < 0)
+                        return r;
+                if (r > 0) {
+                        if (rr->nsec3.flags & 1)
+                                *result = DNSSEC_NSEC_OPTOUT;
+                        else
                                 *result = DNSSEC_NSEC_NXDOMAIN;
+
+                        return 1;
+                }
+        }
+
+        *result = DNSSEC_NSEC_NO_RR;
+        return 0;
+}
+
+int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *result) {
+        DnsResourceRecord *rr;
+        bool have_nsec3 = false;
+        DnsAnswerFlags flags;
+        int r;
+
+        assert(key);
+        assert(result);
+
+        /* Look for any NSEC/NSEC3 RRs that say something about the specified key. */
+
+        DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
+
+                if (rr->key->class != key->class)
+                        continue;
+
+                if ((flags & DNS_ANSWER_AUTHENTICATED) == 0)
+                        continue;
+
+                switch (rr->key->type) {
+
+                case DNS_TYPE_NSEC:
+
+                        r = dns_name_equal(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key));
+                        if (r < 0)
+                                return r;
+                        if (r > 0) {
+                                *result = bitmap_isset(rr->nsec.types, key->type) ? DNSSEC_NSEC_FOUND : DNSSEC_NSEC_NODATA;
                                 return 0;
                         }
 
+                        r = dns_name_between(DNS_RESOURCE_KEY_NAME(rr->key), DNS_RESOURCE_KEY_NAME(key), rr->nsec.next_domain_name);
+                        if (r < 0)
+                                return r;
+                        if (r > 0) {
+                                *result = DNSSEC_NSEC_NXDOMAIN;
+                                return 0;
+                        }
                         break;
-                }
 
-                default:
+                case DNS_TYPE_NSEC3:
+                        have_nsec3 = true;
                         break;
                 }
         }
 
+        /* OK, this was not sufficient. Let's see if NSEC3 can help. */
+        if (have_nsec3)
+                return dnssec_test_nsec3(answer, key, result);
+
         /* No approproate NSEC RR found, report this. */
         *result = DNSSEC_NSEC_NO_RR;
         return 0;
@@ -981,7 +1110,6 @@ int dnssec_test_nsec(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *r
 
 static const char* const dnssec_mode_table[_DNSSEC_MODE_MAX] = {
         [DNSSEC_NO] = "no",
-        [DNSSEC_TRUST] = "trust",
         [DNSSEC_YES] = "yes",
 };
 DEFINE_STRING_TABLE_LOOKUP(dnssec_mode, DnssecMode);