summaryrefslogtreecommitdiffstats
path: root/lib/cache/nsec1.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:26:00 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 15:26:00 +0000
commit830407e88f9d40d954356c3754f2647f91d5c06a (patch)
treed6a0ece6feea91f3c656166dbaa884ef8a29740e /lib/cache/nsec1.c
parentInitial commit. (diff)
downloadknot-resolver-830407e88f9d40d954356c3754f2647f91d5c06a.tar.xz
knot-resolver-830407e88f9d40d954356c3754f2647f91d5c06a.zip
Adding upstream version 5.6.0.upstream/5.6.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'lib/cache/nsec1.c')
-rw-r--r--lib/cache/nsec1.c488
1 files changed, 488 insertions, 0 deletions
diff --git a/lib/cache/nsec1.c b/lib/cache/nsec1.c
new file mode 100644
index 0000000..4554303
--- /dev/null
+++ b/lib/cache/nsec1.c
@@ -0,0 +1,488 @@
+/* Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ * SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+/** @file
+ * Implementation of NSEC (1) handling. Prototypes in ./impl.h
+ */
+
+#include "lib/cache/impl.h"
+#include "lib/dnssec/nsec.h"
+#include "lib/layer/iterate.h"
+
+
+/** Reconstruct a name into a buffer (assuming length at least KNOT_DNAME_MAXLEN).
+ * \return kr_ok() or error code (<0). */
+static int dname_wire_reconstruct(knot_dname_t *buf, const struct key *k,
+ knot_db_val_t kwz)
+{
+ /* Reconstruct from key: first the ending, then zone name. */
+ int ret = knot_dname_lf2wire(buf, kwz.len, kwz.data);
+ if (kr_fails_assert(ret >= 0)) {
+ VERBOSE_MSG(NULL, "=> NSEC: LF2wire ret = %d\n", ret);
+ return ret;
+ }
+ /* The last written byte is the zero label for root -> overwrite. */
+ knot_dname_t *zone_start = buf + ret - 1;
+ if (kr_fails_assert(*zone_start == '\0'))
+ return kr_error(EFAULT);
+ ret = knot_dname_to_wire(zone_start, k->zname, KNOT_DNAME_MAXLEN - kwz.len);
+ if (kr_fails_assert(ret == k->zlf_len + 1))
+ return ret < 0 ? ret : kr_error(EILSEQ);
+ return kr_ok();
+}
+
+
+knot_db_val_t key_NSEC1(struct key *k, const knot_dname_t *name, bool add_wildcard)
+{
+ /* we basically need dname_lf with two bytes added
+ * on a correct place within the name (the cut) */
+ int ret;
+ const bool ok = k && name
+ && !(ret = kr_dname_lf(k->buf, name, add_wildcard));
+ if (kr_fails_assert(ok))
+ return (knot_db_val_t){ NULL, 0 };
+
+ uint8_t *begin = k->buf + 1 + k->zlf_len; /* one byte after zone's zero */
+ uint8_t *end = k->buf + 1 + k->buf[0]; /* we don't use the final zero in key,
+ * but move it anyway */
+ if (kr_fails_assert(end >= begin))
+ return (knot_db_val_t){ NULL, 0 };
+ int key_len;
+ if (end > begin) {
+ memmove(begin + 2, begin, end - begin);
+ key_len = k->buf[0] + 1;
+ } else {
+ key_len = k->buf[0] + 2;
+ }
+ /* CACHE_KEY_DEF: key == zone's dname_lf + '\0' + '1' + dname_lf
+ * of the name within the zone without the final 0. Iff the latter is empty,
+ * there's no zero to cut and thus the key_len difference.
+ */
+ begin[0] = 0;
+ begin[1] = '1'; /* tag for NSEC1 */
+ k->type = KNOT_RRTYPE_NSEC;
+
+ /*
+ VERBOSE_MSG(NULL, "<> key_NSEC1; name: ");
+ kr_dname_print(name, add_wildcard ? "*." : "" , " ");
+ kr_log_debug(CACHE, "(zone name LF length: %d; total key length: %d)\n",
+ k->zlf_len, key_len);
+ */
+
+ return (knot_db_val_t){ k->buf + 1, key_len };
+}
+
+
+/** Assuming that k1 < k4, find where k2 is. (Considers DNS wrap-around.)
+ *
+ * \return Intuition: position of k2 among kX.
+ * 0: k2 < k1; 1: k1 == k2; 2: k1 is a prefix of k2 < k4;
+ * 3: k1 < k2 < k4 (and not 2); 4: k2 == k4; 5: k2 > k4
+ * \note k1.data may be NULL, meaning assumption that k1 < k2 and not a prefix
+ * (i.e. return code will be > 2)
+ */
+static int kwz_between(knot_db_val_t k1, knot_db_val_t k2, knot_db_val_t k4)
+{
+ kr_require(k2.data && k4.data);
+ /* CACHE_KEY_DEF; we need to beware of one key being a prefix of another */
+ int ret_maybe; /**< result, assuming we confirm k2 < k4 */
+ if (k1.data) {
+ const int cmp12 = memcmp(k1.data, k2.data, MIN(k1.len, k2.len));
+ if (cmp12 == 0 && k1.len == k2.len) /* iff k1 == k2 */
+ return 1;
+ if (cmp12 > 0 || (cmp12 == 0 && k1.len > k2.len)) /* iff k1 > k2 */
+ return 0;
+ ret_maybe = cmp12 == 0 ? 2 : 3;
+ } else {
+ ret_maybe = 3;
+ }
+ if (k4.len == 0) { /* wrap-around */
+ return k2.len > 0 ? ret_maybe : 4;
+ } else {
+ const int cmp24 = memcmp(k2.data, k4.data, MIN(k2.len, k4.len));
+ if (cmp24 == 0 && k2.len == k4.len) /* iff k2 == k4 */
+ return 4;
+ if (cmp24 > 0 || (cmp24 == 0 && k2.len > k4.len)) /* iff k2 > k4 */
+ return 5;
+ return ret_maybe;
+ }
+}
+
+
+/** NSEC1 range search.
+ *
+ * \param key Pass output of key_NSEC1(k, ...)
+ * \param value[out] The raw data of the NSEC cache record (optional; consistency checked).
+ * \param exact_match[out] Whether the key was matched exactly or just covered (optional).
+ * \param kwz_low[out] Output the low end of covering NSEC, pointing within DB (optional).
+ * \param kwz_high[in,out] Storage for the high end of covering NSEC (optional).
+ * It's only set if !exact_match.
+ * \param new_ttl[out] New TTL of the NSEC (optional).
+ * \return Error message or NULL.
+ * \note The function itself does *no* bitmap checks, e.g. RFC 6840 sec. 4.
+ */
+static const char * find_leq_NSEC1(struct kr_cache *cache, const struct kr_query *qry,
+ const knot_db_val_t key, const struct key *k, knot_db_val_t *value,
+ bool *exact_match, knot_db_val_t *kwz_low, knot_db_val_t *kwz_high,
+ uint32_t *new_ttl)
+{
+ /* Do the cache operation. */
+ const size_t nwz_off = key_nwz_off(k);
+ if (kr_fails_assert(key.data && key.len >= nwz_off))
+ return "range search ERROR";
+ knot_db_val_t key_nsec = key;
+ knot_db_val_t val = { NULL, 0 };
+ int ret = cache_op(cache, read_leq, &key_nsec, &val);
+ if (ret < 0) {
+ if (kr_fails_assert(ret == kr_error(ENOENT))) {
+ return "range search ERROR";
+ } else {
+ return "range search miss";
+ }
+ }
+ if (value) {
+ *value = val;
+ }
+ /* Check consistency, TTL, rank. */
+ const bool is_exact = (ret == 0);
+ if (exact_match) {
+ *exact_match = is_exact;
+ }
+ const struct entry_h *eh = entry_h_consistent_NSEC(val);
+ if (!eh) {
+ /* This might be just finding something else than NSEC1 entry,
+ * in case we searched before the very first one in the zone. */
+ return "range search found inconsistent entry";
+ }
+ /* Passing just zone name instead of owner, as we don't
+ * have it reconstructed at this point. */
+ int32_t new_ttl_ = get_new_ttl(eh, qry, k->zname, KNOT_RRTYPE_NSEC,
+ qry->timestamp.tv_sec);
+ if (new_ttl_ < 0 || !kr_rank_test(eh->rank, KR_RANK_SECURE)) {
+ return "range search found stale or insecure entry";
+ /* TODO: remove the stale record *and* retry,
+ * in case we haven't run off. Perhaps start by in_zone check. */
+ }
+ if (new_ttl) {
+ *new_ttl = new_ttl_;
+ }
+ if (kwz_low) {
+ *kwz_low = (knot_db_val_t){
+ .data = (uint8_t *)key_nsec.data + nwz_off,
+ .len = key_nsec.len - nwz_off,
+ }; /* CACHE_KEY_DEF */
+ }
+ if (is_exact) {
+ /* Nothing else to do. */
+ return NULL;
+ }
+ /* The NSEC starts strictly before our target name;
+ * now check that it still belongs into that zone. */
+ const bool nsec_in_zone = key_nsec.len >= nwz_off
+ /* CACHE_KEY_DEF */
+ && memcmp(key.data, key_nsec.data, nwz_off) == 0;
+ if (!nsec_in_zone) {
+ return "range search miss (!nsec_in_zone)";
+ }
+ /* We know it starts before sname, so let's check the other end.
+ * 1. construct the key for the next name - kwz_hi. */
+ /* it's *full* name ATM */
+ /* Technical complication: memcpy is safe for unaligned case (on non-x86) */
+ __typeof__(((knot_rdata_t *)NULL)->len) next_len;
+ const uint8_t *next_data;
+ { /* next points to knot_rdata_t but possibly unaligned */
+ const uint8_t *next = eh->data + KR_CACHE_RR_COUNT_SIZE;
+ memcpy(&next_len, next + offsetof(knot_rdata_t, len), sizeof(next_len));
+ next_data = next + offsetof(knot_rdata_t, data);
+ }
+ if (kr_fails_assert(KR_CACHE_RR_COUNT_SIZE == 2 && get_uint16(eh->data) != 0)) {
+ return "ERROR"; /* TODO: more checks? */
+ }
+ /*
+ WITH_VERBOSE {
+ VERBOSE_MSG(qry, "=> NSEC: next name: ");
+ kr_dname_print(next, "", "\n");
+ }
+ */
+ knot_dname_t ch_buf[KNOT_DNAME_MAXLEN];
+ knot_dname_t *chs = kwz_high ? kwz_high->data : ch_buf;
+ if (kr_fails_assert(chs))
+ return "EINVAL";
+
+ {
+ /* Lower-case chs; see also RFC 6840 5.1.
+ * LATER(optim.): we do lots of copying etc. */
+ knot_dname_t lower_buf[KNOT_DNAME_MAXLEN];
+ ret = knot_dname_to_wire(lower_buf, next_data,
+ MIN(next_len, KNOT_DNAME_MAXLEN));
+ if (ret < 0) { /* _ESPACE */
+ return "range search found record with incorrect contents";
+ }
+ knot_dname_to_lower(lower_buf);
+ ret = kr_dname_lf(chs, lower_buf, false);
+ }
+
+ if (kr_fails_assert(ret == 0))
+ return "ERROR";
+ knot_db_val_t kwz_hi = { /* skip the zone name */
+ .data = chs + 1 + k->zlf_len,
+ .len = chs[0] - k->zlf_len,
+ };
+ if (kr_fails_assert((ssize_t)(kwz_hi.len) >= 0))
+ return "ERROR";
+ /* 2. do the actual range check. */
+ const knot_db_val_t kwz_sname = {
+ .data = (void *)/*const-cast*/(k->buf + 1 + nwz_off),
+ .len = k->buf[0] - k->zlf_len,
+ };
+ if (kr_fails_assert((ssize_t)(kwz_sname.len) >= 0))
+ return "ERROR";
+ bool covers = /* we know for sure that the low end is before kwz_sname */
+ 3 == kwz_between((knot_db_val_t){ NULL, 0 }, kwz_sname, kwz_hi);
+ if (!covers) {
+ return "range search miss (!covers)";
+ }
+ if (kwz_high) {
+ *kwz_high = kwz_hi;
+ }
+ return NULL;
+}
+
+
+int nsec1_encloser(struct key *k, struct answer *ans,
+ const int sname_labels, int *clencl_labels,
+ knot_db_val_t *cover_low_kwz, knot_db_val_t *cover_hi_kwz,
+ const struct kr_query *qry, struct kr_cache *cache)
+{
+ static const int ESKIP = ABS(ENOENT);
+ /* Basic sanity check. */
+ const bool ok = k && ans && clencl_labels && cover_low_kwz && cover_hi_kwz
+ && qry && cache;
+ if (kr_fails_assert(ok))
+ return kr_error(EINVAL);
+
+ /* Find a previous-or-equal name+NSEC in cache covering the QNAME,
+ * checking TTL etc. */
+ knot_db_val_t key = key_NSEC1(k, qry->sname, false);
+ knot_db_val_t val = { NULL, 0 };
+ bool exact_match;
+ uint32_t new_ttl;
+ const char *err = find_leq_NSEC1(cache, qry, key, k, &val,
+ &exact_match, cover_low_kwz, cover_hi_kwz, &new_ttl);
+ if (err) {
+ VERBOSE_MSG(qry, "=> NSEC sname: %s\n", err);
+ return ESKIP;
+ }
+
+ /* Get owner name of the record. */
+ const knot_dname_t *owner;
+ knot_dname_t owner_buf[KNOT_DNAME_MAXLEN];
+ if (exact_match) {
+ owner = qry->sname;
+ } else {
+ int ret = dname_wire_reconstruct(owner_buf, k, *cover_low_kwz);
+ if (unlikely(ret)) return ESKIP;
+ owner = owner_buf;
+ }
+ /* Basic checks OK -> materialize data. */
+ {
+ const struct entry_h *nsec_eh = val.data;
+ int ret = entry2answer(ans, AR_NSEC, nsec_eh, knot_db_val_bound(val),
+ owner, KNOT_RRTYPE_NSEC, new_ttl);
+ if (ret) return kr_error(ret);
+ }
+
+ /* Final checks, split for matching vs. covering our sname. */
+ const knot_rrset_t *nsec_rr = ans->rrsets[AR_NSEC].set.rr;
+ const uint8_t *bm = knot_nsec_bitmap(nsec_rr->rrs.rdata);
+ uint16_t bm_size = knot_nsec_bitmap_len(nsec_rr->rrs.rdata);
+ if (kr_fails_assert(bm))
+ return kr_error(EFAULT);
+
+ if (exact_match) {
+ if (kr_nsec_bitmap_nodata_check(bm, bm_size, qry->stype, nsec_rr->owner) != 0) {
+ VERBOSE_MSG(qry,
+ "=> NSEC sname: match but failed type check\n");
+ return ESKIP;
+ }
+ /* NODATA proven; just need to add SOA+RRSIG later */
+ VERBOSE_MSG(qry, "=> NSEC sname: match proved NODATA, new TTL %d\n",
+ new_ttl);
+ ans->rcode = PKT_NODATA;
+ return kr_ok();
+ } /* else */
+
+ /* Inexact match. First check if sname is delegated by that NSEC. */
+ const int nsec_matched = knot_dname_matched_labels(nsec_rr->owner, qry->sname);
+ const bool is_sub = nsec_matched == knot_dname_labels(nsec_rr->owner, NULL);
+ if (is_sub && kr_nsec_children_in_zone_check(bm, bm_size) != 0) {
+ VERBOSE_MSG(qry, "=> NSEC sname: covered but delegated (or error)\n");
+ return ESKIP;
+ }
+ /* NXDOMAIN proven *except* for wildcards. */
+ WITH_VERBOSE(qry) {
+ auto_free char *owner_str = kr_dname_text(nsec_rr->owner),
+ *next_str = kr_dname_text(knot_nsec_next(nsec_rr->rrs.rdata));
+ VERBOSE_MSG(qry, "=> NSEC sname: covered by: %s -> %s, new TTL %d\n",
+ owner_str, next_str, new_ttl);
+ }
+
+ /* Find label count of the closest encloser.
+ * Both endpoints in an NSEC do exist (though possibly in a child zone)
+ * and any prefixes of those names as well (empty non-terminals),
+ * but nothing else exists inside this "triangle".
+ *
+ * Note that we have to lower-case the next name for comparison,
+ * even though we have canonicalized NSEC already; see RFC 6840 5.1.
+ * LATER(optim.): it might be faster to use the LFs we already have.
+ */
+ knot_dname_t next[KNOT_DNAME_MAXLEN];
+ int ret = knot_dname_to_wire(next, knot_nsec_next(nsec_rr->rrs.rdata), sizeof(next));
+ if (kr_fails_assert(ret >= 0))
+ return kr_error(ret);
+ knot_dname_to_lower(next);
+ *clencl_labels = MAX(
+ nsec_matched,
+ knot_dname_matched_labels(qry->sname, next)
+ );
+
+ /* Empty non-terminals don't need to have
+ * a matching NSEC record. */
+ if (sname_labels == *clencl_labels) {
+ ans->rcode = PKT_NODATA;
+ VERBOSE_MSG(qry,
+ "=> NSEC sname: empty non-terminal by the same RR\n");
+ } else {
+ ans->rcode = PKT_NXDOMAIN;
+ }
+ return kr_ok();
+}
+
+/** Verify non-existence after kwz_between() call. */
+static bool nonexistence_ok(int cmp, const knot_rrset_t *rrs)
+{
+ if (cmp == 3) {
+ return true;
+ }
+ if (cmp != 2) {
+ return false;
+ }
+ const uint8_t *bm = knot_nsec_bitmap(rrs->rrs.rdata);
+ uint16_t bm_size = knot_nsec_bitmap_len(rrs->rrs.rdata);
+ return kr_nsec_children_in_zone_check(bm, bm_size) != 0;
+}
+
+int nsec1_src_synth(struct key *k, struct answer *ans, const knot_dname_t *clencl_name,
+ knot_db_val_t cover_low_kwz, knot_db_val_t cover_hi_kwz,
+ const struct kr_query *qry, struct kr_cache *cache)
+{
+ /* Construct key for the source of synthesis. */
+ knot_db_val_t key = key_NSEC1(k, clencl_name, true);
+ const size_t nwz_off = key_nwz_off(k);
+ if (kr_fails_assert(key.data && key.len >= nwz_off))
+ return kr_error(1);
+ /* Check if our sname-covering NSEC also covers/matches SS. */
+ knot_db_val_t kwz = {
+ .data = (uint8_t *)key.data + nwz_off,
+ .len = key.len - nwz_off,
+ };
+ if (kr_fails_assert((ssize_t)(kwz.len) >= 0))
+ return kr_error(EINVAL);
+ const int cmp = kwz_between(cover_low_kwz, kwz, cover_hi_kwz);
+ if (nonexistence_ok(cmp, ans->rrsets[AR_NSEC].set.rr)) {
+ VERBOSE_MSG(qry, "=> NSEC wildcard: covered by the same RR\n");
+ return AR_SOA;
+ }
+ const knot_rrset_t *nsec_rr = NULL; /**< the wildcard proof NSEC */
+ bool exact_match; /**< whether it matches the source of synthesis */
+ if (cmp == 1) {
+ exact_match = true;
+ nsec_rr = ans->rrsets[AR_NSEC].set.rr;
+ } else {
+ /* Try to find the NSEC for SS. */
+ knot_db_val_t val = { NULL, 0 };
+ knot_db_val_t wild_low_kwz = { NULL, 0 };
+ uint32_t new_ttl;
+ const char *err = find_leq_NSEC1(cache, qry, key, k, &val,
+ &exact_match, &wild_low_kwz, NULL, &new_ttl);
+ if (err) {
+ VERBOSE_MSG(qry, "=> NSEC wildcard: %s\n", err);
+ return kr_ok();
+ }
+ /* Materialize the record into answer (speculatively). */
+ knot_dname_t owner[KNOT_DNAME_MAXLEN];
+ int ret = dname_wire_reconstruct(owner, k, wild_low_kwz);
+ if (ret) return kr_error(ret);
+ const struct entry_h *nsec_eh = val.data;
+ ret = entry2answer(ans, AR_WILD, nsec_eh, knot_db_val_bound(val),
+ owner, KNOT_RRTYPE_NSEC, new_ttl);
+ if (ret) return kr_error(ret);
+ nsec_rr = ans->rrsets[AR_WILD].set.rr;
+ }
+
+ if (kr_fails_assert(nsec_rr))
+ return kr_error(EFAULT);
+ const uint8_t *bm = knot_nsec_bitmap(nsec_rr->rrs.rdata);
+ uint16_t bm_size = knot_nsec_bitmap_len(nsec_rr->rrs.rdata);
+ int ret;
+ struct answer_rrset * const arw = &ans->rrsets[AR_WILD];
+ if (kr_fails_assert(bm)) {
+ ret = kr_error(EFAULT);
+ goto clean_wild;
+ }
+ if (!exact_match) {
+ /* Finish verification that the source of synthesis doesn't exist. */
+ const int nsec_matched =
+ knot_dname_matched_labels(nsec_rr->owner, clencl_name);
+ /* we don't need to use the full source of synthesis ^ */
+ const bool is_sub =
+ nsec_matched == knot_dname_labels(nsec_rr->owner, NULL);
+ if (is_sub && kr_nsec_children_in_zone_check(bm, bm_size) != 0) {
+ VERBOSE_MSG(qry,
+ "=> NSEC wildcard: covered but delegated (or error)\n");
+ ret = kr_ok();
+ goto clean_wild;
+ }
+ /* We have a record proving wildcard non-existence. */
+ WITH_VERBOSE(qry) {
+ auto_free char *owner_str = kr_dname_text(nsec_rr->owner),
+ *next_str = kr_dname_text(knot_nsec_next(nsec_rr->rrs.rdata));
+ VERBOSE_MSG(qry, "=> NSEC wildcard: covered by: %s -> %s, new TTL %d\n",
+ owner_str, next_str, nsec_rr->ttl);
+ }
+ return AR_SOA;
+ }
+
+ /* The wildcard exists. Find if it's NODATA - check type bitmap. */
+ if (kr_nsec_bitmap_nodata_check(bm, bm_size, qry->stype, nsec_rr->owner) == 0) {
+ /* NODATA proven; just need to add SOA+RRSIG later */
+ WITH_VERBOSE(qry) {
+ const char *msg_start = "=> NSEC wildcard: match proved NODATA";
+ if (arw->set.rr) {
+ auto_free char *owner_str = kr_dname_text(nsec_rr->owner);
+ VERBOSE_MSG(qry, "%s: %s, new TTL %d\n",
+ msg_start, owner_str, nsec_rr->ttl);
+ } else {
+ /* don't repeat the RR if it's the same */
+ VERBOSE_MSG(qry, "%s, by the same RR\n", msg_start);
+ }
+ }
+ ans->rcode = PKT_NODATA;
+ return AR_SOA;
+
+ } /* else */
+ /* The data probably exists -> don't add this NSEC
+ * and (later) try to find the real wildcard data */
+ VERBOSE_MSG(qry, "=> NSEC wildcard: should exist (or error)\n");
+ ans->rcode = PKT_NOERROR;
+ ret = kr_ok();
+clean_wild:
+ if (arw->set.rr) { /* we may have matched AR_NSEC */
+ knot_rrset_free(arw->set.rr, ans->mm);
+ arw->set.rr = NULL;
+ knot_rdataset_clear(&arw->sig_rds, ans->mm);
+ }
+ return ret;
+}
+