dnssec-signzone.c

/*
 * Portions Copyright (C) 2004-2014  Internet Systems Consortium, Inc. ("ISC")
 * Portions Copyright (C) 1999-2003  Internet Software Consortium.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NETWORK ASSOCIATES DISCLAIMS
 * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE
 * FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
 * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 * Portions Copyright (C) 1995-2000 by Network Associates, Inc.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC AND NETWORK ASSOCIATES DISCLAIMS
 * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE
 * FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
 * IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/* $Id: dnssec-signzone.c,v 1.285.32.1 2012/02/07 00:44:12 each Exp $ */

/*! \file */

#include <config.h>

#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#include <isc/app.h>
#include <isc/base32.h>
#include <isc/commandline.h>
#include <isc/entropy.h>
#include <isc/event.h>
#include <isc/file.h>
#include <isc/hash.h>
#include <isc/hex.h>
#include <isc/mem.h>
#include <isc/mutex.h>
#include <isc/os.h>
#include <isc/print.h>
#include <isc/random.h>
#include <isc/rwlock.h>
#include <isc/serial.h>
#include <isc/stdio.h>
#include <isc/stdlib.h>
#include <isc/string.h>
#include <isc/task.h>
#include <isc/time.h>
#include <isc/util.h>

#include <dns/db.h>
#include <dns/dbiterator.h>
#include <dns/diff.h>
#include <dns/dnssec.h>
#include <dns/ds.h>
#include <dns/fixedname.h>
#include <dns/keyvalues.h>
#include <dns/log.h>
#include <dns/master.h>
#include <dns/masterdump.h>
#include <dns/nsec.h>
#include <dns/nsec3.h>
#include <dns/rdata.h>
#include <dns/rdatalist.h>
#include <dns/rdataset.h>
#include <dns/rdataclass.h>
#include <dns/rdatasetiter.h>
#include <dns/rdatastruct.h>
#include <dns/rdatatype.h>
#include <dns/result.h>
#include <dns/soa.h>
#include <dns/time.h>

#include <dst/dst.h>

#include "dnssectool.h"

#ifndef PATH_MAX
#define PATH_MAX 1024   /* AIX, WIN32, and others don't define this. */
#endif

const char *program = "dnssec-signzone";
int verbose;

typedef struct hashlist hashlist_t;

static int nsec_datatype = dns_rdatatype_nsec;

#define IS_NSEC3	(nsec_datatype == dns_rdatatype_nsec3)
#define OPTOUT(x)	(((x) & DNS_NSEC3FLAG_OPTOUT) != 0)

#define REVOKE(x) ((dst_key_flags(x) & DNS_KEYFLAG_REVOKE) != 0)

#define BUFSIZE 2048
#define MAXDSKEYS 8

#define SIGNER_EVENTCLASS	ISC_EVENTCLASS(0x4453)
#define SIGNER_EVENT_WRITE	(SIGNER_EVENTCLASS + 0)
#define SIGNER_EVENT_WORK	(SIGNER_EVENTCLASS + 1)

#define SOA_SERIAL_KEEP		0
#define SOA_SERIAL_INCREMENT	1
#define SOA_SERIAL_UNIXTIME	2

typedef struct signer_event sevent_t;
struct signer_event {
	ISC_EVENT_COMMON(sevent_t);
	dns_fixedname_t *fname;
	dns_dbnode_t *node;
};

