Adding upstream version 5.6.0.upstream/5.6.0upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 315 insertions, 0 deletions

diff --git a/lib/dnssec/nsec.c b/lib/dnssec/nsec.c
new file mode 100644
index 0000000..8b17247
--- /dev/null
+++ b/lib/dnssec/nsec.c
@@ -0,0 +1,315 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <stdlib.h>
+
+#include <libknot/descriptor.h>
+#include <libknot/dname.h>
+#include <libknot/packet/wire.h>
+#include <libknot/rrset.h>
+#include <libknot/rrtype/nsec.h>
+#include <libknot/rrtype/rrsig.h>
+#include <libdnssec/error.h>
+#include <libdnssec/nsec.h>
+
+#include "lib/defines.h"
+#include "lib/dnssec/nsec.h"
+#include "lib/utils.h"
+#include "resolve.h"
+
+int kr_nsec_children_in_zone_check(const uint8_t *bm, uint16_t bm_size)
+{
+	if (kr_fails_assert(bm))
+		return kr_error(EINVAL);
+	const bool parent_side =
+		dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_DNAME)
+		|| (dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_NS)
+		    && !dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_SOA)
+		);
+	return parent_side ? abs(ENOENT) : kr_ok();
+	/* LATER: after refactoring, probably also check if signer name equals owner,
+	 * but even without that it's not possible to attack *correctly* signed zones.
+	 */
+}
+
+/* This block of functions implements a "safe" version of knot_dname_cmp(),
+ * until that one handles in-label zero bytes correctly. */
+static int lf_cmp(const uint8_t *lf1, const uint8_t *lf2)
+{
+	/* Compare common part. */
+	uint8_t common = lf1[0];
+	if (common > lf2[0]) {
+		common = lf2[0];
+	}
+	int ret = memcmp(lf1 + 1, lf2 + 1, common);
+	if (ret != 0) {
+		return ret;
+	}
+
+	/* If they match, compare lengths. */
+	if (lf1[0] < lf2[0]) {
+		return -1;
+	} else if (lf1[0] > lf2[0]) {
+		return 1;
+	} else {
+		return 0;
+	}
+}
+static void dname_reverse(const knot_dname_t *src, size_t src_len, knot_dname_t *dst)
+{
+	knot_dname_t *idx = dst + src_len - 1;
+	kr_require(src[src_len - 1] == '\0');
+	*idx = '\0';
+
+	while (*src) {
+		uint16_t len = *src + 1;
+		idx -= len;
+		memcpy(idx, src, len);
+		src += len;
+	}
+	kr_require(idx == dst);
+}
+static int dname_cmp(const knot_dname_t *d1, const knot_dname_t *d2)
+{
+	size_t d1_len = knot_dname_size(d1);
+	size_t d2_len = knot_dname_size(d2);
+
+	knot_dname_t d1_rev_arr[d1_len], d2_rev_arr[d2_len];
+	const knot_dname_t *d1_rev = d1_rev_arr, *d2_rev = d2_rev_arr;
+
+	dname_reverse(d1, d1_len, d1_rev_arr);
+	dname_reverse(d2, d2_len, d2_rev_arr);
+
+	int res = 0;
+	while (res == 0 && d1_rev != NULL) {
+		res = lf_cmp(d1_rev, d2_rev);
+		d1_rev = knot_wire_next_label(d1_rev, NULL);
+		d2_rev = knot_wire_next_label(d2_rev, NULL);
+	}
+
+	kr_require(res != 0 || d2_rev == NULL);
+	return res;
+}
+
+
+/**
+ * Check whether this nsec proves that there is no closer match for sname.
+ *
+ * @param nsec  NSEC RRSet.
+ * @param sname Searched name.
+ * @return      0 if proves, >0 if not (abs(ENOENT) or abs(EEXIST)), or error code (<0).
+ */
+static int nsec_covers(const knot_rrset_t *nsec, const knot_dname_t *sname)
+{
+	if (kr_fails_assert(nsec && sname))
+		return kr_error(EINVAL);
+	const int cmp = dname_cmp(sname, nsec->owner);
+	if (cmp  < 0) return abs(ENOENT); /* 'sname' before 'owner', so can't be covered */
+	if (cmp == 0) return abs(EEXIST); /* matched, not covered */
+
+	/* We have to lower-case 'next' with libknot >= 2.7; see also RFC 6840 5.1. */
+	knot_dname_t next[KNOT_DNAME_MAXLEN];
+	int ret = knot_dname_to_wire(next, knot_nsec_next(nsec->rrs.rdata), sizeof(next));
+	if (kr_fails_assert(ret >= 0))
+		return kr_error(ret);
+	knot_dname_to_lower(next);
+
+	/* If NSEC 'owner' >= 'next', it means that there is nothing after 'owner' */
+	const bool is_last_nsec = dname_cmp(nsec->owner, next) >= 0;
+	const bool in_range = is_last_nsec || dname_cmp(sname, next) < 0;
+	if (!in_range)
+		return abs(ENOENT);
+	/* Before returning kr_ok(), we have to check a special case:
+	 * sname might be under delegation from owner and thus
+	 * not in the zone of this NSEC at all.
+	 */
+	if (knot_dname_in_bailiwick(sname, nsec->owner) <= 0)
+		return kr_ok();
+	const uint8_t *bm = knot_nsec_bitmap(nsec->rrs.rdata);
+	uint16_t bm_size = knot_nsec_bitmap_len(nsec->rrs.rdata);
+
+	return kr_nsec_children_in_zone_check(bm, bm_size);
+}
+
+int kr_nsec_bitmap_nodata_check(const uint8_t *bm, uint16_t bm_size, uint16_t type, const knot_dname_t *owner)
+{
+	const int NO_PROOF = abs(ENOENT);
+	if (!bm || !owner)
+		return kr_error(EINVAL);
+	if (dnssec_nsec_bitmap_contains(bm, bm_size, type))
+		return NO_PROOF;
+
+	if (type != KNOT_RRTYPE_CNAME
+	    && dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_CNAME)) {
+		return NO_PROOF;
+	}
+	/* Special behavior around zone cuts. */
+	switch (type) {
+	case KNOT_RRTYPE_DS:
+		/* Security feature: in case of DS also check for SOA
+		 * non-existence to be more certain that we don't hold
+		 * a child-side NSEC by some mistake (e.g. when forwarding).
+		 * See RFC4035 5.2, next-to-last paragraph.
+		 * This doesn't apply for root DS as it doesn't exist in DNS hierarchy.
+		 */
+		if (owner[0] != '\0' && dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_SOA))
+			return NO_PROOF;
+		break;
+	case KNOT_RRTYPE_CNAME:
+		/* Exception from the `default` rule.  It's perhaps disputable,
+		 * but existence of CNAME at zone apex is not allowed, so we
+		 * consider a parent-side record to be enough to prove non-existence. */
+		break;
+	default:
+		/* Parent-side delegation record isn't authoritative for non-DS;
+		 * see RFC6840 4.1. */
+		if (dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_NS)
+		    && !dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_SOA)) {
+			return NO_PROOF;
+		}
+		/* LATER(opt): perhaps short-circuit test if we repeat it here. */
+	}
+
+	return kr_ok();
+}
+
+/// Convenience wrapper for kr_nsec_bitmap_nodata_check()
+static int no_data_response_check_rrtype(const knot_rrset_t *nsec, uint16_t type)
+{
+	if (kr_fails_assert(nsec && nsec->type == KNOT_RRTYPE_NSEC))
+		return kr_error(EINVAL);
+	const uint8_t *bm = knot_nsec_bitmap(nsec->rrs.rdata);
+	uint16_t bm_size = knot_nsec_bitmap_len(nsec->rrs.rdata);
+	return kr_nsec_bitmap_nodata_check(bm, bm_size, type, nsec->owner);
+}
+
+int kr_nsec_wildcard_answer_response_check(const knot_pkt_t *pkt, knot_section_t section_id,
+                                           const knot_dname_t *sname)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, section_id);
+	if (!sec || !sname)
+		return kr_error(EINVAL);
+
+	for (unsigned i = 0; i < sec->count; ++i) {
+		const knot_rrset_t *rrset = knot_pkt_rr(sec, i);
+		if (rrset->type != KNOT_RRTYPE_NSEC)
+			continue;
+		if (nsec_covers(rrset, sname) == 0)
+			return kr_ok();
+	}
+
+	return kr_error(ENOENT);
+}
+
+int kr_nsec_negative(const ranked_rr_array_t *rrrs, uint32_t qry_uid,
+			const knot_dname_t *sname, uint16_t stype)
+{
+	// We really only consider the (canonically) first NSEC in each RRset.
+	// Using same owner with differing content probably isn't useful for NSECs anyway.
+	// Many other parts of code do the same, too.
+	if (kr_fails_assert(rrrs && sname))
+		return kr_error(EINVAL);
+
+	// Terminology: https://datatracker.ietf.org/doc/html/rfc4592#section-3.3.1
+	int clencl_labels = -1; // the label count of the closest encloser of sname
+	for (int i = rrrs->len - 1; i >= 0; --i) { // NSECs near the end typically
+		const knot_rrset_t *nsec = rrrs->at[i]->rr;
+		bool ok = rrrs->at[i]->qry_uid == qry_uid
+			&& nsec->type == KNOT_RRTYPE_NSEC
+			&& kr_rank_test(rrrs->at[i]->rank, KR_RANK_SECURE);
+		if (!ok) continue;
+		const int covers = nsec_covers(nsec, sname);
+		if (covers == abs(EEXIST)
+		    && no_data_response_check_rrtype(nsec, stype) == 0) {
+			return PKT_NODATA; // proven NODATA by matching NSEC
+		}
+		if (covers != 0) continue;
+
+		// We have to lower-case 'next' with libknot >= 2.7; see also RFC 6840 5.1.
+		// LATER(optim.): it's duplicate work with the nsec_covers() call.
+		knot_dname_t next[KNOT_DNAME_MAXLEN];
+		int ret = knot_dname_to_wire(next, knot_nsec_next(nsec->rrs.rdata), sizeof(next));
+		if (kr_fails_assert(ret >= 0))
+			return kr_error(ret);
+		knot_dname_to_lower(next);
+
+		clencl_labels = MAX(knot_dname_matched_labels(nsec->owner, sname),
+				    knot_dname_matched_labels(sname, next));
+		break; // reduce indentation again
+	}
+
+	if (clencl_labels < 0)
+		return kr_error(ENOENT);
+	const int sname_labels = knot_dname_labels(sname, NULL);
+	if (sname_labels == clencl_labels)
+		return PKT_NODATA; // proven NODATA; sname is an empty non-terminal
+
+	// Explicitly construct name for the corresponding source of synthesis.
+	knot_dname_t ssynth[KNOT_DNAME_MAXLEN + 2];
+	ssynth[0] = 1;
+	ssynth[1] = '*';
+	const knot_dname_t *clencl = sname;
+	for (int l = sname_labels; l > clencl_labels; --l)
+		clencl = knot_wire_next_label(clencl, NULL);
+	(void)!!knot_dname_store(&ssynth[2], clencl);
+
+	// Try to (dis)prove the source of synthesis by a covering or matching NSEC.
+	for (int i = rrrs->len - 1; i >= 0; --i) { // NSECs near the end typically
+		const knot_rrset_t *nsec = rrrs->at[i]->rr;
+		bool ok = rrrs->at[i]->qry_uid == qry_uid
+			&& nsec->type == KNOT_RRTYPE_NSEC
+			&& kr_rank_test(rrrs->at[i]->rank, KR_RANK_SECURE);
+		if (!ok) continue;
+		const int covers = nsec_covers(nsec, ssynth);
+		if (covers == abs(EEXIST)) {
+			int ret = no_data_response_check_rrtype(nsec, stype);
+			if (ret == 0) return PKT_NODATA; // proven NODATA by wildcard NSEC
+			// TODO: also try expansion?  Or at least a different return code?
+		} else if (covers == 0) {
+			return PKT_NXDOMAIN | PKT_NODATA;
+		}
+	}
+	return kr_error(ENOENT);
+}
+
+int kr_nsec_ref_to_unsigned(const ranked_rr_array_t *rrrs, uint32_t qry_uid,
+				const knot_dname_t *sname)
+{
+	for (int i = rrrs->len - 1; i >= 0; --i) { // NSECs near the end typically
+		const knot_rrset_t *nsec = rrrs->at[i]->rr;
+		bool ok = rrrs->at[i]->qry_uid == qry_uid
+			&& nsec->type == KNOT_RRTYPE_NSEC
+			&& kr_rank_test(rrrs->at[i]->rank, KR_RANK_SECURE)
+			// avoid any possibility of getting tricked in deeper zones
+			&& knot_dname_in_bailiwick(sname, nsec->owner) >= 0;
+		if (!ok) continue;
+
+		kr_assert(nsec->rrs.rdata);
+		const uint8_t *bm = knot_nsec_bitmap(nsec->rrs.rdata);
+		uint16_t bm_size = knot_nsec_bitmap_len(nsec->rrs.rdata);
+		ok = ok &&  dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_NS)
+			&& !dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_DS)
+			&& !dnssec_nsec_bitmap_contains(bm, bm_size, KNOT_RRTYPE_SOA);
+		if (ok) return kr_ok();
+	}
+	return kr_error(DNSSEC_NOT_FOUND);
+}
+
+int kr_nsec_matches_name_and_type(const knot_rrset_t *nsec,
+				   const knot_dname_t *name, uint16_t type)
+{
+	/* It's not secure enough to just check a single bit for (some) other types,
+	 * but we (currently) only use this API for NS.  See RFC 6840 sec. 4.  */
+	if (kr_fails_assert(type == KNOT_RRTYPE_NS && nsec && nsec->rrs.rdata && name))
+		return kr_error(EINVAL);
+	if (!knot_dname_is_equal(nsec->owner, name))
+		return kr_error(ENOENT);
+	const uint8_t *bm = knot_nsec_bitmap(nsec->rrs.rdata);
+	uint16_t bm_size = knot_nsec_bitmap_len(nsec->rrs.rdata);
+	if (dnssec_nsec_bitmap_contains(bm, bm_size, type)) {
+		return kr_ok();
+	} else {
+		return kr_error(ENOENT);
+	}
+}