/*
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
 *
 * SPDX-License-Identifier: MPL-2.0
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

/*! \file */

#include <ctype.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdlib.h>

#include <isc/buffer.h>
#include <isc/dir.h>
#include <isc/log.h>
#include <isc/mem.h>
#include <isc/result.h>
#include <isc/serial.h>
#include <isc/string.h>
#include <isc/util.h>

#include <dns/db.h>
#include <dns/diff.h>
#include <dns/dnssec.h>
#include <dns/fixedname.h>
#include <dns/kasp.h>
#include <dns/keyvalues.h>
#include <dns/rdata.h>
#include <dns/rdatalist.h>
#include <dns/rdatastruct.h>
#include <dns/stats.h>
#include <dns/tsig.h> /* for DNS_TSIG_FUDGE */

isc_stats_t *dns_dnssec_stats;

#define is_response(msg) ((msg->flags & DNS_MESSAGEFLAG_QR) != 0)

#define TYPE_SIGN   0
#define TYPE_VERIFY 1

static isc_result_t
digest_callback(void *arg, isc_region_t *data);

static int
rdata_compare_wrapper(const void *rdata1, const void *rdata2);

static isc_result_t
rdataset_to_sortedarray(dns_rdataset_t *set, isc_mem_t *mctx,
			dns_rdata_t **rdata, int *nrdata);

static isc_result_t
digest_callback(void *arg, isc_region_t *data) {
	dst_context_t *ctx = arg;

	return dst_context_adddata(ctx, data);
}

static void
inc_stat(isc_statscounter_t counter) {
	if (dns_dnssec_stats != NULL) {
		isc_stats_increment(dns_dnssec_stats, counter);
	}
}

/*
 * Make qsort happy.
 */
static int
rdata_compare_wrapper(const void *rdata1, const void *rdata2) {
	return dns_rdata_compare((const dns_rdata_t *)rdata1,
				 (const dns_rdata_t *)rdata2);
}

/*
 * Sort the rdataset into an array.
 */
static isc_result_t
rdataset_to_sortedarray(dns_rdataset_t *set, isc_mem_t *mctx,
			dns_rdata_t **rdata, int *nrdata) {
	isc_result_t result;
	int i = 0, n;
	dns_rdata_t *data;
	dns_rdataset_t rdataset;

	n = dns_rdataset_count(set);

	data = isc_mem_cget(mctx, n, sizeof(dns_rdata_t));

	dns_rdataset_init(&rdataset);
	dns_rdataset_clone(set, &rdataset);
	result = dns_rdataset_first(&rdataset);
	if (result != ISC_R_SUCCESS) {
		dns_rdataset_disassociate(&rdataset);
		isc_mem_cput(mctx, data, n, sizeof(dns_rdata_t));
		return result;
	}

	/*
	 * Put them in the array.
	 */
	do {
		dns_rdata_init(&data[i]);
		dns_rdataset_current(&rdataset, &data[i++]);
	} while (dns_rdataset_next(&rdataset) == ISC_R_SUCCESS);

	/*
	 * Sort the array.
	 */
	qsort(data, n, sizeof(dns_rdata_t), rdata_compare_wrapper);
	*rdata = data;
	*nrdata = n;
	dns_rdataset_disassociate(&rdataset);
	return ISC_R_SUCCESS;
}

isc_result_t
dns_dnssec_keyfromrdata(const dns_name_t *name, const dns_rdata_t *rdata,
			isc_mem_t *mctx, dst_key_t **key) {
	isc_buffer_t b;
	isc_region_t r;

	INSIST(name != NULL);
	INSIST(rdata != NULL);
	INSIST(mctx != NULL);
	INSIST(key != NULL);
	INSIST(*key == NULL);
	REQUIRE(rdata->type == dns_rdatatype_key ||
		rdata->type == dns_rdatatype_dnskey);

	dns_rdata_toregion(rdata, &r);
	isc_buffer_init(&b, r.base, r.length);
	isc_buffer_add(&b, r.length);
	return dst_key_fromdns(name, rdata->rdclass, &b, mctx, key);
}

static isc_result_t
digest_sig(dst_context_t *ctx, bool downcase, dns_rdata_t *sigrdata,
	   dns_rdata_rrsig_t *rrsig) {
	isc_region_t r;
	dns_fixedname_t fname;

	dns_rdata_toregion(sigrdata, &r);
	INSIST(r.length >= 19);

	r.length = 18;
	RETERR(dst_context_adddata(ctx, &r));
	if (downcase) {
		dns_fixedname_init(&fname);

		RUNTIME_CHECK(dns_name_downcase(&rrsig->signer,
						dns_fixedname_name(&fname)) ==
			      ISC_R_SUCCESS);
		dns_name_toregion(dns_fixedname_name(&fname), &r);
	} else {
		dns_name_toregion(&rrsig->signer, &r);
	}

	return dst_context_adddata(ctx, &r);
}

isc_result_t
dns_dnssec_sign(const dns_name_t *name, dns_rdataset_t *set, dst_key_t *key,
		isc_stdtime_t *inception, isc_stdtime_t *expire,
		isc_mem_t *mctx, isc_buffer_t *buffer, dns_rdata_t *sigrdata) {
	dns_rdata_rrsig_t sig;
	dns_rdata_t tmpsigrdata;
	dns_rdata_t *rdatas;
	int nrdatas, i;
	isc_buffer_t sigbuf, envbuf;
	isc_region_t r;
	dst_context_t *ctx = NULL;
	isc_result_t result;
	isc_buffer_t *databuf = NULL;
	char data[256 + 8];
	unsigned int sigsize;
	dns_fixedname_t fnewname;
	dns_fixedname_t fsigner;

	REQUIRE(name != NULL);
	REQUIRE(dns_name_countlabels(name) <= 255);
	REQUIRE(set != NULL);
	REQUIRE(key != NULL);
	REQUIRE(inception != NULL);
	REQUIRE(expire != NULL);
	REQUIRE(mctx != NULL);
	REQUIRE(sigrdata != NULL);

	if (*inception >= *expire) {
		return DNS_R_INVALIDTIME;
	}

	sig.mctx = mctx;
	sig.common.rdclass = set->rdclass;
	sig.common.rdtype = dns_rdatatype_rrsig;

	/*
	 * Downcase signer.
	 */
	dns_name_init(&sig.signer);
	dns_fixedname_init(&fsigner);
	RUNTIME_CHECK(dns_name_downcase(dst_key_name(key),
					dns_fixedname_name(&fsigner)) ==
		      ISC_R_SUCCESS);
	dns_name_clone(dns_fixedname_name(&fsigner), &sig.signer);

	sig.covered = set->type;
	sig.algorithm = dst_algorithm_tosecalg(dst_key_alg(key));
	sig.labels = dns_name_countlabels(name) - 1;
	if (dns_name_iswildcard(name)) {
		sig.labels--;
	}
	sig.originalttl = set->ttl;
	sig.timesigned = *inception;
	sig.timeexpire = *expire;
	sig.keyid = dst_key_id(key);
	RETERR(dst_key_sigsize(key, &sigsize));
	sig.siglen = sigsize;
	/*
	 * The actual contents of sig.signature are not important yet, since
	 * they're not used in digest_sig().
	 */
	sig.signature = isc_mem_get(mctx, sig.siglen);

	isc_buffer_allocate(mctx, &databuf, sigsize + 256 + 18);

	dns_rdata_init(&tmpsigrdata);
	result = dns_rdata_fromstruct(&tmpsigrdata, sig.common.rdclass,
				      sig.common.rdtype, &sig, databuf);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_databuf;
	}

	result = dst_context_create(key, mctx, DNS_LOGCATEGORY_DNSSEC, true,
				    &ctx);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_databuf;
	}

	/*
	 * Digest the SIG rdata.
	 */
	result = digest_sig(ctx, false, &tmpsigrdata, &sig);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_context;
	}

	dns_fixedname_init(&fnewname);
	RUNTIME_CHECK(dns_name_downcase(name, dns_fixedname_name(&fnewname)) ==
		      ISC_R_SUCCESS);
	dns_name_toregion(dns_fixedname_name(&fnewname), &r);

	/*
	 * Create an envelope for each rdata: <name|type|class|ttl>.
	 */
	isc_buffer_init(&envbuf, data, sizeof(data));
	memmove(data, r.base, r.length);
	isc_buffer_add(&envbuf, r.length);
	isc_buffer_putuint16(&envbuf, set->type);
	isc_buffer_putuint16(&envbuf, set->rdclass);
	isc_buffer_putuint32(&envbuf, set->ttl);

	result = rdataset_to_sortedarray(set, mctx, &rdatas, &nrdatas);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_context;
	}
	isc_buffer_usedregion(&envbuf, &r);

	for (i = 0; i < nrdatas; i++) {
		uint16_t len;
		isc_buffer_t lenbuf;
		isc_region_t lenr;

		/*
		 * Skip duplicates.
		 */
		if (i > 0 && dns_rdata_compare(&rdatas[i], &rdatas[i - 1]) == 0)
		{
			continue;
		}

		/*
		 * Digest the envelope.
		 */
		result = dst_context_adddata(ctx, &r);
		if (result != ISC_R_SUCCESS) {
			goto cleanup_array;
		}

		/*
		 * Digest the length of the rdata.
		 */
		isc_buffer_init(&lenbuf, &len, sizeof(len));
		isc_buffer_putuint16(&lenbuf, (uint16_t)rdatas[i].length);
		isc_buffer_usedregion(&lenbuf, &lenr);
		result = dst_context_adddata(ctx, &lenr);
		if (result != ISC_R_SUCCESS) {
			goto cleanup_array;
		}

		/*
		 * Digest the rdata.
		 */
		result = dns_rdata_digest(&rdatas[i], digest_callback, ctx);
		if (result != ISC_R_SUCCESS) {
			goto cleanup_array;
		}
	}

	isc_buffer_init(&sigbuf, sig.signature, sig.siglen);
	result = dst_context_sign(ctx, &sigbuf);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_array;
	}
	isc_buffer_usedregion(&sigbuf, &r);
	if (r.length != sig.siglen) {
		result = ISC_R_NOSPACE;
		goto cleanup_array;
	}

	result = dns_rdata_fromstruct(sigrdata, sig.common.rdclass,
				      sig.common.rdtype, &sig, buffer);