static dns_dnsseckeylist_t keylist;
static unsigned int keycount = 0;
isc_rwlock_t keylist_lock;
static isc_stdtime_t starttime = 0, endtime = 0, dnskey_endtime = 0, now;
static int cycle = -1;
static int jitter = 0;
static isc_boolean_t tryverify = ISC_FALSE;
static isc_boolean_t printstats = ISC_FALSE;
static isc_mem_t *mctx = NULL;
static isc_entropy_t *ectx = NULL;
static dns_ttl_t zone_soa_min_ttl;
static dns_ttl_t soa_ttl;
static FILE *fp = NULL;
static char *tempfile = NULL;
static const dns_master_style_t *masterstyle;
static dns_masterformat_t inputformat = dns_masterformat_text;
static dns_masterformat_t outputformat = dns_masterformat_text;
static isc_uint32_t rawversion = 1, serialnum = 0;
static isc_boolean_t snset = ISC_FALSE;
static unsigned int nsigned = 0, nretained = 0, ndropped = 0;
static unsigned int nverified = 0, nverifyfailed = 0;
static const char *directory = NULL, *dsdir = NULL;
static isc_mutex_t namelock, statslock;
static isc_taskmgr_t *taskmgr = NULL;
static dns_db_t *gdb;			/* The database */
static dns_dbversion_t *gversion;	/* The database version */
static dns_dbiterator_t *gdbiter;	/* The database iterator */
static dns_rdataclass_t gclass;		/* The class */
static dns_name_t *gorigin;		/* The database origin */
static int nsec3flags = 0;
static dns_iterations_t nsec3iter = 10U;
static unsigned char saltbuf[255];
static unsigned char *salt = saltbuf;
static size_t salt_length = 0;
static isc_task_t *master = NULL;
static unsigned int ntasks = 0;
static isc_boolean_t shuttingdown = ISC_FALSE, finished = ISC_FALSE;
static isc_boolean_t nokeys = ISC_FALSE;
static isc_boolean_t removefile = ISC_FALSE;
static isc_boolean_t generateds = ISC_FALSE;
static isc_boolean_t ignore_kskflag = ISC_FALSE;
static isc_boolean_t keyset_kskonly = ISC_FALSE;
static dns_name_t *dlv = NULL;
static dns_fixedname_t dlv_fixed;
static dns_master_style_t *dsstyle = NULL;
static unsigned int serialformat = SOA_SERIAL_KEEP;
static unsigned int hash_length = 0;
static isc_boolean_t unknownalg = ISC_FALSE;
static isc_boolean_t disable_zone_check = ISC_FALSE;
static isc_boolean_t update_chain = ISC_FALSE;
static isc_boolean_t set_keyttl = ISC_FALSE;
static dns_ttl_t keyttl;
static isc_boolean_t smartsign = ISC_FALSE;
static isc_boolean_t remove_orphansigs = ISC_FALSE;
static isc_boolean_t remove_inactkeysigs = ISC_FALSE;
static isc_boolean_t output_dnssec_only = ISC_FALSE;
static isc_boolean_t output_stdout = ISC_FALSE;
isc_boolean_t set_maxttl = ISC_FALSE;
static dns_ttl_t maxttl = 0;

#define INCSTAT(counter)		\
	if (printstats) {		\
		LOCK(&statslock);	\
		counter++;		\
		UNLOCK(&statslock);	\
	}

static void
sign(isc_task_t *task, isc_event_t *event);

static void
dumpnode(dns_name_t *name, dns_dbnode_t *node) {
	dns_rdataset_t rds;
	dns_rdatasetiter_t *iter = NULL;
	isc_buffer_t *buffer = NULL;
	isc_region_t r;
	isc_result_t result;
	unsigned bufsize = 4096;

	if (outputformat != dns_masterformat_text)
		return;

	if (!output_dnssec_only) {
		result = dns_master_dumpnodetostream(mctx, gdb, gversion, node,
						     name, masterstyle, fp);
		check_result(result, "dns_master_dumpnodetostream");
		return;
	}

	result = dns_db_allrdatasets(gdb, node, gversion, 0, &iter);
	check_result(result, "dns_db_allrdatasets");

	dns_rdataset_init(&rds);

	result = isc_buffer_allocate(mctx, &buffer, bufsize);
	check_result(result, "isc_buffer_allocate");

	for (result = dns_rdatasetiter_first(iter);
	     result == ISC_R_SUCCESS;
	     result = dns_rdatasetiter_next(iter)) {

		dns_rdatasetiter_current(iter, &rds);

		if (rds.type != dns_rdatatype_rrsig &&
		    rds.type != dns_rdatatype_nsec &&
		    rds.type != dns_rdatatype_nsec3 &&
		    rds.type != dns_rdatatype_nsec3param &&
		    (!smartsign || rds.type != dns_rdatatype_dnskey)) {
			dns_rdataset_disassociate(&rds);
			continue;
		}

		for (;;) {
			result = dns_master_rdatasettotext(name, &rds,
							   masterstyle, buffer);
			if (result != ISC_R_NOSPACE)
				break;

			bufsize <<= 1;
			isc_buffer_free(&buffer);
			result = isc_buffer_allocate(mctx, &buffer, bufsize);
			check_result(result, "isc_buffer_allocate");
		}
		check_result(result, "dns_master_rdatasettotext");

		isc_buffer_usedregion(buffer, &r);
		result = isc_stdio_write(r.base, 1, r.length, fp, NULL);
		check_result(result, "isc_stdio_write");
		isc_buffer_clear(buffer);

		dns_rdataset_disassociate(&rds);
	}

	isc_buffer_free(&buffer);
	dns_rdatasetiter_destroy(&iter);
}

