resolved: implement the full NSEC and NSEC3 postive wildcard proofs

5 files changed, 186 insertions, 17 deletions

diff --git a/src/resolve/resolved-dns-answer.c b/src/resolve/resolved-dns-answer.c
index b50558e280..c359432a7a 100644
--- a/src/resolve/resolved-dns-answer.c
+++ b/src/resolve/resolved-dns-answer.c
@@ -320,6 +320,33 @@ int dns_answer_contains_nsec_or_nsec3(DnsAnswer *a) {
         return false;
 }
 
+int dns_answer_contains_zone_nsec3(DnsAnswer *answer, const char *zone) {
+        DnsResourceRecord *rr;
+        int r;
+
+        /* Checks whether the specified answer contains at least one NSEC3 RR in the specified zone */
+
+        DNS_ANSWER_FOREACH(rr, answer) {
+                const char *p;
+
+                if (rr->key->type != DNS_TYPE_NSEC3)
+                        continue;
+
+                p = DNS_RESOURCE_KEY_NAME(rr->key);
+                r = dns_name_parent(&p);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        continue;
+
+                r = dns_name_equal(p, zone);
+                if (r != 0)
+                        return r;
+        }
+
+        return false;
+}
+
 int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret, DnsAnswerFlags *flags) {
         DnsResourceRecord *rr, *soa = NULL;
         DnsAnswerFlags rr_flags, soa_flags = 0;
diff --git a/src/resolve/resolved-dns-answer.h b/src/resolve/resolved-dns-answer.h
index 715e487d94..3eff21f8d0 100644
--- a/src/resolve/resolved-dns-answer.h
+++ b/src/resolve/resolved-dns-answer.h
@@ -64,6 +64,7 @@ int dns_answer_match_key(DnsAnswer *a, const DnsResourceKey *key, DnsAnswerFlags
 int dns_answer_contains_rr(DnsAnswer *a, DnsResourceRecord *rr, DnsAnswerFlags *combined_flags);
 int dns_answer_contains_key(DnsAnswer *a, const DnsResourceKey *key, DnsAnswerFlags *combined_flags);
 int dns_answer_contains_nsec_or_nsec3(DnsAnswer *a);
+int dns_answer_contains_zone_nsec3(DnsAnswer *answer, const char *zone);
 
 int dns_answer_find_soa(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret, DnsAnswerFlags *flags);
 int dns_answer_find_cname_or_dname(DnsAnswer *a, const DnsResourceKey *key, DnsResourceRecord **ret, DnsAnswerFlags *flags);
diff --git a/src/resolve/resolved-dns-dnssec.c b/src/resolve/resolved-dns-dnssec.c
index 6f0f8f837e..afff979b5a 100644
--- a/src/resolve/resolved-dns-dnssec.c
+++ b/src/resolve/resolved-dns-dnssec.c
@@ -1604,7 +1604,7 @@ int dnssec_nsec_test(DnsAnswer *answer, DnsResourceKey *key, DnssecNsecResult *r
         return 0;
 }
 
-int dnssec_nsec_test_between(DnsAnswer *answer, const char *name, const char *zone, bool *authenticated) {
+int dnssec_nsec_test_enclosed(DnsAnswer *answer, uint16_t type, const char *name, const char *zone, bool *authenticated) {
         DnsResourceRecord *rr;
         DnsAnswerFlags flags;
         int r;
@@ -1618,6 +1618,9 @@ int dnssec_nsec_test_between(DnsAnswer *answer, const char *name, const char *zo
         DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
                 bool found = false;
 
+                if (rr->key->type != type && type != DNS_TYPE_ANY)
+                        continue;
+
                 r = dns_name_endswith(DNS_RESOURCE_KEY_NAME(rr->key), zone);
                 if (r < 0)
                         return r;
@@ -1685,6 +1688,145 @@ int dnssec_nsec_test_between(DnsAnswer *answer, const char *name, const char *zo
         return 0;
 }
 
+static int dnssec_test_positive_wildcard_nsec3(
+                DnsAnswer *answer,
+                const char *name,
+                const char *source,
+                const char *zone,
+                bool *authenticated) {
+
+        const char *next_closer = NULL;
+        int r;
+
+        /* Run a positive NSEC3 wildcard proof. Specifically:
+         *
+         * A proof that the the "next closer" of the generating wildcard does not exist.
+         *
+         * Note a key difference between the NSEC3 and NSEC versions of the proof. NSEC RRs don't have to exist for
+         * empty non-transients. NSEC3 RRs however have to. This means it's sufficient to check if the next closer name
+         * exists for the NSEC3 RR and we are done.
+         *
+         * To prove that a.b.c.d.e.f is rightfully synthesized from a wildcard *.d.e.f all we have to check is that
+         * c.d.e.f does not exist. */
+
+        for (;;) {
+                next_closer = name;
+                r = dns_name_parent(&name);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        return 0;
+
+                r = dns_name_equal(name, source);
+                if (r < 0)
+                        return r;
+                if (r > 0)
+                        break;
+        }
+
+        return dnssec_nsec_test_enclosed(answer, DNS_TYPE_NSEC3, next_closer, zone, authenticated);
+}
+
+static int dnssec_test_positive_wildcard_nsec(
+                DnsAnswer *answer,
+                const char *name,
+                const char *source,
+                const char *zone,
+                bool *_authenticated) {
+
+        bool authenticated = true;
+        int r;
+
+        /* Run a positive NSEC wildcard proof. Specifically:
+         *
+         * A proof that there's neither a wildcard name nor a non-wildcard name that is a suffix of the name "name" and
+         * a prefix of the synthesizing source "source" in the zone "zone".
+         *
+         * See RFC 5155, Section 8.8 and RFC 4035, Section 5.3.4
+         *
+         * Note that if we want to prove that a.b.c.d.e.f is rightfully synthesized from a wildcard *.d.e.f, then we
+         * have to prove that none of the following exist:
+         *
+         *      1) a.b.c.d.e.f
+         *      2) *.b.c.d.e.f
+         *      3)   b.c.d.e.f
+         *      4)   *.c.d.e.f
+         *      5)     c.d.e.f
+         *
+         */
+
+        for (;;) {
+                _cleanup_free_ char *wc = NULL;
+                bool a = false;
+
+                /* Check if there's an NSEC or NSEC3 RR that proves that the mame we determined is really non-existing,
+                 * i.e between the owner name and the next name of an NSEC RR. */
+                r = dnssec_nsec_test_enclosed(answer, DNS_TYPE_NSEC, name, zone, &a);
+                if (r <= 0)
+                        return r;
+
+                authenticated = authenticated && a;
+
+                /* Strip one label off */
+                r = dns_name_parent(&name);
+                if (r <= 0)
+                        return r;
+
+                /* Did we reach the source of synthesis? */
+                r = dns_name_equal(name, source);
+                if (r < 0)
+                        return r;
+                if (r > 0) {
+                        /* Successful exit */
+                        *_authenticated = authenticated;
+                        return 1;
+                }
+
+                /* Safety check, that the source of synthesis is still our suffix */
+                r = dns_name_endswith(name, source);
+                if (r < 0)
+                        return r;
+                if (r == 0)
+                        return -EBADMSG;
+
+                /* Replace the label we stripped off with an asterisk */
+                wc = strappend("*.", name);
+                if (!wc)
+                        return -ENOMEM;
+
+                /* And check if the proof holds for the asterisk name, too */
+                r = dnssec_nsec_test_enclosed(answer, DNS_TYPE_NSEC, wc, zone, &a);
+                if (r <= 0)
+                        return r;
+
+                authenticated = authenticated && a;
+                /* In the next iteration we'll check the non-asterisk-prefixed version */
+        }
+}
+
+int dnssec_test_positive_wildcard(
+                DnsAnswer *answer,
+                const char *name,
+                const char *source,
+                const char *zone,
+                bool *authenticated) {
+
+        int r;
+
+        assert(name);
+        assert(source);
+        assert(zone);
+        assert(authenticated);
+
+        r = dns_answer_contains_zone_nsec3(answer, zone);
+        if (r < 0)
+                return r;
+        if (r > 0)
+                return dnssec_test_positive_wildcard_nsec3(answer, name, source, zone, authenticated);
+        else
+                return dnssec_test_positive_wildcard_nsec(answer, name, source, zone, authenticated);
+}
+
 static const char* const dnssec_result_table[_DNSSEC_RESULT_MAX] = {
         [DNSSEC_VALIDATED] = "validated",
         [DNSSEC_VALIDATED_WILDCARD] = "validated-wildcard",
diff --git a/src/resolve/resolved-dns-dnssec.h b/src/resolve/resolved-dns-dnssec.h
index 8a9bcf5b91..b9d32db120 100644
--- a/src/resolve/resolved-dns-dnssec.h
+++ b/src/resolve/resolved-dns-dnssec.h
@@ -83,7 +83,10 @@ typedef enum DnssecNsecResult {
 } DnssecNsecResult;
 
 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);
+
+int dnssec_nsec_test_enclosed(DnsAnswer *answer, uint16_t type, const char *name, const char *zone, bool *authenticated);
+
+int dnssec_test_positive_wildcard(DnsAnswer *a, const char *name, const char *source, 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 9ee10f21c8..c7d2d82ecf 100644
--- a/src/resolve/resolved-dns-transaction.c
+++ b/src/resolve/resolved-dns-transaction.c
@@ -2531,28 +2531,24 @@ int dns_transaction_validate_dnssec(DnsTransaction *t) {
 
                         if (result == DNSSEC_VALIDATED_WILDCARD) {
                                 bool authenticated = false;
-                                const char *suffix;
+                                const char *source;
 
-                                /* 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*/
+                                /* This RRset validated, but as a wildcard. This means we need to prove via NSEC/NSEC3
+                                 * that no matching non-wildcard RR exists.*/
 
-                                r = dns_name_suffix(DNS_RESOURCE_KEY_NAME(rr->key), rrsig->rrsig.labels, &suffix);
+                                /* First step, determine the source of synthesis */
+                                r = dns_name_suffix(DNS_RESOURCE_KEY_NAME(rr->key), rrsig->rrsig.labels, &source);
                                 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;
+                                r = dnssec_test_positive_wildcard(
+                                                validated,
+                                                DNS_RESOURCE_KEY_NAME(rr->key),
+                                                source,
+                                                rrsig->rrsig.signer,
+                                                &authenticated);
 
                                 /* Unless the NSEC proof showed that the key really doesn't exist something is off. */
                                 if (r == 0)