Merge branch 'release-6.0.6' into 6.0v6.0.6

17 files changed, 207 insertions, 29 deletions

diff --git a/AUTHORS b/AUTHORS
index 193c3fd3..3f8f226e 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -36,6 +36,7 @@ Jiří Helebrant <jiri.helebrant@nic.cz>
 Jonathan Coetzee <jon@thancoetzee.com>
 Josh Soref <jsoref@users.noreply.github.com>
 Karel Slaný <karel.slany@nic.cz>
+Kirill A. Korinsky <kirill@korins.ky>
 Konstantin Amelichev <kostya.amelichev@gmail.com>
 Ladislav Lhotka <ladislav.lhotka@nic.cz>
 Leo Vandewoestijne <github@unicycle.net>
diff --git a/NEWS b/NEWS
index 43dee12f..d4ce40fb 100644
--- a/NEWS
+++ b/NEWS
@@ -1,12 +1,31 @@
-Knot Resolver 6.0.6 (2024-0m-dd)
+Knot Resolver 6.0.6 (2024-02-13)
 ================================
 
+Security
+--------
+- CVE-2023-50868: NSEC3 closest encloser proof can exhaust CPU
+  * validator: lower the NSEC3 iteration limit (150 -> 50)
+  * validator: similarly also limit excessive NSEC3 salt length
+  * cache: limit the amount of work on SHA1 in NSEC3 aggressive cache
+  * validator: limit the amount of work on SHA1 in NSEC3 proofs
+  * validator: refuse to validate answers with more than 8 NSEC3 records
+
+- CVE-2023-50387 "KeyTrap": DNSSEC verification complexity
+  could be exploited to exhaust CPU resources and stall DNS resolvers.
+  Solution boils down mainly to limiting crypto-validations per packet.
+
+  We would like to thank Elias Heftrig, Haya Schulmann, Niklas Vogel and Michael Waidner
+  from the German National Research Center for Applied Cybersecurity ATHENE
+  for bringing this vulnerability to our attention.
+
 Improvements
 ------------
+- update addresses of B.root-servers.net (!1478)
 - tweak the default run_dir on non-Linux (!1481)
 
 Bugfixes
 --------