/*%
 * Sign the given RRset with given key, and add the signature record to the
 * given tuple.
 */
static void
signwithkey(dns_name_t *name, dns_rdataset_t *rdataset, dst_key_t *key,
	    dns_ttl_t ttl, dns_diff_t *add, const char *logmsg)
{
	isc_result_t result;
	isc_stdtime_t jendtime, expiry;
	char keystr[DST_KEY_FORMATSIZE];
	dns_rdata_t trdata = DNS_RDATA_INIT;
	unsigned char array[BUFSIZE];
	isc_buffer_t b;
	dns_difftuple_t *tuple;

	dst_key_format(key, keystr, sizeof(keystr));
	vbprintf(1, "\t%s %s\n", logmsg, keystr);

	if (rdataset->type == dns_rdatatype_dnskey)
		expiry = dnskey_endtime;
	else
		expiry = endtime;

	jendtime = (jitter != 0) ? isc_random_jitter(expiry, jitter) : expiry;
	isc_buffer_init(&b, array, sizeof(array));
	result = dns_dnssec_sign(name, rdataset, key, &starttime, &jendtime,
				 mctx, &b, &trdata);
	isc_entropy_stopcallbacksources(ectx);
	if (result != ISC_R_SUCCESS) {
		char keystr[DST_KEY_FORMATSIZE];
		dst_key_format(key, keystr, sizeof(keystr));
		fatal("dnskey '%s' failed to sign data: %s",
		      keystr, isc_result_totext(result));
	}
	INCSTAT(nsigned);

	if (tryverify) {
		result = dns_dnssec_verify(name, rdataset, key,
					   ISC_TRUE, mctx, &trdata);
		if (result == ISC_R_SUCCESS) {
			vbprintf(3, "\tsignature verified\n");
			INCSTAT(nverified);
		} else {
			vbprintf(3, "\tsignature failed to verify\n");
			INCSTAT(nverifyfailed);
		}
	}

	tuple = NULL;
	result = dns_difftuple_create(mctx, DNS_DIFFOP_ADDRESIGN,
				      name, ttl, &trdata, &tuple);
	check_result(result, "dns_difftuple_create");
	dns_diff_append(add, &tuple);
}

static inline isc_boolean_t
issigningkey(dns_dnsseckey_t *key) {
	return (key->force_sign || key->hint_sign);
}

static inline isc_boolean_t
ispublishedkey(dns_dnsseckey_t *key) {
	return ((key->force_publish || key->hint_publish) &&
		!key->hint_remove);
}

static inline isc_boolean_t
iszonekey(dns_dnsseckey_t *key) {
	return (ISC_TF(dns_name_equal(dst_key_name(key->key), gorigin) &&
		       dst_key_iszonekey(key->key)));
}

static inline isc_boolean_t
isksk(dns_dnsseckey_t *key) {
	return (key->ksk);
}

static inline isc_boolean_t
iszsk(dns_dnsseckey_t *key) {
	return (ignore_kskflag || !key->ksk);
}

/*%
 * Find the key that generated an RRSIG, if it is in the key list.  If
 * so, return a pointer to it, otherwise return NULL.
 *
 * No locking is performed here, this must be done by the caller.
 */
static dns_dnsseckey_t *
keythatsigned_unlocked(dns_rdata_rrsig_t *rrsig) {
	dns_dnsseckey_t *key;

	for (key = ISC_LIST_HEAD(keylist);
	     key != NULL;
	     key = ISC_LIST_NEXT(key, link)) {
		if (rrsig->keyid == dst_key_id(key->key) &&
		    rrsig->algorithm == dst_key_alg(key->key) &&
		    dns_name_equal(&rrsig->signer, dst_key_name(key->key)))
			return (key);
	}
	return (NULL);
}

