Adding upstream version 5.7.1.upstream/5.7.1

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

10 files changed, 2603 insertions, 0 deletions

diff --git a/lib/dnssec.c b/lib/dnssec.c
new file mode 100644
index 0000000..262570c
--- /dev/null
+++ b/lib/dnssec.c
@@ -0,0 +1,629 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <libdnssec/binary.h>
+#include <libdnssec/crypto.h>
+#include <libdnssec/error.h>
+#include <libdnssec/key.h>
+#include <libdnssec/sign.h>
+#include <libknot/descriptor.h>
+#include <libknot/packet/wire.h>
+#include <libknot/rdataset.h>
+#include <libknot/rrset.h>
+#include <libknot/rrtype/dnskey.h>
+#include <libknot/rrtype/nsec.h>
+#include <libknot/rrtype/rrsig.h>
+
+#include "contrib/cleanup.h"
+#include "lib/defines.h"
+#include "lib/dnssec/nsec.h"
+#include "lib/dnssec/nsec3.h"
+#include "lib/dnssec/signature.h"
+#include "lib/dnssec.h"
+#include "lib/resolve.h"
+
+/* forward */
+static int kr_rrset_validate_with_key(kr_rrset_validation_ctx_t *vctx,
+	knot_rrset_t *covered, size_t key_pos, const struct dnssec_key *key);
+
+void kr_crypto_init(void)
+{
+	dnssec_crypto_init();
+}
+
+void kr_crypto_cleanup(void)
+{
+	dnssec_crypto_cleanup();
+}
+
+void kr_crypto_reinit(void)
+{
+	dnssec_crypto_reinit();
+}
+
+#define FLG_WILDCARD_EXPANSION 0x01 /**< Possibly generated by using wildcard expansion. */
+
+/**
+ * Check the RRSIG RR validity according to RFC4035 5.3.1 .
+ * @param flags     The flags are going to be set according to validation result.
+ * @param cov_labels Covered RRSet owner label count.
+ * @param rrsigs    rdata containing the signatures.
+ * @param key_alg   DNSKEY's algorithm.
+ * @param keytag    Used key tag.
+ * @param vctx->zone_name The name of the zone cut (and the DNSKEY).
+ * @param vctx->timestamp Validation time.
+ */
+static int validate_rrsig_rr(int *flags, int cov_labels,
+                             const knot_rdata_t *rrsigs,
+                             uint8_t key_alg,
+			     uint16_t keytag,
+                             kr_rrset_validation_ctx_t *vctx)
+{
+	if (kr_fails_assert(flags && rrsigs && vctx && vctx->zone_name)) {
+		return kr_error(EINVAL);
+	}
+	/* bullet 5 */
+	if (knot_rrsig_sig_expiration(rrsigs) < vctx->timestamp) {
+		vctx->rrs_counters.expired++;
+		return kr_error(EINVAL);
+	}
+	/* bullet 6 */
+	if (knot_rrsig_sig_inception(rrsigs) > vctx->timestamp) {
+		vctx->rrs_counters.notyet++;
+		return kr_error(EINVAL);
+	}
+	/* bullet 2 */
+	const knot_dname_t *signer_name = knot_rrsig_signer_name(rrsigs);
+	if (!signer_name || !knot_dname_is_equal(signer_name, vctx->zone_name)) {
+		vctx->rrs_counters.signer_invalid++;
+		return kr_error(EAGAIN);
+	}
+	/* bullet 4 */
+	{
+		int rrsig_labels = knot_rrsig_labels(rrsigs);
+		if (rrsig_labels > cov_labels) {
+			vctx->rrs_counters.labels_invalid++;
+			return kr_error(EINVAL);
+		}
+		if (rrsig_labels < cov_labels) {
+			*flags |= FLG_WILDCARD_EXPANSION;
+		}
+	}
+
+	/* bullet 7
+	 * Part checked elsewhere: key owner matching the zone_name. */
+	if (key_alg != knot_rrsig_alg(rrsigs) || keytag != knot_rrsig_key_tag(rrsigs)) {
+		vctx->rrs_counters.key_invalid++;
+		return kr_error(EINVAL);
+	}
+	/* bullet 8 */
+	/* Checked somewhere else. */
+	/* bullet 9 and 10 */
+	/* One of the requirements should be always fulfilled. */
+
+	return kr_ok();
+}
+
+/**
+ * Returns the number of labels that have been added by wildcard expansion.
+ * @param expanded Expanded wildcard.
+ * @param rrsigs   RRSet containing the signatures.
+ * @param sig_pos  Specifies the signature within the RRSIG RRSet.
+ * @return         Number of added labels, -1 on error.
+ */
+static inline int wildcard_radix_len_diff(const knot_dname_t *expanded,
+					  const knot_rdata_t *rrsig)
+{
+	if (!expanded || !rrsig) {
+		return -1;
+	}
+
+	return knot_dname_labels(expanded, NULL) - knot_rrsig_labels(rrsig);
+}
+
+int kr_rrset_validate(kr_rrset_validation_ctx_t *vctx, knot_rrset_t *covered)
+{
+	if (!vctx) {
+		return kr_error(EINVAL);
+	}
+	if (!vctx->pkt || !covered || !vctx->keys || !vctx->zone_name) {
+		return kr_error(EINVAL);
+	}
+
+	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 || ret == kr_error(E2BIG)) {
+			return ret;
+		}
+	}
+
+	return kr_error(ENOENT);
+}
+
+/** Assuming `rrs` was validated with `sig`, trim its TTL in case it's over-extended. */
+static bool trim_ttl(knot_rrset_t *rrs, const knot_rdata_t *sig,
+			const kr_rrset_validation_ctx_t *vctx)
+{
+	/* The trimming logic is a bit complicated.
+	 *
+	 * We respect configured ttl_min over the (signed) original TTL,
+	 * but we very much want to avoid TTLs over signature expiration,
+	 * as that could cause serious issues with downstream validators.
+	 */
+	const uint32_t ttl_max = MIN(
+			MAX(knot_rrsig_original_ttl(sig), vctx->ttl_min),
+			knot_rrsig_sig_expiration(sig) - vctx->timestamp
+	);
+	if (likely(rrs->ttl <= ttl_max))
+		return false;
+	if (kr_log_is_debug_qry(VALIDATOR, vctx->log_qry)) {
+		auto_free char *name_str = kr_dname_text(rrs->owner),
+				*type_str = kr_rrtype_text(rrs->type);
+		kr_log_q(vctx->log_qry, VALIDATOR, "trimming TTL of %s %s: %d -> %d\n",
+			name_str, type_str, (int)rrs->ttl, (int)ttl_max);
+	}
+	rrs->ttl = ttl_max;
+	return true;
+}
+
+
+typedef struct {
+	struct dnssec_key *key;
+	uint8_t alg;
+	uint16_t tag;
+} kr_svldr_key_t;
+
+struct kr_svldr_ctx {
+	kr_rrset_validation_ctx_t vctx;
+	array_t(kr_svldr_key_t) keys; // owned(malloc), also insides via svldr_key_*
+};
+
+static int svldr_key_new(const knot_rdata_t *rdata, const knot_dname_t *owner,
+			 kr_svldr_key_t *result)
+{
+	result->alg = knot_dnskey_alg(rdata);
+	result->key = NULL; // just silence analyzers
+	int ret = kr_dnssec_key_from_rdata(&result->key, owner, rdata->data, rdata->len);
+	if (likely(ret == 0))
+		result->tag = dnssec_key_get_keytag(result->key);
+	return ret;
+}
+static inline void svldr_key_del(kr_svldr_key_t *skey)
+{
+	kr_dnssec_key_free(&skey->key);
+}
+
+void kr_svldr_free_ctx(struct kr_svldr_ctx *ctx)
+{
+	if (!ctx) return;
+	for (ssize_t i = 0; i < ctx->keys.len; ++i)
+		svldr_key_del(&ctx->keys.at[i]);
+	array_clear(ctx->keys);
+	free_const(ctx->vctx.zone_name);
+	free(ctx);
+}
+struct kr_svldr_ctx * kr_svldr_new_ctx(const knot_rrset_t *ds, knot_rrset_t *dnskey,
+		const knot_rdataset_t *dnskey_sigs, uint32_t timestamp,
+		kr_rrset_validation_ctx_t *err_ctx)
+{
+	// Basic init.
+	struct kr_svldr_ctx *ctx = calloc(1, sizeof(*ctx));
+	if (unlikely(!ctx))
+		return NULL;
+	ctx->vctx.timestamp = timestamp; // .ttl_min is implicitly zero
+	ctx->vctx.zone_name = knot_dname_copy(ds->owner, NULL);
+	if (unlikely(!ctx->vctx.zone_name))
+		goto fail;
+	// Validate the DNSKEY set.
+	ctx->vctx.keys = dnskey;
+	if (kr_dnskeys_trusted(&ctx->vctx, dnskey_sigs, ds) != 0)
+		goto fail;
+	// Put usable DNSKEYs into ctx->keys.  (Some duplication of work happens, but OK.)
+	array_init(ctx->keys);
+	array_reserve(ctx->keys, dnskey->rrs.count);
+	knot_rdata_t *krr = dnskey->rrs.rdata;
+	for (int i = 0; i < dnskey->rrs.count; ++i, krr = knot_rdataset_next(krr)) {
+		if (!kr_dnssec_key_zsk(krr->data) || kr_dnssec_key_revoked(krr->data))
+			continue; // key not usable for this
+		kr_svldr_key_t key;
+		if (unlikely(svldr_key_new(krr, NULL/*seems OK here*/, &key) != 0))
+			goto fail;
+		array_push(ctx->keys, key);
+	}
+	return ctx;
+fail:
+	if (err_ctx)
+		memcpy(err_ctx, &ctx->vctx, sizeof(*err_ctx));
+	kr_svldr_free_ctx(ctx);
+	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)
+{
+	const int covered_labels = knot_dname_labels(rrs->owner, NULL)
+				- knot_dname_is_wildcard(rrs->owner);
+	knot_rdata_t *rdata_j = rrsigs->rdata;
+	for (uint16_t j = 0; j < rrsigs->count; ++j, rdata_j = knot_rdataset_next(rdata_j)) {
+		if (kr_fails_assert(knot_rrsig_type_covered(rdata_j) == rrs->type))
+			continue; //^^ not a problem but no reason to allow them in the API
+		int val_flgs = 0;
+		int retv = validate_rrsig_rr(&val_flgs, covered_labels, rdata_j,
+						key->alg, key->tag, vctx);
+		if (retv == kr_error(EAGAIN)) {
+			vctx->result = retv;
+			return vctx->result;
+		} 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;
+		if (kr_check_signature(rdata_j, key->key, rrs, trim_labels) == 0) {
+			trim_ttl(rrs, rdata_j, vctx);
+			vctx->result = kr_ok();
+			return vctx->result;
+		} else {
+			vctx->rrs_counters.crypto_invalid++;
+		}
+	}
+	vctx->result = kr_error(ENOENT);
+	return vctx->result;
+}
+/* The implementation basically performs "parts of" kr_rrset_validate(). */
+int kr_svldr_rrset(knot_rrset_t *rrs, const knot_rdataset_t *rrsigs,
+			struct kr_svldr_ctx *ctx)
+{
+	if (knot_dname_in_bailiwick(rrs->owner, ctx->vctx.zone_name) < 0) {
+		ctx->vctx.result = kr_error(EAGAIN);
+		return ctx->vctx.result;
+	}
+	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 || ctx->vctx.result == kr_error(E2BIG))
+			break;
+	}
+	return ctx->vctx.result;
+}
+
+
+/**
+ * Validate RRSet using a specific key.
+ * @param vctx    Pointer to validation context.
+ * @param covered RRSet covered by a signature.  It must be in canonical format.
+ * 		  TTL may get lowered.
+ * @param key_pos Position of the key to be validated with.
+ * @param key     Key to be used to validate.
+ *		  If NULL, then key from DNSKEY RRSet is used.
+ * @return        0 or error code, same as vctx->result.
+ */
+static int kr_rrset_validate_with_key(kr_rrset_validation_ctx_t *vctx,
+				knot_rrset_t *covered,
+				size_t key_pos, const struct dnssec_key *key)
+{
+	const knot_pkt_t *pkt         = vctx->pkt;
+	const knot_rrset_t *keys      = vctx->keys;
+	const knot_dname_t *zone_name = vctx->zone_name;
+	bool has_nsec3		      = vctx->has_nsec3;
+	struct dnssec_key *created_key = NULL;
+
+	if (!knot_dname_is_equal(keys->owner, zone_name)
+	   /* It's just caller's approximation that the RR is in that particular zone,
+	    * so we verify that in the following condition.
+	    * We MUST guard against attempts of zones signing out-of-bailiwick records. */
+	    || knot_dname_in_bailiwick(covered->owner, zone_name) < 0) {
+		vctx->result = kr_error(ENOENT);
+		return vctx->result;
+	}
+
+	const knot_rdata_t *key_rdata = knot_rdataset_at(&keys->rrs, key_pos);
+	if (key == NULL) {
+		int ret = kr_dnssec_key_from_rdata(&created_key, keys->owner,
+						   key_rdata->data, key_rdata->len);
+		if (ret != 0) {
+			vctx->result = ret;
+			return vctx->result;
+		}
+		key = created_key;
+	}
+	uint16_t keytag = dnssec_key_get_keytag(key);
+	const uint8_t key_alg = knot_dnskey_alg(key_rdata);
+	/* The asterisk does not count, RFC4034 3.1.3, paragraph 3. */
+	const int covered_labels = knot_dname_labels(covered->owner, NULL)
+				- knot_dname_is_wildcard(covered->owner);
+
+	for (uint16_t i = 0; i < vctx->rrs->len; ++i) {
+		/* Consider every RRSIG that matches and comes from the same query. */
+		const knot_rrset_t *rrsig = vctx->rrs->at[i]->rr;
+		const bool ok = vctx->rrs->at[i]->qry_uid == vctx->qry_uid
+			&& rrsig->type == KNOT_RRTYPE_RRSIG
+			&& rrsig->rclass == covered->rclass
+			&& knot_dname_is_equal(rrsig->owner, covered->owner);
+		if (!ok)
+			continue;
+
+		knot_rdata_t *rdata_j = rrsig->rrs.rdata;
+		for (uint16_t j = 0; j < rrsig->rrs.count; ++j, rdata_j = knot_rdataset_next(rdata_j)) {
+			int val_flgs = 0;
+			int trim_labels = 0;
+			if (knot_rrsig_type_covered(rdata_j) != covered->type) {
+				continue;
+			}
+			kr_rank_set(&vctx->rrs->at[i]->rank, KR_RANK_BOGUS); /* defensive style */
+			vctx->rrs_counters.matching_name_type++;
+			int retv = validate_rrsig_rr(&val_flgs, covered_labels, rdata_j,
+							key_alg, keytag, vctx);
+			if (retv == kr_error(EAGAIN)) {
+				vctx->result = retv;
+				goto finish;
+			} else if (retv != 0) {
+				continue;
+			}
+			if (val_flgs & FLG_WILDCARD_EXPANSION) {
+				trim_labels = wildcard_radix_len_diff(covered->owner, rdata_j);
+				if (trim_labels < 0) {
+					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;
+			}
+			if (val_flgs & FLG_WILDCARD_EXPANSION) {
+				int ret = 0;
+				if (!has_nsec3) {
+					ret = kr_nsec_wildcard_answer_response_check(pkt, KNOT_AUTHORITY, covered->owner);
+				} else {
+					ret = kr_nsec3_wildcard_answer_response_check(pkt, KNOT_AUTHORITY, covered->owner, trim_labels - 1);
+					if (ret == kr_error(KNOT_ERANGE)) {
+						ret = 0;
+						vctx->flags |= KR_DNSSEC_VFLG_OPTOUT;
+					}
+				}
+				if (ret != 0) {
+					vctx->rrs_counters.nsec_invalid++;
+					continue;
+				}
+				vctx->flags |= KR_DNSSEC_VFLG_WEXPAND;
+			}
+
+			trim_ttl(covered, rdata_j, vctx);
+
+			kr_rank_set(&vctx->rrs->at[i]->rank, KR_RANK_SECURE); /* upgrade from bogus */
+			vctx->result = kr_ok();
+			goto finish;
+		}
+	}
+	/* No applicable key found, cannot be validated. */
+	vctx->result = kr_error(ENOENT);
+finish:
+	kr_dnssec_key_free(&created_key);
+	return vctx->result;
+}
+
+bool kr_ds_algo_support(const knot_rrset_t *ta)
+{
+	if (kr_fails_assert(ta && ta->type == KNOT_RRTYPE_DS && ta->rclass == KNOT_CLASS_IN))
+		return false;
+	/* Check if at least one DS has a usable algorithm pair. */
+	knot_rdata_t *rdata_i = ta->rrs.rdata;
+	for (uint16_t i = 0; i < ta->rrs.count;
+			++i, rdata_i = knot_rdataset_next(rdata_i)) {
+		if (dnssec_algorithm_digest_support(knot_ds_digest_type(rdata_i))
+		    && dnssec_algorithm_key_support(knot_ds_alg(rdata_i))) {
+			return true;
+		}
+	}
+	return false;
+}
+
+int kr_dnskeys_trusted(kr_rrset_validation_ctx_t *vctx, const knot_rdataset_t *sigs,
+			const knot_rrset_t *ta)
+{
+	knot_rrset_t *keys = vctx->keys;
+	const bool ok = keys && ta && ta->rrs.count && ta->rrs.rdata
+			&& ta->type == KNOT_RRTYPE_DS
+			&& knot_dname_is_equal(ta->owner, keys->owner);
+	if (kr_fails_assert(ok))
+		return kr_error(EINVAL);
+
+	/* RFC4035 5.2, bullet 1
+	 * The supplied DS record has been authenticated.
+	 * It has been validated or is part of a configured trust anchor.
+	 */
+	knot_rdata_t *krr = keys->rrs.rdata;
+	for (int i = 0; i < keys->rrs.count; ++i, krr = knot_rdataset_next(krr)) {
+		/* RFC4035 5.3.1, bullet 8 */ /* ZSK */
+		if (!kr_dnssec_key_zsk(krr->data) || kr_dnssec_key_revoked(krr->data))
+			continue;
+
+		kr_svldr_key_t key;
+		if (svldr_key_new(krr, keys->owner, &key) != 0)
+			continue; // it might e.g. be malformed
+
+		int ret = kr_authenticate_referral(ta, key.key);
+		if (ret == 0)
+			ret = kr_svldr_rrset_with_key(keys, sigs, vctx, &key);
+		svldr_key_del(&key);
+		if (ret == 0 || ret == kr_error(E2BIG)) {
+			kr_assert(vctx->result == 0);
+			return vctx->result;
+		}
+	}
+
+	/* No useable key found */
+	vctx->result = kr_error(ENOENT);
+	return vctx->result;
+}
+
+bool kr_dnssec_key_zsk(const uint8_t *dnskey_rdata)
+{
+	return knot_wire_read_u16(dnskey_rdata) & 0x0100;
+}
+
+bool kr_dnssec_key_ksk(const uint8_t *dnskey_rdata)
+{
+	return knot_wire_read_u16(dnskey_rdata) & 0x0001;
+}
+
+/** Return true if the DNSKEY is revoked. */
+bool kr_dnssec_key_revoked(const uint8_t *dnskey_rdata)
+{
+	return knot_wire_read_u16(dnskey_rdata) & 0x0080;
+}
+
+int kr_dnssec_key_tag(uint16_t rrtype, const uint8_t *rdata, size_t rdlen)
+{
+	if (!rdata || rdlen == 0 || (rrtype != KNOT_RRTYPE_DS && rrtype != KNOT_RRTYPE_DNSKEY)) {
+		return kr_error(EINVAL);
+	}
+	if (rrtype == KNOT_RRTYPE_DS) {
+		return knot_wire_read_u16(rdata);
+	} else if (rrtype == KNOT_RRTYPE_DNSKEY) {
+		struct dnssec_key *key = NULL;
+		int ret = kr_dnssec_key_from_rdata(&key, NULL, rdata, rdlen);
+		if (ret != 0) {
+			return ret;
+		}
+		uint16_t keytag = dnssec_key_get_keytag(key);
+		kr_dnssec_key_free(&key);
+		return keytag;
+	} else {
+		return kr_error(EINVAL);
+	}
+}
+
+int kr_dnssec_key_match(const uint8_t *key_a_rdata, size_t key_a_rdlen,
+                        const uint8_t *key_b_rdata, size_t key_b_rdlen)
+{
+	dnssec_key_t *key_a = NULL, *key_b = NULL;
+	int ret = kr_dnssec_key_from_rdata(&key_a, NULL, key_a_rdata, key_a_rdlen);
+	if (ret != 0) {
+		return ret;
+	}
+	ret = kr_dnssec_key_from_rdata(&key_b, NULL, key_b_rdata, key_b_rdlen);
+	if (ret != 0) {
+		dnssec_key_free(key_a);
+		return ret;
+	}
+	/* If the algorithm and the public key match, we can be sure
+	 * that they are the same key. */
+	ret = kr_error(ENOENT);
+	dnssec_binary_t pk_a, pk_b;
+	if (dnssec_key_get_algorithm(key_a) == dnssec_key_get_algorithm(key_b) &&
+	    dnssec_key_get_pubkey(key_a, &pk_a) == DNSSEC_EOK &&
+	    dnssec_key_get_pubkey(key_b, &pk_b) == DNSSEC_EOK) {
+		if (pk_a.size == pk_b.size && memcmp(pk_a.data, pk_b.data, pk_a.size) == 0) {
+			ret = 0;
+		}
+	}
+	dnssec_key_free(key_a);
+	dnssec_key_free(key_b);
+	return ret;
+}
+
+int kr_dnssec_key_from_rdata(struct dnssec_key **key, const knot_dname_t *kown, const uint8_t *rdata, size_t rdlen)
+{
+	if (!key || !rdata || rdlen == 0) {
+		return kr_error(EINVAL);
+	}
+
+	dnssec_key_t *new_key = NULL;
+	const dnssec_binary_t binary_key = {
+		.size = rdlen,
+		.data = (uint8_t *)rdata
+	};
+
+	int ret = dnssec_key_new(&new_key);
+	if (ret != DNSSEC_EOK) {
+		return kr_error(ENOMEM);
+	}
+	ret = dnssec_key_set_rdata(new_key, &binary_key);
+	if (ret != DNSSEC_EOK) {
+		dnssec_key_free(new_key);
+		return kr_error(ret);
+	}
+	if (kown) {
+		ret = dnssec_key_set_dname(new_key, kown);
+		if (ret != DNSSEC_EOK) {
+			dnssec_key_free(new_key);
+			return kr_error(ENOMEM);
+		}
+	}
+
+	*key = new_key;
+	return kr_ok();
+}
+
+void kr_dnssec_key_free(struct dnssec_key **key)
+{
+	if (kr_fails_assert(key))
+		return;
+
+	dnssec_key_free(*key);
+	*key = NULL;
+}
+
+int kr_dnssec_matches_name_and_type(const ranked_rr_array_t *rrs, uint32_t qry_uid,
+				    const knot_dname_t *name, uint16_t type)
+{
+	int ret = kr_error(ENOENT);
+	for (size_t i = 0; i < rrs->len; ++i) {
+		const ranked_rr_array_entry_t *entry = rrs->at[i];
+		if (kr_fails_assert(!entry->in_progress))
+			return kr_error(EINVAL);
+		const knot_rrset_t *nsec = entry->rr;
+		if (entry->qry_uid != qry_uid || entry->yielded) {
+			continue;
+		}
+		if (nsec->type != KNOT_RRTYPE_NSEC &&
+		    nsec->type != KNOT_RRTYPE_NSEC3) {
+			continue;
+		}
+		if (!kr_rank_test(entry->rank, KR_RANK_SECURE)) {
+			continue;
+		}
+		if (nsec->type == KNOT_RRTYPE_NSEC) {
+			ret = kr_nsec_matches_name_and_type(nsec, name, type);
+		} else {
+			ret = kr_nsec3_matches_name_and_type(nsec, name, type);
+		}
+		if (ret == kr_ok()) {
+			return kr_ok();
+		} else if (ret != kr_error(ENOENT)) {
+			return ret;
+		}
+	}
+	return ret;
+}
diff --git a/lib/dnssec.h b/lib/dnssec.h
new file mode 100644
index 0000000..ca737cf
--- /dev/null
+++ b/lib/dnssec.h
@@ -0,0 +1,192 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include "lib/defines.h"
+#include "lib/utils.h"
+#include <libknot/packet/pkt.h>
+
+/**
+ * Initialise cryptographic back-end.
+ */
+KR_EXPORT
+void kr_crypto_init(void);
+
+/**
+ * De-initialise cryptographic back-end.
+ */
+KR_EXPORT
+void kr_crypto_cleanup(void);
+
+/**
+ * Re-initialise cryptographic back-end.
+ * @note Must be called after fork() in the child.
+ */
+KR_EXPORT
+void kr_crypto_reinit(void);
+
+#define KR_DNSSEC_VFLG_WEXPAND 0x01
+#define KR_DNSSEC_VFLG_OPTOUT  0x02
+
+/** DNSSEC validation context. */
+struct kr_rrset_validation_ctx {
+	const knot_pkt_t *pkt;		/*!< Packet to be validated. */
+	ranked_rr_array_t *rrs;		/*!< List of preselected RRs to be validated. */
+	knot_section_t section_id;	/*!< Section to work with. */
+	knot_rrset_t *keys;		/*!< DNSKEY RRSet; TTLs may get lowered when validating this set. */
+        const knot_dname_t *zone_name;	/*!< Name of the zone containing the RRSIG RRSet. */
+	uint32_t timestamp;		/*!< Validation time. */
+	uint32_t ttl_min;		/*!< See trim_ttl() for details. */
+        bool has_nsec3;			/*!< Whether to use NSEC3 validation. */
+	uint32_t qry_uid;		/*!< Current query uid. */
+	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.
+	 *
+	 * ENOENT: the usual, no suitable signature found
+	 * EAGAIN: encountered a different signer name
+	 * +others
+	 */
+	int result;
+	const struct kr_query *log_qry; /*!< The query; just for logging purposes. */
+	struct {
+		unsigned int matching_name_type;	/*!< Name + type matches */
+		unsigned int expired;
+		unsigned int notyet;
+		unsigned int signer_invalid;		/*!< Signer is not zone apex */
+		unsigned int labels_invalid;		/*!< Number of labels in RRSIG */
+		unsigned int key_invalid;		/*!< Algorithm/keytag/key owner */
+		unsigned int crypto_invalid;
+		unsigned int nsec_invalid;
+	} rrs_counters;	/*!< Error counters for single RRset validation. */
+};
+
+typedef struct kr_rrset_validation_ctx kr_rrset_validation_ctx_t;
+
+/**
+ * Validate RRSet.
+ * @param vctx    Pointer to validation context.
+ * @param covered RRSet covered by a signature. It must be in canonical format.
+ * 		  Its TTL may get lowered.
+ * @return        0 or kr_error() code, same as vctx->result (see its docs).
+ */
+int kr_rrset_validate(kr_rrset_validation_ctx_t *vctx, knot_rrset_t *covered);
+
+/**
+ * Return true iff the RRset contains at least one usable DS.  See RFC6840 5.2.
+ */
+KR_EXPORT KR_PURE
+bool kr_ds_algo_support(const knot_rrset_t *ta);
+
+/**
+ * Check whether the DNSKEY rrset matches the supplied trust anchor RRSet.
+ *
+ * @param vctx  Pointer to validation context.  Note that TTL of vctx->keys may get lowered.
+ * @param sigs  RRSIGs for this DNSKEY set
+ * @param ta    Trusted DS RRSet against which to validate the DNSKEY RRSet.
+ * @return      0 or error code, same as vctx->result.
+ */
+int kr_dnskeys_trusted(kr_rrset_validation_ctx_t *vctx, const knot_rdataset_t *sigs,
+			const knot_rrset_t *ta);
+
+/** Return true if the DNSKEY can be used as a ZSK.  */
+KR_EXPORT KR_PURE
+bool kr_dnssec_key_zsk(const uint8_t *dnskey_rdata);
+
+/** Return true if the DNSKEY indicates being KSK (=> has SEP).  */
+KR_EXPORT KR_PURE
+bool kr_dnssec_key_ksk(const uint8_t *dnskey_rdata);
+
+/** Return true if the DNSKEY is revoked. */
+KR_EXPORT KR_PURE
+bool kr_dnssec_key_revoked(const uint8_t *dnskey_rdata);
+
+/** Return DNSKEY tag.
+  * @param rrtype RR type (either DS or DNSKEY are supported)
+  * @param rdata  Key/digest RDATA.
+  * @param rdlen  RDATA length.
+  * @return Key tag (positive number), or an error code
+  */
+KR_EXPORT KR_PURE
+int kr_dnssec_key_tag(uint16_t rrtype, const uint8_t *rdata, size_t rdlen);
+
+/** Return 0 if the two keys are identical.
+  * @note This compares RDATA only, algorithm and public key must match.
+  * @param key_a_rdata First key RDATA
+  * @param key_a_rdlen First key RDATA length
+  * @param key_b_rdata Second key RDATA
+  * @param key_b_rdlen Second key RDATA length
+  * @return 0 if they match or an error code
+  */
+KR_EXPORT KR_PURE
+int kr_dnssec_key_match(const uint8_t *key_a_rdata, size_t key_a_rdlen,
+                        const uint8_t *key_b_rdata, size_t key_b_rdlen);
+
+/* Opaque DNSSEC key struct; forward declaration from libdnssec. */
+struct dnssec_key;
+
+/**
+ * Construct a DNSSEC key.
+ * @param key   Pointer to be set to newly created DNSSEC key.
+ * @param kown  DNSKEY owner name.
+ * @param rdata DNSKEY RDATA
+ * @param rdlen DNSKEY RDATA length
+ * @return 0 or error code; in particular: DNSSEC_INVALID_KEY_ALGORITHM
+ */
+int kr_dnssec_key_from_rdata(struct dnssec_key **key, const knot_dname_t *kown, const uint8_t *rdata, size_t rdlen);
+
+/**
+ * Frees the DNSSEC key.
+ * @param key Pointer to freed key.
+ */
+void kr_dnssec_key_free(struct dnssec_key **key);
+
+/**
+ * Checks whether NSEC/NSEC3 RR selected by iterator matches the supplied name and type.
+ * @param rrs     Records selected by iterator.
+ * @param qry_uid Query unique identifier where NSEC/NSEC3 belongs to.
+ * @param name    Name to be checked.
+ * @param type    Type to be checked.
+ * @return        0 or error code.
+ */
+int kr_dnssec_matches_name_and_type(const ranked_rr_array_t *rrs, uint32_t qry_uid,
+				    const knot_dname_t *name, uint16_t type);
+
+
+/* Simple validator API.  Main use case: prefill module, i.e. RRs from a zone file. */
+
+/** Opaque context for simple validator. */
+struct kr_svldr_ctx;
+/**
+ * Create new context for validating within a given zone.
+ *
+ * - `ds` is assumed to be trusted, and it's used to validate `dnskey+dnskey_sigs`.
+ * - The TTL of `dnskey` may get trimmed.
+ * - The insides are placed on malloc heap (use _free_ctx).
+ * - `err_ctx` is optional, for use when error happens (but avoid the inside pointers)
+ */
+KR_EXPORT
+struct kr_svldr_ctx * kr_svldr_new_ctx(const knot_rrset_t *ds, knot_rrset_t *dnskey,
+		const knot_rdataset_t *dnskey_sigs, uint32_t timestamp,
+		kr_rrset_validation_ctx_t *err_ctx);
+/** Free the context.  Passing NULL is OK. */
+KR_EXPORT
+void kr_svldr_free_ctx(struct kr_svldr_ctx *ctx);
+/**
+ * Validate an RRset with the associated signatures; assume no wildcard expansions.
+ *
+ * - It's caller's responsibility that rrsigs have matching owner, class and type.
+ * - The TTL of `rrs` may get trimmed.
+ * - If it's a wildcard other than in its simple `*.` form, it may fail to validate.
+ * - More generally, non-existence proofs are not supported.
+ * @return  0 or kr_error() code, same as kr_rrset_validation_ctx::result (see its docs).
+ */
+KR_EXPORT
+int kr_svldr_rrset(knot_rrset_t *rrs, const knot_rdataset_t *rrsigs,
+			struct kr_svldr_ctx *ctx);
+
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);
+	}
+}
diff --git a/lib/dnssec/nsec.h b/lib/dnssec/nsec.h
new file mode 100644
index 0000000..a173fa5
--- /dev/null
+++ b/lib/dnssec/nsec.h
@@ -0,0 +1,69 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include <libknot/packet/pkt.h>
+
+#include "lib/layer/iterate.h"
+
+/**
+ * Check bitmap that child names are contained in the same zone.
+ * @note see RFC6840 4.1.
+ * @param bm      Bitmap from NSEC or NSEC3.
+ * @param bm_size Bitmap size.
+ * @return 0 if they are, >0 if not (abs(ENOENT)), <0 on error.
+ */
+int kr_nsec_children_in_zone_check(const uint8_t *bm, uint16_t bm_size);
+
+/**
+ * Check an NSEC or NSEC3 bitmap for NODATA for a type.
+ * @param bm      Bitmap.
+ * @param bm_size Bitmap size.
+ * @param type    RR type to check.
+ * @param owner   NSEC record owner.
+ * @note This includes special checks for zone cuts, e.g. from RFC 6840 sec. 4.
+ * @return 0, abs(ENOENT) (no proof), kr_error(EINVAL)
+ */
+int kr_nsec_bitmap_nodata_check(const uint8_t *bm, uint16_t bm_size, uint16_t type, const knot_dname_t *owner);
+
+/**
+ * Wildcard answer response check (RFC4035 3.1.3.3).
+ * @param pkt        Packet structure to be processed.
+ * @param section_id Packet section to be processed.
+ * @param sname      Name to be checked.
+ * @return           0 or error code.
+ */
+int kr_nsec_wildcard_answer_response_check(const knot_pkt_t *pkt, knot_section_t section_id,
+                                           const knot_dname_t *sname);
+
+/**
+ * Search for a negative proof for sname+stype among validated NSECs.
+ *
+ * @param rrrs       list of RRs to search; typically kr_request::auth_selected
+ * @param qry_uid    only consider NSECs from this packet, for better efficiency
+ * @return           negative error code, or PKT_NXDOMAIN | PKT_NODATA (both for NXDOMAIN)
+ */
+int kr_nsec_negative(const ranked_rr_array_t *rrrs, uint32_t qry_uid,
+			const knot_dname_t *sname, uint16_t stype);
+
+/**
+ * Referral to unsigned subzone check (RFC4035 5.2).
+ *
+ * @param rrrs       list of RRs to search; typically kr_request::auth_selected
+ * @param qry_uid    only consider NSECs from this packet, for better efficiency
+ * @return           0 or negative error code, in particular DNSSEC_NOT_FOUND
+ */
+int kr_nsec_ref_to_unsigned(const ranked_rr_array_t *rrrs, uint32_t qry_uid,
+				const knot_dname_t *sname);
+
+/**
+ * Checks whether supplied NSEC RR matches the supplied name and type.
+ * @param nsec  NSEC RR.
+ * @param name  Name to be checked.
+ * @param type  Type to be checked.  Only use with NS!  TODO (+copy&paste NSEC3)
+ * @return      0 or error code.
+ */
+int kr_nsec_matches_name_and_type(const knot_rrset_t *nsec,
+				   const knot_dname_t *name, uint16_t type);
diff --git a/lib/dnssec/nsec3.c b/lib/dnssec/nsec3.c
new file mode 100644
index 0000000..4199f25
--- /dev/null
+++ b/lib/dnssec/nsec3.c
@@ -0,0 +1,734 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <string.h>
+
+#include <libdnssec/binary.h>
+#include <libdnssec/error.h>
+#include <libdnssec/nsec.h>
+#include <libknot/descriptor.h>
+#include <contrib/base32hex.h>
+#include <libknot/rrset.h>
+#include <libknot/rrtype/nsec3.h>
+
+#include "lib/defines.h"
+#include "lib/dnssec/nsec.h"
+#include "lib/dnssec/nsec3.h"
+#include "lib/utils.h"
+
+#define OPT_OUT_BIT 0x01
+
+//#define FLG_CLOSEST_ENCLOSER (1 << 0)
+#define FLG_CLOSEST_PROVABLE_ENCLOSER (1 << 1)
+#define FLG_NAME_COVERED (1 << 2)
+#define FLG_NAME_MATCHED (1 << 3)
+#define FLG_TYPE_BIT_MISSING (1 << 4)
+#define FLG_CNAME_BIT_MISSING (1 << 5)
+
+/**
+ * Obtains NSEC3 parameters from RR.
+ * @param params NSEC3 parameters structure to be set.
+ * @param nsec3  NSEC3 RR containing the parameters.
+ * @return       0 or error code.
+ */
+static int nsec3_parameters(dnssec_nsec3_params_t *params, const knot_rrset_t *nsec3)
+{
+	if (kr_fails_assert(params && nsec3))
+		return kr_error(EINVAL);
+
+	const knot_rdata_t *rr = knot_rdataset_at(&nsec3->rrs, 0);
+	if (kr_fails_assert(rr))
+		return kr_error(EINVAL);
+
+	/* Every NSEC3 RR contains data from NSEC3PARAMS. */
+	const size_t SALT_OFFSET = 5; /* First 5 octets contain { Alg, Flags, Iterations, Salt length } */
+	dnssec_binary_t rdata = {
+		.size = SALT_OFFSET + (size_t)knot_nsec3_salt_len(nsec3->rrs.rdata),
+		.data = /*const-cast*/(uint8_t *)rr->data,
+	};
+	if (rdata.size > rr->len)
+		return kr_error(EMSGSIZE);
+
+	int ret = dnssec_nsec3_params_from_rdata(params, &rdata);
+	if (ret != DNSSEC_EOK)
+		return kr_error(EINVAL);
+
+	return kr_ok();
+}
+
+/**
+ * Computes a hash of a given domain name.
+ * @param hash   Resulting hash, must be freed.
+ * @param params NSEC3 parameters.
+ * @param name   Domain name to be hashed.
+ * @return       0 or error code.
+ */
+static int hash_name(dnssec_binary_t *hash, const dnssec_nsec3_params_t *params,
+                     const knot_dname_t *name)
+{
+	if (kr_fails_assert(hash && params))
+		return kr_error(EINVAL);
+	if (!name)
+		return kr_error(EINVAL);
+	if (kr_fails_assert(!kr_nsec3_limited_params(params))) {
+		/* This if is mainly defensive; it shouldn't happen. */
+		return kr_error(EINVAL);
+	}
+
+	dnssec_binary_t dname = {
+		.size = knot_dname_size(name),
+		.data = (uint8_t *) name,
+	};
+
+	int ret = dnssec_nsec3_hash(&dname, params, hash);
+	if (ret != DNSSEC_EOK) {
+		return kr_error(EINVAL);
+	}
+
+	return kr_ok();
+}
+
+/**
+ * Read hash from NSEC3 owner name and store its binary form.
+ * @param hash          Buffer to be written.
+ * @param max_hash_size Maximal has size.
+ * @param nsec3         NSEC3 RR.
+ * @return              0 or error code.
+ */
+static int read_owner_hash(dnssec_binary_t *hash, size_t max_hash_size, const knot_rrset_t *nsec3)
+{
+	if (kr_fails_assert(hash && nsec3 && hash->data))
+		return kr_error(EINVAL);
+
+	int32_t ret = base32hex_decode(nsec3->owner + 1, nsec3->owner[0], hash->data, max_hash_size);
+	if (ret < 0)
+		return kr_error(EILSEQ);
+	hash->size = ret;
+
+	return kr_ok();
+}
+
+#define MAX_HASH_BYTES 64
+/**
+ * Closest (provable) encloser match (RFC5155 7.2.1, bullet 1).
+ * @param flags   Flags to be set according to check outcome.
+ * @param nsec3   NSEC3 RR.
+ * @param name    Name to be checked.
+ * @param skipped Number of skipped labels to find closest (provable) match.
+ * @return        0 or error code.
+ */
+static int closest_encloser_match(int *flags, const knot_rrset_t *nsec3,
+                                  const knot_dname_t *name, unsigned *skipped)
+{
+	if (kr_fails_assert(flags && nsec3 && name && skipped))
+		return kr_error(EINVAL);
+
+	uint8_t hash_data[MAX_HASH_BYTES] = {0, };
+	dnssec_binary_t owner_hash = { 0, hash_data };
+	dnssec_nsec3_params_t params = { 0, };
+	dnssec_binary_t name_hash = { 0, };
+
+	int ret = read_owner_hash(&owner_hash, MAX_HASH_BYTES, nsec3);
+	if (ret != 0)
+		goto fail;
+
+	ret = nsec3_parameters(&params, nsec3);
+	if (ret != 0)
+		goto fail;
+
+	/* Root label has no encloser */
+	if (!name[0]) {
+		ret = kr_error(ENOENT);
+		goto fail;
+	}
+
+	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)
+			goto fail;
+
+		if ((owner_hash.size == name_hash.size) &&
+		    (memcmp(owner_hash.data, name_hash.data, owner_hash.size) == 0)) {
+			dnssec_binary_free(&name_hash);
+			*flags |= FLG_CLOSEST_PROVABLE_ENCLOSER;
+			break;
+		}
+
+		dnssec_binary_free(&name_hash);
+
+		if (!encloser[0])
+			break;
+		encloser = knot_wire_next_label(encloser, NULL);
+		++(*skipped);
+	}
+
+	ret = kr_ok();
+
+fail:
+	if (params.salt.data)
+		dnssec_nsec3_params_free(&params);
+	if (name_hash.data)
+		dnssec_binary_free(&name_hash);
+	return ret;
+}
+
+/**
+ * Checks whether NSEC3 RR covers the supplied name (RFC5155 7.2.1, bullet 2).
+ * @param flags Flags to be set according to check outcome.
+ * @param nsec3 NSEC3 RR.
+ * @param name  Name to be checked.
+ * @return      0 or error code.
+ */
+static int covers_name(int *flags, const knot_rrset_t *nsec3, const knot_dname_t *name)
+{
+	if (kr_fails_assert(flags && nsec3 && name))
+		return kr_error(EINVAL);
+
+	uint8_t hash_data[MAX_HASH_BYTES] = { 0, };
+	dnssec_binary_t owner_hash = { 0, hash_data };
+	dnssec_nsec3_params_t params = { 0, };
+	dnssec_binary_t name_hash = { 0, };
+
+	int ret = read_owner_hash(&owner_hash, MAX_HASH_BYTES, nsec3);
+	if (ret != 0)
+		goto fail;
+
+	ret = nsec3_parameters(&params, nsec3);
+	if (ret != 0)
+		goto fail;
+
+	ret = hash_name(&name_hash, &params, name);
+	if (ret != 0)
+		goto fail;
+
+	uint8_t next_size = knot_nsec3_next_len(nsec3->rrs.rdata);
+	const uint8_t *next_hash = knot_nsec3_next(nsec3->rrs.rdata);
+
+	if ((next_size > 0) && (owner_hash.size == next_size) && (name_hash.size == next_size)) {
+		/* All hash lengths must be same. */
+		const uint8_t *ownerd = owner_hash.data;
+		const uint8_t *nextd = next_hash;
+		int covered = 0;
+		int greater_then_owner = (memcmp(ownerd, name_hash.data, next_size) < 0);
+		int less_then_next = (memcmp(name_hash.data, nextd, next_size) < 0);
+		if (memcmp(ownerd, nextd, next_size) < 0) {
+			/*
+			 * 0 (...) owner ... next (...) MAX
+			 *                ^
+			 *                name
+			 * ==>
+			 * (owner < name) && (name < next)
+			 */
+			covered = ((greater_then_owner) && (less_then_next));
+		} else {
+			/*
+			 * owner ... MAX, 0 ... next
+			 *        ^     ^    ^
+			 *        name  name name
+			 * =>
+			 * (owner < name) || (name < next)
+			 */
+			covered = ((greater_then_owner) || (less_then_next));
+		}
+
+		if (covered) {
+			*flags |= FLG_NAME_COVERED;
+
+			uint8_t nsec3_flags = knot_nsec3_flags(nsec3->rrs.rdata);
+			if (nsec3_flags & ~OPT_OUT_BIT) {
+				/* RFC5155 3.1.2 */
+				ret = kr_error(EINVAL);
+			} else {
+				ret = kr_ok();
+			}
+		}
+	}
+
+fail:
+	if (params.salt.data)
+		dnssec_nsec3_params_free(&params);
+	if (name_hash.data)
+		dnssec_binary_free(&name_hash);
+	return ret;
+}
+
+/**
+ * Checks whether NSEC3 RR has the opt-out bit set.
+ * @param flags Flags to be set according to check outcome.
+ * @param nsec3 NSEC3 RR.
+ * @param name  Name to be checked.
+ * @return      0 or error code.
+ */
+static bool has_optout(const knot_rrset_t *nsec3)
+{
+	if (!nsec3)
+		return false;
+
+	uint8_t nsec3_flags = knot_nsec3_flags(nsec3->rrs.rdata);
+	if (nsec3_flags & ~OPT_OUT_BIT) {
+		/* RFC5155 3.1.2 */
+		return false;
+	}
+
+	return nsec3_flags & OPT_OUT_BIT;
+}
+
+/**
+ * Checks whether NSEC3 RR matches the supplied name.
+ * @param flags Flags to be set according to check outcome.
+ * @param nsec3 NSEC3 RR.
+ * @param name  Name to be checked.
+ * @return      0 if matching, >0 if not (abs(ENOENT)), or error code (<0).
+ */
+static int matches_name(const knot_rrset_t *nsec3, const knot_dname_t *name)
+{
+	if (kr_fails_assert(nsec3 && name))
+		return kr_error(EINVAL);
+
+	uint8_t hash_data[MAX_HASH_BYTES] = { 0, };
+	dnssec_binary_t owner_hash = { 0, hash_data };
+	dnssec_nsec3_params_t params = { 0, };
+	dnssec_binary_t name_hash = { 0, };
+
+	int ret = read_owner_hash(&owner_hash, MAX_HASH_BYTES, nsec3);
+	if (ret != 0)
+		goto fail;
+
+	ret = nsec3_parameters(&params, nsec3);
+	if (ret != 0)
+		goto fail;
+
+	ret = hash_name(&name_hash, &params, name);
+	if (ret != 0)
+		goto fail;
+
+	if ((owner_hash.size == name_hash.size) &&
+	    (memcmp(owner_hash.data, name_hash.data, owner_hash.size) == 0)) {
+		ret = kr_ok();
+	} else {
+		ret = abs(ENOENT);
+	}
+
+fail:
+	if (params.salt.data)
+		dnssec_nsec3_params_free(&params);
+	if (name_hash.data)
+		dnssec_binary_free(&name_hash);
+	return ret;
+}
+#undef MAX_HASH_BYTES
+
+/**
+ * Prepends an asterisk label to given name.
+ *
+ * @param tgt  Target buffer to write domain name into.
+ * @param name Name to be added to the asterisk.
+ * @return     Size of the resulting name or error code.
+ */
+static int prepend_asterisk(uint8_t *tgt, size_t maxlen, const knot_dname_t *name)
+{
+	if (kr_fails_assert(maxlen >= 3))
+		return kr_error(EINVAL);
+	memcpy(tgt, "\1*", 3);
+	return knot_dname_to_wire(tgt + 2, name, maxlen - 2);
+}
+
+/**
+ * Closest encloser proof (RFC5155 7.2.1).
+ * @note No RRSIGs are validated.
+ * @param pkt                     Packet structure to be processed.
+ * @param section_id              Packet section to be processed.
+ * @param sname                   Name to be checked.
+ * @param encloser_name           Returned matching encloser name, if found.
+ * @param matching_encloser_nsec3 Pointer to matching encloser NSEC RRSet.
+ * @param covering_next_nsec3     Pointer to covering next closer NSEC3 RRSet.
+ * @return                        0 or error code.
+ */
+static int closest_encloser_proof(const knot_pkt_t *pkt,
+				  knot_section_t section_id,
+				  const knot_dname_t *sname,
+				  const knot_dname_t **encloser_name,
+				  const knot_rrset_t **matching_encloser_nsec3,
+				  const knot_rrset_t **covering_next_nsec3)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, section_id);
+	if (!sec || !sname)
+		return kr_error(EINVAL);
+
+	const knot_rrset_t *matching = NULL;
+	const knot_rrset_t *covering = NULL;
+
+	int flags = 0;
+	const knot_dname_t *next_closer = NULL;
+	for (unsigned i = 0; i < sec->count; ++i) {
+		const knot_rrset_t *rrset = knot_pkt_rr(sec, i);
+		if (rrset->type != KNOT_RRTYPE_NSEC3)
+			continue;
+		/* Also skip the NSEC3-to-match an ancestor of sname if it's
+		 * a parent-side delegation, as that would mean the owner
+		 * does not really exist (authoritatively in this zone,
+		 * even in case of opt-out).
+		 */
+		const uint8_t *bm = knot_nsec3_bitmap(rrset->rrs.rdata);
+		uint16_t bm_size = knot_nsec3_bitmap_len(rrset->rrs.rdata);
+		if (kr_nsec_children_in_zone_check(bm, bm_size) != 0)
+			continue; /* no fatal errors from bad RRs */
+		/* Match the NSEC3 to sname or one of its ancestors. */
+		unsigned skipped = 0;
+		flags = 0;
+		int ret = closest_encloser_match(&flags, rrset, sname, &skipped);
+		if (ret != 0)
+			return ret;
+		if (!(flags & FLG_CLOSEST_PROVABLE_ENCLOSER))
+			continue;
+		matching = rrset;
+		/* Construct the next closer name and try to cover it. */
+		--skipped;
+		next_closer = sname;
+		for (unsigned j = 0; j < skipped; ++j) {
+			if (kr_fails_assert(next_closer[0]))
+				return kr_error(EINVAL);
+			next_closer = knot_wire_next_label(next_closer, NULL);
+		}
+		for (unsigned j = 0; j < sec->count; ++j) {
+			const knot_rrset_t *rrset_j = knot_pkt_rr(sec, j);
+			if (rrset_j->type != KNOT_RRTYPE_NSEC3)
+				continue;
+			ret = covers_name(&flags, rrset_j, next_closer);
+			if (ret != 0)
+				return ret;
+			if (flags & FLG_NAME_COVERED) {
+				covering = rrset_j;
+				break;
+			}
+		}
+		if (flags & FLG_NAME_COVERED)
+			break;
+		flags = 0; //
+	}
+
+	if ((flags & FLG_CLOSEST_PROVABLE_ENCLOSER) && (flags & FLG_NAME_COVERED) && next_closer) {
+		if (encloser_name && next_closer[0])
+			*encloser_name = knot_wire_next_label(next_closer, NULL);
+		if (matching_encloser_nsec3)
+			*matching_encloser_nsec3 = matching;
+		if (covering_next_nsec3)
+			*covering_next_nsec3 = covering;
+		return kr_ok();
+	}
+
+	return kr_error(ENOENT);
+}
+
+/**
+ * Check whether any NSEC3 RR covers a wildcard RR at the closer encloser.
+ * @param pkt        Packet structure to be processed.
+ * @param section_id Packet section to be processed.
+ * @param encloser   Closest (provable) encloser domain name.
+ * @return           0 or error code:
+ *                   KNOT_ERANGE - NSEC3 RR (that covers a wildcard)
+ *                   has been found, but has opt-out flag set;
+ *                   otherwise - error.
+ */
+static int covers_closest_encloser_wildcard(const knot_pkt_t *pkt, knot_section_t section_id,
+                                            const knot_dname_t *encloser)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, section_id);
+	if (!sec || !encloser)
+		return kr_error(EINVAL);
+
+	uint8_t wildcard[KNOT_DNAME_MAXLEN];
+	wildcard[0] = 1;
+	wildcard[1] = '*';
+	int encloser_len = knot_dname_size(encloser);
+	if (encloser_len < 0)
+		return encloser_len;
+	memcpy(wildcard + 2, encloser, encloser_len);
+
+	int flags = 0;
+	for (unsigned i = 0; i < sec->count; ++i) {
+		const knot_rrset_t *rrset = knot_pkt_rr(sec, i);
+		if (rrset->type != KNOT_RRTYPE_NSEC3)
+			continue;
+		int ret = covers_name(&flags, rrset, wildcard);
+		if (ret != 0)
+			return ret;
+		if (flags & FLG_NAME_COVERED) {
+			return has_optout(rrset) ?
+			       kr_error(KNOT_ERANGE) : kr_ok();
+		}
+	}
+
+	return kr_error(ENOENT);
+}
+
+int kr_nsec3_name_error_response_check(const knot_pkt_t *pkt, knot_section_t section_id,
+                                       const knot_dname_t *sname)
+{
+	const knot_dname_t *encloser = NULL;
+	const knot_rrset_t *covering_next_nsec3 = NULL;
+	int ret = closest_encloser_proof(pkt, section_id, sname,
+					 &encloser, NULL, &covering_next_nsec3);
+	if (ret != 0)
+		return ret;
+	ret = covers_closest_encloser_wildcard(pkt, section_id, encloser);
+	if (ret != 0) {
+		/* OK, but NSEC3 for wildcard at encloser has opt-out;
+		 * or error */
+		return ret;
+	}
+	/* Closest encloser proof is OK and
+	 * NSEC3 for wildcard has been found and optout flag is not set.
+	 * Now check if NSEC3 that covers next closer name has opt-out. */
+	return has_optout(covering_next_nsec3) ?
+	       kr_error(KNOT_ERANGE) : kr_ok();
+}
+
+/**
+ * Search the packet section for a matching NSEC3 with nodata-proving bitmap.
+ * @param pkt        Packet structure to be processed.
+ * @param section_id Packet section to be processed.
+ * @param sname      Name to be checked.
+ * @param stype      Type to be checked.
+ * @return           0 or error code.
+ * @note             This does NOT check the opt-out case if type is DS;
+ *                   see RFC 5155 8.6.
+ */
+static int nodata_find(const knot_pkt_t *pkt, knot_section_t section_id,
+			const knot_dname_t *name, const uint16_t type)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, section_id);
+	if (!sec || !name)
+		return kr_error(EINVAL);
+
+	for (unsigned i = 0; i < sec->count; ++i) {
+		const knot_rrset_t *nsec3 = knot_pkt_rr(sec, i);
+		/* Records causing any errors are simply skipped. */
+		if (nsec3->type != KNOT_RRTYPE_NSEC3
+		    || matches_name(nsec3, name) != kr_ok()) {
+			continue;
+			/* LATER(optim.): we repeatedly recompute the hash of `name` */
+		}
+
+		const uint8_t *bm = knot_nsec3_bitmap(nsec3->rrs.rdata);
+		uint16_t bm_size = knot_nsec3_bitmap_len(nsec3->rrs.rdata);
+		if (kr_nsec_bitmap_nodata_check(bm, bm_size, type, nsec3->owner) == kr_ok())
+			return kr_ok();
+	}
+
+	return kr_error(ENOENT);
+}
+
+/**
+ * Check whether NSEC3 RR matches a wildcard at the closest encloser and has given type bit missing.
+ * @param pkt        Packet structure to be processed.
+ * @param section_id Packet section to be processed.
+ * @param encloser   Closest (provable) encloser domain name.
+ * @param stype      Type to be checked.
+ * @return           0 or error code.
+ */
+static int matches_closest_encloser_wildcard(const knot_pkt_t *pkt, knot_section_t section_id,
+                                             const knot_dname_t *encloser, uint16_t stype)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, section_id);
+	if (!sec || !encloser)
+		return kr_error(EINVAL);
+
+	uint8_t wildcard[KNOT_DNAME_MAXLEN]; /**< the source of synthesis */
+	int ret = prepend_asterisk(wildcard, sizeof(wildcard), encloser);
+	if (ret < 0)
+		return ret;
+	kr_require(ret >= 3);
+	return nodata_find(pkt, section_id, wildcard, stype);
+}
+
+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)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, section_id);
+	if (!sec || !sname)
+		return kr_error(EINVAL);
+
+	/* Compute the next closer name. */
+	for (int i = 0; i < trim_to_next; ++i) {
+		if (kr_fails_assert(sname[0]))
+			return kr_error(EINVAL);
+		sname = knot_wire_next_label(sname, NULL);
+	}
+
+	int flags = 0;
+	for (unsigned i = 0; i < sec->count; ++i) {
+		const knot_rrset_t *rrset = knot_pkt_rr(sec, i);
+		if (rrset->type != KNOT_RRTYPE_NSEC3)
+			continue;
+		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
+			 * gets to verifying one of these over-limit NSEC3 RRs. */
+			continue;
+		}
+		int ret = covers_name(&flags, rrset, sname);
+		if (ret != 0)
+			return ret;
+		if (flags & FLG_NAME_COVERED) {
+			return has_optout(rrset) ?
+			       kr_error(KNOT_ERANGE) : kr_ok();
+		}
+	}
+
+	return kr_error(ENOENT);
+}
+
+
+int kr_nsec3_no_data(const knot_pkt_t *pkt, knot_section_t section_id,
+                     const knot_dname_t *sname, uint16_t stype)
+{
+	/* DS record may be also matched by an existing NSEC3 RR. */
+	int ret = nodata_find(pkt, section_id, sname, stype);
+	if (ret == 0) {
+		/* Satisfies RFC5155 8.5 and 8.6, both first paragraph. */
+		return ret;
+	}
+
+	/* Find closest provable encloser. */
+	const knot_dname_t *encloser_name = NULL;
+	const knot_rrset_t *covering_next_nsec3 = NULL;
+	ret = closest_encloser_proof(pkt, section_id, sname, &encloser_name,
+                                     NULL, &covering_next_nsec3);
+	if (ret != 0)
+		return ret;
+
+	if (kr_fails_assert(encloser_name && covering_next_nsec3))
+		return kr_error(EFAULT);
+	ret = matches_closest_encloser_wildcard(pkt, section_id,
+	                                         encloser_name, stype);
+	if (ret == 0) {
+		/* Satisfies RFC5155 8.7 */
+		if (has_optout(covering_next_nsec3)) {
+			/* Opt-out is detected.
+			 * Despite the fact that all records
+			 * in the packet can be properly signed,
+			 * AD bit must not be set due to rfc5155 9.2.
+			 * Return appropriate code to the caller */
+			ret = kr_error(KNOT_ERANGE);
+		}
+		return ret;
+	}
+
+	if (!has_optout(covering_next_nsec3)) {
+		/* Bogus */
+		ret = kr_error(ENOENT);
+	} else {
+		/*
+		 * Satisfies RFC5155 8.6 (QTYPE == DS), 2nd paragraph.
+		 * Also satisfies ERRATA 3441 8.5 (QTYPE != DS), 3rd paragraph.
+		 * - (wildcard) empty nonterminal
+		 * derived from insecure delegation.
+		 * Denial of existence can not be proven.
+		 * Set error code to proceed insecure.
+		 */
+		ret = kr_error(KNOT_ERANGE);
+	}
+
+	return ret;
+}
+
+int kr_nsec3_ref_to_unsigned(const knot_pkt_t *pkt)
+{
+	const knot_pktsection_t *sec = knot_pkt_section(pkt, KNOT_AUTHORITY);
+	if (!sec)
+		return kr_error(EINVAL);
+	for (unsigned i = 0; i < sec->count; ++i) {
+		const knot_rrset_t *ns = knot_pkt_rr(sec, i);
+		if (ns->type == KNOT_RRTYPE_DS)
+			return kr_error(EEXIST);
+		if (ns->type != KNOT_RRTYPE_NS)
+			continue;
+
+		bool nsec3_found = false;
+		for (unsigned j = 0; j < sec->count; ++j) {
+			const knot_rrset_t *nsec3 = knot_pkt_rr(sec, j);
+			if (nsec3->type == KNOT_RRTYPE_DS)
+				return kr_error(EEXIST);
+			if (nsec3->type != KNOT_RRTYPE_NSEC3)
+				continue;
+			nsec3_found = true;
+			/* nsec3 found, check if owner name matches the delegation name.
+			 * Just skip in case of *any* errors. */
+			if (matches_name(nsec3, ns->owner) != kr_ok())
+				continue;
+
+			const uint8_t *bm = knot_nsec3_bitmap(nsec3->rrs.rdata);
+			uint16_t bm_size = knot_nsec3_bitmap_len(nsec3->rrs.rdata);
+			if (!bm)
+				return kr_error(EINVAL);
+			if (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)) {
+				/* Satisfies rfc5155, 8.9. paragraph 2 */
+				return kr_ok();
+			}
+		}
+		if (!nsec3_found)
+			return kr_error(DNSSEC_NOT_FOUND);
+		/* nsec3 that matches the delegation was not found.
+		 * Check rfc5155, 8.9. paragraph 4.
+		 * Find closest provable encloser.
+		 */
+		const knot_dname_t *encloser_name = NULL;
+		const knot_rrset_t *covering_next_nsec3 = NULL;
+		int ret = closest_encloser_proof(pkt, KNOT_AUTHORITY, ns->owner,
+				&encloser_name, NULL, &covering_next_nsec3);
+		if (ret != 0)
+			return kr_error(EINVAL);
+
+		if (has_optout(covering_next_nsec3)) {
+			return kr_error(KNOT_ERANGE);
+		} else {
+			return kr_error(EINVAL);
+		}
+	}
+	return kr_error(EINVAL);
+}
+
+int kr_nsec3_matches_name_and_type(const knot_rrset_t *nsec3,
+				   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 don't (currently) only use this API for NS.  See RFC 6840 sec. 4.
+	 */
+	if (kr_fails_assert(type == KNOT_RRTYPE_NS))
+		return kr_error(EINVAL);
+	int ret = matches_name(nsec3, name);
+	if (ret)
+		return kr_error(ret);
+	const uint8_t *bm = knot_nsec3_bitmap(nsec3->rrs.rdata);
+	uint16_t bm_size = knot_nsec3_bitmap_len(nsec3->rrs.rdata);
+	if (!bm)
+		return kr_error(EINVAL);
+	if (dnssec_nsec_bitmap_contains(bm, bm_size, type)) {
+		return kr_ok();
+	} else {
+		return kr_error(ENOENT);
+	}
+}
diff --git a/lib/dnssec/nsec3.h b/lib/dnssec/nsec3.h
new file mode 100644
index 0000000..a28d3c7
--- /dev/null
+++ b/lib/dnssec/nsec3.h
@@ -0,0 +1,116 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#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 limit is a current compromise;
+ * answers using NSEC3 over kr_nsec3_limited* get downgraded to insecure status.
+ *
+   https://datatracker.ietf.org/doc/html/rfc9276#name-recommendation-for-validati
+ */
+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).
+ * @note No RRSIGs are validated.
+ * @param pkt        Packet structure to be processed.
+ * @param section_id Packet section to be processed.
+ * @param sname      Name to be checked.
+ * @return           0 or error code.
+ */
+int kr_nsec3_name_error_response_check(const knot_pkt_t *pkt, knot_section_t section_id,
+                                       const knot_dname_t *sname);
+
+/**
+ * Wildcard answer response check (RFC5155 7.2.6).
+ * @param pkt          Packet structure to be processed.
+ * @param section_id   Packet section to be processed.
+ * @param sname        Name to be checked.
+ * @param trim_to_next Number of labels to remove to obtain next closer name.
+ * @return             0 or error code:
+ *                     KNOT_ERANGE - NSEC3 RR that covers a wildcard
+ *                     has been found, but has opt-out flag set;
+ *                     otherwise - error.
+ * 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);
+
+/**
+ * Authenticated denial of existence according to RFC5155 8.5 and 8.7.
+ * @note No RRSIGs are validated.
+ * @param pkt        Packet structure to be processed.
+ * @param section_id Packet section to be processed.
+ * @param sname      Queried domain name.
+ * @param stype      Queried type.
+ * @return           0 or error code:
+ *                   DNSSEC_NOT_FOUND - neither ds nor nsec records
+ *                   were not found.
+ *                   KNOT_ERANGE - denial of existence can't be proven
+ *                   due to opt-out, otherwise - bogus.
+ */
+int kr_nsec3_no_data(const knot_pkt_t *pkt, knot_section_t section_id,
+                     const knot_dname_t *sname, uint16_t stype);
+
+/**
+ * Referral to unsigned subzone check (RFC5155 8.9).
+ * @note 	     No RRSIGs are validated.
+ * @param pkt        Packet structure to be processed.
+ * @return           0 or error code:
+ *                   KNOT_ERANGE - denial of existence can't be proven
+ *                   due to opt-out.
+ *                   EEXIST - ds record was found.
+ *                   EINVAL - bogus.
+ */
+int kr_nsec3_ref_to_unsigned(const knot_pkt_t *pkt);
+
+/**
+ * Checks whether supplied NSEC3 RR matches the supplied name and NS type.
+ * @param nsec3 NSEC3 RR.
+ * @param name  Name to be checked.
+ * @param type  Type to be checked.  Only use with NS!  TODO
+ * @return      0 or error code.
+ */
+int kr_nsec3_matches_name_and_type(const knot_rrset_t *nsec3,
+				   const knot_dname_t *name, uint16_t type);
diff --git a/lib/dnssec/signature.c b/lib/dnssec/signature.c
new file mode 100644
index 0000000..aadb5cb
--- /dev/null
+++ b/lib/dnssec/signature.c
@@ -0,0 +1,304 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <arpa/inet.h>
+#include <string.h>
+
+#include <libdnssec/error.h>
+#include <libdnssec/key.h>
+#include <libdnssec/sign.h>
+#include <libknot/descriptor.h>
+#include <libknot/packet/rrset-wire.h>
+#include <libknot/packet/wire.h>
+#include <libknot/rrset.h>
+#include <libknot/rrtype/rrsig.h>
+#include <libknot/rrtype/ds.h>
+#include <libknot/wire.h>
+
+#include "lib/defines.h"
+#include "lib/utils.h"
+#include "lib/dnssec/signature.h"
+
+static int authenticate_ds(const dnssec_key_t *key, dnssec_binary_t *ds_rdata, uint8_t digest_type)
+{
+	/* Compute DS RDATA from the DNSKEY. */
+	dnssec_binary_t computed_ds = { 0, };
+	int ret = dnssec_key_create_ds(key, digest_type, &computed_ds);
+	if (ret != DNSSEC_EOK)
+		goto fail;
+
+	/* DS records contain algorithm, key tag and the digest.
+	 * Therefore the comparison of the two DS is sufficient.
+	 */
+	ret = (ds_rdata->size == computed_ds.size) &&
+	    (memcmp(ds_rdata->data, computed_ds.data, ds_rdata->size) == 0);
+	ret = ret ? kr_ok() : kr_error(ENOENT);
+
+fail:
+	dnssec_binary_free(&computed_ds);
+	return kr_error(ret);
+}
+
+int kr_authenticate_referral(const knot_rrset_t *ref, const dnssec_key_t *key)
+{
+	if (kr_fails_assert(ref && key))
+		return kr_error(EINVAL);
+	if (ref->type != KNOT_RRTYPE_DS)
+		return kr_error(EINVAL);
+
+	/* Determine whether to ignore SHA1 digests, because:
+	    https://datatracker.ietf.org/doc/html/rfc4509#section-3
+	 * Now, the RFCs seem to only mention SHA1 and SHA256 (e.g. no SHA384),
+	 * but the most natural extension is to make any other algorithm trump SHA1.
+	 * (Note that the old GOST version is already unsupported by libdnssec.) */
+	bool skip_sha1 = false;
+	knot_rdata_t *rd = ref->rrs.rdata;
+	for (int i = 0; i < ref->rrs.count; ++i, rd = knot_rdataset_next(rd)) {
+		const uint8_t algo = knot_ds_digest_type(rd);
+		if (algo != DNSSEC_KEY_DIGEST_SHA1 && dnssec_algorithm_digest_support(algo)) {
+			skip_sha1 = true;
+			break;
+		}
+	}
+	/* But otherwise try all possible DS records. */
+	int ret = 0;
+	rd = ref->rrs.rdata;
+	for (int i = 0; i < ref->rrs.count; ++i, rd = knot_rdataset_next(rd)) {
+		const uint8_t algo = knot_ds_digest_type(rd);
+		if (skip_sha1 && algo == DNSSEC_KEY_DIGEST_SHA1)
+			continue;
+		dnssec_binary_t ds_rdata = {
+			.size = rd->len,
+			.data = rd->data
+		};
+		ret = authenticate_ds(key, &ds_rdata, algo);
+		if (ret == 0) /* Found a good DS */
+			return kr_ok();
+	}
+
+	return kr_error(ret);
+}
+
+/**
+ * Adjust TTL in wire format.
+ * @param wire      RR Set in wire format.
+ * @param wire_size Size of the wire data portion.
+ * @param new_ttl   TTL value to be set for all RRs.
+ * @return          0 or error code.
+ */
+static int adjust_wire_ttl(uint8_t *wire, size_t wire_size, uint32_t new_ttl)
+{
+	if (kr_fails_assert(wire))
+		return kr_error(EINVAL);
+	static_assert(sizeof(uint16_t) == 2, "uint16_t must be exactly 2 bytes");
+	static_assert(sizeof(uint32_t) == 4, "uint32_t must be exactly 4 bytes");
+	uint16_t rdlen;
+
+	int ret;
+
+	new_ttl = htonl(new_ttl);
+
+	size_t i = 0;
+	/* RR wire format in RFC1035 3.2.1 */
+	while(i < wire_size) {
+		ret = knot_dname_size(wire + i);
+		if (ret < 0)
+			return ret;
+		i += ret + 4;
+		memcpy(wire + i, &new_ttl, sizeof(uint32_t));
+		i += sizeof(uint32_t);
+
+		memcpy(&rdlen, wire + i, sizeof(uint16_t));
+		rdlen = ntohs(rdlen);
+		i += sizeof(uint16_t) + rdlen;
+
+		if (kr_fails_assert(i <= wire_size))
+			return kr_error(EINVAL);
+	}
+
+	return kr_ok();
+}
+
+/*!
+ * \brief Add RRSIG RDATA without signature to signing context.
+ *
+ * Requires signer name in RDATA in canonical form.
+ *
+ * \param ctx   Signing context.
+ * \param rdata Pointer to RRSIG RDATA.
+ *
+ * \return Error code, KNOT_EOK if successful.
+ */
+#define RRSIG_RDATA_SIGNER_OFFSET 18
+static int sign_ctx_add_self(dnssec_sign_ctx_t *ctx, const uint8_t *rdata)
+{
+	if (kr_fails_assert(ctx && rdata))
+		return kr_error(EINVAL);
+
+	int result;
+
+	// static header
+
+	dnssec_binary_t header = {
+		.data = (uint8_t *)rdata,
+		.size = RRSIG_RDATA_SIGNER_OFFSET,
+	};
+
+	result = dnssec_sign_add(ctx, &header);
+	if (result != DNSSEC_EOK)
+		return result;
+
+	// signer name
+
+	const uint8_t *rdata_signer = rdata + RRSIG_RDATA_SIGNER_OFFSET;
+	dnssec_binary_t signer = { 0 };
+	signer.data = knot_dname_copy(rdata_signer, NULL);
+	signer.size = knot_dname_size(signer.data);
+
+	result = dnssec_sign_add(ctx, &signer);
+	free(signer.data);
+
+	return result;
+}
+#undef RRSIG_RDATA_SIGNER_OFFSET
+
+/*!
+ * \brief Add covered RRs to signing context.
+ *
+ * Requires all DNAMEs in canonical form and all RRs ordered canonically.
+ *
+ * \param ctx      Signing context.
+ * \param covered  Covered RRs.
+ *
+ * \return Error code, KNOT_EOK if successful.
+ */
+static int sign_ctx_add_records(dnssec_sign_ctx_t *ctx, const knot_rrset_t *covered,
+                                uint32_t orig_ttl, int trim_labels)
+{
+	if (!ctx || !covered || trim_labels < 0)
+		return kr_error(EINVAL);
+
+	// huge block of rrsets can be optionally created
+	static uint8_t wire_buffer[KNOT_WIRE_MAX_PKTSIZE];
+	int written = knot_rrset_to_wire(covered, wire_buffer, sizeof(wire_buffer), NULL);
+	if (written < 0)
+		return written;
+
+	/* Set original ttl. */
+	int ret = adjust_wire_ttl(wire_buffer, written, orig_ttl);
+	if (ret != 0)
+		return ret;
+
+	if (!trim_labels) {
+		const dnssec_binary_t wire_binary = {
+			.size = written,
+			.data = wire_buffer
+		};
+		return dnssec_sign_add(ctx, &wire_binary);
+	}
+
+	/* RFC4035 5.3.2
+	 * Remove leftmost labels and replace them with '*.'
+	 * for each RR in covered.
+	 */
+	uint8_t *beginp = wire_buffer;
+	for (uint16_t i = 0; i < covered->rrs.count; ++i) {
+		/* RR(i) = name | type | class | OrigTTL | RDATA length | RDATA */
+		for (int j = 0; j < trim_labels; ++j) {
+			if (kr_fails_assert(beginp[0]))
+				return kr_error(EINVAL);
+			beginp = (uint8_t *) knot_wire_next_label(beginp, NULL);
+			if (kr_fails_assert(beginp))
+				return kr_error(EFAULT);
+		}
+		*(--beginp) = '*';
+		*(--beginp) = 1;
+		const size_t rdatalen_offset = knot_dname_size(beginp) + /* name */
+			sizeof(uint16_t) + /* type */
+			sizeof(uint16_t) + /* class */
+			sizeof(uint32_t);  /* OrigTTL */
+		const uint8_t *rdatalen_ptr = beginp + rdatalen_offset;
+		const uint16_t rdata_size = knot_wire_read_u16(rdatalen_ptr);
+		const size_t rr_size = rdatalen_offset +
+			sizeof(uint16_t) + /* RDATA length */
+			rdata_size;        /* RDATA */
+		const dnssec_binary_t wire_binary = {
+			.size = rr_size,
+			.data = beginp
+		};
+		ret = dnssec_sign_add(ctx, &wire_binary);
+		if (ret != 0)
+			break;
+		beginp += rr_size;
+	}
+	return ret;
+}
+
+/*!
+ * \brief Add all data covered by signature into signing context.
+ *
+ * RFC 4034: The signature covers RRSIG RDATA field (excluding the signature)
+ * and all matching RR records, which are ordered canonically.
+ *
+ * Requires all DNAMEs in canonical form and all RRs ordered canonically.
+ *
+ * \param ctx          Signing context.
+ * \param rrsig_rdata  RRSIG RDATA with populated fields except signature.
+ * \param covered      Covered RRs.
+ *
+ * \return Error code, KNOT_EOK if successful.
+ */
+/* TODO -- Taken from knot/src/knot/dnssec/rrset-sign.c. Re-write for better fit needed. */
+static int sign_ctx_add_data(dnssec_sign_ctx_t *ctx, const uint8_t *rrsig_rdata,
+                             const knot_rrset_t *covered, uint32_t orig_ttl, int trim_labels)
+{
+	int result = sign_ctx_add_self(ctx, rrsig_rdata);
+	if (result != KNOT_EOK)
+		return result;
+
+	return sign_ctx_add_records(ctx, covered, orig_ttl, trim_labels);
+}
+
+int kr_check_signature(const knot_rdata_t *rrsig,
+                       const dnssec_key_t *key, const knot_rrset_t *covered,
+                       int trim_labels)
+{
+	if (!rrsig || !key || !dnssec_key_can_verify(key))
+		return kr_error(EINVAL);
+
+	int ret = 0;
+	dnssec_sign_ctx_t *sign_ctx = NULL;
+	dnssec_binary_t signature = {
+		.data = /*const-cast*/(uint8_t*)knot_rrsig_signature(rrsig),
+		.size = knot_rrsig_signature_len(rrsig),
+	};
+	if (!signature.data || !signature.size) {
+		ret = kr_error(EINVAL);
+		goto fail;
+	}
+
+	if (dnssec_sign_new(&sign_ctx, key) != 0) {
+		ret = kr_error(ENOMEM);
+		goto fail;
+	}
+
+	uint32_t orig_ttl = knot_rrsig_original_ttl(rrsig);
+
+	if (sign_ctx_add_data(sign_ctx, rrsig->data, covered, orig_ttl, trim_labels) != 0) {
+		ret = kr_error(ENOMEM);
+		goto fail;
+	}
+
+	ret = dnssec_sign_verify(sign_ctx, false, &signature);
+	if (ret != 0) {
+		ret = kr_error(EBADMSG);
+		goto fail;
+	}
+
+	ret = kr_ok();
+
+fail:
+	dnssec_sign_free(sign_ctx);
+	return ret;
+}
diff --git a/lib/dnssec/signature.h b/lib/dnssec/signature.h
new file mode 100644
index 0000000..1cc6c8f
--- /dev/null
+++ b/lib/dnssec/signature.h
@@ -0,0 +1,29 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include <libdnssec/key.h>
+#include <libknot/rrset.h>
+
+/**
+ * Performs referral authentication according to RFC4035 5.2, bullet 2
+ * @param ref Referral RRSet. Currently only DS can be used.
+ * @param key Already parsed key.
+ * @return    0 or error code.  In particular: DNSSEC_INVALID_DS_ALGORITHM
+ *            in case *all* DSs in ref use an unimplemented algorithm.
+ */
+int kr_authenticate_referral(const knot_rrset_t *ref, const dnssec_key_t *key);
+
+/**
+ * Check the signature of the supplied RRSet.
+ * @param rrsig       A single signature.
+ * @param key         Key to be used to validate the signature.
+ * @param covered     The covered RRSet.
+ * @param trim_labels Number of the leftmost labels to be removed and replaced with '*.'.
+ * @return            0 if signature valid, error code else.
+ */
+int kr_check_signature(const knot_rdata_t *rrsig,
+                       const dnssec_key_t *key, const knot_rrset_t *covered,
+                       int trim_labels);
diff --git a/lib/dnssec/ta.c b/lib/dnssec/ta.c
new file mode 100644
index 0000000..becf7d8
--- /dev/null
+++ b/lib/dnssec/ta.c
@@ -0,0 +1,154 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#include <contrib/cleanup.h>
+#include <libknot/descriptor.h>
+#include <libknot/rdataset.h>
+#include <libknot/rrset.h>
+#include <libknot/packet/wire.h>
+#include <libdnssec/key.h>
+#include <libdnssec/error.h>
+
+#include "lib/defines.h"
+#include "lib/dnssec.h"
+#include "lib/dnssec/ta.h"
+#include "lib/resolve.h"
+#include "lib/utils.h"
+
+knot_rrset_t *kr_ta_get(trie_t *trust_anchors, const knot_dname_t *name)
+{
+	trie_val_t *val = trie_get_try(trust_anchors, (const char *)name, strlen((const char *)name));
+	return (val) ? *val : NULL;
+}
+
+const knot_dname_t * kr_ta_closest(const struct kr_context *ctx, const knot_dname_t *name,
+				   const uint16_t type)
+{
+	kr_require(ctx && name);
+	if (type == KNOT_RRTYPE_DS && name[0] != '\0') {
+		/* DS is parent-side record, so the parent name needs to be covered. */
+		name = knot_wire_next_label(name, NULL);
+	}
+	while (name) {
+		struct kr_context *ctx_nc = (struct kr_context *)/*const-cast*/ctx;
+		if (kr_ta_get(ctx_nc->trust_anchors, name)) {
+			return name;
+		}
+		if (kr_ta_get(ctx_nc->negative_anchors, name)) {
+			return NULL;
+		}
+		name = knot_wire_next_label(name, NULL);
+	}
+	return NULL;
+}
+
+/* @internal Create DS from DNSKEY, caller MUST free dst if successful. */
+static int dnskey2ds(dnssec_binary_t *dst, const knot_dname_t *owner, const uint8_t *rdata, uint16_t rdlen)
+{
+	dnssec_key_t *key = NULL;
+	int ret = dnssec_key_new(&key);
+	if (ret) goto cleanup;
+	/* Create DS from DNSKEY and reinsert */
+	const dnssec_binary_t key_data = { .size = rdlen, .data = (uint8_t *)rdata };
+	ret = dnssec_key_set_rdata(key, &key_data);
+	if (ret) goto cleanup;
+	/* Accept only keys with Zone and SEP flags that aren't revoked,
+	 * as a precaution.  RFC 5011 also utilizes these flags.
+	 * TODO: kr_dnssec_key_* names are confusing. */
+	const bool flags_ok = kr_dnssec_key_zsk(rdata) && !kr_dnssec_key_revoked(rdata);
+	if (!flags_ok) {
+		auto_free char *owner_str = kr_dname_text(owner);
+		kr_log_error(TA, "refusing to trust %s DNSKEY because of flags %d\n",
+			owner_str, dnssec_key_get_flags(key));
+		ret = kr_error(EILSEQ);
+		goto cleanup;
+	} else if (!kr_dnssec_key_ksk(rdata)) {
+		auto_free char *owner_str = kr_dname_text(owner);
+		int flags = dnssec_key_get_flags(key);
+		kr_log_warning(TA, "warning: %s DNSKEY is missing the SEP bit; "
+			"flags %d instead of %d\n",
+			owner_str, flags, flags + 1/*a little ugly*/);
+	}
+	ret = dnssec_key_set_dname(key, owner);
+	if (ret) goto cleanup;
+	ret = dnssec_key_create_ds(key, DNSSEC_KEY_DIGEST_SHA256, dst);
+cleanup:
+	dnssec_key_free(key);
+	return kr_error(ret);
+}
+
+/* @internal Insert new TA to trust anchor set, rdata MUST be of DS type. */
+static int insert_ta(trie_t *trust_anchors, const knot_dname_t *name,
+                     uint32_t ttl, const uint8_t *rdata, uint16_t rdlen)
+{
+	bool is_new_key = false;
+	knot_rrset_t *ta_rr = kr_ta_get(trust_anchors, name);
+	if (!ta_rr) {
+		ta_rr = knot_rrset_new(name, KNOT_RRTYPE_DS, KNOT_CLASS_IN, ttl, NULL);
+		is_new_key = true;
+	}
+	/* Merge-in new key data */
+	if (!ta_rr || (rdlen > 0 && knot_rrset_add_rdata(ta_rr, rdata, rdlen, NULL) != 0)) {
+		knot_rrset_free(ta_rr, NULL);
+		return kr_error(ENOMEM);
+	}
+	if (is_new_key) {
+		trie_val_t *val = trie_get_ins(trust_anchors, (const char *)name, strlen((const char *)name));
+		if (kr_fails_assert(val))
+			return kr_error(EINVAL);
+		*val = ta_rr;
+	}
+	return kr_ok();
+}
+
+int kr_ta_add(trie_t *trust_anchors, const knot_dname_t *name, uint16_t type,
+              uint32_t ttl, const uint8_t *rdata, uint16_t rdlen)
+{
+	if (!trust_anchors || !name) {
+		return kr_error(EINVAL);
+	}
+
+	/* DS/DNSKEY types are accepted, for DNSKEY we
+	 * need to compute a DS digest. */
+	if (type == KNOT_RRTYPE_DS) {
+		return insert_ta(trust_anchors, name, ttl, rdata, rdlen);
+	} else if (type == KNOT_RRTYPE_DNSKEY) {
+		dnssec_binary_t ds_rdata = { 0, };
+		int ret = dnskey2ds(&ds_rdata, name, rdata, rdlen);
+		if (ret != 0) {
+			return ret;
+		}
+		ret = insert_ta(trust_anchors, name, ttl, ds_rdata.data, ds_rdata.size);
+		dnssec_binary_free(&ds_rdata);
+		return ret;
+	} else { /* Invalid type for TA */
+		return kr_error(EINVAL);
+	}
+}
+
+/* Delete record data */
+static int del_record(trie_val_t *v, void *ext)
+{
+	knot_rrset_t *ta_rr = *v;
+	if (ta_rr) {
+		knot_rrset_free(ta_rr, NULL);
+	}
+	return 0;
+}
+
+int kr_ta_del(trie_t *trust_anchors, const knot_dname_t *name)
+{
+	knot_rrset_t *ta_rr;
+	int ret = trie_del(trust_anchors, (const char *)name, strlen((const char *)name),
+			(trie_val_t *) &ta_rr);
+	if (ret == KNOT_EOK && ta_rr)
+		knot_rrset_free(ta_rr, NULL);
+	return kr_ok();
+}
+
+void kr_ta_clear(trie_t *trust_anchors)
+{
+	trie_apply(trust_anchors, del_record, NULL);
+	trie_clear(trust_anchors);
+}
diff --git a/lib/dnssec/ta.h b/lib/dnssec/ta.h
new file mode 100644
index 0000000..1eb1dd9
--- /dev/null
+++ b/lib/dnssec/ta.h
@@ -0,0 +1,61 @@
+/*  Copyright (C) CZ.NIC, z.s.p.o. <knot-resolver@labs.nic.cz>
+ *  SPDX-License-Identifier: GPL-3.0-or-later
+ */
+
+#pragma once
+
+#include "lib/defines.h"
+#include "lib/generic/trie.h"
+#include <libknot/rrset.h>
+
+/**
+ * Find TA RRSet by name.
+ * @param  trust_anchors trust store
+ * @param  name          name of the TA
+ * @return non-empty RRSet or NULL
+ */
+KR_EXPORT
+knot_rrset_t *kr_ta_get(trie_t *trust_anchors, const knot_dname_t *name);
+
+/**
+ * Add TA to trust store. DS or DNSKEY types are supported.
+ * @param  trust_anchors trust store
+ * @param  name          name of the TA
+ * @param  type          RR type of the TA (DS or DNSKEY)
+ * @param  ttl
+ * @param  rdata
+ * @param  rdlen
+ * @return 0 or an error
+ */
+KR_EXPORT
+int kr_ta_add(trie_t *trust_anchors, const knot_dname_t *name, uint16_t type,
+               uint32_t ttl, const uint8_t *rdata, uint16_t rdlen);
+
+struct kr_context;
+
+/**
+ * Return pointer to the name of the closest positive trust anchor or NULL.
+ *
+ * "Closest" means on path towards root.  Closer negative anchor results into NULL.
+ * @param type serves as a shorthand because DS needs to start one level higher.
+ */
+KR_EXPORT KR_PURE
+const knot_dname_t * kr_ta_closest(const struct kr_context *ctx, const knot_dname_t *name,
+				   const uint16_t type);
+
+/**
+ * Remove TA from trust store.
+ * @param  trust_anchors trust store
+ * @param  name          name of the TA
+ * @return 0 or an error
+ */
+KR_EXPORT
+int kr_ta_del(trie_t *trust_anchors, const knot_dname_t *name);
+
+/**
+ * Clear trust store.
+ * @param trust_anchors trust store
+ */
+KR_EXPORT
+void kr_ta_clear(trie_t *trust_anchors);
+