cleanup_array:
	isc_mem_cput(mctx, rdatas, nrdatas, sizeof(dns_rdata_t));
cleanup_context:
	dst_context_destroy(&ctx);
cleanup_databuf:
	isc_buffer_free(&databuf);
	isc_mem_put(mctx, sig.signature, sig.siglen);

	return result;
}

isc_result_t
dns_dnssec_verify(const dns_name_t *name, dns_rdataset_t *set, dst_key_t *key,
		  bool ignoretime, isc_mem_t *mctx, dns_rdata_t *sigrdata,
		  dns_name_t *wild) {
	dns_rdata_rrsig_t sig;
	dns_fixedname_t fnewname;
	isc_region_t r;
	isc_buffer_t envbuf;
	dns_rdata_t *rdatas;
	int nrdatas, i;
	isc_stdtime_t now;
	isc_result_t result;
	unsigned char data[300];
	dst_context_t *ctx = NULL;
	int labels = 0;
	bool downcase = false;

	REQUIRE(name != NULL);
	REQUIRE(set != NULL);
	REQUIRE(key != NULL);
	REQUIRE(mctx != NULL);
	REQUIRE(sigrdata != NULL && sigrdata->type == dns_rdatatype_rrsig);

	RETERR(dns_rdata_tostruct(sigrdata, &sig, NULL));

	if (set->type != sig.covered) {
		return DNS_R_SIGINVALID;
	}

	if (isc_serial_lt(sig.timeexpire, sig.timesigned)) {
		inc_stat(dns_dnssecstats_fail);
		return DNS_R_SIGINVALID;
	}

	if (!ignoretime) {
		now = isc_stdtime_now();

		/*
		 * Is SIG temporally valid?
		 */
		if (isc_serial_lt((uint32_t)now, sig.timesigned)) {
			inc_stat(dns_dnssecstats_fail);
			return DNS_R_SIGFUTURE;
		} else if (isc_serial_lt(sig.timeexpire, (uint32_t)now)) {
			inc_stat(dns_dnssecstats_fail);
			return DNS_R_SIGEXPIRED;
		}
	}

	/*
	 * NS, SOA and DNSKEY records are signed by their owner.
	 * DS records are signed by the parent.
	 */
	switch (set->type) {
	case dns_rdatatype_ns:
	case dns_rdatatype_soa:
	case dns_rdatatype_dnskey:
		if (!dns_name_equal(name, &sig.signer)) {
			inc_stat(dns_dnssecstats_fail);
			return DNS_R_SIGINVALID;
		}
		break;
	case dns_rdatatype_ds:
		if (dns_name_equal(name, &sig.signer)) {
			inc_stat(dns_dnssecstats_fail);
			return DNS_R_SIGINVALID;
		}
		FALLTHROUGH;
	default:
		if (!dns_name_issubdomain(name, &sig.signer)) {
			inc_stat(dns_dnssecstats_fail);
			return DNS_R_SIGINVALID;
		}
		break;
	}

again:
	result = dst_context_create(key, mctx, DNS_LOGCATEGORY_DNSSEC, false,
				    &ctx);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_struct;
	}

	/*
	 * Digest the SIG rdata (not including the signature).
	 */
	result = digest_sig(ctx, downcase, sigrdata, &sig);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_context;
	}

	/*
	 * If the name is an expanded wildcard, use the wildcard name.
	 */
	dns_fixedname_init(&fnewname);
	labels = dns_name_countlabels(name) - 1;
	RUNTIME_CHECK(dns_name_downcase(name, dns_fixedname_name(&fnewname)) ==
		      ISC_R_SUCCESS);
	if (labels - sig.labels > 0) {
		dns_name_split(dns_fixedname_name(&fnewname), sig.labels + 1,
			       NULL, dns_fixedname_name(&fnewname));
	}

	dns_name_toregion(dns_fixedname_name(&fnewname), &r);

	/*
	 * Create an envelope for each rdata: <name|type|class|ttl>.
	 */
	isc_buffer_init(&envbuf, data, sizeof(data));
	if (labels - sig.labels > 0) {
		isc_buffer_putuint8(&envbuf, 1);
		isc_buffer_putuint8(&envbuf, '*');
		memmove(data + 2, r.base, r.length);
	} else {
		memmove(data, r.base, r.length);
	}
	isc_buffer_add(&envbuf, r.length);
	isc_buffer_putuint16(&envbuf, set->type);
	isc_buffer_putuint16(&envbuf, set->rdclass);
	isc_buffer_putuint32(&envbuf, sig.originalttl);

	result = rdataset_to_sortedarray(set, mctx, &rdatas, &nrdatas);
	if (result != ISC_R_SUCCESS) {
		goto cleanup_context;
	}

	isc_buffer_usedregion(&envbuf, &r);

	for (i = 0; i < nrdatas; i++) {
		uint16_t len;
		isc_buffer_t lenbuf;
		isc_region_t lenr;

		/*
		 * Skip duplicates.
		 */
		if (i > 0 && dns_rdata_compare(&rdatas[i], &rdatas[i - 1]) == 0)
		{
			continue;
		}

		/*
		 * Digest the envelope.
		 */
		result = dst_context_adddata(ctx, &r);
		if (result != ISC_R_SUCCESS) {
			goto cleanup_array;
		}

		/*
		 * Digest the rdata length.
		 */
		isc_buffer_init(&lenbuf, &len, sizeof(len));
		isc_buffer_putuint16(&lenbuf, (uint16_t)rdatas[i].length);
		isc_buffer_usedregion(&lenbuf, &lenr);

		/*
		 * Digest the rdata.
		 */
		result = dst_context_adddata(ctx, &lenr);
		if (result != ISC_R_SUCCESS) {
			goto cleanup_array;
		}
		result = dns_rdata_digest(&rdatas[i], digest_callback, ctx);
		if (result != ISC_R_SUCCESS) {
			goto cleanup_array;
		}
	}

	r.base = sig.signature;
	r.length = sig.siglen;
	result = dst_context_verify(ctx, &r);
	if (result == ISC_R_SUCCESS && downcase) {
		char namebuf[DNS_NAME_FORMATSIZE];
		dns_name_format(&sig.signer, namebuf, sizeof(namebuf));
		isc_log_write(DNS_LOGCATEGORY_DNSSEC, DNS_LOGMODULE_DNSSEC,
			      ISC_LOG_DEBUG(1),
			      "successfully validated after lower casing "
			      "signer '%s'",
			      namebuf);
		inc_stat(dns_dnssecstats_downcase);
	} else if (result == ISC_R_SUCCESS) {
		inc_stat(dns_dnssecstats_asis);
	}

cleanup_array:
	isc_mem_cput(mctx, rdatas, nrdatas, sizeof(dns_rdata_t));
cleanup_context:
	dst_context_destroy(&ctx);
	if (result == DST_R_VERIFYFAILURE && !downcase) {
		downcase = true;
		goto again;
	}
cleanup_struct:
	dns_rdata_freestruct(&sig);

	if (result == DST_R_VERIFYFAILURE) {
		result = DNS_R_SIGINVALID;
	}

	if (result != ISC_R_SUCCESS) {
		inc_stat(dns_dnssecstats_fail);
	}

	if (result == ISC_R_SUCCESS && labels - sig.labels > 0) {
		if (wild != NULL) {
			RUNTIME_CHECK(dns_name_concatenate(
					      dns_wildcardname,
					      dns_fixedname_name(&fnewname),
					      wild) == ISC_R_SUCCESS);
		}
		inc_stat(dns_dnssecstats_wildcard);
		result = DNS_R_FROMWILDCARD;
	}
	return result;
}

bool
dns_dnssec_keyactive(dst_key_t *key, isc_stdtime_t now) {
	isc_result_t result;
	isc_stdtime_t publish, active, revoke, remove;
	bool hint_publish, hint_zsign, hint_ksign, hint_revoke, hint_remove;
	int major, minor;
	bool ksk = false, zsk = false;

	/* Is this an old-style key? */
	result = dst_key_getprivateformat(key, &major, &minor);
	RUNTIME_CHECK(result == ISC_R_SUCCESS);

	/* Is this a KSK? */
	result = dst_key_getbool(key, DST_BOOL_KSK, &ksk);
	if (result != ISC_R_SUCCESS) {
		ksk = ((dst_key_flags(key) & DNS_KEYFLAG_KSK) != 0);
	}
	result = dst_key_getbool(key, DST_BOOL_ZSK, &zsk);
	if (result != ISC_R_SUCCESS) {
		zsk = ((dst_key_flags(key) & DNS_KEYFLAG_KSK) == 0);
	}

	/*
	 * Smart signing started with key format 1.3; prior to that, all
	 * keys are assumed active.
	 */
	if (major == 1 && minor <= 2) {
		return true;
	}

	hint_publish = dst_key_is_published(key, now, &publish);
	hint_zsign = dst_key_is_signing(key, DST_BOOL_ZSK, now, &active);
	hint_ksign = dst_key_is_signing(key, DST_BOOL_KSK, now, &active);
	hint_revoke = dst_key_is_revoked(key, now, &revoke);
	hint_remove = dst_key_is_removed(key, now, &remove);

	if (hint_remove) {
		return false;
	}
	if (hint_publish && hint_revoke) {
		return true;
	}
	if (hint_zsign && zsk) {
		return true;
	}
	if (hint_ksign && ksk) {
		return true;
	}
	return false;
}

/*%<
 * Indicate whether a key is scheduled to to have CDS/CDNSKEY records
 * published now.
 *
 * Returns true if.
 *  - kasp says the DS record should be published (e.g. the DS state is in
 *    RUMOURED or OMNIPRESENT state).
 * Or:
 *  - SyncPublish is set and in the past, AND
 *  - SyncDelete is unset or in the future
 */
static bool
syncpublish(dst_key_t *key, isc_stdtime_t now) {
	isc_result_t result;
	isc_stdtime_t when;
	dst_key_state_t state;
	int major, minor;
	bool publish;

	/*
	 * Is this an old-style key?
	 */
	result = dst_key_getprivateformat(key, &major, &minor);
	RUNTIME_CHECK(result == ISC_R_SUCCESS);

	/*
	 * Smart signing started with key format 1.3
	 */
	if (major == 1 && minor <= 2) {
		return false;
	}

	/* Check kasp state first. */
	result = dst_key_getstate(key, DST_KEY_DS, &state);
	if (result == ISC_R_SUCCESS) {
		return state == DST_KEY_STATE_RUMOURED ||
		       state == DST_KEY_STATE_OMNIPRESENT;
	}

	/* If no kasp state, check timings. */
	publish = false;
	result = dst_key_gettime(key, DST_TIME_SYNCPUBLISH, &when);
	if (result == ISC_R_SUCCESS && when <= now) {
		publish = true;
	}
	result = dst_key_gettime(key, DST_TIME_SYNCDELETE, &when);
	if (result == ISC_R_SUCCESS && when < now) {
		publish = false;
	}
	return publish;
}