/*%
 * Finds the key that generated a RRSIG, if possible.  First look at the keys
 * that we've loaded already, and then see if there's a key on disk.
 */
static dns_dnsseckey_t *
keythatsigned(dns_rdata_rrsig_t *rrsig) {
	isc_result_t result;
	dst_key_t *pubkey = NULL, *privkey = NULL;
	dns_dnsseckey_t *key = NULL;

	isc_rwlock_lock(&keylist_lock, isc_rwlocktype_read);
	key = keythatsigned_unlocked(rrsig);
	isc_rwlock_unlock(&keylist_lock, isc_rwlocktype_read);
	if (key != NULL)
		return (key);

	/*
	 * We did not find the key in our list.  Get a write lock now, since
	 * we may be modifying the bits.  We could do the tryupgrade() dance,
	 * but instead just get a write lock and check once again to see if
	 * it is on our list.  It's possible someone else may have added it
	 * after all.
	 */
	isc_rwlock_lock(&keylist_lock, isc_rwlocktype_write);
	key = keythatsigned_unlocked(rrsig);
	if (key != NULL) {
		isc_rwlock_unlock(&keylist_lock, isc_rwlocktype_write);
		return (key);
	}

	result = dst_key_fromfile(&rrsig->signer, rrsig->keyid,
				  rrsig->algorithm, DST_TYPE_PUBLIC,
				  directory, mctx, &pubkey);
	if (result != ISC_R_SUCCESS) {
		isc_rwlock_unlock(&keylist_lock, isc_rwlocktype_write);
		return (NULL);
	}

	result = dst_key_fromfile(&rrsig->signer, rrsig->keyid,
				  rrsig->algorithm,
				  DST_TYPE_PUBLIC | DST_TYPE_PRIVATE,
				  directory, mctx, &privkey);
	if (result == ISC_R_SUCCESS) {
		dst_key_free(&pubkey);
		result = dns_dnsseckey_create(mctx, &privkey, &key);
	} else
		result = dns_dnsseckey_create(mctx, &pubkey, &key);

	if (result == ISC_R_SUCCESS) {
		key->force_publish = ISC_FALSE;
		key->force_sign = ISC_FALSE;
		key->index = keycount++;
		ISC_LIST_APPEND(keylist, key, link);
	}

	isc_rwlock_unlock(&keylist_lock, isc_rwlocktype_write);
	return (key);
}

/*%
 * Check to see if we expect to find a key at this name.  If we see a RRSIG
 * and can't find the signing key that we expect to find, we drop the rrsig.
 * I'm not sure if this is completely correct, but it seems to work.
 */
static isc_boolean_t
expecttofindkey(dns_name_t *name) {
	unsigned int options = DNS_DBFIND_NOWILD;
	dns_fixedname_t fname;
	isc_result_t result;
	char namestr[DNS_NAME_FORMATSIZE];

	dns_fixedname_init(&fname);
	result = dns_db_find(gdb, name, gversion, dns_rdatatype_dnskey, options,
			     0, NULL, dns_fixedname_name(&fname), NULL, NULL);
	switch (result) {
	case ISC_R_SUCCESS:
	case DNS_R_NXDOMAIN:
	case DNS_R_NXRRSET:
		return (ISC_TRUE);
	case DNS_R_DELEGATION:
	case DNS_R_CNAME:
	case DNS_R_DNAME:
		return (ISC_FALSE);
	}
	dns_name_format(name, namestr, sizeof(namestr));
	fatal("failure looking for '%s DNSKEY' in database: %s",
	      namestr, isc_result_totext(result));
	/* NOTREACHED */
	return (ISC_FALSE); /* removes a warning */
}

static inline isc_boolean_t
setverifies(dns_name_t *name, dns_rdataset_t *set, dst_key_t *key,
	    dns_rdata_t *rrsig)
{
	isc_result_t result;
	result = dns_dnssec_verify(name, set, key, ISC_FALSE, mctx, rrsig);
	if (result == ISC_R_SUCCESS) {
		INCSTAT(nverified);
		return (ISC_TRUE);
	} else {
		INCSTAT(nverifyfailed);
		return (ISC_FALSE);
	}
}

