resolved: properly look for NSEC/NSEC3 RRs when getting a positive wildcard response

This implements RFC 5155, Section 8.8 and RFC 4035, Section 5.3.4:

When we receive a response with an RRset generated from a wildcard we
need to look for one NSEC/NSEC3 RR that proves that there's no explicit RR
around before we accept the wildcard RRset as response.

This patch does a couple of things: the validation calls will now
identify wildcard signatures for us, and let us know the RRSIG used (so
that the RRSIG's signer field let's us know what the wildcard was that
generate the entry). Moreover, when iterating trough the RRsets of a
response we now employ three phases instead of just two.

a) in the first phase we only look for DNSKEYs RRs
b) in the second phase we only look for NSEC RRs
c) in the third phase we look for all kinds of RRs

Phase a) is necessary, since DNSKEYs "unlock" more signatures for us,
hence we shouldn't assume a key is missing until all DNSKEY RRs have
been processed.

Phase b) is necessary since NSECs need to be validated before we can
validate wildcard RRs due to the logic explained above.

Phase c) validates everything else. This phase also handles RRsets that
cannot be fully validated and removes them or lets the transaction fail.

3 files changed, 201 insertions, 27 deletions

diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index 9930b56619..43fcbe1460 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -512,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);
@@ -599,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)
@@ -651,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:
@@ -748,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;
@@ -808,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:
@@ -859,6 +872,9 @@ int dnssec_verify_rrset_search(
         else
                 *result = DNSSEC_NO_SIGNATURE;
 
+        if (ret_rrsig)
+                *ret_rrsig = NULL;
+
         return 0;
 }
 
@@ -1501,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;
@@ -1570,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-transaction.c b/src/resolve/resolved-dns-transaction.c
index 23378ce4f1..9a79a8e90d 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -2282,7 +2282,11 @@ static int dns_transaction_invalidate_revoked_keys(DnsTransaction *t) {
 
 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;
@@ -2340,16 +2344,44 @@ int dns_transaction_validate_dnssec(DnsTransaction *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;
 
@@ -2393,13 +2425,52 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                                 break;
                         }
 
-                        /* If we haven't read all DNSKEYs yet a
-                         * negative result of the validation is
-                         * irrelevant, as there might be more DNSKEYs
-                         * coming. */
-                        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 (result == DNSSEC_VALIDATED_WILDCARD) {
+                                bool authenticated = false;
+                                const char *suffix;
+
+                                /* 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*/
+
+                                r = dns_name_suffix(DNS_RESOURCE_KEY_NAME(rr->key), rrsig->rrsig.labels, &suffix);
+                                if (r < 0)
+                                        return r;
+                                if (r == 0)
+                                        return -EBADMSG;
+
+                                r = dns_name_parent(&suffix);
+                                if (r < 0)
+                                        return r;
+                                if (r == 0)
+                                        return -EBADMSG;
+
+                                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 || !authenticated)
+                                        result = DNSSEC_INVALID;
+
+                                r = dns_answer_move_by_key(&validated, &t->answer, rr->key, DNS_ANSWER_AUTHENTICATED|DNS_ANSWER_CACHEABLE);
+                                if (r < 0)
+                                        return r;
+
+                                t->scope->manager->n_dnssec_secure++;
+
+                                /* Exit the loop, we dropped something from the answer, start from the beginning */
+                                changed = true;
+                                break;
+                        }
+
                         if (result == DNSSEC_NO_SIGNATURE) {
                                 r = dns_transaction_requires_rrsig(t, rr);
                                 if (r < 0)
@@ -2519,17 +2590,20 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
                         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;
                 }
 
@@ -2565,7 +2639,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;