/*%<
 * Indicate whether a key is scheduled to to have CDS/CDNSKEY records
 * deleted now.
 *
 * Returns true if:
 *  - kasp says the DS record should be unpublished (e.g. the DS state is in
 *    UNRETENTIVE or HIDDEN state).
 * Or:
 * - SyncDelete is set and in the past.
 */
static bool
syncdelete(dst_key_t *key, isc_stdtime_t now) {
	isc_result_t result;
	isc_stdtime_t when;
	dst_key_state_t state;
	int major, minor;

	/*
	 * Is this an old-style key?
	 */
	result = dst_key_getprivateformat(key, &major, &minor);
	RUNTIME_CHECK(result == ISC_R_SUCCESS);

	/*
	 * Smart signing started with key format 1.3.
	 */
	if (major == 1 && minor <= 2) {
		return false;
	}

	/* Check kasp state first. */
	result = dst_key_getstate(key, DST_KEY_DS, &state);
	if (result == ISC_R_SUCCESS) {
		return state == DST_KEY_STATE_UNRETENTIVE ||
		       state == DST_KEY_STATE_HIDDEN;
	}

	/* If no kasp state, check timings. */
	result = dst_key_gettime(key, DST_TIME_SYNCDELETE, &when);
	if (result != ISC_R_SUCCESS) {
		return false;
	}
	if (when <= now) {
		return true;
	}
	return false;
}

#define is_zone_key(key) \
	((dst_key_flags(key) & DNS_KEYFLAG_OWNERMASK) == DNS_KEYOWNER_ZONE)

isc_result_t
dns_dnssec_signmessage(dns_message_t *msg, dst_key_t *key) {
	dns_rdata_sig_t sig; /* SIG(0) */
	unsigned char data[512];
	unsigned char header[DNS_MESSAGE_HEADERLEN];
	isc_buffer_t headerbuf, databuf, sigbuf;
	unsigned int sigsize;
	isc_buffer_t *dynbuf = NULL;
	dns_rdata_t *rdata;
	dns_rdatalist_t *datalist;
	dns_rdataset_t *dataset;
	isc_region_t r;
	isc_stdtime_t now;
	dst_context_t *ctx = NULL;
	isc_mem_t *mctx;
	isc_result_t result;

	REQUIRE(msg != NULL);
	REQUIRE(key != NULL);

	if (is_response(msg)) {
		REQUIRE(msg->query.base != NULL);
	}

	mctx = msg->mctx;

	memset(&sig, 0, sizeof(sig));

	sig.mctx = mctx;
	sig.common.rdclass = dns_rdataclass_any;
	sig.common.rdtype = dns_rdatatype_sig; /* SIG(0) */

	sig.covered = 0;
	sig.algorithm = dst_algorithm_tosecalg(dst_key_alg(key));
	sig.labels = 0; /* the root name */
	sig.originalttl = 0;

	if (msg->fuzzing) {
		now = msg->fuzztime;
	} else {
		now = isc_stdtime_now();
	}
	sig.timesigned = now - DNS_TSIG_FUDGE;
	sig.timeexpire = now + DNS_TSIG_FUDGE;

	sig.keyid = dst_key_id(key);

	dns_name_init(&sig.signer);
	dns_name_clone(dst_key_name(key), &sig.signer);

	sig.siglen = 0;
	sig.signature = NULL;

	isc_buffer_init(&databuf, data, sizeof(data));

	CHECK(dst_context_create(key, mctx, DNS_LOGCATEGORY_DNSSEC, true,
				 &ctx));

	/*
	 * Digest the fields of the SIG - we can cheat and use
	 * dns_rdata_fromstruct.  Since siglen is 0, the digested data
	 * is identical to dns format.
	 */
	CHECK(dns_rdata_fromstruct(NULL, dns_rdataclass_any,
				   dns_rdatatype_sig /* SIG(0) */, &sig,
				   &databuf));
	isc_buffer_usedregion(&databuf, &r);
	CHECK(dst_context_adddata(ctx, &r));

	/*
	 * If this is a response, digest the query.
	 */
	if (is_response(msg)) {
		CHECK(dst_context_adddata(ctx, &msg->query));
	}

	/*
	 * Digest the header.
	 */
	isc_buffer_init(&headerbuf, header, sizeof(header));
	dns_message_renderheader(msg, &headerbuf);
	isc_buffer_usedregion(&headerbuf, &r);
	CHECK(dst_context_adddata(ctx, &r));

	/*
	 * Digest the remainder of the message.
	 */
	isc_buffer_usedregion(msg->buffer, &r);
	isc_region_consume(&r, DNS_MESSAGE_HEADERLEN);
	CHECK(dst_context_adddata(ctx, &r));

	CHECK(dst_key_sigsize(key, &sigsize));
	sig.siglen = sigsize;
	sig.signature = isc_mem_get(mctx, sig.siglen);

	isc_buffer_init(&sigbuf, sig.signature, sig.siglen);
	CHECK(dst_context_sign(ctx, &sigbuf));
	dst_context_destroy(&ctx);

	rdata = NULL;
	dns_message_gettemprdata(msg, &rdata);
	isc_buffer_allocate(msg->mctx, &dynbuf, 1024);
	CHECK(dns_rdata_fromstruct(rdata, dns_rdataclass_any,
				   dns_rdatatype_sig /* SIG(0) */, &sig,
				   dynbuf));

	isc_mem_put(mctx, sig.signature, sig.siglen);

	dns_message_takebuffer(msg, &dynbuf);

	datalist = NULL;
	dns_message_gettemprdatalist(msg, &datalist);
	datalist->rdclass = dns_rdataclass_any;
	datalist->type = dns_rdatatype_sig; /* SIG(0) */
	ISC_LIST_APPEND(datalist->rdata, rdata, link);
	dataset = NULL;
	dns_message_gettemprdataset(msg, &dataset);
	dns_rdatalist_tordataset(datalist, dataset);
	msg->sig0 = dataset;

	return ISC_R_SUCCESS;

cleanup:
	if (dynbuf != NULL) {
		isc_buffer_free(&dynbuf);
	}
	if (sig.signature != NULL) {
		isc_mem_put(mctx, sig.signature, sig.siglen);
	}
	if (ctx != NULL) {
		dst_context_destroy(&ctx);
	}

	return result;
}

isc_result_t
dns_dnssec_verifymessage(isc_buffer_t *source, dns_message_t *msg,
			 dst_key_t *key) {
	dns_rdata_sig_t sig; /* SIG(0) */
	unsigned char header[DNS_MESSAGE_HEADERLEN];
	dns_rdata_t rdata = DNS_RDATA_INIT;
	isc_region_t r, source_r, sig_r, header_r;
	isc_stdtime_t now;
	dst_context_t *ctx = NULL;
	isc_mem_t *mctx;
	isc_result_t result;
	uint16_t addcount, addcount_n;
	bool signeedsfree = false;

	REQUIRE(source != NULL);
	REQUIRE(msg != NULL);
	REQUIRE(key != NULL);

	mctx = msg->mctx;

	msg->verify_attempted = 1;
	msg->verified_sig = 0;
	msg->sig0status = dns_tsigerror_badsig;

	if (is_response(msg)) {
		if (msg->query.base == NULL) {
			return DNS_R_UNEXPECTEDTSIG;
		}
	}

	isc_buffer_usedregion(source, &source_r);

	CHECK(dns_rdataset_first(msg->sig0));
	dns_rdataset_current(msg->sig0, &rdata);

	CHECK(dns_rdata_tostruct(&rdata, &sig, NULL));
	signeedsfree = true;

	if (sig.labels != 0) {
		CLEANUP(DNS_R_SIGINVALID);
	}

	if (isc_serial_lt(sig.timeexpire, sig.timesigned)) {
		msg->sig0status = dns_tsigerror_badtime;
		CLEANUP(DNS_R_SIGINVALID);
	}

	if (msg->fuzzing) {
		now = msg->fuzztime;
	} else {
		now = isc_stdtime_now();
	}

	if (isc_serial_lt((uint32_t)now, sig.timesigned)) {
		msg->sig0status = dns_tsigerror_badtime;
		CLEANUP(DNS_R_SIGFUTURE);
	} else if (isc_serial_lt(sig.timeexpire, (uint32_t)now)) {
		msg->sig0status = dns_tsigerror_badtime;
		CLEANUP(DNS_R_SIGEXPIRED);
	}

	if (!dns_name_equal(dst_key_name(key), &sig.signer)) {
		msg->sig0status = dns_tsigerror_badkey;
		CLEANUP(DNS_R_SIGINVALID);
	}

	CHECK(dst_context_create(key, mctx, DNS_LOGCATEGORY_DNSSEC, false,
				 &ctx));

	/*
	 * Digest the SIG(0) record, except for the signature.
	 */
	dns_rdata_toregion(&rdata, &r);
	r.length -= sig.siglen;
	CHECK(dst_context_adddata(ctx, &r));

	/*
	 * If this is a response, digest the query.
	 */
	if (is_response(msg)) {
		CHECK(dst_context_adddata(ctx, &msg->query));
	}

	/*
	 * Extract the header.
	 */
	memmove(header, source_r.base, DNS_MESSAGE_HEADERLEN);

	/*
	 * Decrement the additional field counter.
	 */
	memmove(&addcount, &header[DNS_MESSAGE_HEADERLEN - 2], 2);
	addcount_n = ntohs(addcount);
	addcount = htons((uint16_t)(addcount_n - 1));
	memmove(&header[DNS_MESSAGE_HEADERLEN - 2], &addcount, 2);

	/*
	 * Digest the modified header.
	 */
	header_r.base = (unsigned char *)header;
	header_r.length = DNS_MESSAGE_HEADERLEN;
	CHECK(dst_context_adddata(ctx, &header_r));

	/*
	 * Digest all non-SIG(0) records.
	 */
	r.base = source_r.base + DNS_MESSAGE_HEADERLEN;
	r.length = msg->sigstart - DNS_MESSAGE_HEADERLEN;
	CHECK(dst_context_adddata(ctx, &r));

	sig_r.base = sig.signature;
	sig_r.length = sig.siglen;
	result = dst_context_verify(ctx, &sig_r);
	if (result != ISC_R_SUCCESS) {
		msg->sig0status = dns_tsigerror_badsig;
		goto cleanup;
	}

	msg->verified_sig = 1;
	msg->sig0status = dns_rcode_noerror;

	dst_context_destroy(&ctx);
	dns_rdata_freestruct(&sig);

	return ISC_R_SUCCESS;

cleanup:
	if (signeedsfree) {
		dns_rdata_freestruct(&sig);
	}
	if (ctx != NULL) {
		dst_context_destroy(&ctx);
	}

	return result;
}