/*%
 * Signs a set.  Goes through contortions to decide if each RRSIG should
 * be dropped or retained, and then determines if any new SIGs need to
 * be generated.
 */
static void
signset(dns_diff_t *del, dns_diff_t *add, dns_dbnode_t *node, dns_name_t *name,
	dns_rdataset_t *set)
{
	dns_rdataset_t sigset;
	dns_rdata_t sigrdata = DNS_RDATA_INIT;
	dns_rdata_rrsig_t rrsig;
	dns_dnsseckey_t *key;
	isc_result_t result;
	isc_boolean_t nosigs = ISC_FALSE;
	isc_boolean_t *wassignedby, *nowsignedby;
	int arraysize;
	dns_difftuple_t *tuple;
	dns_ttl_t ttl;
	int i;
	char namestr[DNS_NAME_FORMATSIZE];
	char typestr[TYPE_FORMATSIZE];
	char sigstr[SIG_FORMATSIZE];

	dns_name_format(name, namestr, sizeof(namestr));
	type_format(set->type, typestr, sizeof(typestr));

	ttl = ISC_MIN(set->ttl, endtime - starttime);

	dns_rdataset_init(&sigset);
	result = dns_db_findrdataset(gdb, node, gversion, dns_rdatatype_rrsig,
				     set->type, 0, &sigset, NULL);
	if (result == ISC_R_NOTFOUND) {
		result = ISC_R_SUCCESS;
		nosigs = ISC_TRUE;
	}
	if (result != ISC_R_SUCCESS)
		fatal("failed while looking for '%s RRSIG %s': %s",
		      namestr, typestr, isc_result_totext(result));

	vbprintf(1, "%s/%s:\n", namestr, typestr);

	arraysize = keycount;
	if (!nosigs)
		arraysize += dns_rdataset_count(&sigset);
	wassignedby = isc_mem_get(mctx, arraysize * sizeof(isc_boolean_t));
	nowsignedby = isc_mem_get(mctx, arraysize * sizeof(isc_boolean_t));
	if (wassignedby == NULL || nowsignedby == NULL)
		fatal("out of memory");

	for (i = 0; i < arraysize; i++)
		wassignedby[i] = nowsignedby[i] = ISC_FALSE;

	if (nosigs)
		result = ISC_R_NOMORE;
	else
		result = dns_rdataset_first(&sigset);

	while (result == ISC_R_SUCCESS) {
		isc_boolean_t expired, future;
		isc_boolean_t keep = ISC_FALSE, resign = ISC_FALSE;

		dns_rdataset_current(&sigset, &sigrdata);

		result = dns_rdata_tostruct(&sigrdata, &rrsig, NULL);
		check_result(result, "dns_rdata_tostruct");

		future = isc_serial_lt(now, rrsig.timesigned);

		key = keythatsigned(&rrsig);
		sig_format(&rrsig, sigstr, sizeof(sigstr));
		if (key != NULL && issigningkey(key))
			expired = isc_serial_gt(now + cycle, rrsig.timeexpire);
		else
			expired = isc_serial_gt(now, rrsig.timeexpire);

		if (isc_serial_gt(rrsig.timesigned, rrsig.timeexpire)) {
			/* rrsig is dropped and not replaced */
			vbprintf(2, "\trrsig by %s dropped - "
				 "invalid validity period\n",
				 sigstr);
		} else if (key == NULL && !future &&
			   expecttofindkey(&rrsig.signer)) {
			/* rrsig is dropped and not replaced */
			vbprintf(2, "\trrsig by %s dropped - "
				 "private dnskey not found\n",
				 sigstr);
		} else if (key == NULL || future) {
			keep = (!expired && !remove_orphansigs);
			vbprintf(2, "\trrsig by %s %s - dnskey not found\n",
				 keep ? "retained" : "dropped", sigstr);
		} else if (!dns_dnssec_keyactive(key->key, now) &&
			   remove_inactkeysigs) {
			keep = ISC_FALSE;
			vbprintf(2, "\trrsig by %s dropped - key inactive\n",
				 sigstr);
		} else if (issigningkey(key)) {
			wassignedby[key->index] = ISC_TRUE;

			if (!expired && rrsig.originalttl == set->ttl &&
			    setverifies(name, set, key->key, &sigrdata)) {
				vbprintf(2, "\trrsig by %s retained\n", sigstr);
				keep = ISC_TRUE;
			} else {
				vbprintf(2, "\trrsig by %s dropped - %s\n",
					 sigstr, expired ? "expired" :
					 rrsig.originalttl != set->ttl ?
					 "ttl change" : "failed to verify");
				resign = ISC_TRUE;
			}
		} else if (!ispublishedkey(key) && remove_orphansigs) {
			vbprintf(2, "\trrsig by %s dropped - dnskey removed\n",
				 sigstr);
		} else if (iszonekey(key)) {
			wassignedby[key->index] = ISC_TRUE;

			if (!expired && rrsig.originalttl == set->ttl &&
			    setverifies(name, set, key->key, &sigrdata)) {
				vbprintf(2, "\trrsig by %s retained\n", sigstr);
				keep = ISC_TRUE;
			} else {
				vbprintf(2, "\trrsig by %s dropped - %s\n",
					 sigstr, expired ? "expired" :
					 rrsig.originalttl != set->ttl ?
					 "ttl change" : "failed to verify");
			}
		} else if (!expired) {
			vbprintf(2, "\trrsig by %s retained\n", sigstr);
			keep = ISC_TRUE;
		} else {
			vbprintf(2, "\trrsig by %s expired\n", sigstr);
		}

		if (keep) {
			if (key != NULL)
				nowsignedby[key->index] = ISC_TRUE;
			INCSTAT(nretained);
			if (sigset.ttl != ttl) {
				vbprintf(2, "\tfixing ttl %s\n", sigstr);
				tuple = NULL;
				result = dns_difftuple_create(mctx,
						      DNS_DIFFOP_DELRESIGN,
						      name, sigset.ttl,
						      &sigrdata, &tuple);
				check_result(result, "dns_difftuple_create");
				dns_diff_append(del, &tuple);
				result = dns_difftuple_create(mctx,
						      DNS_DIFFOP_ADDRESIGN,
						      name, ttl,
						      &sigrdata, &tuple);
				check_result(result, "dns_difftuple_create");
				dns_diff_append(add, &tuple);
			}
		} else {
			tuple = NULL;
			vbprintf(2, "removing signature by %s\n", sigstr);
			result = dns_difftuple_create(mctx,
						      DNS_DIFFOP_DELRESIGN,
						      name, sigset.ttl,
						      &sigrdata, &tuple);
			check_result(result, "dns_difftuple_create");
			dns_diff_append(del, &tuple);
			INCSTAT(ndropped);
		}

		if (resign) {
			INSIST(!keep);

			signwithkey(name, set, key->key, ttl, add,
				    "resigning with dnskey");
			nowsignedby[key->index] = ISC_TRUE;
		}

		dns_rdata_reset(&sigrdata);
		dns_rdata_freestruct(&rrsig);
		result = dns_rdataset_next(&sigset);
	}
	if (result == ISC_R_NOMORE)
		result = ISC_R_SUCCESS;

	check_result(result, "dns_rdataset_first/next");
	if (dns_rdataset_isassociated(&sigset))
		dns_rdataset_disassociate(&sigset);

	for (key = ISC_LIST_HEAD(keylist);
	     key != NULL;
	     key = ISC_LIST_NEXT(key, link))
	{
		if (nowsignedby[key->index])
			continue;

		if (!issigningkey(key))
			continue;

		if (set->type == dns_rdatatype_dnskey &&
		     dns_name_equal(name, gorigin)) {
			isc_boolean_t have_ksk;
			dns_dnsseckey_t *tmpkey;

			have_ksk = isksk(key);
			for (tmpkey = ISC_LIST_HEAD(keylist);
			     tmpkey != NULL;
			     tmpkey = ISC_LIST_NEXT(tmpkey, link)) {
				if (dst_key_alg(key->key) !=
				    dst_key_alg(tmpkey->key))
					continue;
				if (REVOKE(tmpkey->key))
					continue;
				if (isksk(tmpkey))
					have_ksk = ISC_TRUE;
			}
			if (isksk(key) || !have_ksk ||
			    (iszsk(key) && !keyset_kskonly))
				signwithkey(name, set, key->key, ttl, add,
					    "signing with dnskey");
		} else if (iszsk(key)) {
			signwithkey(name, set, key->key, ttl, add,
				    "signing with dnskey");
		}
	}

	isc_mem_put(mctx, wassignedby, arraysize * sizeof(isc_boolean_t));
	isc_mem_put(mctx, nowsignedby, arraysize * sizeof(isc_boolean_t));
}