+- fix potential SERVFAIL deadlocks if net.ipv6 = false (#880)
 - fix validation of RRsets around 64 KiB size; needs libknot >= 3.4 (!1497)
 
 
@@ -27,9 +46,26 @@ https://knot.pages.nic.cz/knot-resolver/upgrading-to-6.html
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 
-Knot Resolver 5.x.y (202y-mm-dd)
+Knot Resolver 5.7.1 (2024-02-13)
 ================================
 
+Security
+--------
+- CVE-2023-50868: NSEC3 closest encloser proof can exhaust CPU
+  * validator: lower the NSEC3 iteration limit (150 -> 50)
+  * validator: similarly also limit excessive NSEC3 salt length
+  * cache: limit the amount of work on SHA1 in NSEC3 aggressive cache
+  * validator: limit the amount of work on SHA1 in NSEC3 proofs
+  * validator: refuse to validate answers with more than 8 NSEC3 records
+
+- CVE-2023-50387 "KeyTrap": DNSSEC verification complexity
+  could be exploited to exhaust CPU resources and stall DNS resolvers.
+  Solution boils down mainly to limiting crypto-validations per packet.
+
+  We would like to thank Elias Heftrig, Haya Schulmann, Niklas Vogel and Michael Waidner
+  from the German National Research Center for Applied Cybersecurity ATHENE
+  for bringing this vulnerability to our attention.
+
 Improvements
 ------------
 - update addresses of B.root-servers.net (!1478)
diff --git a/daemon/lua/kres-gen-30.lua b/daemon/lua/kres-gen-30.lua
index 2e110d1c..48ea7a90 100644
--- a/daemon/lua/kres-gen-30.lua
+++ b/daemon/lua/kres-gen-30.lua
@@ -371,6 +371,8 @@ struct kr_query {
 	struct kr_qflags forward_flags;
 	uint32_t secret;
 	uint32_t uid;
+	int32_t vld_limit_crypto_remains;
+	uint32_t vld_limit_uid;
 	uint64_t creation_time_mono;
 	uint64_t timestamp_mono;
 	struct timeval timestamp;
@@ -389,6 +391,7 @@ struct kr_context {
 	knot_rrset_t *upstream_opt_rr;
 	trie_t *trust_anchors;
 	trie_t *negative_anchors;
+	int32_t vld_limit_crypto;
 	struct kr_zonecut root_hints;
 	struct kr_cache cache;
 	unsigned int cache_rtt_tout_retry_interval;
diff --git a/daemon/lua/kres-gen-31.lua b/daemon/lua/kres-gen-31.lua
index 1b4e62bb..0bc50931 100644
--- a/daemon/lua/kres-gen-31.lua
+++ b/daemon/lua/kres-gen-31.lua
@@ -371,6 +371,8 @@ struct kr_query {
 	struct kr_qflags forward_flags;
 	uint32_t secret;
 	uint32_t uid;
+	int32_t vld_limit_crypto_remains;
+	uint32_t vld_limit_uid;
 	uint64_t creation_time_mono;
 	uint64_t timestamp_mono;
 	struct timeval timestamp;
@@ -389,6 +391,7 @@ struct kr_context {
 	knot_rrset_t *upstream_opt_rr;
 	trie_t *trust_anchors;
 	trie_t *negative_anchors;
+	int32_t vld_limit_crypto;
 	struct kr_zonecut root_hints;
 	struct kr_cache cache;
 	unsigned int cache_rtt_tout_retry_interval;
diff --git a/daemon/lua/kres-gen-32.lua b/daemon/lua/kres-gen-32.lua
index e6f7db45..88d9511f 100644
--- a/daemon/lua/kres-gen-32.lua
+++ b/daemon/lua/kres-gen-32.lua
@@ -372,6 +372,8 @@ struct kr_query {
 	struct kr_qflags forward_flags;
 	uint32_t secret;
 	uint32_t uid;
+	int32_t vld_limit_crypto_remains;
+	uint32_t vld_limit_uid;
 	uint64_t creation_time_mono;
 	uint64_t timestamp_mono;
 	struct timeval timestamp;
@@ -390,6 +392,7 @@ struct kr_context {
 	knot_rrset_t *upstream_opt_rr;
 	trie_t *trust_anchors;
 	trie_t *negative_anchors;
+	int32_t vld_limit_crypto;
 	struct kr_zonecut root_hints;
 	struct kr_cache cache;
 	unsigned int cache_rtt_tout_retry_interval;
diff --git a/lib/cache/api.c b/lib/cache/api.c
index 37dff26e..b611085d 100644
--- a/lib/cache/api.c
+++ b/lib/cache/api.c
@@ -512,7 +512,7 @@ static ssize_t stash_rrset(struct kr_cache *cache, const struct kr_query *qry,
 		return kr_ok();
 	}
 	if (rr->type == KNOT_RRTYPE_NSEC3 && rr->rrs.count
-	    && knot_nsec3_iters(rr->rrs.rdata) > KR_NSEC3_MAX_ITERATIONS) {
+	    && kr_nsec3_limited_rdata(rr->rrs.rdata)) {
 		/* This shouldn't happen often, thanks to downgrades during validation. */
 		VERBOSE_MSG(qry, "=> skipping NSEC3 with too many iterations\n");
 		return kr_ok();
diff --git a/lib/cache/nsec3.c b/lib/cache/nsec3.c
index 0b707759..2716456c 100644
--- a/lib/cache/nsec3.c
+++ b/lib/cache/nsec3.c
@@ -84,7 +84,7 @@ static knot_db_val_t key_NSEC3_name(struct key *k, const knot_dname_t *name,
 		.data = (uint8_t *)/*const-cast*/name,
 	};
 
-	if (kr_fails_assert(nsec_p->libknot.iterations <= KR_NSEC3_MAX_ITERATIONS)) {
+	if (kr_fails_assert(!kr_nsec3_limited_params(&nsec_p->libknot))) {
 		/* This is mainly defensive; it shouldn't happen thanks to downgrades. */
 		return VAL_EMPTY;
 	}
@@ -272,8 +272,22 @@ int nsec3_encloser(struct key *k, struct answer *ans,
 	const int zname_labels = knot_dname_labels(k->zname, NULL);
 	int last_nxproven_labels = -1;
 	const knot_dname_t *name = qry->sname;
+
+	/* Avoid doing too much work on SHA1; we might consider that a part of mitigating
+	 *    CVE-2023-50868: NSEC3 closest encloser proof can exhaust CPU
+	 * As currently the code iterates from the longest name, we limit that.
+	 * Note that we don't want to limit too much, as the alternative usually includes
+	 * sending more queries upstream, which would come with nontrivial work, too.
+	 */
+	const int max_labels = zname_labels + kr_nsec3_max_depth(&ans->nsec_p.libknot);
+	if (sname_labels > max_labels)
+		VERBOSE_MSG(qry, "=> NSEC3 hashing partly skipped due to too long SNAME (CVE-2023-50868)\n");
+
 	for (int name_labels = sname_labels; name_labels >= zname_labels;
 					--name_labels, name += 1 + name[0]) {
+		if (name_labels > max_labels)
+			continue; // avoid the hashing
+
 		/* Find a previous-or-equal NSEC3 in cache covering the name,
 		 * checking TTL etc. */
 		const knot_db_val_t key = key_NSEC3_name(k, name, false, &ans->nsec_p);
diff --git a/lib/defines.h b/lib/defines.h
index 6b6dac56..e8328928 100644
--- a/lib/defines.h
+++ b/lib/defines.h
@@ -57,6 +57,8 @@ static inline int KR_COLD kr_error(int x) {
 #define KR_COUNT_NO_NSADDR_LIMIT 5
 #define KR_CONSUME_FAIL_ROW_LIMIT 3 /* Maximum number of KR_STATE_FAIL in a row. */
 
+#define KR_VLD_LIMIT_CRYPTO_DEFAULT 32 /**< default for struct kr_query::vld_limit_crypto */
+
 /*
  * Defines.
  */
diff --git a/lib/dnssec.c b/lib/dnssec.c
index d6ae3cc6..262570c4 100644
--- a/lib/dnssec.c
+++ b/lib/dnssec.c
@@ -134,7 +134,7 @@ int kr_rrset_validate(kr_rrset_validation_ctx_t *vctx, knot_rrset_t *covered)
 	memset(&vctx->rrs_counters, 0, sizeof(vctx->rrs_counters));
 	for (unsigned i = 0; i < vctx->keys->rrs.count; ++i) {
 		int ret = kr_rrset_validate_with_key(vctx, covered, i, NULL);
-		if (ret == 0) {
+		if (ret == 0 || ret == kr_error(E2BIG)) {
 			return ret;
 		}
 	}
@@ -240,6 +240,29 @@ fail:
 	return NULL;
 }
 
+/// Return if we want to afford yet another crypto-validation (and account it).
+static bool check_crypto_limit(const kr_rrset_validation_ctx_t *vctx)
+{
+	if (vctx->limit_crypto_remains == NULL)
+		return true; // no limiting
+	if (*vctx->limit_crypto_remains > 0) {
+		--*vctx->limit_crypto_remains;
+		return true;
+	}
+	// We got over limit.  There are optional actions to do.
+	if (vctx->log_qry && kr_log_is_debug_qry(VALIDATOR, vctx->log_qry)) {
+		auto_free char *name_str = kr_dname_text(vctx->zone_name);
+		kr_log_q(vctx->log_qry, VALIDATOR,
+			"expensive crypto limited, mitigating CVE-2023-50387, current zone: %s\n",
+			name_str);
+	}
+	if (vctx->log_qry && vctx->log_qry->request) {
+		kr_request_set_extended_error(vctx->log_qry->request, KNOT_EDNS_EDE_BOGUS,
+				"EAIE: expensive crypto limited, mitigating CVE-2023-50387");
+	}
+	return false;
+}
+
 static int kr_svldr_rrset_with_key(knot_rrset_t *rrs, const knot_rdataset_t *rrsigs,
 				kr_rrset_validation_ctx_t *vctx, const kr_svldr_key_t *key)
 {
@@ -258,6 +281,8 @@ static int kr_svldr_rrset_with_key(knot_rrset_t *rrs, const knot_rdataset_t *rrs
 		} else if (retv != 0) {
 			continue;
 		}
+		if (!check_crypto_limit(vctx))
+			return vctx->result = kr_error(E2BIG);
 		// We only expect non-expanded wildcard records in input;
 		// that also means we don't need to perform non-existence proofs.
 		const int trim_labels = (val_flgs & FLG_WILDCARD_EXPANSION) ? 1 : 0;
@@ -282,7 +307,7 @@ int kr_svldr_rrset(knot_rrset_t *rrs, const knot_rdataset_t *rrsigs,
 	}
 	for (ssize_t i = 0; i < ctx->keys.len; ++i) {
 		kr_svldr_rrset_with_key(rrs, rrsigs, &ctx->vctx, &ctx->keys.at[i]);
-		if (ctx->vctx.result == 0)
+		if (ctx->vctx.result == 0 || ctx->vctx.result == kr_error(E2BIG))
 			break;
 	}
 	return ctx->vctx.result;
@@ -356,9 +381,8 @@ static int kr_rrset_validate_with_key(kr_rrset_validation_ctx_t *vctx,
 			int retv = validate_rrsig_rr(&val_flgs, covered_labels, rdata_j,
 							key_alg, keytag, vctx);
 			if (retv == kr_error(EAGAIN)) {
-				kr_dnssec_key_free(&created_key);
 				vctx->result = retv;
-				return retv;
+				goto finish;
 			} else if (retv != 0) {
 				continue;
 			}
@@ -368,6 +392,10 @@ static int kr_rrset_validate_with_key(kr_rrset_validation_ctx_t *vctx,
 					break;
 				}
 			}
+			if (!check_crypto_limit(vctx)) {
+				vctx->result = kr_error(E2BIG);
+				goto finish;
+			}
 			if (kr_check_signature(rdata_j, key, covered, trim_labels) != 0) {
 				vctx->rrs_counters.crypto_invalid++;
 				continue;
@@ -392,15 +420,15 @@ static int kr_rrset_validate_with_key(kr_rrset_validation_ctx_t *vctx,
 
 			trim_ttl(covered, rdata_j, vctx);
 
-			kr_dnssec_key_free(&created_key);
-			vctx->result = kr_ok();
 			kr_rank_set(&vctx->rrs->at[i]->rank, KR_RANK_SECURE); /* upgrade from bogus */
-			return vctx->result;
+			vctx->result = kr_ok();
+			goto finish;
 		}
 	}
 	/* No applicable key found, cannot be validated. */
-	kr_dnssec_key_free(&created_key);
 	vctx->result = kr_error(ENOENT);
+finish:
+	kr_dnssec_key_free(&created_key);
 	return vctx->result;
 }
 
@@ -448,7 +476,7 @@ int kr_dnskeys_trusted(kr_rrset_validation_ctx_t *vctx, const knot_rdataset_t *s
 		if (ret == 0)
 			ret = kr_svldr_rrset_with_key(keys, sigs, vctx, &key);
 		svldr_key_del(&key);
-		if (ret == 0) {
+		if (ret == 0 || ret == kr_error(E2BIG)) {
 			kr_assert(vctx->result == 0);
 			return vctx->result;
 		}
diff --git a/lib/dnssec.h b/lib/dnssec.h
index 0fbd47c0..ca737cfe 100644
--- a/lib/dnssec.h
+++ b/lib/dnssec.h
@@ -44,6 +44,7 @@ struct kr_rrset_validation_ctx {
 	uint32_t flags;			/*!< Output - Flags. */
 	uint32_t err_cnt;		/*!< Output - Number of validation failures. */
 	uint32_t cname_norrsig_cnt;	/*!< Output - Number of CNAMEs missing RRSIGs. */
+	int32_t *limit_crypto_remains;  /*!< Optional pointer to struct kr_query::vld_limit_crypto_remains */
 
 	/** Validation result: kr_error() code.
 	 *
diff --git a/lib/dnssec/nsec3.c b/lib/dnssec/nsec3.c
index 037d5bdc..4199f25f 100644
--- a/lib/dnssec/nsec3.c
+++ b/lib/dnssec/nsec3.c
@@ -71,7 +71,7 @@ static int hash_name(dnssec_binary_t *hash, const dnssec_nsec3_params_t *params,
 		return kr_error(EINVAL);
 	if (!name)
 		return kr_error(EINVAL);
-	if (kr_fails_assert(params->iterations <= KR_NSEC3_MAX_ITERATIONS)) {
+	if (kr_fails_assert(!kr_nsec3_limited_params(params))) {
 		/* This if is mainly defensive; it shouldn't happen. */
 		return kr_error(EINVAL);
 	}
@@ -146,6 +146,18 @@ static int closest_encloser_match(int *flags, const knot_rrset_t *nsec3,
 	const knot_dname_t *encloser = knot_wire_next_label(name, NULL);
 	*skipped = 1;
 
+	/* Avoid doing too much work on SHA1, mitigating:
+	 *   CVE-2023-50868: NSEC3 closest encloser proof can exhaust CPU
+	 * We log nothing here; it wouldn't be easy from this place
+	 * and huge SNAME should be suspicious on its own.
+	 */
+	const int max_labels = knot_dname_labels(nsec3->owner, NULL) - 1
+				+ kr_nsec3_max_depth(&params);
+	for (int l = knot_dname_labels(encloser, NULL); l > max_labels; --l) {
+		encloser = knot_wire_next_label(encloser, NULL);
+		++(*skipped);
+	}
+
 	while(encloser) {
 		ret = hash_name(&name_hash, &params, encloser);
 		if (ret != 0)
@@ -565,7 +577,7 @@ int kr_nsec3_wildcard_answer_response_check(const knot_pkt_t *pkt, knot_section_
 		const knot_rrset_t *rrset = knot_pkt_rr(sec, i);
 		if (rrset->type != KNOT_RRTYPE_NSEC3)
 			continue;
-		if (knot_nsec3_iters(rrset->rrs.rdata) > KR_NSEC3_MAX_ITERATIONS) {
+		if (kr_nsec3_limited_rdata(rrset->rrs.rdata)) {
 			/* Avoid hashing with too many iterations.
 			 * If we get here, the `sname` wildcard probably ends up bogus,
 			 * but it gets downgraded to KR_RANK_INSECURE when validator
diff --git a/lib/dnssec/nsec3.h b/lib/dnssec/nsec3.h
index eb0bd397..a28d3c78 100644
--- a/lib/dnssec/nsec3.h
+++ b/lib/dnssec/nsec3.h
@@ -5,18 +5,51 @@
 #pragma once
 
 #include <libknot/packet/pkt.h>
+#include <libknot/rrtype/nsec3.h>
+#include <libdnssec/nsec.h>
+
+
+static inline unsigned int kr_nsec3_price(unsigned int iterations, unsigned int salt_len)
+{
+	// SHA1 works on 64-byte chunks.
+	// On iterating we hash the salt + 20 bytes of the previous hash.
+	int chunks_per_iter = (20 + salt_len - 1) / 64 + 1;
+	return (iterations + 1) * chunks_per_iter;
+}
 
 /** High numbers in NSEC3 iterations don't really help security
  *
- * ...so we avoid doing all the work.  The value is a current compromise;
- * zones shooting over get downgraded to insecure status.
+ * ...so we avoid doing all the work.  The limit is a current compromise;
+ * answers using NSEC3 over kr_nsec3_limited* get downgraded to insecure status.
  *
- * Original restriction wasn't that strict:
-   https://datatracker.ietf.org/doc/html/rfc5155#section-10.3
- * but there is discussion about officially lowering the limits:
-   https://tools.ietf.org/id/draft-hardaker-dnsop-nsec3-guidance-02.html#section-2.3
+   https://datatracker.ietf.org/doc/html/rfc9276#name-recommendation-for-validati
  */
-#define KR_NSEC3_MAX_ITERATIONS 150
+static inline bool kr_nsec3_limited(unsigned int iterations, unsigned int salt_len)
+{
+	const int MAX_ITERATIONS = 50; // limit with short salt length
+	return kr_nsec3_price(iterations, salt_len) > MAX_ITERATIONS + 1;
+}
+static inline bool kr_nsec3_limited_rdata(const knot_rdata_t *rd)
+{
+	return kr_nsec3_limited(knot_nsec3_iters(rd), knot_nsec3_salt_len(rd));
+}
+static inline bool kr_nsec3_limited_params(const dnssec_nsec3_params_t *params)
+{
+	return kr_nsec3_limited(params->iterations, params->salt.size);
+}
+
+/** Return limit on NSEC3 depth.  The point is to avoid doing too much work on SHA1.
+ *
+ * CVE-2023-50868: NSEC3 closest encloser proof can exhaust CPU
+ *
+ * 128 is chosen so that zones with good NSEC3 parameters (giving _price() == 1)
+ * won't be limited in any way.  Performance doesn't seem too bad with that either.
+ */
+static inline int kr_nsec3_max_depth(const dnssec_nsec3_params_t *params)
+{
+	return 128 / kr_nsec3_price(params->iterations, params->salt.size);
+}
+
 
 /**
  * Name error response check (RFC5155 7.2.2).
@@ -39,7 +72,7 @@ int kr_nsec3_name_error_response_check(const knot_pkt_t *pkt, knot_section_t sec
  *                     KNOT_ERANGE - NSEC3 RR that covers a wildcard
  *                     has been found, but has opt-out flag set;
  *                     otherwise - error.
- * Records over KR_NSEC3_MAX_ITERATIONS are skipped, so you probably get kr_error(ENOENT).
+ * Too expensive NSEC3 records are skipped, so you probably get kr_error(ENOENT).
  */
 int kr_nsec3_wildcard_answer_response_check(const knot_pkt_t *pkt, knot_section_t section_id,
                                             const knot_dname_t *sname, int trim_to_next);
diff --git a/lib/layer/validate.c b/lib/layer/validate.c
index 17f90740..3bdb205c 100644
--- a/lib/layer/validate.c
+++ b/lib/layer/validate.c
@@ -128,14 +128,15 @@ static bool maybe_downgrade_nsec3(const ranked_rr_array_entry_t *e, struct kr_qu
 	const knot_rdataset_t *rrs = &e->rr->rrs;
 	knot_rdata_t *rd = rrs->rdata;
 	for (int j = 0; j < rrs->count; ++j, rd = knot_rdataset_next(rd)) {
-		if (knot_nsec3_iters(rd) > KR_NSEC3_MAX_ITERATIONS)
+		if (kr_nsec3_limited_rdata(rd))
 			goto do_downgrade;
 	}
 	return false;
 
 do_downgrade: // we do this deep inside calls because of having signer name available
-	VERBOSE_MSG(qry, "<= DNSSEC downgraded due to NSEC3 iterations %d > %d\n",
-			(int)knot_nsec3_iters(rd), (int)KR_NSEC3_MAX_ITERATIONS);
+	VERBOSE_MSG(qry,
+		"<= DNSSEC downgraded due to expensive NSEC3: %d iterations, %d salt length\n",
+		(int)knot_nsec3_iters(rd), (int)knot_nsec3_salt_len(rd));
 	qry->flags.DNSSEC_WANT = false;
 	qry->flags.DNSSEC_INSECURE = true;
 	rank_records(qry, true, KR_RANK_INSECURE, vctx->zone_name);
@@ -275,6 +276,7 @@ static int validate_records(struct kr_request *req, knot_pkt_t *answer, knot_mm_
 		.err_cnt	= 0,
 		.cname_norrsig_cnt = 0,
 		.result		= 0,
+		.limit_crypto_remains = &qry->vld_limit_crypto_remains,
 		.log_qry	= qry,
 	};
 
@@ -383,6 +385,7 @@ static int validate_keyset(struct kr_request *req, knot_pkt_t *answer, bool has_
 			.has_nsec3	= has_nsec3,
 			.flags		= 0,
 			.result		= 0,
+			.limit_crypto_remains = &qry->vld_limit_crypto_remains,
 			.log_qry	= qry,
 		};
 		int ret = kr_dnskeys_trusted(&vctx, sig_rds, qry->zone_cut.trust_anchor);
@@ -1029,6 +1032,11 @@ static int validate(kr_layer_t *ctx, knot_pkt_t *pkt)
 	struct kr_request *req = ctx->req;
 	struct kr_query *qry = req->current_query;
 
+	if (qry->vld_limit_uid != qry->uid) {
+		qry->vld_limit_uid = qry->uid;
+		qry->vld_limit_crypto_remains = req->ctx->vld_limit_crypto;
+	}
+
 	/* Ignore faulty or unprocessed responses. */
 	if (ctx->state & (KR_STATE_FAIL|KR_STATE_CONSUME)) {
 		return ctx->state;
@@ -1119,6 +1127,24 @@ static int validate(kr_layer_t *ctx, knot_pkt_t *pkt)
 		}
 	}
 
+	/* Check for too many NSEC3 records.  That's an issue, as some parts of validation
+	 * are quadratic in their count, doing nontrivial computations inside.
+	 * Also there seems to be no use in sending many NSEC3 records. */
+	if (!qry->flags.CACHED) {
+		const knot_pktsection_t *sec = knot_pkt_section(pkt, KNOT_AUTHORITY);
+		int count = 0;
+		for (int i = 0; i < sec->count; ++i)
+			count += (knot_pkt_rr(sec, i)->type == KNOT_RRTYPE_NSEC3);
+		if (count > 8) {
+			VERBOSE_MSG(qry, "<= too many NSEC3 records in AUTHORITY (%d)\n", count);
+			kr_request_set_extended_error(req, 27/*KNOT_EDNS_EDE_NSEC3_ITERS*/,
+				/* It's not about iteration values per se, but close enough. */
+				"DYRH: too many NSEC3 records");
+			qry->flags.DNSSEC_BOGUS = true;
+			return KR_STATE_FAIL;
+		}
+	}
+
 	if (knot_wire_get_aa(pkt->wire) && qtype == KNOT_RRTYPE_DNSKEY) {
 		const knot_rrset_t *ds = qry->zone_cut.trust_anchor;
 		if (ds && !kr_ds_algo_support(ds)) {
@@ -1151,6 +1177,10 @@ static int validate(kr_layer_t *ctx, knot_pkt_t *pkt)
 		ret = validate_records(req, pkt, req->rplan.pool, has_nsec3);
 		if (ret == KNOT_EDOWNGRADED) {
 			return KR_STATE_DONE;
+		} else if (ret == kr_error(E2BIG)) {
+			qry->flags.DNSSEC_BOGUS = true;
+			return KR_STATE_FAIL;
+
 		} else if (ret != 0) {
 			/* something exceptional - no DNS key, empty pointers etc
 			 * normally it shouldn't happen */
diff --git a/lib/resolve.c b/lib/resolve.c
index e9b118c5..e8a63489 100644
--- a/lib/resolve.c
+++ b/lib/resolve.c
@@ -479,6 +479,7 @@ int kr_resolver_init(module_array_t *modules, knot_mm_t *pool)
 
 	/* Default options (request flags). */
 	the_resolver->options.REORDER_RR = true;
+	the_resolver->vld_limit_crypto = KR_VLD_LIMIT_CRYPTO_DEFAULT;
 
 	/* Open resolution context */
 	the_resolver->trust_anchors = trie_create(NULL);
@@ -764,7 +765,9 @@ int kr_resolve_consume(struct kr_request *request, struct kr_transport **transpo
 
 	/* Do not finish with bogus answer. */
 	if (qry->flags.DNSSEC_BOGUS)  {
-		if (qry->flags.FORWARD || qry->flags.STUB) {
+		if (qry->flags.FORWARD || qry->flags.STUB
+				/* Probably CPU exhaustion attempt, so do not retry. */
+				|| qry->vld_limit_crypto_remains <= 0) {
 			return KR_STATE_FAIL;
 		}
 		/* Other servers might not have broken DNSSEC. */
@@ -1026,7 +1029,7 @@ int kr_request_set_extended_error(struct kr_request *request, int info_code, con
 		return KNOT_EDNS_EDE_NONE;
 	}
 
-	if (ede_priority(info_code) >= ede_priority(ede->info_code)) {
+	if (ede_priority(info_code) > ede_priority(ede->info_code)) {
 		ede->info_code = info_code;
 		ede->extra_text = extra_text;
 	}
diff --git a/lib/resolve.h b/lib/resolve.h
index 5fc66541..443fef29 100644
--- a/lib/resolve.h
+++ b/lib/resolve.h
@@ -163,6 +163,9 @@ struct kr_context
 
 	trie_t *trust_anchors;
 	trie_t *negative_anchors;
+	/** Validator's limit on the number of cryptographic steps for a single upstream packet. */
+	int32_t vld_limit_crypto;
+
 	struct kr_zonecut root_hints;
 	struct kr_cache cache;
 	unsigned cache_rtt_tout_retry_interval;
diff --git a/lib/rplan.h b/lib/rplan.h
index 4998bf05..98f13450 100644
--- a/lib/rplan.h
+++ b/lib/rplan.h
@@ -94,6 +94,12 @@ struct kr_query {
 	struct kr_qflags forward_flags;
 	uint32_t secret;
 	uint32_t uid; /**< Query iteration number, unique within the kr_rplan. */
+
+	/** Remaining limit; see kr_query::vld_limit_crypto docs */
+	int32_t  vld_limit_crypto_remains;
+	/** ::uid value to which this remaining limit applies. */
+	uint32_t vld_limit_uid;
+
 	uint64_t creation_time_mono; /* The time of query's creation (milliseconds).
 				 * Or time of creation of an oldest
 				 * ancestor if it is a subquery. */
diff --git a/meson.build b/meson.build
index e6066e7a..015d59f9 100644
--- a/meson.build
+++ b/meson.build
@@ -4,7 +4,7 @@ project(
   'knot-resolver',
   ['c', 'cpp'],
   license: 'GPLv3+',
-  version: '6.0.5',
+  version: '6.0.6',
   default_options: ['c_std=gnu11', 'b_ndebug=true'],
   meson_version: '>=0.49',
 )