/*%
 * Does this key ('rdata') self sign the rrset ('rdataset')?
 */
bool
dns_dnssec_selfsigns(dns_rdata_t *rdata, const dns_name_t *name,
		     dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset,
		     bool ignoretime, isc_mem_t *mctx) {
	INSIST(rdataset->type == dns_rdatatype_key ||
	       rdataset->type == dns_rdatatype_dnskey);
	if (rdataset->type == dns_rdatatype_key) {
		INSIST(sigrdataset->type == dns_rdatatype_sig);
		INSIST(sigrdataset->covers == dns_rdatatype_key);
	} else {
		INSIST(sigrdataset->type == dns_rdatatype_rrsig);
		INSIST(sigrdataset->covers == dns_rdatatype_dnskey);
	}

	return dns_dnssec_signs(rdata, name, rdataset, sigrdataset, ignoretime,
				mctx);
}

bool
dns_dnssec_signs(dns_rdata_t *rdata, const dns_name_t *name,
		 dns_rdataset_t *rdataset, dns_rdataset_t *sigrdataset,
		 bool ignoretime, isc_mem_t *mctx) {
	dst_key_t *dstkey = NULL;
	dns_keytag_t keytag;
	dns_rdata_dnskey_t key;
	dns_rdata_rrsig_t sig;
	isc_result_t result;

	INSIST(sigrdataset->type == dns_rdatatype_rrsig);
	if (sigrdataset->covers != rdataset->type) {
		return false;
	}

	result = dns_dnssec_keyfromrdata(name, rdata, mctx, &dstkey);
	if (result != ISC_R_SUCCESS) {
		return false;
	}
	result = dns_rdata_tostruct(rdata, &key, NULL);
	RUNTIME_CHECK(result == ISC_R_SUCCESS);

	keytag = dst_key_id(dstkey);
	DNS_RDATASET_FOREACH(sigrdataset) {
		dns_rdata_t sigrdata = DNS_RDATA_INIT;
		dns_rdataset_current(sigrdataset, &sigrdata);
		result = dns_rdata_tostruct(&sigrdata, &sig, NULL);
		RUNTIME_CHECK(result == ISC_R_SUCCESS);

		if (sig.algorithm == key.algorithm && sig.keyid == keytag) {
			result = dns_dnssec_verify(name, rdataset, dstkey,
						   ignoretime, mctx, &sigrdata,
						   NULL);
			if (result == ISC_R_SUCCESS) {
				dst_key_free(&dstkey);
				return true;
			}
		}
	}
	dst_key_free(&dstkey);
	return false;
}

bool
dns_dnssec_iszonekey(dns_rdata_dnskey_t *key) {
	return (key->flags & DNS_KEYFLAG_OWNERMASK) == DNS_KEYOWNER_ZONE &&
	       (key->protocol == DNS_KEYPROTO_DNSSEC ||
		key->protocol == DNS_KEYPROTO_ANY);
}

bool
dns_dnssec_haszonekey(dns_rdataset_t *keyset) {
	REQUIRE(keyset != NULL);

	if (keyset->type != dns_rdatatype_dnskey) {
		return false;
	}

	DNS_RDATASET_FOREACH(keyset) {
		dns_rdata_t rdata = DNS_RDATA_INIT;
		dns_rdata_dnskey_t key;

		dns_rdataset_current(keyset, &rdata);
		dns_rdata_tostruct(&rdata, &key, NULL); /* can't fail */

		if (dns_dnssec_iszonekey(&key)) {
			return true;
		}
	}

	return false;
}

void
dns_dnsseckey_create(isc_mem_t *mctx, dst_key_t **dstkey,
		     dns_dnsseckey_t **dkp) {
	isc_result_t result;
	dns_dnsseckey_t *dk;
	int major, minor;

	REQUIRE(dkp != NULL && *dkp == NULL);
	dk = isc_mem_get(mctx, sizeof(dns_dnsseckey_t));

	dk->key = *dstkey;
	*dstkey = NULL;
	dk->force_publish = false;
	dk->force_sign = false;
	dk->hint_publish = false;
	dk->hint_sign = false;
	dk->hint_revoke = false;
	dk->hint_remove = false;
	dk->first_sign = false;
	dk->is_active = false;
	dk->pubkey = false;
	dk->purge = false;
	dk->prepublish = 0;
	dk->source = dns_keysource_unknown;
	dk->index = 0;

	/* KSK or ZSK? */
	result = dst_key_getbool(dk->key, DST_BOOL_KSK, &dk->ksk);
	if (result != ISC_R_SUCCESS) {
		dk->ksk = ((dst_key_flags(dk->key) & DNS_KEYFLAG_KSK) != 0);
	}
	result = dst_key_getbool(dk->key, DST_BOOL_ZSK, &dk->zsk);
	if (result != ISC_R_SUCCESS) {
		dk->zsk = ((dst_key_flags(dk->key) & DNS_KEYFLAG_KSK) == 0);
	}

	/* Is this an old-style key? */
	result = dst_key_getprivateformat(dk->key, &major, &minor);
	INSIST(result == ISC_R_SUCCESS);

	/* Smart signing started with key format 1.3 */
	dk->legacy = (major == 1 && minor <= 2);

	ISC_LINK_INIT(dk, link);
	*dkp = dk;
}

void
dns_dnsseckey_destroy(isc_mem_t *mctx, dns_dnsseckey_t **dkp) {
	dns_dnsseckey_t *dk;

	REQUIRE(dkp != NULL && *dkp != NULL);
	dk = *dkp;
	*dkp = NULL;
	if (dk->key != NULL) {
		dst_key_free(&dk->key);
	}
	isc_mem_put(mctx, dk, sizeof(dns_dnsseckey_t));
}

void
dns_dnssec_get_hints(dns_dnsseckey_t *key, isc_stdtime_t now) {
	isc_stdtime_t publish = 0, active = 0, revoke = 0, remove = 0;

	REQUIRE(key != NULL && key->key != NULL);

	key->hint_publish = dst_key_is_published(key->key, now, &publish);
	key->hint_sign = dst_key_is_signing(key->key, DST_BOOL_ZSK, now,
					    &active);
	key->hint_revoke = dst_key_is_revoked(key->key, now, &revoke);
	key->hint_remove = dst_key_is_removed(key->key, now, &remove);

	/*
	 * Activation date is set (maybe in the future), but publication date
	 * isn't. Most likely the user wants to publish now and activate later.
	 * Most likely because this is true for most rollovers, except for:
	 * 1. The unpopular ZSK Double-RRSIG method.
	 * 2. When introducing a new algorithm.
	 * These two cases are rare enough that we will set hint_publish
	 * anyway when hint_sign is set, because BIND 9 natively does not
	 * support the ZSK Double-RRSIG method, and when introducing a new
	 * algorithm, we strive to publish its signatures and DNSKEY records
	 * at the same time.
	 */
	if (key->hint_sign && publish == 0) {
		key->hint_publish = true;
	}

	/*
	 * If activation date is in the future, make note of how far off.
	 */
	if (key->hint_publish && active > now) {
		key->prepublish = active - now;
	}

	/*
	 * Metadata says revoke.  If the key is published, we *have to* sign
	 * with it per RFC5011 -- even if it was not active before.
	 *
	 * If it hasn't already been done, we should also revoke it now.
	 */
	if (key->hint_publish && key->hint_revoke) {
		uint32_t flags;
		key->hint_sign = true;
		flags = dst_key_flags(key->key);
		if ((flags & DNS_KEYFLAG_REVOKE) == 0) {
			flags |= DNS_KEYFLAG_REVOKE;
			dst_key_setflags(key->key, flags);
		}
	}

	/*
	 * Metadata says delete, so don't publish this key or sign with it
	 * (note that signatures of a removed key may still be reused).
	 */
	if (key->hint_remove) {
		key->hint_publish = false;
		key->hint_sign = false;
	}
}