struct hashlist {
	unsigned char *hashbuf;
	size_t entries;
	size_t size;
	size_t length;
};

static void
hashlist_init(hashlist_t *l, unsigned int nodes, unsigned int length) {

	l->entries = 0;
	l->length = length + 1;

	if (nodes != 0) {
		l->size = nodes;
		l->hashbuf = malloc(l->size * l->length);
		if (l->hashbuf == NULL)
			l->size = 0;
	} else {
		l->size = 0;
		l->hashbuf = NULL;
	}
}

static void
hashlist_add(hashlist_t *l, const unsigned char *hash, size_t len)
{

	REQUIRE(len <= l->length);

	if (l->entries == l->size) {
		l->size = l->size * 2 + 100;
		l->hashbuf = realloc(l->hashbuf, l->size * l->length);
		if (l->hashbuf == NULL)
			fatal("unable to grow hashlist: out of memory");
	}
	memset(l->hashbuf + l->entries * l->length, 0, l->length);
	memmove(l->hashbuf + l->entries * l->length, hash, len);
	l->entries++;
}

static void
hashlist_add_dns_name(hashlist_t *l, /*const*/ dns_name_t *name,
		      unsigned int hashalg, unsigned int iterations,
		      const unsigned char *salt, size_t salt_length,
		      isc_boolean_t speculative)
{
	char nametext[DNS_NAME_FORMATSIZE];
	unsigned char hash[NSEC3_MAX_HASH_LENGTH + 1];
	unsigned int len;
	size_t i;

	len = isc_iterated_hash(hash, hashalg, iterations,
				salt, (int)salt_length,
				name->ndata, name->length);
	if (verbose) {
		dns_name_format(name, nametext, sizeof nametext);
		for (i = 0 ; i < len; i++)
			fprintf(stderr, "%02x", hash[i]);
		fprintf(stderr, " %s\n", nametext);
	}
	hash[len++] = speculative ? 1 : 0;
	hashlist_add(l, hash, len);
}