static isc_result_t
findmatchingkeys(const char *directory, bool rrtypekey, char *namebuf,
		 unsigned int len, isc_mem_t *mctx, isc_stdtime_t now,
		 dns_dnsseckeylist_t *list) {
	isc_result_t result;
	isc_dir_t dir;
	bool dir_open = false, match = false;
	unsigned int i;
	dns_dnsseckey_t *key = NULL;
	dst_key_t *dstkey = NULL;

	isc_dir_init(&dir);
	if (directory == NULL) {
		directory = ".";
	}

	CHECK(isc_dir_open(&dir, directory));
	dir_open = true;

	while (isc_dir_read(&dir) == ISC_R_SUCCESS) {
		if (dir.entry.name[0] != 'K' || dir.entry.length < len + 1 ||
		    dir.entry.name[len + 1] != '+' ||
		    strncasecmp(dir.entry.name + 1, namebuf, len) != 0)
		{
			continue;
		}

		for (i = len + 1 + 1; i < dir.entry.length; i++) {
			if (!isdigit((unsigned char)dir.entry.name[i])) {
				break;
			}
		}

		/*
		 * Did we not read exactly 3 digits?
		 * Did we overflow?
		 * Did we correctly terminate?
		 */
		if (i != len + 1 + 1 + 3 || i >= dir.entry.length ||
		    dir.entry.name[i] != '+')
		{
			continue;
		}

		for (i++; i < dir.entry.length; i++) {
			if (!isdigit((unsigned char)dir.entry.name[i])) {
				break;
			}
		}

		/*
		 * Did we not read exactly 5 more digits?
		 * Did we overflow?
		 * Did we correctly terminate?
		 */
		if (i != len + 1 + 1 + 3 + 1 + 5 || i >= dir.entry.length ||
		    strcmp(dir.entry.name + i, ".private") != 0)
		{
			continue;
		}

		int type = DST_TYPE_PUBLIC | DST_TYPE_PRIVATE | DST_TYPE_STATE;
		if (rrtypekey) {
			type |= DST_TYPE_KEY;
		}
		dstkey = NULL;
		result = dst_key_fromnamedfile(dir.entry.name, directory, type,
					       mctx, &dstkey);
		if (result == DST_R_BADKEYTYPE) {
			continue;
		}
		if (result != ISC_R_SUCCESS) {
			isc_log_write(DNS_LOGCATEGORY_GENERAL,
				      DNS_LOGMODULE_DNSSEC, ISC_LOG_WARNING,
				      "dns_dnssec_findmatchingkeys: "
				      "error reading key file %s: %s",
				      dir.entry.name,
				      isc_result_totext(result));
			continue;
		}

		dns_dnsseckey_create(mctx, &dstkey, &key);
		key->source = dns_keysource_repository;
		dns_dnssec_get_hints(key, now);

		if (key->legacy) {
			dns_dnsseckey_destroy(mctx, &key);
		} else {
			ISC_LIST_APPEND(*list, key, link);
			match = true;
			key = NULL;
		}
	}
	result = match ? ISC_R_SUCCESS : ISC_R_NOTFOUND;

cleanup:
	if (dir_open) {
		isc_dir_close(&dir);
	}
	if (dstkey != NULL) {
		dst_key_free(&dstkey);
	}
	return result;
}

/*%
 * Get a list of KEY or DNSKEY keys from the key repository. If rrtypekey
 * is true KEY keys will be returned otherwise DNSSEC keys.
 */
isc_result_t
dns_dnssec_findmatchingkeys(const dns_name_t *origin, dns_kasp_t *kasp,
			    const char *keydir, dns_keystorelist_t *keystores,
			    isc_stdtime_t now, bool rrtypekey, isc_mem_t *mctx,
			    dns_dnsseckeylist_t *keylist) {
	isc_result_t result = ISC_R_SUCCESS;
	dns_dnsseckeylist_t list;
	char namebuf[DNS_NAME_FORMATSIZE];
	isc_buffer_t b;
	unsigned int len;

	REQUIRE(keylist != NULL);
	ISC_LIST_INIT(list);

	isc_buffer_init(&b, namebuf, sizeof(namebuf) - 1);
	CHECK(dns_name_tofilenametext(origin, false, &b));
	len = isc_buffer_usedlength(&b);
	namebuf[len] = '\0';

	if (kasp == NULL || (strcmp(dns_kasp_getname(kasp), "none") == 0) ||
	    (strcmp(dns_kasp_getname(kasp), "insecure") == 0))
	{
		CHECK(findmatchingkeys(keydir, rrtypekey, namebuf, len, mctx,
				       now, &list));
	} else if (keystores != NULL) {
		ISC_LIST_FOREACH(*keystores, keystore, link) {
			ISC_LIST_FOREACH(dns_kasp_keys(kasp), kkey, link) {
				if (dns_kasp_key_keystore(kkey) == keystore) {
					const char *directory =
						dns_keystore_directory(keystore,
								       keydir);
					CHECK(findmatchingkeys(
						directory, rrtypekey, namebuf,
						len, mctx, now, &list));
					break;
				}
			}
		}
	}

	if (!ISC_LIST_EMPTY(list)) {
		result = ISC_R_SUCCESS;
		ISC_LIST_APPENDLIST(*keylist, list, link);
	} else {
		result = ISC_R_NOTFOUND;
	}

cleanup:
	ISC_LIST_FOREACH(list, key, link) {
		ISC_LIST_UNLINK(list, key, link);
		INSIST(key->key != NULL);
		dst_key_free(&key->key);
		dns_dnsseckey_destroy(mctx, &key);
	}
	return result;
}

/*%
 * Add 'newkey' to 'keylist' if it's not already there.
 *
 * If 'savekeys' is true, then we need to preserve all
 * the keys in the keyset, regardless of whether they have
 * metadata indicating they should be deactivated or removed.
 */
static void
addkey(dns_dnsseckeylist_t *keylist, dst_key_t **newkey, bool savekeys,
       bool pubkey_only, isc_mem_t *mctx) {
	dns_dnsseckey_t *key = NULL;

	/* Skip duplicates */
	ISC_LIST_FOREACH(*keylist, k, link) {
		if (dst_key_id(k->key) == dst_key_id(*newkey) &&
		    dst_key_alg(k->key) == dst_key_alg(*newkey) &&
		    dns_name_equal(dst_key_name(k->key), dst_key_name(*newkey)))
		{
			key = k;
			break;
		}
	}

	if (key != NULL) {
		/*
		 * Found a match. If we already had a private key, then
		 * the new key can't be an improvement. If the existing
		 * key was public-only but the new key is too, then it's
		 * still not an improvement. Mark the old key as having
		 * been found in the zone and stop.
		 */
		if (dst_key_isprivate(key->key) || !dst_key_isprivate(*newkey))
		{
			key->source = dns_keysource_zoneapex;
			return;
		}

		/*
		 * However, if the old key was public-only, and the new key
		 * is private, then we're throwing away the old key.
		 */
		dst_key_free(&key->key);
		ISC_LIST_UNLINK(*keylist, key, link);
		dns_dnsseckey_destroy(mctx, &key);
	}

	/* Store the new key. */
	dns_dnsseckey_create(mctx, newkey, &key);
	key->source = dns_keysource_zoneapex;
	key->pubkey = pubkey_only;
	if (key->legacy || savekeys) {
		key->force_publish = true;
		key->force_sign = dst_key_isprivate(key->key);
	}
	ISC_LIST_APPEND(*keylist, key, link);
	*newkey = NULL;
}

/*%
 * Mark all keys which signed the DNSKEY/SOA RRsets as "active",
 * for future reference.
 */
static isc_result_t
mark_active_keys(dns_dnsseckeylist_t *keylist, dns_rdataset_t *rrsigs) {
	isc_result_t result = ISC_R_SUCCESS;
	dns_rdata_t rdata = DNS_RDATA_INIT;
	dns_rdataset_t sigs;

	REQUIRE(rrsigs != NULL && dns_rdataset_isassociated(rrsigs));

	dns_rdataset_init(&sigs);
	dns_rdataset_clone(rrsigs, &sigs);
	ISC_LIST_FOREACH(*keylist, key, link) {
		uint16_t keyid, sigid;
		dst_algorithm_t keyalg, sigalg;
		keyid = dst_key_id(key->key);
		keyalg = dst_key_alg(key->key);

		DNS_RDATASET_FOREACH(&sigs) {
			dns_rdata_rrsig_t sig;

			dns_rdata_reset(&rdata);
			dns_rdataset_current(&sigs, &rdata);
			result = dns_rdata_tostruct(&rdata, &sig, NULL);
			RUNTIME_CHECK(result == ISC_R_SUCCESS);
			sigalg = dst_algorithm_fromdata(
				sig.algorithm, sig.signature, sig.siglen);
			sigid = sig.keyid;
			if (keyid == sigid && keyalg == sigalg) {
				key->is_active = true;
				break;
			}
		}
	}

	dns_rdataset_cleanup(&sigs);
	return result;
}

static isc_result_t
keyfromfile(dns_kasp_t *kasp, const char *keydir, dst_key_t *key, int type,
	    isc_mem_t *mctx, dst_key_t **savekey) {
	const char *directory = keydir;
	isc_result_t result = ISC_R_NOTFOUND;

	if (kasp == NULL || (strcmp(dns_kasp_getname(kasp), "none") == 0) ||
	    (strcmp(dns_kasp_getname(kasp), "insecure") == 0))
	{
		result = dst_key_fromfile(dst_key_name(key), dst_key_id(key),
					  dst_key_alg(key), type, directory,
					  mctx, savekey);
	} else {
		ISC_LIST_FOREACH(dns_kasp_keys(kasp), kkey, link) {
			dns_keystore_t *ks = dns_kasp_key_keystore(kkey);
			directory = dns_keystore_directory(ks, keydir);
			result = dst_key_fromfile(dst_key_name(key),
						  dst_key_id(key),
						  dst_key_alg(key), type,
						  directory, mctx, savekey);
			if (result == ISC_R_SUCCESS) {
				break;
			}
		}
	}

	return result;
}

/*%
 * Add the contents of a DNSKEY rdataset 'keyset' to 'keylist'.
 */
isc_result_t
dns_dnssec_keylistfromrdataset(const dns_name_t *origin, dns_kasp_t *kasp,
			       const char *directory, isc_mem_t *mctx,
			       dns_rdataset_t *keyset, dns_rdataset_t *keysigs,
			       dns_rdataset_t *soasigs, bool savekeys,
			       bool publickey, dns_dnsseckeylist_t *keylist) {
	dns_rdataset_t keys;
	dst_key_t *dnskey = NULL, *pubkey = NULL, *privkey = NULL;
	isc_result_t result;

	REQUIRE(keyset != NULL && dns_rdataset_isassociated(keyset));

	dns_rdataset_init(&keys);

	dns_rdataset_clone(keyset, &keys);
	DNS_RDATASET_FOREACH(&keys) {
		dns_rdata_t rdata = DNS_RDATA_INIT;
		dst_algorithm_t algorithm;
		dns_rdata_dnskey_t keystruct;

		dns_rdataset_current(&keys, &rdata);

		REQUIRE(rdata.type == dns_rdatatype_key ||
			rdata.type == dns_rdatatype_dnskey);
		REQUIRE(rdata.length > 3);

		result = dns_rdata_tostruct(&rdata, &keystruct, NULL);
		RUNTIME_CHECK(result == ISC_R_SUCCESS);

		algorithm = dst_algorithm_fromdata(
			keystruct.algorithm, keystruct.data, keystruct.datalen);

		/* Skip unsupported algorithms */
		if (!dst_algorithm_supported(algorithm)) {
			goto skip;
		}

		CHECK(dns_dnssec_keyfromrdata(origin, &rdata, mctx, &dnskey));
		dst_key_setttl(dnskey, keys.ttl);

		if (!is_zone_key(dnskey)) {
			goto skip;
		}

		/* Corrupted .key file? */
		if (!dns_name_equal(origin, dst_key_name(dnskey))) {
			goto skip;
		}

		if (publickey) {
			addkey(keylist, &dnskey, savekeys, true, mctx);
			goto skip;
		}

		/* Try to read the public key. */
		result = keyfromfile(kasp, directory, dnskey,
				     DST_TYPE_PUBLIC | DST_TYPE_STATE, mctx,
				     &pubkey);
		if (result == ISC_R_FILENOTFOUND || result == ISC_R_NOPERM) {
			result = ISC_R_SUCCESS;
		}
		CHECK(result);

		if (kasp != NULL && dns_kasp_offlineksk(kasp) &&
		    (dst_key_flags(dnskey) & DNS_KEYFLAG_KSK) != 0)
		{
			result = ISC_R_NOPERM;
			goto addkey;
		}

		/* Now read the private key. */
		result = keyfromfile(kasp, directory, dnskey,
				     DST_TYPE_PUBLIC | DST_TYPE_PRIVATE |
					     DST_TYPE_STATE,
				     mctx, &privkey);

		/*
		 * If the key was revoked and the private file
		 * doesn't exist, maybe it was revoked internally
		 * by named.  Try loading the unrevoked version.
		 */
		if (result == ISC_R_FILENOTFOUND) {
			uint32_t flags;
			flags = dst_key_flags(dnskey);
			if ((flags & DNS_KEYFLAG_REVOKE) != 0) {
				dst_key_setflags(dnskey,
						 flags & ~DNS_KEYFLAG_REVOKE);
				result = keyfromfile(kasp, directory, dnskey,
						     DST_TYPE_PUBLIC |
							     DST_TYPE_PRIVATE |
							     DST_TYPE_STATE,
						     mctx, &privkey);
				if (result == ISC_R_SUCCESS &&
				    dst_key_pubcompare(dnskey, privkey, false))
				{
					dst_key_setflags(privkey, flags);
				}
				dst_key_setflags(dnskey, flags);
			}
		}

		if (result != ISC_R_SUCCESS) {
			char filename[DNS_NAME_FORMATSIZE +
				      DNS_SECALG_FORMATSIZE +
				      sizeof("key file for //65535")];
			isc_result_t result2;
			isc_buffer_t buf;

			isc_buffer_init(&buf, filename, NAME_MAX);
			result2 = dst_key_getfilename(
				dst_key_name(dnskey), dst_key_id(dnskey),
				dst_key_alg(dnskey),
				DST_TYPE_PUBLIC | DST_TYPE_PRIVATE |
					DST_TYPE_STATE,
				NULL, mctx, &buf);
			if (result2 != ISC_R_SUCCESS) {
				char namebuf[DNS_NAME_FORMATSIZE];
				char algbuf[DNS_SECALG_FORMATSIZE];

				dns_name_format(dst_key_name(dnskey), namebuf,
						sizeof(namebuf));
				dns_secalg_format(dst_key_alg(dnskey), algbuf,
						  sizeof(algbuf));
				snprintf(filename, sizeof(filename) - 1,
					 "key file for %s/%s/%d", namebuf,
					 algbuf, dst_key_id(dnskey));
			}

			isc_log_write(DNS_LOGCATEGORY_GENERAL,
				      DNS_LOGMODULE_DNSSEC, ISC_LOG_WARNING,
				      "dns_dnssec_keylistfromrdataset: error "
				      "reading %s: %s",
				      filename, isc_result_totext(result));
		}

	addkey:
		if (result == ISC_R_FILENOTFOUND || result == ISC_R_NOPERM) {
			if (pubkey != NULL) {
				addkey(keylist, &pubkey, savekeys, true, mctx);
			} else {
				addkey(keylist, &dnskey, savekeys, false, mctx);
			}
			goto skip;
		}
		CHECK(result);

		/*
		 * Whatever the key's default TTL may have
		 * been, the rdataset TTL takes priority.
		 */
		dst_key_setttl(privkey, dst_key_getttl(dnskey));

		addkey(keylist, &privkey, savekeys, false, mctx);
	skip:
		if (dnskey != NULL) {
			dst_key_free(&dnskey);
		}
		if (pubkey != NULL) {
			dst_key_free(&pubkey);
		}
		if (privkey != NULL) {
			dst_key_free(&privkey);
		}
	}

	if (keysigs != NULL && dns_rdataset_isassociated(keysigs)) {
		CHECK(mark_active_keys(keylist, keysigs));
	}

	if (soasigs != NULL && dns_rdataset_isassociated(soasigs)) {
		CHECK(mark_active_keys(keylist, soasigs));
	}

	result = ISC_R_SUCCESS;

cleanup:
	dns_rdataset_cleanup(&keys);
	if (dnskey != NULL) {
		dst_key_free(&dnskey);
	}
	if (pubkey != NULL) {
		dst_key_free(&pubkey);
	}
	if (privkey != NULL) {
		dst_key_free(&privkey);
	}
	return result;
}

isc_result_t
dns_dnssec_make_dnskey(dst_key_t *key, unsigned char *buf, int bufsize,
		       dns_rdata_t *target) {
	isc_buffer_t b;
	isc_region_t r;

	isc_buffer_init(&b, buf, bufsize);
	RETERR(dst_key_todns(key, &b));

	dns_rdata_reset(target);
	isc_buffer_usedregion(&b, &r);
	dns_rdata_fromregion(target, dst_key_class(key), dns_rdatatype_dnskey,
			     &r);
	return ISC_R_SUCCESS;
}

static void
addrdata(dns_rdata_t *rdata, dns_diff_t *diff, const dns_name_t *origin,
	 dns_ttl_t ttl, isc_mem_t *mctx) {
	dns_difftuple_t *tuple = NULL;

	dns_difftuple_create(mctx, DNS_DIFFOP_ADD, origin, ttl, rdata, &tuple);
	dns_diff_appendminimal(diff, &tuple);
}

static void
delrdata(dns_rdata_t *rdata, dns_diff_t *diff, const dns_name_t *origin,
	 dns_ttl_t ttl, isc_mem_t *mctx) {
	dns_difftuple_t *tuple = NULL;

	dns_difftuple_create(mctx, DNS_DIFFOP_DEL, origin, ttl, rdata, &tuple);
	dns_diff_appendminimal(diff, &tuple);
}

static isc_result_t
publish_key(dns_diff_t *diff, dns_dnsseckey_t *key, const dns_name_t *origin,
	    dns_ttl_t ttl, isc_mem_t *mctx,
	    void (*report)(const char *, ...) ISC_FORMAT_PRINTF(1, 2)) {
	isc_result_t result = ISC_R_SUCCESS;
	unsigned char buf[DST_KEY_MAXSIZE];
	char keystr[DST_KEY_FORMATSIZE];
	dns_rdata_t dnskey = DNS_RDATA_INIT;

	dns_rdata_reset(&dnskey);
	CHECK(dns_dnssec_make_dnskey(key->key, buf, sizeof(buf), &dnskey));
	dst_key_format(key->key, keystr, sizeof(keystr));

	report("Fetching %s (%s) from key %s.", keystr,
	       key->ksk ? (key->zsk ? "CSK" : "KSK") : "ZSK",
	       key->source == dns_keysource_user ? "file" : "repository");

	if (key->prepublish && ttl > key->prepublish) {
		isc_stdtime_t now;

		report("Key %s: Delaying activation to match the DNSKEY TTL "
		       "(%u).",
		       keystr, ttl);

		now = isc_stdtime_now();
		dst_key_settime(key->key, DST_TIME_ACTIVATE, now + ttl);
	}

	/* publish key */
	addrdata(&dnskey, diff, origin, ttl, mctx);

cleanup:
	return result;
}

static isc_result_t
remove_key(dns_diff_t *diff, dns_dnsseckey_t *key, const dns_name_t *origin,
	   dns_ttl_t ttl, isc_mem_t *mctx, const char *reason,
	   void (*report)(const char *, ...) ISC_FORMAT_PRINTF(1, 2)) {
	isc_result_t result = ISC_R_SUCCESS;
	unsigned char buf[DST_KEY_MAXSIZE];
	dns_rdata_t dnskey = DNS_RDATA_INIT;
	char alg[80];
	char namebuf[DNS_NAME_FORMATSIZE];

	dns_secalg_format(dst_key_alg(key->key), alg, sizeof(alg));
	dns_name_format(dst_key_name(key->key), namebuf, sizeof(namebuf));
	report("Removing %s key %s/%d/%s from DNSKEY RRset.", reason, namebuf,
	       dst_key_id(key->key), alg);

	CHECK(dns_dnssec_make_dnskey(key->key, buf, sizeof(buf), &dnskey));
	delrdata(&dnskey, diff, origin, ttl, mctx);

cleanup:
	return result;
}

static bool
exists(dns_rdataset_t *rdataset, dns_rdata_t *rdata) {
	dns_rdataset_t trdataset = DNS_RDATASET_INIT;
	dns_rdataset_clone(rdataset, &trdataset);

	DNS_RDATASET_FOREACH(&trdataset) {
		dns_rdata_t current = DNS_RDATA_INIT;

		dns_rdataset_current(&trdataset, &current);
		if (dns_rdata_compare(rdata, &current) == 0) {
			dns_rdataset_disassociate(&trdataset);
			return true;
		}
	}
	dns_rdataset_disassociate(&trdataset);
	return false;
}

static isc_result_t
add_cds(dns_dnsseckey_t *key, dns_rdata_t *keyrdata, const char *keystr,
	dns_rdataset_t *cds, unsigned int digesttype, dns_ttl_t ttl,
	dns_diff_t *diff, isc_mem_t *mctx) {
	isc_result_t r;
	unsigned char dsbuf[DNS_DS_BUFFERSIZE];
	dns_rdata_t cdsrdata = DNS_RDATA_INIT;
	dns_name_t *origin = dst_key_name(key->key);

	r = dns_ds_buildrdata(origin, keyrdata, digesttype, dsbuf,
			      sizeof(dsbuf), &cdsrdata);
	if (r != ISC_R_SUCCESS) {
		char algbuf[DNS_DSDIGEST_FORMATSIZE];
		dns_dsdigest_format(digesttype, algbuf,
				    DNS_DSDIGEST_FORMATSIZE);
		isc_log_write(DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DNSSEC,
			      ISC_LOG_ERROR,
			      "build rdata CDS (%s) for key %s failed", algbuf,
			      keystr);
		return r;
	}

	cdsrdata.type = dns_rdatatype_cds;
	if (!dns_rdataset_isassociated(cds) || !exists(cds, &cdsrdata)) {
		char algbuf[DNS_DSDIGEST_FORMATSIZE];
		dns_dsdigest_format(digesttype, algbuf,
				    DNS_DSDIGEST_FORMATSIZE);
		isc_log_write(DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DNSSEC,
			      ISC_LOG_INFO,
			      "CDS (%s) for key %s is now published", algbuf,
			      keystr);
		addrdata(&cdsrdata, diff, origin, ttl, mctx);
		return ISC_R_SUCCESS;
	}
	return DNS_R_UNCHANGED;
}