static int
hashlist_comp(const void *a, const void *b) {
	return (memcmp(a, b, hash_length + 1));
}

static void
hashlist_sort(hashlist_t *l) {
	qsort(l->hashbuf, l->entries, l->length, hashlist_comp);
}

static isc_boolean_t
hashlist_hasdup(hashlist_t *l) {
	unsigned char *current;
	unsigned char *next = l->hashbuf;
	size_t entries = l->entries;

	/*
	 * Skip initial speculative wild card hashs.
	 */
	while (entries > 0U && next[l->length-1] != 0U) {
		next += l->length;
		entries--;
	}

	current = next;
	while (entries-- > 1U) {
		next += l->length;
		if (next[l->length-1] != 0)
			continue;
		if (memcmp(current, next, l->length - 1) == 0)
			return (ISC_TRUE);
		current = next;
	}
	return (ISC_FALSE);
}

static const unsigned char *
hashlist_findnext(const hashlist_t *l,
		  const unsigned char hash[NSEC3_MAX_HASH_LENGTH])
{
	size_t entries = l->entries;
	const unsigned char *next = bsearch(hash, l->hashbuf, l->entries,
					    l->length, hashlist_comp);
	INSIST(next != NULL);

	do {
		if (next < l->hashbuf + (l->entries - 1) * l->length)
			next += l->length;
		else
			next = l->hashbuf;
		if (next[l->length - 1] == 0)
			break;
	} while (entries-- > 1U);
	INSIST(entries != 0U);