static isc_result_t
delete_cds(dns_dnsseckey_t *key, dns_rdata_t *keyrdata, const char *keystr,
	   dns_rdataset_t *cds, unsigned int digesttype, dns_diff_t *diff,
	   isc_mem_t *mctx) {
	unsigned char dsbuf[DNS_DS_BUFFERSIZE];
	dns_rdata_t cdsrdata = DNS_RDATA_INIT;
	dns_name_t *origin = dst_key_name(key->key);

	RETERR(dns_ds_buildrdata(origin, keyrdata, digesttype, dsbuf,
				 sizeof(dsbuf), &cdsrdata));

	cdsrdata.type = dns_rdatatype_cds;
	if (exists(cds, &cdsrdata)) {
		char algbuf[DNS_DSDIGEST_FORMATSIZE];
		dns_dsdigest_format(digesttype, algbuf,
				    DNS_DSDIGEST_FORMATSIZE);
		isc_log_write(DNS_LOGCATEGORY_GENERAL, DNS_LOGMODULE_DNSSEC,
			      ISC_LOG_INFO,
			      "CDS (%s) for key %s is now deleted", algbuf,
			      keystr);
		delrdata(&cdsrdata, diff, origin, cds->ttl, mctx);
		return ISC_R_SUCCESS;
	}
	return DNS_R_UNCHANGED;
}

isc_result_t
dns_dnssec_syncupdate(dns_dnsseckeylist_t *keys, dns_dnsseckeylist_t *rmkeys,
		      dns_rdataset_t *cds, dns_rdataset_t *cdnskey,
		      isc_stdtime_t now, dns_kasp_digestlist_t *digests,
		      bool gencdnskey, dns_ttl_t ttl, dns_diff_t *diff,
		      isc_mem_t *mctx) {
	unsigned char keybuf[DST_KEY_MAXSIZE];
	isc_result_t result = DNS_R_UNCHANGED;
	dns_ttl_t cdsttl = ttl;
	dns_ttl_t cdnskeyttl = ttl;
	bool changed = false;

	REQUIRE(digests != NULL);
	REQUIRE(keys != NULL);
	REQUIRE(rmkeys != NULL);

	if (dns_rdataset_isassociated(cds)) {
		cdsttl = cds->ttl;
	}

	if (dns_rdataset_isassociated(cdnskey)) {
		cdnskeyttl = cdnskey->ttl;
	}

	ISC_LIST_FOREACH(*keys, key, link) {
		dns_rdata_t cdnskeyrdata = DNS_RDATA_INIT;
		dns_name_t *origin = dst_key_name(key->key);

		CHECK(dns_dnssec_make_dnskey(key->key, keybuf, sizeof(keybuf),
					     &cdnskeyrdata));
		cdnskeyrdata.type = dns_rdatatype_cdnskey;

		if (syncpublish(key->key, now)) {
			char keystr[DST_KEY_FORMATSIZE];
			dst_key_format(key->key, keystr, sizeof(keystr));

			ISC_LIST_FOREACH(*digests, alg, link) {
				result = add_cds(key, &cdnskeyrdata,
						 (const char *)keystr, cds,
						 alg->digest, cdsttl, diff,
						 mctx);
				if (result == ISC_R_SUCCESS) {
					changed = true;
				} else if (result != DNS_R_UNCHANGED) {
					goto cleanup;
				}
			}

			if (gencdnskey &&
			    (!dns_rdataset_isassociated(cdnskey) ||
			     !exists(cdnskey, &cdnskeyrdata)))
			{
				isc_log_write(
					DNS_LOGCATEGORY_GENERAL,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"CDNSKEY for key %s is now published",
					keystr);
				addrdata(&cdnskeyrdata, diff, origin,
					 cdnskeyttl, mctx);
				changed = true;
			}
		}

		if (syncdelete(key->key, now)) {
			char keystr[DST_KEY_FORMATSIZE];
			dst_key_format(key->key, keystr, sizeof(keystr));

			if (dns_rdataset_isassociated(cds)) {
				/* Delete all possible CDS records */
				for (dns_dsdigest_t digest = DNS_DSDIGEST_SHA1;
				     digest < DNS_DSDIGEST_TOTAL; digest++)
				{
					result = delete_cds(
						key, &cdnskeyrdata,
						(const char *)keystr, cds,
						digest, diff, mctx);

					switch (result) {
					case ISC_R_SUCCESS:
						changed = true;
						break;
					case DNS_R_UNCHANGED:
					case ISC_R_NOTIMPLEMENTED:
						/*
						 * Either the digest is not
						 * supported and we cannot
						 * construct the CDS for it, or
						 * the CDS with this digest is
						 * not present in the CDS RRset.
						 */
						break;
					default:
						goto cleanup;
					}
				}
			}

			if (dns_rdataset_isassociated(cdnskey)) {
				if (exists(cdnskey, &cdnskeyrdata)) {
					isc_log_write(DNS_LOGCATEGORY_GENERAL,
						      DNS_LOGMODULE_DNSSEC,
						      ISC_LOG_INFO,
						      "CDNSKEY for key %s is "
						      "now deleted",
						      keystr);
					delrdata(&cdnskeyrdata, diff, origin,
						 cdnskey->ttl, mctx);
					changed = true;
				}
			}
		}
	}

	if (!dns_rdataset_isassociated(cds) &&
	    !dns_rdataset_isassociated(cdnskey))
	{
		if (changed) {
			return ISC_R_SUCCESS;
		}
		return DNS_R_UNCHANGED;
	}

	/*
	 * Unconditionally remove CDS/DNSKEY records for removed keys.
	 */
	ISC_LIST_FOREACH(*rmkeys, key, link) {
		dns_rdata_t cdnskeyrdata = DNS_RDATA_INIT;
		dns_name_t *origin = dst_key_name(key->key);

		char keystr[DST_KEY_FORMATSIZE];
		dst_key_format(key->key, keystr, sizeof(keystr));

		CHECK(dns_dnssec_make_dnskey(key->key, keybuf, sizeof(keybuf),
					     &cdnskeyrdata));

		if (dns_rdataset_isassociated(cds)) {
			for (dns_dsdigest_t digest = DNS_DSDIGEST_SHA1;
			     digest < DNS_DSDIGEST_TOTAL; digest++)
			{
				result = delete_cds(key, &cdnskeyrdata,
						    (const char *)keystr, cds,
						    digest, diff, mctx);
				switch (result) {
				case ISC_R_SUCCESS:
					changed = true;
					break;
				case DNS_R_UNCHANGED:
				case ISC_R_NOTIMPLEMENTED:
					/*
					 * Either the digest is not
					 * supported and we cannot
					 * construct the CDS for it, or
					 * the CDS with this digest is
					 * not present in the CDS RRset.
					 */
					break;
				default:
					goto cleanup;
				}
			}
		}

		if (dns_rdataset_isassociated(cdnskey)) {
			if (exists(cdnskey, &cdnskeyrdata)) {
				isc_log_write(
					DNS_LOGCATEGORY_GENERAL,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"CDNSKEY for key %s is now deleted",
					keystr);
				delrdata(&cdnskeyrdata, diff, origin,
					 cdnskey->ttl, mctx);
				changed = true;
			}
		}
	}

	if (changed) {
		return ISC_R_SUCCESS;
	}
	return DNS_R_UNCHANGED;

cleanup:
	return result;
}

isc_result_t
dns_dnssec_syncdelete(dns_rdataset_t *cds, dns_rdataset_t *cdnskey,
		      dns_name_t *origin, dns_rdataclass_t zclass,
		      dns_ttl_t ttl, dns_diff_t *diff, isc_mem_t *mctx,
		      bool expect_cds_delete, bool expect_cdnskey_delete) {
	unsigned char dsbuf[5] = { 0, 0, 0, 0, 0 };  /* CDS DELETE rdata */
	unsigned char keybuf[5] = { 0, 0, 3, 0, 0 }; /* CDNSKEY DELETE rdata */
	char namebuf[DNS_NAME_FORMATSIZE];
	dns_rdata_t cds_delete = DNS_RDATA_INIT;
	dns_rdata_t cdnskey_delete = DNS_RDATA_INIT;
	isc_region_t r;
	bool changed = false;

	r.base = keybuf;
	r.length = sizeof(keybuf);
	dns_rdata_fromregion(&cdnskey_delete, zclass, dns_rdatatype_cdnskey,
			     &r);

	r.base = dsbuf;
	r.length = sizeof(dsbuf);
	dns_rdata_fromregion(&cds_delete, zclass, dns_rdatatype_cds, &r);

	dns_name_format(origin, namebuf, sizeof(namebuf));

	if (expect_cds_delete) {
		if (!dns_rdataset_isassociated(cds) ||
		    !exists(cds, &cds_delete))
		{
			isc_log_write(DNS_LOGCATEGORY_GENERAL,
				      DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
				      "CDS (DELETE) for zone %s is now "
				      "published",
				      namebuf);
			addrdata(&cds_delete, diff, origin, ttl, mctx);
			changed = true;
		}
	} else {
		if (dns_rdataset_isassociated(cds) && exists(cds, &cds_delete))
		{
			isc_log_write(DNS_LOGCATEGORY_GENERAL,
				      DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
				      "CDS (DELETE) for zone %s is now "
				      "deleted",
				      namebuf);
			delrdata(&cds_delete, diff, origin, cds->ttl, mctx);
			changed = true;
		}
	}

	if (expect_cdnskey_delete) {
		if (!dns_rdataset_isassociated(cdnskey) ||
		    !exists(cdnskey, &cdnskey_delete))
		{
			isc_log_write(DNS_LOGCATEGORY_GENERAL,
				      DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
				      "CDNSKEY (DELETE) for zone %s is now "
				      "published",
				      namebuf);
			addrdata(&cdnskey_delete, diff, origin, ttl, mctx);
			changed = true;
		}
	} else {
		if (dns_rdataset_isassociated(cdnskey) &&
		    exists(cdnskey, &cdnskey_delete))
		{
			isc_log_write(DNS_LOGCATEGORY_GENERAL,
				      DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
				      "CDNSKEY (DELETE) for zone %s is now "
				      "deleted",
				      namebuf);
			delrdata(&cdnskey_delete, diff, origin, cdnskey->ttl,
				 mctx);
			changed = true;
		}
	}

	if (changed) {
		return ISC_R_SUCCESS;
	}
	return DNS_R_UNCHANGED;
}

/*
 * Update 'keys' with information from 'newkeys'.
 *
 * If 'removed' is not NULL, any keys that are being removed from
 * the zone will be added to the list for post-removal processing.
 */
isc_result_t
dns_dnssec_updatekeys(dns_dnsseckeylist_t *keys, dns_dnsseckeylist_t *newkeys,
		      dns_dnsseckeylist_t *removed, const dns_name_t *origin,
		      dns_ttl_t hint_ttl, dns_diff_t *diff, isc_mem_t *mctx,
		      void (*report)(const char *, ...)
			      ISC_FORMAT_PRINTF(1, 2)) {
	isc_result_t result;
	bool found_ttl = false;
	dns_ttl_t ttl = hint_ttl;

	/*
	 * First, look through the existing key list to find keys
	 * supplied from the command line which are not in the zone.
	 * Update the zone to include them.
	 *
	 * Also, if there are keys published in the zone already,
	 * use their TTL for all subsequent published keys.
	 */
	ISC_LIST_FOREACH(*keys, key, link) {
		if (key->source == dns_keysource_user &&
		    (key->hint_publish || key->force_publish))
		{
			CHECK(publish_key(diff, key, origin, ttl, mctx,
					  report));
		}
		if (key->source == dns_keysource_zoneapex) {
			ttl = dst_key_getttl(key->key);
			found_ttl = true;
		}
	}

	/*
	 * If there were no existing keys, use the smallest nonzero
	 * TTL of the keys found in the repository.
	 */
	if (!found_ttl && !ISC_LIST_EMPTY(*newkeys)) {
		dns_ttl_t shortest = 0;

		ISC_LIST_FOREACH(*newkeys, key, link) {
			dns_ttl_t thisttl = dst_key_getttl(key->key);
			if (thisttl != 0 &&
			    (shortest == 0 || thisttl < shortest))
			{
				shortest = thisttl;
			}
		}

		if (shortest != 0) {
			ttl = shortest;
		}
	}

	/*
	 * Second, scan the list of newly found keys looking for matches
	 * with known keys, and update accordingly.
	 */
	ISC_LIST_FOREACH(*newkeys, key1, link) {
		bool key_revoked = false;
		char keystr1[DST_KEY_FORMATSIZE];
		char keystr2[DST_KEY_FORMATSIZE];
		dns_dnsseckey_t *key2 = NULL;

		ISC_LIST_FOREACH(*keys, k2, link) {
			int f1 = dst_key_flags(key1->key);
			int f2 = dst_key_flags(k2->key);
			int nr1 = f1 & ~DNS_KEYFLAG_REVOKE;
			int nr2 = f2 & ~DNS_KEYFLAG_REVOKE;
			if (nr1 == nr2 &&
			    dst_key_alg(key1->key) == dst_key_alg(k2->key) &&
			    dst_key_pubcompare(key1->key, k2->key, true))
			{
				int r1 = dst_key_flags(key1->key) &
					 DNS_KEYFLAG_REVOKE;
				int r2 = dst_key_flags(k2->key) &
					 DNS_KEYFLAG_REVOKE;
				key_revoked = (r1 != r2);
				key2 = k2;
				break;
			}
		}

		/* Printable version of key1 (the newly acquired key) */
		dst_key_format(key1->key, keystr1, sizeof(keystr1));

		/* No match found in keys; add the new key. */
		if (key2 == NULL) {
			ISC_LIST_UNLINK(*newkeys, key1, link);
			ISC_LIST_APPEND(*keys, key1, link);

			if (key1->source != dns_keysource_zoneapex &&
			    (key1->hint_publish || key1->force_publish))
			{
				CHECK(publish_key(diff, key1, origin, ttl, mctx,
						  report));
				isc_log_write(
					DNS_LOGCATEGORY_DNSSEC,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"DNSKEY %s (%s) is now published",
					keystr1,
					key1->ksk ? (key1->zsk ? "CSK" : "KSK")
						  : "ZSK");
				if (key1->hint_sign || key1->force_sign) {
					key1->first_sign = true;
					isc_log_write(
						DNS_LOGCATEGORY_DNSSEC,
						DNS_LOGMODULE_DNSSEC,
						ISC_LOG_INFO,
						"DNSKEY %s (%s) is now "
						"active",
						keystr1,
						key1->ksk ? (key1->zsk ? "CSK"
								       : "KSK")
							  : "ZSK");
				}
			}

			continue;
		}

		/* Printable version of key2 (the old key, if any) */
		dst_key_format(key2->key, keystr2, sizeof(keystr2));

		/* Copy key metadata. */
		dst_key_copy_metadata(key2->key, key1->key);

		/* Match found: remove or update it as needed */
		if (key1->hint_remove) {
			CHECK(remove_key(diff, key2, origin, ttl, mctx,
					 "expired", report));
			ISC_LIST_UNLINK(*keys, key2, link);

			if (removed != NULL) {
				ISC_LIST_APPEND(*removed, key2, link);
				isc_log_write(
					DNS_LOGCATEGORY_DNSSEC,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"DNSKEY %s (%s) is now deleted",
					keystr2,
					key2->ksk ? (key2->zsk ? "CSK" : "KSK")
						  : "ZSK");
			} else {
				dns_dnsseckey_destroy(mctx, &key2);
			}
		} else if (key_revoked &&
			   (dst_key_flags(key1->key) & DNS_KEYFLAG_REVOKE) != 0)
		{
			/*
			 * A previously valid key has been revoked.
			 * We need to remove the old version and pull
			 * in the new one.
			 */
			CHECK(remove_key(diff, key2, origin, ttl, mctx,
					 "revoked", report));
			ISC_LIST_UNLINK(*keys, key2, link);
			if (removed != NULL) {
				ISC_LIST_APPEND(*removed, key2, link);
				isc_log_write(
					DNS_LOGCATEGORY_DNSSEC,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"DNSKEY %s (%s) is now revoked; "
					"new ID is %05d",
					keystr2,
					key2->ksk ? (key2->zsk ? "CSK" : "KSK")
						  : "ZSK",
					dst_key_id(key1->key));
			} else {
				dns_dnsseckey_destroy(mctx, &key2);
			}

			CHECK(publish_key(diff, key1, origin, ttl, mctx,
					  report));
			ISC_LIST_UNLINK(*newkeys, key1, link);
			ISC_LIST_APPEND(*keys, key1, link);

			/*
			 * XXX: The revoke flag is only defined for trust
			 * anchors.  Setting the flag on a non-KSK is legal,
			 * but not defined in any RFC.  It seems reasonable
			 * to treat it the same as a KSK: keep it in the
			 * zone, sign the DNSKEY set with it, but not
			 * sign other records with it.
			 */
			key1->ksk = true;
			continue;
		} else {
			if (!key2->is_active &&
			    (key1->hint_sign || key1->force_sign))
			{
				key2->first_sign = true;
				isc_log_write(
					DNS_LOGCATEGORY_DNSSEC,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"DNSKEY %s (%s) is now active", keystr1,
					key1->ksk ? (key1->zsk ? "CSK" : "KSK")
						  : "ZSK");
			} else if (key2->is_active && !key1->hint_sign &&
				   !key1->force_sign)
			{
				isc_log_write(
					DNS_LOGCATEGORY_DNSSEC,
					DNS_LOGMODULE_DNSSEC, ISC_LOG_INFO,
					"DNSKEY %s (%s) is now inactive",
					keystr1,
					key1->ksk ? (key1->zsk ? "CSK" : "KSK")
						  : "ZSK");
			}

			key2->hint_sign = key1->hint_sign;
			key2->hint_publish = key1->hint_publish;
		}
	}

	/* Free any leftover keys in newkeys */
	ISC_LIST_FOREACH(*newkeys, key1, link) {
		ISC_LIST_UNLINK(*newkeys, key1, link);
		dns_dnsseckey_destroy(mctx, &key1);
	}

	result = ISC_R_SUCCESS;

cleanup:
	return result;
}

isc_result_t
dns_dnssec_matchdskey(dns_name_t *name, dns_rdata_t *dsrdata,
		      dns_rdataset_t *keyset, dns_rdata_t *keyrdata) {
	isc_result_t result;
	unsigned char buf[DNS_DS_BUFFERSIZE];
	dns_keytag_t keytag;
	dns_rdata_dnskey_t key;
	dns_rdata_ds_t ds;
	isc_region_t r;

	result = dns_rdata_tostruct(dsrdata, &ds, NULL);
	RUNTIME_CHECK(result == ISC_R_SUCCESS);

	DNS_RDATASET_FOREACH(keyset) {
		dns_rdata_t newdsrdata = DNS_RDATA_INIT;

		dns_rdata_reset(keyrdata);
		dns_rdataset_current(keyset, keyrdata);

		result = dns_rdata_tostruct(keyrdata, &key, NULL);
		RUNTIME_CHECK(result == ISC_R_SUCCESS);

		dns_rdata_toregion(keyrdata, &r);
		keytag = dst_region_computeid(&r);

		if (ds.key_tag != keytag || ds.algorithm != key.algorithm) {
			continue;
		}

		result = dns_ds_buildrdata(name, keyrdata, ds.digest_type, buf,
					   sizeof(buf), &newdsrdata);
		if (result != ISC_R_SUCCESS) {
			continue;
		}

		if (dns_rdata_compare(dsrdata, &newdsrdata) == 0) {
			return ISC_R_SUCCESS;
		}
	}

	return ISC_R_NOTFOUND;
}
